Articles 🧠 Quiz ↗

Qualcomm Practice — Part 1 Solutions — Linked lists, Stacks & Queues, Trees & BST, Hashing

Clean, compilable solutions for Part 1 categories H, I, J, K of practice_questions.md — the linked-list / stack-queue / tree / hashing block, which is the most-asked DSA family in the Qualcomm loop. Each item: the idea in a sentence or two, a commented C/C++ solution, complexity, and a gotcha/variant. C is used for pointer/memory work; C++ where STL or templates make it idiomatic. Node types assumed throughout: 

struct Node  { int val; struct Node *next; };           // singly linked
struct DNode { int val; struct DNode *prev, *next; };   // doubly linked
struct TNode { int val; struct TNode *left, *right; };  // binary tree

Table of Contents

H. Linked lists - Reverse a singly linked list - Insert a node (front / kth / sorted) - Find the middle of a linked list - Detect a loop (Floyd) - Find the length of the loop - Detect and remove a loop - Nth node from the end - Delete a node given only a pointer to it - Pairwise swap nodes - Reverse a doubly linked list - Intersection point of two lists - Rotate: move last node to front - Merge two sorted linked lists - Convert a sorted linked list to a BST - Reverse nodes in k-group - Merge k sorted lists

I. Stacks & queues - Implement a stack - Stack using queues / queue using stacks - Asteroid Collision

J. Trees & BST - Find the maximum element in a binary tree - Left view of a binary tree - Create / insert into a BST - Delete a node in a binary tree / BST - Check whether a binary tree is a BST - Minimum distance between two nodes - Fix a BST where two nodes were swapped - Binary Tree Maximum Path Sum - Count permutations of a preorder that form the same BST

K. Hashing - Implement a hash table (chaining) - Hashing vs hash tables; count pairs divisible by k

H. Linked lists

H1. Reverse a singly linked list [E]

  • Idea: Walk the list, flipping each next to point backward, carrying three pointers: prev, curr, next.
  • Code: 
    struct Node *reverse(struct Node *head) {
    struct Node *prev = NULL, *curr = head;
    while (curr) {
        struct Node *next = curr->next; // save before we clobber it
        curr->next = prev;              // flip the link
        prev = curr;                    // advance window
        curr = next;
    }
    return prev; // new head (old tail)
}
  • Complexity: O(n) time, O(1) space.
  • Gotcha / variants: Empty list and single node both work (loop body just doesn't run / runs once). Recursive variant: 
    struct Node *reverseRec(struct Node *head) {
    if (!head || !head->next) return head;   // base: empty or last node
    struct Node *newHead = reverseRec(head->next);
    head->next->next = head;                 // make next point back to me
    head->next = NULL;                       // I become the tail
    return newHead;
}
    Recursive costs O(n) stack — interviewers prefer iterative for that reason.

H2. Insert a node at beginning / kth position / into a sorted list [E]

  • Idea: Insertion is pure pointer rewiring; always wire the new node's next before you change the predecessor's next. Use a pointer-to-pointer (or a dummy head) to handle "insert at front" without a special case.
  • Code: 
    struct Node *newNode(int v) {
    struct Node *n = malloc(sizeof *n);
    n->val = v; n->next = NULL;
    return n;
}

// 1) At the beginning — returns new head.
struct Node *insertFront(struct Node *head, int v) {
    struct Node *n = newNode(v);
    n->next = head;
    return n;
}

// 2) At position k (0-based; k>=len appends at the tail).
struct Node *insertAt(struct Node *head, int k, int v) {
    struct Node **pp = &head;               // ptr to the link we'll splice into
    while (k-- > 0 && *pp) pp = &(*pp)->next;
    struct Node *n = newNode(v);
    n->next = *pp;
    *pp = n;
    return head;
}

// 3) Into a sorted (ascending) list, keeping it sorted.
struct Node *insertSorted(struct Node *head, int v) {
    struct Node **pp = &head;
    while (*pp && (*pp)->val < v) pp = &(*pp)->next; // stop at first >= v
    struct Node *n = newNode(v);
    n->next = *pp;
    *pp = n;
    return head;
}
  • Complexity: front O(1); kth/sorted O(n) time, O(1) space.
  • Gotcha / variants: The pointer-to-pointer (Node **pp) trick removes the "is this the head?" special case — *pp is the link to overwrite whether it's head or some node's next. "Dictionary-order" sorted insert is the same with strcmp on a string key.

H3. Find the middle of a linked list [E]

  • Idea: Fast/slow pointers: fast moves 2, slow moves 1. When fast falls off the end, slow is at the middle.
  • Code: 
    struct Node *middle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow; // for even length, this is the 2nd of the two middles
}
  • Complexity: O(n) time, O(1) space.
  • Gotcha / variants: For even length the loop above returns the upper middle (e.g. 3 of 1-2-3-4). To get the lower middle, loop on fast->next && fast->next->next. Single-pass is the point — don't compute length then re-walk.

H4. Detect a loop (Floyd slow/fast) [M]

  • Idea: Floyd's tortoise & hare. If a cycle exists, the fast pointer laps the slow one and they meet inside the loop; if fast hits NULL, there's no loop.
  • Code: 
    int hasLoop(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1; // pointers met → cycle
    }
    return 0;                       // fast reached the end → no cycle
}
  • Complexity: O(n) time, O(1) space.
  • Gotcha / variants: Guard fast && fast->next before fast->next->next or you'll deref NULL. A self-loop (node points to itself) is caught on the first step. The hash-set approach (store visited nodes) is also O(n) time but O(n) space — Floyd's O(1) space is the expected answer. Doubly/circular lists: a circular list is intentionally a loop (tail→head), so "detect a loop" there usually means an unintended cycle — same Floyd's logic applies.

H5. Find the length of the loop [M]

  • Idea: Once slow and fast meet inside the loop, freeze one pointer and walk the other around until it returns — counting the steps gives the cycle length.
  • Code: 
    int loopLength(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {                  // meeting point found
            int len = 1;
            struct Node *p = slow->next;
            while (p != slow) { p = p->next; len++; }
            return len;
        }
    }
    return 0; // no loop
}
  • Complexity: O(n) time, O(1) space.
  • Gotcha / variants: The meeting point is guaranteed to lie on the loop, so walking from it back to itself measures exactly one lap.

H6. Detect and remove a loop [M]

  • Idea: Detect with Floyd's, then find the loop's start: reset one pointer to head and advance both one step at a time — they meet at the start. The node before the start is the loop's tail; set its next = NULL.
  • Code: 
    void removeLoop(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;            // cycle detected
    }
    if (!fast || !fast->next) return;       // no loop, nothing to do

    slow = head;
    if (slow == fast) {                     // loop starts at head: find tail
        while (fast->next != slow) fast = fast->next;
    } else {
        while (slow->next != fast->next) {  // advance until next is the start
            slow = slow->next;
            fast = fast->next;
        }
    }
    fast->next = NULL;                      // sever the back-edge
}
  • Complexity: O(n) time, O(1) space.
  • Gotcha / variants: Why does resetting to head work? The distance from head to the loop start equals the distance from the meeting point to the loop start (mod loop length) — a classic Floyd's corollary. Handle the special case where the loop starts exactly at head.

H7. Nth node from the end [M]

  • Idea: Two pointers spaced n apart: advance lead n steps first, then move both until lead falls off — trail lands on the nth-from-end.
  • Code: 
    struct Node *nthFromEnd(struct Node *head, int n) {
    struct Node *lead = head, *trail = head;
    for (int i = 0; i < n; i++) {
        if (!lead) return NULL;   // list shorter than n
        lead = lead->next;
    }
    while (lead) { lead = lead->next; trail = trail->next; }
    return trail;
}
  • Complexity: O(n) time, O(1) space, single pass.
  • Gotcha / variants: Other approaches: (1) count length L, then walk L−n — two passes; (2) recursion that counts on the way back up. To delete the nth-from-end (LC19), run the gap with a dummy head so removing the head itself is uniform.

H8. Delete a node given only a pointer to it [M]

  • Idea: You can't reach the predecessor, so instead copy the next node's value into this node and unlink the next node — effectively deleting "this" by becoming its successor.
  • Code: 
    // Works for any node EXCEPT the tail (no successor to copy from).
void deleteNode(struct Node *node) {
    if (!node || !node->next) return;       // can't delete the last node this way
    struct Node *nxt = node->next;
    node->val  = nxt->val;                  // steal successor's value
    node->next = nxt->next;                 // unlink successor
    free(nxt);
}
  • Complexity: O(1) time, O(1) space.
  • Gotcha / variants: Tail node fails — there's no successor to copy. In a circular list every node has a successor, so even the "last" node works (copy from head-ish successor). If asked to handle the tail in a singly list, it's impossible in O(1) without the predecessor.

H9. Pairwise swap nodes (swap in pairs) [M]

  • Idea: Walk the list two at a time, relinking each pair (a→b) into (b→a). A dummy head keeps the head-swap uniform.
  • Code: 
    struct Node *swapPairs(struct Node *head) {
    struct Node dummy = {0, head};
    struct Node *prev = &dummy;
    while (prev->next && prev->next->next) {
        struct Node *a = prev->next;
        struct Node *b = a->next;
        a->next = b->next;   // a now points past b
        b->next = a;         // b precedes a
        prev->next = b;      // hook the swapped pair to the chain
        prev = a;            // a is the tail of this pair
    }
    return dummy.next;
}
  • Complexity: O(n) time, O(1) space.
  • Gotcha / variants: Swap pointers, not values — interviewers usually want the node relinking. Odd trailing node stays put (loop condition needs a full pair). This is the k=2 case of H15.

H10. Reverse a doubly linked list [M]

  • Idea: For each node swap its prev and next; the old tail becomes the new head.
  • Code: 
    struct DNode *reverseDLL(struct DNode *head) {
    struct DNode *curr = head, *newHead = head;
    while (curr) {
        struct DNode *tmp = curr->prev;     // swap prev <-> next
        curr->prev = curr->next;
        curr->next = tmp;
        newHead = curr;                      // last processed = new head
        curr = curr->prev;                   // (which is the old next)
    }
    return newHead;
}
  • Complexity: O(n) time, O(1) space.
  • Gotcha / variants: After swapping, advance via curr->prev (that holds the old next). Don't forget to return the new head — the original head->prev ends up NULL correctly because it was the first swap.

H11. Intersection point of two linked lists [M]

  • Idea: Two pointers, each starting at one head; when a pointer hits the end, redirect it to the other list's head. After at most one switch they've walked equal total lengths and meet at the intersection (or both reach NULL).
  • Code: 
    struct Node *getIntersection(struct Node *a, struct Node *b) {
    struct Node *pa = a, *pb = b;
    while (pa != pb) {                  // also terminates if both become NULL
        pa = pa ? pa->next : b;         // switch to b's head at the end
        pb = pb ? pb->next : a;         // switch to a's head at the end
    }
    return pa;                          // intersection node, or NULL
}
  • Complexity: O(m + n) time, O(1) space.
  • Gotcha / variants: No-intersection case terminates because both pointers become NULL simultaneously after m+n steps. Brute force: for each node in A, scan all of B — O(m·n). Length-diff method: advance the longer list by |m−n| first, then step together.

H12. Rotate: move the last node to the front [M]

  • Idea: Find the tail and the node before it; unlink the tail, make it the new head pointing at the old head.
  • Code: 
    // 1 2 3 4 5  ->  5 1 2 3 4
struct Node *moveLastToFront(struct Node *head) {
    if (!head || !head->next) return head;
    struct Node *secondLast = head;
    while (secondLast->next->next) secondLast = secondLast->next;
    struct Node *last = secondLast->next;
    secondLast->next = NULL;   // new tail
    last->next = head;         // old head follows the moved node
    return last;               // new head
}
  • Complexity: O(n) time, O(1) space.
  • Gotcha / variants: Handle 0- and 1-node lists up front. General "rotate right by k": reduce k mod length, find the new tail at position len-k-1, splice. To move first to last, detach the head and append it.

H13. Merge two sorted linked lists [M]

  • Idea: Like the merge step of merge sort: a dummy head plus a tail pointer; repeatedly attach the smaller front node.
  • Code: 
    struct Node *mergeTwo(struct Node *a, struct Node *b) {
    struct Node dummy = {0, NULL};
    struct Node *tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;     // attach whichever remains
    return dummy.next;
}
  • Complexity: O(m + n) time, O(1) extra space (relinks in place).
  • Gotcha / variants: Use <= (not <) to keep the merge stable. Recursive variant is elegant but O(m+n) stack: 
    struct Node *mergeRec(struct Node *a, struct Node *b) {
    if (!a) return b;
    if (!b) return a;
    if (a->val <= b->val) { a->next = mergeRec(a->next, b); return a; }
    else                  { b->next = mergeRec(a, b->next); return b; }
}

H14. Convert a sorted linked list to a BST [H]

  • Idea: A sorted list is an in-order BST traversal. Build bottom-up in inorder: recurse over an index range, building the left subtree first, then consume the list's current node as the root (advancing a shared pointer), then the right subtree. This consumes nodes in order, so no slow mid-finding.
  • Code: 
    static struct TNode *tnew(int v) {
    struct TNode *t = malloc(sizeof *t);
    t->val = v; t->left = t->right = NULL;
    return t;
}
// build a balanced BST from `n` nodes; *list walks forward as we consume.
static struct TNode *build(struct Node **list, int n) {
    if (n <= 0) return NULL;
    struct TNode *left = build(list, n / 2);          // left half first
    struct TNode *root = tnew((*list)->val);          // current node = root
    *list = (*list)->next;                            // consume it
    root->left  = left;
    root->right = build(list, n - n / 2 - 1);         // remaining = right
    return root;
}
struct TNode *sortedListToBST(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;  // count once
    return build(&head, n);
}
  • Complexity: O(n) time, O(log n) recursion space (balanced) — beats the O(n log n) "find middle each time" version.
  • Gotcha / variants: The trick is consuming the list in inorder: build left subtree before reading the root value, so the shared *list pointer naturally lands on the right node each time. The simpler-to-explain O(n log n) version finds the middle of the current sublist with fast/slow each recursion.

H15. Reverse nodes in k-group [H]

  • Idea: Reverse each consecutive block of k nodes. Before reversing a block, check there are at least k nodes left (otherwise leave the remainder as-is). Stitch each reversed block onto the previous one.
  • Code: 
    struct Node *reverseKGroup(struct Node *head, int k) {
    // 1) verify there are at least k nodes ahead
    struct Node *check = head;
    for (int i = 0; i < k; i++) {
        if (!check) return head;   // fewer than k → leave unchanged
        check = check->next;
    }
    // 2) reverse this block of k
    struct Node *prev = NULL, *curr = head;
    for (int i = 0; i < k; i++) {
        struct Node *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    // 3) head is now the block's tail; link it to the recursively-done rest
    head->next = reverseKGroup(curr, k);
    return prev;                   // new head of this block
}
  • Complexity: O(n) time; O(n/k) recursion stack (can be made O(1) iteratively).
  • Gotcha / variants: Leftover < k must stay un-reversed (LC25 semantics) — that's what the up-front length check guards. If the variant says "reverse the leftover too," drop the check and reverse whatever remains. k=2 is exactly H9.

H16. Merge k sorted lists [H]

  • Idea: Use a min-heap of the k current heads; repeatedly pop the smallest, append it, and push its successor. Each of the n nodes enters/leaves the heap once → O(n log k).
  • Code (C++ with priority_queue): 
    #include <queue>
#include <vector>
struct Node { int val; Node *next; };

Node *mergeKLists(std::vector<Node*> &lists) {
    auto cmp = [](Node *a, Node *b) { return a->val > b->val; }; // min-heap
    std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> pq(cmp);
    for (Node *l : lists) if (l) pq.push(l);

    Node dummy{0, nullptr};
    Node *tail = &dummy;
    while (!pq.empty()) {
        Node *node = pq.top(); pq.pop();
        tail->next = node;
        tail = node;
        if (node->next) pq.push(node->next);   // refill from the same list
    }
    tail->next = nullptr;
    return dummy.next;
}
  • Complexity: O(n log k) time (n = total nodes), O(k) heap space.
  • Gotcha / variants: Skip empty input lists when seeding the heap. Divide-and-conquer alternative: pairwise-merge lists (H13) in a tournament — also O(n log k) and avoids a heap. Naive "merge one at a time" is O(n·k).

I. Stacks & queues

I1. Implement a stack (all operations) [E]

  • Idea: LIFO. Array-backed gives O(1) push/pop with a top index; the alternative is a singly linked list pushing at the head.
  • Code (array-backed, fixed capacity): 
    #define CAP 100
typedef struct { int data[CAP]; int top; } Stack;

void init(Stack *s)      { s->top = -1; }
int  isEmpty(Stack *s)   { return s->top == -1; }
int  isFull(Stack *s)    { return s->top == CAP - 1; }

int  push(Stack *s, int x) {
    if (isFull(s)) return 0;            // overflow
    s->data[++s->top] = x;
    return 1;
}
int  pop(Stack *s, int *out) {
    if (isEmpty(s)) return 0;           // underflow
    *out = s->data[s->top--];
    return 1;
}
int  peek(Stack *s, int *out) {
    if (isEmpty(s)) return 0;
    *out = s->data[s->top];
    return 1;
}
  • Complexity: push/pop/peek O(1); O(n) space.
  • Gotcha / variants: Always check overflow/underflow — the canonical bug interviewers probe. Linked-list version pushes/pops at the head (no fixed cap, but per-node malloc). For a growable array, double CAP on overflow (amortized O(1)). C++ one-liner: std::stack<int>.

I2. Stack using queues / queue using stacks [M]

  • Idea: Stack from two queues: make push costly — enqueue the new item, then rotate all earlier items behind it so the queue front is always the last-in. Queue from two stacks: keep an in and out stack; pop/peek lazily moves in→out only when out is empty, giving amortized O(1).
  • Code (queue using two stacks, C++): 
    #include <stack>
class MyQueue {
    std::stack<int> in, out;
    void shift() {                          // move in -> out only when needed
        if (out.empty())
            while (!in.empty()) { out.push(in.top()); in.pop(); }
    }
public:
    void push(int x) { in.push(x); }        // O(1)
    int  pop()  { shift(); int v = out.top(); out.pop(); return v; }
    int  peek() { shift(); return out.top(); }
    bool empty() { return in.empty() && out.empty(); }
};
  • Complexity: queue-from-stacks: push O(1), pop/peek amortized O(1) (each element moves at most once). Stack-from-queues: one op O(n), the other O(1).
  • Gotcha / variants: Choose which operation pays: queue-from-stacks does the rotation lazily (amortized O(1)), so it's the cleaner answer. Stack-from-queues can use a single queue by rotating size−1 elements on every push.

I3. Asteroid Collision [M]

  • Idea: Asteroids on a line; only a right-mover (+) followed by a left-mover (−) collide. Process left to right with a stack of survivors: a new left-mover pops smaller positive tops until it's destroyed, survives, or meets a non-positive/empty top.
  • Code (C, in-place on a stack array): 
    // returns the number of survivors; writes them into out[].
int asteroids(const int *a, int n, int *out) {
    int top = 0;                                   // out[] used as the stack
    for (int i = 0; i < n; i++) {
        int cur = a[i];
        int alive = 1;
        // collision only when top moves right (+) and cur moves left (-)
        while (alive && top > 0 && out[top-1] > 0 && cur < 0) {
            int diff = out[top-1] + cur;           // compare magnitudes
            if (diff < 0)        top--;            // top explodes, cur continues
            else if (diff == 0) { top--; alive = 0; } // both explode
            else                 alive = 0;         // cur explodes
        }
        if (alive) out[top++] = cur;
    }
    return top;
}
  • Complexity: O(n) time, O(n) space (stack of survivors).
  • Gotcha / variants: The collision condition is precisely top > 0 && stack_top > 0 && cur < 0. Equal magnitudes → both vanish. Same-direction or (−)(+) pairs never collide (they move apart), which is why only that one sign pattern triggers the while loop.

J. Trees & BST

J1. Find the maximum element in a binary tree [E]

  • Idea: In a general binary tree the max can be anywhere — recurse and take the max of node, left-subtree, right-subtree.
  • Code: 
    #include <limits.h>
int treeMax(struct TNode *root) {
    if (!root) return INT_MIN;              // identity for max
    int l = treeMax(root->left);
    int r = treeMax(root->right);
    int m = root->val;
    if (l > m) m = l;
    if (r > m) m = r;
    return m;
}
  • Complexity: O(n) time, O(h) recursion space (h = height).
  • Gotcha / variants: Use INT_MIN as the empty-tree identity. In a BST, the max is simply the rightmost node — follow right until NULL, O(h): 
    int bstMax(struct TNode *root){ while(root->right) root=root->right; return root->val; }

J2. Left view of a binary tree [M]

  • Idea: The left view is the first node at each level. Either BFS and take the first dequeued node per level, or DFS visiting left-first and record a node the first time its depth exceeds the max seen.
  • Code (DFS, left-first): 
    // records the first node seen at each new depth.
void leftViewDFS(struct TNode *root, int depth, int *maxDepth, int *out, int *cnt) {
    if (!root) return;
    if (depth > *maxDepth) {                // first node at this depth
        out[(*cnt)++] = root->val;
        *maxDepth = depth;
    }
    leftViewDFS(root->left,  depth + 1, maxDepth, out, cnt); // left BEFORE right
    leftViewDFS(root->right, depth + 1, maxDepth, out, cnt);
}
// usage: int maxD = -1, cnt = 0; leftViewDFS(root, 0, &maxD, out, &cnt);
  • Complexity: O(n) time, O(h) space (DFS) or O(width) for the BFS queue.
  • Gotcha / variants: Visiting left child before right is what makes the first-at-depth be the leftmost. Right view: swap the recursion order (right first) or take the last node per BFS level. Don't confuse "left view" with "all left children."

J3. Create / insert into a BST [E]

  • Idea: Recurse down comparing the key: go left if smaller, right if larger; create the node at the empty slot you reach. Building a BST is just repeated insertion.
  • Code: 
    struct TNode *bstInsert(struct TNode *root, int v) {
    if (!root) return tnew(v);              // found the empty slot (tnew from H14)
    if (v < root->val)      root->left  = bstInsert(root->left,  v);
    else if (v > root->val) root->right = bstInsert(root->right, v);
    // v == root->val: ignore duplicate (or handle per spec)
    return root;
}
struct TNode *buildBST(const int *a, int n) {
    struct TNode *root = NULL;
    for (int i = 0; i < n; i++) root = bstInsert(root, a[i]);
    return root;
}
  • Complexity: insert O(h) — O(log n) balanced, O(n) worst (skewed); build O(n·h).
  • Gotcha / variants: Decide duplicate policy explicitly (ignore / count / go right). Inserting already-sorted input produces a degenerate linked-list-shaped tree (O(n) height) — the motivation for self-balancing trees (AVL/red-black).

J4. Delete a node in a BST [M]

  • Idea: Three cases. Leaf: just remove. One child: splice the child up. Two children: replace the node's value with its in-order successor (smallest in the right subtree), then delete that successor.
  • Code: 
    static struct TNode *minNode(struct TNode *n) {
    while (n->left) n = n->left;            // leftmost = smallest
    return n;
}
struct TNode *bstDelete(struct TNode *root, int key) {
    if (!root) return NULL;
    if (key < root->val)      root->left  = bstDelete(root->left,  key);
    else if (key > root->val) root->right = bstDelete(root->right, key);
    else {                                  // found it
        if (!root->left)  { struct TNode *r = root->right; free(root); return r; }
        if (!root->right) { struct TNode *l = root->left;  free(root); return l; }
        struct TNode *succ = minNode(root->right);  // two children
        root->val = succ->val;                       // copy successor value up
        root->right = bstDelete(root->right, succ->val); // delete successor
    }
    return root;
}
  • Complexity: O(h) time, O(h) recursion space.
  • Gotcha / variants: One-child cases also cover the leaf case (child is NULL → returns NULL). You can mirror the two-child case using the in-order predecessor (max of left subtree) instead. For a general binary tree (not BST), "delete" usually means replacing the target with the deepest-rightmost node, then removing that leaf.

J5. Check whether a binary tree is a BST [M]

  • Idea: Validate that every node lies within a (min, max) range that tightens as you descend — left subtree gets an upper bound of the node, right subtree gets a lower bound. (An in-order traversal must be strictly increasing — equivalent.)
  • Code (range method): 
    #include <limits.h>
// bounds are exclusive; use long to avoid INT_MIN/INT_MAX edge issues
int isBSTrange(struct TNode *root, long lo, long hi) {
    if (!root) return 1;
    if (root->val <= lo || root->val >= hi) return 0;   // out of allowed range
    return isBSTrange(root->left,  lo, root->val) &&
           isBSTrange(root->right, root->val, hi);
}
int isBST(struct TNode *root) {
    return isBSTrange(root, LONG_MIN, LONG_MAX);
}
  • Complexity: O(n) time, O(h) recursion space.
  • Gotcha / variants: The classic bug is only comparing a node to its immediate children — that misses violations deeper down; the range must be propagated. Use long (or pass node pointers) so a node holding INT_MIN/INT_MAX doesn't false-fail. In-order alternative: traverse and verify each value > the previous one.

J6. Minimum distance between two nodes [M]

  • Idea: Distance(a, b) = depth(a) + depth(b) − 2·depth(LCA), where LCA is the lowest common ancestor. Find the LCA, then measure each node's depth from it.
  • Code: 
    // LCA in a general binary tree (values n1, n2 assumed present).
struct TNode *lca(struct TNode *root, int n1, int n2) {
    if (!root || root->val == n1 || root->val == n2) return root;
    struct TNode *l = lca(root->left,  n1, n2);
    struct TNode *r = lca(root->right, n1, n2);
    if (l && r) return root;                 // split → this is the LCA
    return l ? l : r;                         // both on one side
}
// depth of `key` below `root`, or -1 if absent.
int depth(struct TNode *root, int key, int d) {
    if (!root) return -1;
    if (root->val == key) return d;
    int l = depth(root->left, key, d + 1);
    return (l != -1) ? l : depth(root->right, key, d + 1);
}
int minDistance(struct TNode *root, int n1, int n2) {
    struct TNode *a = lca(root, n1, n2);
    return depth(a, n1, 0) + depth(a, n2, 0);
}
  • Complexity: O(n) time (each helper is one traversal), O(h) recursion space.
  • Gotcha / variants: Call-stack angle interviewers probe: each recursion frame holds the node pointer and bookkeeping; max simultaneous frames = tree height h, so stack space is O(h) — O(log n) balanced, O(n) for a skewed tree (stack-overflow risk on deep inputs). In a BST the LCA is found in O(h) by branching on value comparisons (no full traversal needed).

J7. Fix a BST where two nodes were swapped [H]

  • Idea: An in-order traversal of a valid BST is strictly increasing. With two nodes swapped you see one or two "descents." Record the first node of the first descent and the second node of the (last) descent, then swap their values back.
  • Code: 
    struct TNode *first = NULL, *second = NULL, *prev = NULL;
void inorderFix(struct TNode *root) {
    if (!root) return;
    inorderFix(root->left);
    if (prev && prev->val > root->val) {     // a descent in the sequence
        if (!first) first = prev;            // 1st violation: take the larger (prev)
        second = root;                       // always update the smaller side
    }
    prev = root;
    inorderFix(root->right);
}
void recoverBST(struct TNode *root) {
    first = second = prev = NULL;
    inorderFix(root);
    if (first && second) {                   // swap the two values back
        int t = first->val; first->val = second->val; second->val = t;
    }
}
  • Complexity: O(n) time, O(h) recursion space (O(1) extra besides the three pointers).
  • Gotcha / variants: Two cases: if the swapped nodes are adjacent in inorder you get one descent (second = the node in that descent); if non-adjacent you get two descents and second is updated to the second one. The single code above handles both because first is only set once but second is always overwritten. The O(h)-space Morris-traversal version makes it O(1) space.

J8. Binary Tree Maximum Path Sum [H]

  • Idea: For each node compute the best downward path gain it can contribute to its parent (node + max(0, one child)). Separately track the best full path through each node (node + left gain + right gain), updating a global maximum.
  • Code (C++): 
    #include <algorithm>
#include <climits>
struct TNode { int val; TNode *left, *right; };

int best;   // global maximum path sum
int gain(TNode *node) {
    if (!node) return 0;
    int l = std::max(0, gain(node->left));   // drop negative branches
    int r = std::max(0, gain(node->right));
    best = std::max(best, node->val + l + r); // path bending at this node
    return node->val + std::max(l, r);        // best straight-down path to parent
}
int maxPathSum(TNode *root) {
    best = INT_MIN;
    gain(root);
    return best;
}
  • Complexity: O(n) time, O(h) recursion space.
  • Gotcha / variants: Two distinct quantities: what you return (a straight path that can extend into the parent — at most one child) vs what you record in best (a path that bends through the node — both children). Clamp negative child gains to 0 so they're dropped. Initialise best = INT_MIN because all values can be negative.

J9. Count permutations of a preorder that form the same BST [H]

  • Idea: Inserting the array elements in order builds a fixed BST; the first element is the root, smaller elements form the left subtree (in their given relative order), larger form the right. Any interleaving of the two subtrees' sequences that preserves each side's internal order yields the same tree. So ways(n) = C(L+R, L) · ways(left) · ways(right).
  • Code (C++): 
    #include <vector>
using std::vector;

// Pascal's triangle for binomial coefficients up to n.
long countSameBST(const vector<int> &a) {
    int n = a.size();
    vector<vector<long>> C(n + 1, vector<long>(n + 1, 0));
    for (int i = 0; i <= n; i++) { C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = C[i-1][j-1] + C[i-1][j]; }

    // recursive helper over a subsequence
    struct H {
        vector<vector<long>> &C;
        long go(const vector<int> &v) {
            if (v.size() <= 1) return 1;
            int root = v[0];
            vector<int> left, right;
            for (size_t i = 1; i < v.size(); i++)
                (v[i] < root ? left : right).push_back(v[i]); // keep order
            long L = left.size(), R = right.size();
            return C[L + R][L] * go(left) * go(right);        // interleavings
        }
    } h{C};
    return h.go(a);
}
  • Complexity: O(n²) overall (each recursion level partitions and the binomial table is O(n²)).
  • Gotcha / variants: The answer includes the original ordering itself; subtract 1 if the question asks for other permutations. Use modular arithmetic / big integers — the count blows up fast for larger n.

K. Hashing

K1. Implement a hash table (buckets + chaining) [M]

  • Idea: An array of buckets; each key hashes to a bucket index. Collisions (different keys, same bucket) are resolved by chaining — a linked list per bucket. Load factor = entries / buckets; rehash when it gets high.
  • Code (C, int→int map with separate chaining): 
    #include <stdlib.h>
#define NB 16
typedef struct Entry { int key, val; struct Entry *next; } Entry;
typedef struct { Entry *buckets[NB]; } HashMap;

static unsigned hash(int key) { return (unsigned)key % NB; } // simple modulo

void hm_init(HashMap *m) { for (int i = 0; i < NB; i++) m->buckets[i] = NULL; }

void hm_put(HashMap *m, int key, int val) {
    unsigned b = hash(key);
    for (Entry *e = m->buckets[b]; e; e = e->next)
        if (e->key == key) { e->val = val; return; }  // update existing
    Entry *e = malloc(sizeof *e);                      // else prepend new
    e->key = key; e->val = val; e->next = m->buckets[b];
    m->buckets[b] = e;
}
int hm_get(HashMap *m, int key, int *out) {
    for (Entry *e = m->buckets[hash(key)]; e; e = e->next)
        if (e->key == key) { *out = e->val; return 1; }
    return 0;                                           // not found
}
int hm_remove(HashMap *m, int key) {
    Entry **pp = &m->buckets[hash(key)];               // ptr-to-ptr for splice
    while (*pp) {
        if ((*pp)->key == key) { Entry *d = *pp; *pp = d->next; free(d); return 1; }
        pp = &(*pp)->next;
    }
    return 0;
}
  • Complexity: put/get/remove O(1) average, O(n) worst (all keys collide into one chain); O(n) space.
  • Gotcha / variants: Update-on-duplicate (don't blindly prepend). The Entry ** splice removes the predecessor special-case on delete. Open addressing (linear/quadratic probing) is the alternative to chaining — better cache locality, but needs tombstones on delete and degrades sharply past ~0.7 load factor. Rehash (grow NB, re-insert all) when load factor crosses the threshold.

K2. Hashing vs hash tables + count pairs divisible by k [M]

  • Idea: Hashing = the technique (a hash function mapping keys to indices); a hash table = the data structure that uses hashing for O(1)-average lookup. For "count pairs with sum divisible by k," bucket each element by its remainder mod k; a pair (i, j) is divisible by k iff r_i + r_j ≡ 0 (mod k), i.e. remainders r and k−r pair up (with remainder 0 and k/2 pairing within themselves).
  • Code (C++): 
    #include <vector>
long countPairsDivByK(const std::vector<int> &a, int k) {
    std::vector<long> cnt(k, 0);
    for (int x : a) cnt[((x % k) + k) % k]++;   // normalize negatives

    long pairs = cnt[0] * (cnt[0] - 1) / 2;     // remainder 0 pairs among itself
    for (int r = 1; r <= k / 2; r++) {
        if (r == k - r)                          // exact middle (k even)
            pairs += cnt[r] * (cnt[r] - 1) / 2;
        else
            pairs += cnt[r] * cnt[k - r];        // r pairs with k-r
    }
    return pairs;
}
  • Complexity: O(n + k) time, O(k) space — a single pass to bucket plus O(k) to combine.
  • Gotcha / variants: Normalize remainders with ((x % k) + k) % k so negative inputs don't index out of range. Remainder 0 (and the exact middle k/2 when k is even) pair within their own bucket → use c·(c−1)/2, not c·c. The map/array of remainder counts is the hashing insight; a plain map keyed by remainder works identically.

Footer — these cover Part 1 categories H, I, J, K of practice_questions.md. Linked lists are the highest-yield family here: drill H1–H7 until the pointer rewiring is automatic, then layer on the harder H14–H16 and the tree problems. State complexity out loud and offer a second approach (iterative vs recursive, heap vs divide-and-conquer) — interviewers explicitly reward that. Concept depth lives in 03_dsa.md.