Stack and Queue Fundamentals

• Stacks and queues share the trait that insertion and deletion occur solely at their endpoints.
• Typical stack storage models are sequential arrays and linked lists.
• A stack exhibits last-in-first-out behavior.
• Linked lists lack random access; elemants must be traversed sequentially.
• Linked representation simplifies insertions and deletions compared to array form.
• Head nodes in singly linked lists streamline manipulation logic.
• Circular linked lists allow traversal from any node back to itself covering all nodes.
• In a linear sequence (a₁, a₂, …, aₙ), every element except the first and last has exactly one predecessor and one successor.
• Chained storage does not require contiguous memory blocks.
• Sequential storage enables direct indexed access; linked storage requires traversal.

Tree Characteristics

• A tree consists of nodes with exactly one root.
• A full binary tree of depth k holds 2^k - 1 nodes; leaves count 2^(k-1).
• With three nodes, five distinct binary tree shapes exist.
• For a binary tree having three leaf nodes and eight nodes of degree one, total nodes = 13.
• Traversals:
  • Postorder dabec, inorder debac → preorder: cedba
  • Preorder ABDEGCFH, inorder DBGEACHF → postorder: DGEBHFCA
  • Preorder abdgcefh, inorder dgbaechf → postorder: gdbehfca

Algorithm Properties and Complexity

• An algorithm is a finite, deterministic, feasible procedure with sufficient input/output definition.
• Control structures: sequence, selection, iteration.
• Time complexity measures basic operations executed; space compelxity measures auxiliary memory usage.
• Goal of analysis: evaluate and improve efficiency.
• Correct statements:
  • Finiteness means termination after limited steps.
  • Storage structure impacts processing efficiency.
  • Logical structure is implementation-agnostic.
• Memory arrangement of logical structures defines storage structure.
• Linear structures: arrays, stacks, queues. Nonlinear: trees, graphs.
• Stacks remember order via LIFO; recursion often leverages stacks.
• Two stacks sharing memory mitigate overflow risk.
• Print jobs use queue discipline (FIFO).
• In circular singly linked lists, tail node's next points to head.
• Doubly linked lists ease neighbor access.
• Any node in a circular list can reach all others.

Sorting and Searching

• String length equals its character count; locating pattern occurrence is called matching.
• Minimum edges in connected graph with N vertices: N-1; strongly connected directed graph: N.
• Sequnetial search worst-case comparisons: N.
• Simplest exchange sort: bubble sort; comparisons in worst case: n(n-1)/2.
• Nearly sorted input maximizes bubble sort efficiency.
• Heap sort achieves smallest worst-case time among classic sorts.
• Shell sort belongs to insertion-based methods; heap sort to selection-based.
• Merge sort demands most auxiliary memory.
• Insertion sort suits nearly ordered data.

Advanced Pointer and Array Problems

Detect Cycle in Singly Linked List

struct Node {
    int val;
    Node* link;
};

bool hasCycle(Node* head) {
    if (!head || !head->link) return false;
    Node *slow = head, *fast = head;
    do {
        slow = slow->link;
        fast = fast->link->link;
    } while (fast && fast->link && slow != fast);
    return slow == fast;
}

Reverse Linked List (Iterative)

struct ListNode {
    int value;
    ListNode* nextNode;
};

void iterativeReverse(ListNode*& headRef) {
    if (!headRef) return;
    ListNode *prev = nullptr, *curr = headRef, *next = nullptr;
    while (curr) {
        next = curr->nextNode;
        curr->nextNode = prev;
        prev = curr;
        curr = next;
    }
    headRef = prev;
}

Reverse Linked List (Recursive)

ListNode* recursiveReverse(ListNode* node, ListNode*& headRef) {
    if (!node || !node->nextNode) {
        headRef = node;
        return node;
    }
    ListNode* tail = recursiveReverse(node->nextNode, headRef);
    tail->nextNode = node;
    return node;
}

Common Element in Two Sorted Arrays (Linear)

bool sharedElementLinear(int arr1[], int n1, int arr2[], int n2) {
    int idx1 = 0, idx2 = 0;
    while (idx1 < n1 && idx2 < n2) {
        if (arr1[idx1] == arr2[idx2]) return true;
        if (arr1[idx1] < arr2[idx2]) ++idx1;
        else ++idx2;
    }
    return false;
}

Maximum Subarray Sum (Kadane’s Algorithm)

int maxSubarraySum(int seq[], int len) {
    int maxSum = 0, curSum = 0;
    for (int i = 0; i < len; ++i) {
        curSum += seq[i];
        if (curSum > maxSum) maxSum = curSum;
        else if (curSum < 0) curSum = 0;
    }
    return maxSum;
}

Reverse Words in String

char* reverseWords(const char* src) {
    int len = strlen(src);
    char* buf = new char[len + 1];
    strcpy(buf, src);
    // Reverse entire string
    for (int i = 0, j = len - 1; i < j; ++i, --j) {
        char tmp = buf[i]; buf[i] = buf[j]; buf[j] = tmp;
    }
    // Reverse each word
    int pos = 0;
    while (pos < len) {
        int start = pos, end = pos;
        while (buf[end] && buf[end] != ' ') ++end;
        int right = end - 1;
        for (int l = start, r = right; l < r; ++l, --r) {
            char tmp = buf[l]; buf[l] = buf[r]; buf[r] = tmp;
        }
        pos = end + 1;
    }
    return buf;
}

Remove Duplicates from Integer Array (In-place)

void compactArray(int arr[]) {
    if (!arr || arr[0] == 0) return;
    int writeIdx = 1, readIdx = 1;
    while (arr[readIdx] != 0) {
        if (arr[readIdx] != arr[readIdx - 1]) {
            arr[writeIdx++] = arr[readIdx];
        }
        ++readIdx;
    }
    arr[writeIdx] = 0;
}

Check Balanced Binary Tree

template<typename T>
int treeDepth(BTNode<T>* node) {
    if (!node) return 0;
    int leftDepth = treeDepth(node->left);
    int rightDepth = treeDepth(node->right);
    return 1 + max(leftDepth, rightDepth);
}

template<typename T>
bool isBalanced(BTNode<T>* node) {
    if (!node) return true;
    int diff = treeDepth(node->left) - treeDepth(node->right);
    if (diff < -1 || diff > 1) return false;
    return isBalanced(node->left) && isBalanced(node->right);
}

Class Design and Syntax Pitfalls

• Abstract methods cannot be private or final.
• Local variables must not have access modifiers (private, public, protected).
• Abstract method declaration ends with semicolon, no body braces.

Merging Two Sorted Linked Lists (Iterative)

Node* mergeSortedLists(Node* h1, Node* h2) {
    if (!h1) return h2;
    if (!h2) return h1;
    Node* merged = nullptr;
    if (h1->data <= h2->data) {
        merged = h1;
        h1 = h1->next;
    } else {
        merged = h2;
        h2 = h2->next;
    }
    Node* tail = merged;
    while (h1 && h2) {
        if (h1->data <= h2->data) {
            tail->next = h1;
            h1 = h1->next;
        } else {
            tail->next = h2;
            h2 = h2->next;
        }
        tail = tail->next;
    }
    tail->next = h1 ? h1 : h2;
    return merged;
}

Merging Two Sorted Linked Lists (Recursive)

Node* mergeSortedRecursive(Node* h1, Node* h2) {
    if (!h1) return h2;
    if (!h2) return h1;
    if (h1->data <= h2->data) {
        h1->next = mergeSortedRecursive(h1->next, h2);
        return h1;
    } else {
        h2->next = mergeSortedRecursive(h1, h2->next);
        return h2;
    }
}

String Class Implementation

class MyString {
private:
    char* buffer;
public:
    MyString(const char* str = nullptr) {
        if (!str) {
            buffer = new char[1];
            buffer[0] = '\0';
        } else {
            buffer = new char[strlen(str) + 1];
            strcpy(buffer, str);
        }
    }
    MyString(const MyString& other) {
        buffer = new char[strlen(other.buffer) + 1];
        strcpy(buffer, other.buffer);
    }
    MyString& operator=(const MyString& rhs) {
        if (this == &rhs) return *this;
        delete[] buffer;
        buffer = new char[strlen(rhs.buffer) + 1];
        strcpy(buffer, rhs.buffer);
        return *this;
    }
    ~MyString() { delete[] buffer; }
};