Qualcomm Interview Prep — 03. Data Structures & Algorithms¶

Scope. Core data structures and algorithms that recur across the Qualcomm loop — arrays & strings, linked lists (the single most-asked DSA family here), stacks/queues, trees & BSTs, hashing, sorting/searching, recursion/backtracking, graphs, bit manipulation, and the design-flavoured questions (LRU cache, asteroid collision). Pure C-language/memory mechanics (pointers, malloc, dangling pointers, memory map) live in 01_c_programming.md; C++/STL/OOP and std:: containers in 02_cpp_oop.md; complexity of OS-level structures (scheduler queues, page tables) in 04_os.md; the producer/consumer & reader-writer concurrency framing of the screen-tearing problem in 04_os.md/10_lld_system_design.md; full system/LLD design (lift system, lottery machine, Google-Maps road-blocks, text-editor undo) in 10_lld_system_design.md; bit/number representation depth (two's complement, endianness) in 09_computer_arch_digital_design.md. Overlaps are cross-linked, not duplicated.

How to read each entry. Every question is answered in layers so you can stop at the depth you need: - Q — the question, phrased as interviewers actually ask it. - Frequency — how often it showed up in the 75 collected reports (tier + approximate count). - Concept — the basis — book-style fundamentals with worked examples and, where it helps, an SVG diagram. - The "wh"s — Why it exists (what problem the structure/algorithm solves), Where you see it (real Qualcomm/camera/embedded situations), and any important caveat. - Answer — a tight, say-it-out-loud interview answer. - Solution / good example — for "implement/design X" questions, complete, copy-pasteable code. - Follow-ups / gotchas — the traps interviewers spring next. - Seen in — the source reports.

Terms in bold-italics like amortized, stable sort, in-place, load factor, self-loop are defined in the § Encyclopedia at the bottom — search there for any keyword.

Frequency legend (sample = 75 collected interview reports; counts are approximate and partly from aggregator pages, so treat them as directional): 🔥🔥🔥 Very common (~8+ reports) · 🔥🔥 Common (~4–7) · 🔥 Occasional (~2–3) · ◽ Foundational (rarely asked verbatim, but assumed and underpinning everything else).

Why DSA dominates the Qualcomm loop. Almost every report contains at least one whiteboard/CodePair coding problem, and linked lists (reverse, detect loop, merge k sorted, delete given node, reverse in k-groups), bit manipulation, trees (max element, max path sum, left view), and complexity analysis appear over and over. Interviewers explicitly weight thinking aloud, giving multiple approaches, and stating complexity — several candidates were told to "explain the approach before coding." Evidence base: qualcomm_camera_interview_experiences.md.

Table of contents¶

• A. Complexity & Big-O — A1 Big-O / time & space · A2 amortized analysis · A3 which DS for searching + complexity
• B. Arrays & strings — B1 merge two sorted arrays in-place · B2 missing number 1..n · B3 count occurrences of each letter (no extra space) · B4 reverse words in a string · B5 dynamic 2D array alloc & multiply · B6 rotate k / sliding-window max · B7 pairs divisible by k
• C. Linked lists — C1 reverse · C2 detect loop (Floyd) + length of loop · C3 merge two sorted · C4 merge k sorted · C5 delete a node given only its pointer · C6 intersection of two lists · C7 nth node from end + middle · C8 reverse in k-groups · C9 reverse in pairs · C10 sorted list → BST · C11 insert at position / types
• D. Stacks & queues — D1 implement a stack · D2 stack using queues · D3 queue using stacks · D4 asteroid collision
• E. Trees & BST — E1 insert into BST · E2 delete a node from BST · E3 find max element · E4 binary tree maximum path sum · E5 left view · E6 min distance between two nodes · E7 traversals · E8 check if a tree is a BST
• F. Hashing — F1 hash table implementation & collision handling
• G. Sorting & searching — G1 merge sort · G2 quick sort & pivot impact · G3 complexity & stability table · G4 binary search
• H. Recursion, backtracking & graphs — H1 recursion & call stack · H2 backtracking · H3 graph representation · H4 BFS/DFS
• I. Bit manipulation — I1 count set bits · I2 reverse bits · I3 swap without temp · I4 check power of two
• J. Design-flavoured DSA — J1 LRU cache
• § Encyclopedia — searchable glossary
• § Last-5-minutes cheat sheet

A. Complexity & Big-O¶

A1 · Q: Explain time and space complexity / Big-O notation.¶

Frequency: 🔥🔥🔥 Very common (~8+ reports) — "explain time complexity notations," and every coding problem ends with "what's the complexity?"

Concept — the basis. Big-O describes how an algorithm's running time (or memory) grows as the input size n grows, ignoring constant factors and lower-order terms — it's an upper bound on growth rate, not a stopwatch reading. We care about the shape of the curve because constants stop mattering once n is large. The common classes, from best to worst:

Worked example — counting operations:

/* O(n): one pass */
for (int i = 0; i < n; i++) sum += a[i];

/* O(n^2): pass for every element */
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) pairs++;

/* O(log n): halve the search space each step */
while (lo <= hi){ int mid = lo + (hi-lo)/2; ... lo = mid+1 OR hi = mid-1; }

Why it exists. It lets you compare algorithms independently of hardware/compiler/language. An O(n log n) sort beats an O(n²) sort for large n on any machine, even if the O(n²) one has a smaller constant and wins for tiny n. Space complexity matters just as much on Qualcomm targets: a phone/ISP has tight RAM, so an O(1)-space in-place algorithm can be the difference between fitting and OOM.

Where you see it (Qualcomm). Per-pixel/per-frame ISP code runs width×height times per frame at 30–120 fps, so an O(n) vs O(n²) choice in an inner loop is a hard real-time pass/fail; choosing an O(1)-space streaming algorithm over an O(n)-buffer one because the buffer won't fit; justifying why a hash lookup (O(1)) beats a linear scan (O(n)) in a request table.

Answer. "Big-O expresses how runtime or memory scales with input size, dropping constants and lower-order terms — it's an upper bound on growth. The ladder is O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). I always give both time and space complexity, and I distinguish worst/average/best where they differ — e.g. quicksort is O(n log n) average but O(n²) worst, while merge sort is O(n log n) always at the cost of O(n) extra space."

Follow-ups / gotchas. Drop constants (O(2n)=O(n)) and keep the dominant term (O(n²+n)=O(n²)). Recursion's space includes the call-stack depth (e.g. recursive tree traversal is O(h) space). O(log n) base doesn't matter (bases differ by a constant). Don't confuse "worst case" with "always" — average case often drives the real choice.

Seen in: GfG Graphics SWE ("explain time complexity notations"), GfG Embedded System ("complexity analysis" on every DS), and essentially every coding round.

A2 · Q: What is amortized complexity? (Why is push to a dynamic array "O(1)"?)¶

Frequency: 🔥 Occasional — surfaces with dynamic arrays, hash-table resizing, and queue-using-stacks (D3).

Concept — the basis. Amortized analysis averages the cost of an operation over a worst-case sequence of operations, so an occasional expensive step is "paid for" by many cheap ones. It is not average-case over random inputs — it's a worst-case guarantee per operation across a sequence. Classic example: appending to a dynamic array (std::vector, a growable buffer). Most push_backs are O(1); when full, it doubles capacity and copies everything (O(n)). But doubling means that costly copy happens only every n pushes, so n pushes cost O(n) total → O(1) amortized each.

Worked example — the "doubling" argument:

push 1..n into a vector that doubles when full:
  total copies = 1 + 2 + 4 + 8 + ... + n  ≈ 2n   (geometric series)
  total work over n pushes = O(n)  →  O(1) amortized per push

Why it exists. It gives an honest, useful cost when worst-case-per-operation overstates reality. Saying push_back is O(n) (because one push might reallocate) is technically true but misleading; amortized O(1) captures that a long run of pushes is cheap. The same logic justifies hash-table rehash and the two-stack queue.

Where you see it (Qualcomm). A growable list of capture requests or events that doubles on overflow; a hash table that rehashes when its load factor crosses a threshold; understanding why a ring/pool with fixed capacity is preferred on hard-real-time paths (no amortized spike at all — every op is true O(1)).

Answer. "Amortized complexity is the average cost per operation over a worst-case sequence, where rare expensive operations are spread across many cheap ones. A dynamic array's push_back is O(1) amortized: it usually just writes, and the O(n) doubling-copy happens only every n pushes, so n pushes total O(n). It differs from average-case — it's a guarantee over the sequence, not over random inputs. The catch for real-time code is that the individual worst-case op is still O(n), so deterministic paths use fixed-capacity pools instead."

Follow-ups / gotchas. Growth must be multiplicative (doubling) — growing by a constant +1 each time gives O(n) amortized (bad). The three accounting methods are aggregate, accounting (assign credits), and potential. Amortized O(1) still has worst-case O(n) spikes — matters for latency-sensitive code.

Seen in: standard DSA expectation; underpins D3 (queue-using-stacks) and F1 (hash resize), both of which appear in the evidence.

A3 · Q: For searching an element in unsorted data, which data structure is best — and what's the complexity?¶

Frequency: 🔥 Occasional (~2 reports) — GfG Embedded System asked this directly with complexity analysis.

Concept — the basis. The right structure depends on what you optimize for:

For a one-off search of unsorted data, a linear scan (O(n)) is optimal — you can't beat looking at every element once if there's no structure. For repeated searches, build a hash table once (O(n)) and then each lookup is O(1) average.

Worked example:

/* one search, unsorted → just scan, O(n) */
int found = -1;
for (int i = 0; i < n; i++) if (a[i] == key) { found = i; break; }

/* many searches → hash once, then O(1) each (conceptually) */
HashSet *s = build_set(a, n);   // O(n)
contains(s, key);               // O(1) average

Why it matters. Interviewers use this to see if you reason about amortizing build cost over query count and about average-vs-worst case. The "trick" answer "hash table, O(1)" is only right when searches are repeated and a good hash/low load factor holds.

Where you see it (Qualcomm). A lookup table mapping sensor IDs → calibration; a set of in-flight buffer handles checked on every frame; deciding between a sorted config array (bsearch, O(log n)) and a hash map.

Answer. "If I'll search the unsorted data many times, the best structure is a hash table: O(1) average lookup after an O(n) build, degrading to O(n) only with bad hashing or a high load factor. For a single search there's nothing to gain from preprocessing — a linear scan is O(n) and optimal. If I also need ordering or range queries, I'd use a balanced BST or a sorted array with binary search at O(log n)."

Follow-ups / gotchas. Hashing's O(1) is average — adversarial keys or a bad hash give O(n). Sorting first (O(n log n)) then binary-searching only pays off for many queries. Bloom filter for membership-only with tiny memory (probabilistic).

Seen in: GfG Embedded System ("for searching an element which data structure is best — with complexity"; "HashMap, Stack, Binary Tree questions and complexity").

B. Arrays & strings¶

B1 · Q: Merge two sorted arrays into one sorted array (in-place into the first).¶

Frequency: 🔥🔥 Common (~4 reports) — "merge two arrays in sorted order," LeetCode-88-style "merge in-place into nums1."

Concept — the basis. Given nums1 (size m, with n empty slots at the end) and nums2 (size n), merge into nums1. The trick for in-place merge is to fill from the back: compare the largest remaining elements and place the bigger at the current tail. Going backward means you never overwrite a nums1 element you haven't read yet.

Worked example: nums1=[1,2,3,_,_,_], nums2=[2,5,6] → write from index 5 down: 6,5,3,2,2,1 → [1,2,2,3,5,6].

Why it exists / why backward. A forward merge into nums1 would clobber not-yet-merged nums1 values (same hazard as memcpy overlap, see 01_c_programming.md E1). Filling from the back uses the free tail space first, so each write lands on an already-consumed or empty slot — O(m+n) time, O(1) extra space.

Where you see it (Qualcomm). Merging two sorted event/timestamp streams; combining per-tile sorted results; the merge step of an external sort over data too big for RAM.

Answer (code).

/* nums1 has m valid elements then n blanks; nums2 has n elements. */
void merge(int *nums1, int m, int *nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;   // read tails, write tail
    while (j >= 0) {                            // until nums2 exhausted
        if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
        else                               nums1[k--] = nums2[j--];
    }
}

Follow-ups / gotchas. Loop only needs to run while j >= 0 — leftover nums1 elements are already in place. If you're given two separate arrays and an output buffer, a forward two-pointer merge is simplest (O(m+n) time, O(m+n) space). Watch the index arithmetic (m+n-1, not m+n).

Seen in: AmbitionBox Engineer #60 ("Merge Two Sorted Arrays in-place into nums1"), AmbitionBox Engineer #51 ("merge two arrays in sorted order").

B2 · Q: Given an unsorted list of 1..n with one element missing, find the missing element (optimally).¶

Frequency: 🔥 Occasional (~1–2 reports) — GfG Embedded System ("find the missing element, optimal approach").

Concept — the basis. Two O(n)-time, O(1)-space approaches: 1. Sum formula (Gauss): the sum of 1..n is n(n+1)/2. Subtract the actual array sum → the missing number. 2. XOR: XOR all numbers 1..n and XOR all array elements; equal numbers cancel (since x ^ x = 0), leaving the missing one. XOR avoids the overflow risk of the sum approach for large n.

Worked example: n=5, array [1,2,4,5]. Sum approach: 15 − 12 = 3. XOR: (1^2^3^4^5) ^ (1^2^4^5) = 3.

Why XOR is the "optimal" answer. Both are O(n)/O(1), but the sum n(n+1)/2 can overflow a 32-bit int for large n; the XOR running value never exceeds the max element, so it's overflow-safe — interviewers reward naming that. (Verified: both run O(n) time, O(1) space; XOR is preferred to avoid overflow.)

Where you see it (Qualcomm). Detecting a dropped frame/sequence number in a stream; finding a gap in allocated buffer IDs; a sanity check on a supposedly-complete index set.

Answer (code).

/* XOR — overflow-safe, O(n) time, O(1) space */
int missing(const int *a, int n /* values are 1..n with one absent, len = n-1 */) {
    int x = 0;
    for (int i = 1; i <= n; i++)        x ^= i;     // XOR of full range 1..n
    for (int i = 0; i < n - 1; i++)     x ^= a[i];  // XOR of present elements
    return x;                                       // survivor = missing value
}
/* Sum variant: return (long)n*(n+1)/2 - sum;  (watch overflow → use 64-bit) */

Follow-ups / gotchas. If two numbers are missing (or one missing + one duplicate), XOR alone needs an extra split-by-bit trick. For a range 0..n adjust the bounds. State your assumption about whether the range is 0..n or 1..n. Use a wider type for the sum approach.

Seen in: GfG Embedded System #41 ("find the missing element if you have been given an unsorted list from 1-n, optimal approach").

B3 · Q: Count the occurrence of each letter in a string/array — without extra space.¶

Frequency: 🔥🔥 Common (~4 reports) — "count occurrence of each letter without extra space," "find the word 'is' / count occurrences," and the Python file-word-count variant.

Concept — the basis. "Without extra space" usually means O(1) auxiliary relative to input size. For letters there are only 26 (or 256 for bytes), so a fixed-size frequency array of constant size is considered O(1) extra space — it doesn't grow with n. You scan once (O(n)), bumping count[c - 'a'] for each character.

Worked example: "banana" → scan once → a:3, b:1, n:2.

Why "fixed array = no extra space." A 26- or 256-entry table is a constant, independent of the input length, so asymptotically it's O(1) space. The interviewer wants the single-pass counting-array idiom and a clear statement that the table size is bounded by the alphabet, not by n.

Where you see it (Qualcomm). Histogram of pixel values (the basis of image histograms, auto-exposure metering, and histogram equalization — a 256-bin array per channel!); token frequency in a parser; quick character-class checks.

Answer (code).

/* Letters only: 26-entry table is constant space → "no extra space" w.r.t. n. */
void count_letters(const char *s) {
    int count[26] = {0};                          // O(1) extra (alphabet-bounded)
    for (; *s; s++)
        if (*s >= 'a' && *s <= 'z') count[*s - 'a']++;
    for (int i = 0; i < 26; i++)
        if (count[i]) printf("%c:%d\n", 'a' + i, count[i]);
}
/* Count a WORD's occurrences in a sentence (the GfG 'is' question): tokenize on
   spaces and strcmp each token to the target; O(total chars). */

Follow-ups / gotchas. "Without extra space" is interpreted as constant extra, not literally zero — say that out loud. For arbitrary Unicode you'd need a hash map (no longer O(1) space). If they truly forbid any auxiliary array and the input is mutable, you can sort in place (O(n log n)) and count runs. The "find word 'is'" version needs whole-word matching (don't count "island" or "this").

Seen in: LeetCode SWE #15 ("count the occurrence of each letter in an array without extra space"), GfG Set 8 #40 ("find the word 'is' … count: 4 … strcmp / HashMap approaches"), GfG Graphics SWE #3 (Python word-occurrence count).

B4 · Q: Reverse the words in a string.¶

Frequency: 🔥🔥 Common (~5 reports) — "reverse the words in it and print," "reverse the order of the words," plus the AmbitionBox "reverse words in string."

Concept — the basis. Turn "the sky is blue" into "blue is sky the". The clean in-place technique (when the buffer is mutable) is the reverse-twice trick: (1) reverse the entire string, then (2) reverse each word back. After step 1 the words are in the right order but each is spelled backward; step 2 fixes the spelling.

Worked example: "the sky" → reverse all → "yks eht" → reverse each word → "sky the".

Why reverse-twice. It achieves the reorder in O(n) time and O(1) extra space (no second buffer, no split into a word array). The double reversal elegantly composes to a word-order reversal — a classic "do you see the in-place trick?" probe.

Where you see it (Qualcomm). Reversing token order in a parsed command/protocol line; an embedded convention of editing a caller-supplied mutable buffer with no allocation (mirrors the "caller provides the buffer" pattern in 01_c_programming.md).

Answer (code).

static void rev(char *s, int i, int j){ while (i < j){ char t=s[i]; s[i++]=s[j]; s[j--]=t; } }

void reverse_words(char *s) {
    int n = 0; while (s[n]) n++;
    rev(s, 0, n - 1);                       // 1) reverse whole string
    int start = 0;                          // 2) reverse each word back
    for (int i = 0; i <= n; i++) {
        if (i == n || s[i] == ' ') { rev(s, start, i - 1); start = i + 1; }
    }
}

Follow-ups / gotchas. Clarify handling of multiple/leading/trailing spaces (the LeetCode variant collapses them — that needs an extra compaction pass). The "reverse odd-positioned words" variant (GfG #19) just reverses selected words. If the string is immutable, allocate an output buffer (O(n) space). Don't reverse characters of the whole string only — they want word order reversed.

Seen in: GfG FTE #19 ("reverse the words … print the sentence"; also "remove extra spaces and reverse the odd positioned words"), GfG SDE #20 ("reverse the order of the words"), AmbitionBox Engineer #35/#46 ("Reverse words in String").

B5 · Q: Dynamically allocate a 2D array and multiply two matrices.¶

Frequency: 🔥 Occasional (~2 reports) — AmbitionBox Engineer #35/#46 ("dynamic 2D array multiplication"); prep tip "array w.r.t. dynamic memory allocation."

Concept — the basis. C has no built-in dynamic 2D array, so you build one. Two idioms: (a) array of row pointers (int ** — rows can be non-contiguous), or (b) a single flat block indexed as m[i*cols + j] (contiguous, cache-friendly, one malloc/free — preferred). Matrix multiply C = A·B (A is p×q, B is q×r, C is p×r) is the triple loop C[i][j] = Σₖ A[i][k]·B[k][j], which is O(p·q·r) (O(n³) for square n).

Why it matters. It tests dynamic memory (cross-link 01_c_programming.md C1), pointer-of-pointer reasoning, and whether you know the cache-friendly flat layout. The flat layout is one malloc (no per-row leaks, contiguous for DMA/SIMD).

Where you see it (Qualcomm). Image = a 2D pixel matrix; convolution/filter kernels and color-correction 3×3 matrices multiply per pixel; ML/CV layers are matrix multiplies. Contiguous storage matters for cache and DMA.

Answer (code — flat, contiguous; the better pattern).

/* allocate */
int *mat_alloc(int rows, int cols){ return calloc((size_t)rows*cols, sizeof(int)); }
#define AT(m,cols,i,j) ((m)[(size_t)(i)*(cols)+(j)])

/* C(p x r) = A(p x q) * B(q x r) */
void matmul(const int *A, const int *B, int *C, int p, int q, int r) {
    for (int i = 0; i < p; i++)
        for (int j = 0; j < r; j++) {
            int s = 0;
            for (int k = 0; k < q; k++) s += AT(A,q,i,k) * AT(B,r,k,j);
            AT(C,r,i,j) = s;                       // O(p*q*r)
        }
}
/* free: just free(A); — one block. */

Follow-ups / gotchas. With int **, free rows before the top array. Dimensions must conform (A.cols == B.rows). Loop order i,k,j improves cache locality over i,j,k. Naive multiply is O(n³); Strassen is O(n^2.81) (rarely expected). Always check malloc/calloc for NULL.

Seen in: AmbitionBox Engineer #35 & #46 ("Dynamic 2d array multiplication"), prep tips ("Array and String w.r.t. dynamic memory allocation," "Pointer Arithmetic").

B6 · Q: Rotate k elements to the right / sliding-window maximum.¶

Frequency: 🔥 Occasional — GfG Embedded System ("rotate k-elements to the right," on a compiler) and foundit's "sliding window max."

Concept — the basis. Rotate right by k: the in-place reversal algorithm — reverse the whole array, reverse the first k, reverse the rest. O(n) time, O(1) space. Sliding-window maximum: for a window of size k sliding over n, maintain a monotonic deque of indices whose values are decreasing; the front is always the window max → O(n) total (each index pushed/popped once).

Worked example (rotate [1,2,3,4,5] right by 2): reverse all → [5,4,3,2,1]; reverse first 2 → [4,5,3,2,1]; reverse rest → [4,5,1,2,3]. ✓

Why these tricks. Rotation-by-reversal avoids an O(n) temp buffer or O(n·k) one-at-a-time shifting. The monotonic deque turns a naive O(n·k) window-max into O(n) by discarding indices that can never be the max again.

Where you see it (Qualcomm). Circular/ring buffers (rotation logic); sliding-window stats over a signal/pixel row (running max/min for local filters, morphological dilation = window max); streaming metrics.

Answer (code).

static void rev(int*a,int i,int j){ while(i<j){int t=a[i];a[i++]=a[j];a[j--]=t;} }
void rotate_right(int *a, int n, int k) {
    k %= n; if (k < 0) k += n;
    rev(a, 0, n-1); rev(a, 0, k-1); rev(a, k, n-1);   // O(n) time, O(1) space
}

Follow-ups / gotchas. Reduce k %= n first (rotating by n is a no-op). For window-max, a max-heap also works but is O(n log k); the deque is O(n). Off-by-one on the window boundary is the classic bug.

Seen in: GfG Embedded System #41 ("rotate k-elements to the right in an array"), foundit #9 ("window of size k sliding … find the maximum in each window").

B7 · Q: Count pairs whose sum is divisible by k.¶

Frequency: 🔥 Occasional (~2 reports) — Medium Sr-Engineer (GenAI) #25 and SDE-1 #17 ("Count Array Pairs Divisible by K").

Concept — the basis. Brute force checks all pairs (O(n²)). The remainder-bucket trick is O(n): group numbers by value % k. A pair (a,b) is divisible by k iff (a%k + b%k) % k == 0 — i.e. remainder r pairs with remainder k−r (and r=0 pairs with r=0, r=k/2 with itself). Count how many fall in each remainder bucket, then combine.

Worked example: [2,4,1,8,7], k=3 → remainders [2,1,1,2,1]. Bucket counts: r0=0, r1=3, r2=2. Pairs: r1·r2 = 3·2 = 6 (each remainder-1 with each remainder-2), plus C(r0,2)=0. → matches the "(2,4),(2,7),(1,8)…" examples.

Why the modular trick. It replaces the O(n²) pair scan with one O(n) pass to build k buckets and an O(k) combine. The key identity (a+b)%k==0 ⇔ a%k + b%k ∈ {0, k} is exactly the insight the Qualcomm candidate credited.

Where you see it (Qualcomm). Alignment/stride checks (is an offset pair aligned to k?); hash-bucket distribution reasoning; any "group by residue" counting.

Answer (code).

long count_pairs_div_k(const int *a, int n, int k) {
    long cnt[1024] = {0};                       // assume k <= 1024 buckets
    for (int i = 0; i < n; i++) cnt[((a[i] % k) + k) % k]++;
    long pairs = cnt[0] * (cnt[0] - 1) / 2;     // both remainder 0
    for (int r = 1; r <= k / 2; r++) {
        if (r == k - r) pairs += cnt[r] * (cnt[r] - 1) / 2;   // r pairs with itself
        else            pairs += cnt[r] * (cnt[k - r]);
    }
    return pairs;
}

Follow-ups / gotchas. Handle negative numbers with ((x%k)+k)%k. The r == k-r case (when k is even, r=k/2) pairs within its own bucket → use C(c,2). Don't double-count: only loop r up to k/2.

Seen in: Medium Sr Engineer #25 ("pairs … divisible by k … (a+b)%k==0 ⇒ a%k+b%k==k"), SDE-1 #17 ("Count Array Pairs Divisible by K").

C. Linked lists¶

Linked lists are the Qualcomm DSA family — reverse, detect loop, merge k sorted, delete-given-node, reverse-in-k-groups, intersection, nth-from-end, and sorted-list→BST all appear repeatedly. Master the pointer-rewiring mechanics once and they all fall out. A node is struct Node { int val; struct Node *next; };.

C1 · Q: Reverse a singly linked list.¶

Frequency: 🔥🔥🔥 Very common (~10+ reports) — the single most-asked coding question in the whole evidence set ("reverse a linked list" appears in at least a dozen reports).

Concept — the basis. Walk the list flipping each next pointer to point backward, keeping three pointers: prev (the reversed part so far), cur (node being processed), and a saved next (so you don't lose the rest after cutting the link). At the end prev is the new head.

Worked example: 1→2→3→NULL becomes 3→2→1→NULL. Each step: save next, point cur->next to prev, slide prev and cur forward.

Why it exists / why three pointers. The moment you set cur->next = prev you destroy the forward link, so you must save next first. It's the canonical pointer-surgery question: it proves you can rewire a structure without losing nodes, in O(n) time and O(1) space.

Where you see it (Qualcomm). Reversing a processing order (e.g. undo a pipeline stage order); building a list in reverse during parsing; it underpins reverse-in-k-groups (C8) and pairs (C9), both asked.

Answer (code — iterative, preferred).

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

struct Node *reverse(struct Node *head) {
    struct Node *prev = NULL, *cur = head;
    while (cur) {
        struct Node *next = cur->next;   // 1) save the rest
        cur->next = prev;                // 2) flip the link
        prev = cur;                      // 3) advance prev
        cur  = next;                     // 4) advance cur
    }
    return prev;                         // new head
}
/* recursive (O(n) stack): */
struct Node *reverse_rec(struct Node *h){
    if (!h || !h->next) return h;
    struct Node *r = reverse_rec(h->next);
    h->next->next = h; h->next = NULL;
    return r;
}

Follow-ups / gotchas. Iterative is O(1) space; recursive is O(n) stack space (can overflow on a long list). Handle empty/single-node lists. For a doubly linked list, also swap each node's prev. Be ready to dry-run on 1→2→3 aloud — interviewers love watching the pointers move.

Seen in: GfG Set 8 #40, GfG SDE #20, AmbitionBox Engineer #36/#47/#56/#57, LeetCode kernel SWE context, GfG Set-2 #23, and many more (most-cited DSA question).

C2 · Q: Detect a loop in a linked list (Floyd's). Then find the length of the loop.¶

Frequency: 🔥🔥🔥 Very common (~8 reports) — "detect loop," "how to detect a loop," "length of loop in a linked list," plus the circular/doubly-list variants.

Concept — the basis. Floyd's cycle detection (tortoise & hare): two pointers from the head, slow advances 1 node/step, fast advances 2. If there's a loop, fast laps slow and they meet inside the loop; if fast reaches NULL, there's no loop. O(n) time, O(1) space.

• Length of the loop: once they meet, keep one pointer fixed and walk the other around until it returns to the meeting node — the number of steps is the loop length.
• Start of the loop (bonus): reset one pointer to the head; advance both by 1; they meet at the loop's start. (Math: the head-to-start distance d equals the meeting-point-to-start distance, mod cycle length c.)

Worked example: 1→2→3→4→5→3 (5 points back to 3). slow/fast meet inside {3,4,5}; walking from the meeting node back to itself counts 3 → loop length 3.

Why it works (say this if pushed). Once both are in the cycle, fast gains exactly 1 on slow per step (it moves 2, slow moves 1), so the distance from fast to slow around the cycle shrinks by 1 each step. Since the cycle length c is finite, that gap must reach 0 within c steps — they meet. (Verified.)

Where you see it (Qualcomm). A corrupted free-list/request-queue that accidentally became circular (a real driver bug); detecting an unintended cycle in a graph of buffer references; sanity-checking linked structures during debugging.

Answer (code).

/* detect; returns the meeting node or NULL */
struct Node *detect_loop(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return slow;        // loop found
    }
    return NULL;                              // no loop
}
int loop_length(struct Node *meet) {
    if (!meet) return 0;
    int len = 1; struct Node *p = meet->next;
    while (p != meet) { p = p->next; len++; } // walk around once
    return len;
}
struct Node *loop_start(struct Node *head, struct Node *meet) {
    if (!meet) return NULL;
    struct Node *a = head, *b = meet;
    while (a != b) { a = a->next; b = b->next; }   // meet at loop start
    return a;
}

Follow-ups / gotchas. The hash-set approach (store visited nodes) is also O(n) time but O(n) space — Floyd's O(1) space is the "good" answer. Guard fast && fast->next before fast->next->next. To remove the loop, set the node before the loop start's next = NULL. A self-loop (node points to itself) is detected on the first step.

Seen in: GfG Graphics SWE #3, GfG FTE #18 ("detect and remove the loop"), GfG Set 8 #40 ("detect loop in a circular linked list"), GfG off-campus #44 ("detect loop … find middle"), Medium Senior #4, GfG Associate-off-campus #12 ("length of loop"), foundit #9 ("loop in a doubly linked list").

C3 · Q: Merge two sorted linked lists.¶

Frequency: 🔥🔥 Common (~4 reports) — AmbitionBox Engineer #35/#46 ("merge two sorted linked lists"), and as the building block of merge-k.

Concept — the basis. Weave two sorted lists into one sorted list by repeatedly taking the smaller head. A dummy head node simplifies the code (no special-casing the first append). O(m+n) time, O(1) extra space (you splice existing nodes — no new allocation).

Worked example: 1→3→5 and 2→4 → compare heads, pull smaller each time → 1→2→3→4→5.

Why the dummy node. Without it you'd need an if (!result) result = node; else tail->next = node; branch on every step. A dummy sentinel lets you always do tail->next = node, then return dummy.next. Clean and bug-resistant.

Where you see it (Qualcomm). Merging two sorted event streams; the merge phase of merge sort on lists (which the FTE candidate discussed — merge sort is preferred for linked lists since it needs no random access); combining sorted per-source results.

Answer (code).

struct Node *merge_two(struct Node *a, struct Node *b) {
    struct Node dummy, *tail = &dummy; dummy.next = NULL;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }   // <= keeps it stable
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;                  // attach the remaining tail
    return dummy.next;
}

Follow-ups / gotchas. Use <= (not <) to keep equal elements stable (relevant if nodes carry payload). Recursion is elegant but O(m+n) stack. This is the merge step for merge-k (C4) and list merge sort. Handle either list being NULL.

Seen in: AmbitionBox Engineer #35/#46 ("Merge two sorted linked lists"), GfG FTE #19 ("sort the list … merge sort vs quick sort for linked lists").

C4 · Q: Merge k sorted linked lists.¶

Frequency: 🔥🔥 Common (~3 reports, all "Hard") — the signature Display-team question ("Merge k Sorted Lists," full whiteboard + complexity).

Concept — the basis. Merge k sorted lists into one. Three approaches, in increasing quality: 1. Sequential merge: fold list 2 into 1, then 3, … → O(N·k) where N = total nodes (each merge re-walks the growing result). 2. Min-heap (priority queue): push all k heads; pop the min, append it, push its next. Heap size k → O(N log k). This is the expected optimal. 3. Divide & conquer: pairwise-merge lists (merge k/2 pairs, then k/4, …) → also O(N log k), O(1) extra (no heap).

Worked example: lists [1→4→5], [1→3→4], [2→6] → heap always yields the global min → 1→1→2→3→4→4→5→6.

Why heap / divide-conquer beat sequential. Sequential re-traverses already-merged elements k times → O(N·k). The heap only ever compares k current heads (log k per pop), and divide-and-conquer halves the number of lists each round (log k rounds), both giving O(N log k). Stating this complexity tradeoff is exactly what the Display-team interviewers wanted.

Where you see it (Qualcomm). k-way merge of sorted streams from multiple sensors/cores; external/merge sort; combining per-thread sorted partial results.

Answer (code — divide & conquer, no heap dependency, easy in C).

/* uses merge_two() from C3 */
struct Node *merge_k(struct Node **lists, int k) {
    if (k == 0) return NULL;
    while (k > 1) {
        int j = 0;
        for (int i = 0; i < k; i += 2) {
            struct Node *b = (i + 1 < k) ? lists[i + 1] : NULL;
            lists[j++] = merge_two(lists[i], b);     // pair up
        }
        k = j;                                       // half as many lists
    }
    return lists[0];                                 // O(N log k) time, O(1) extra
}

Follow-ups / gotchas. Sequential merge is the trap answer (O(N·k)) — mention it, then beat it. Heap needs a comparator on head->val. Divide-and-conquer recursion depth is O(log k). Be ready to write merge_two (C3) as the helper and analyze both pieces.

Seen in: Display Senior #2 & #6 ("Merge k Sorted Lists," full solution on whiteboard + complexity — Hard).

C5 · Q: Delete a node from a linked list given only a pointer to that node.¶

Frequency: 🔥🔥 Common (~3 reports) — "delete a node given only a pointer," incl. the circular linked-list variant.

Concept — the basis. You're given a pointer to the node to delete, but not the head or the previous node — so you can't fix the predecessor's next. The trick: copy the next node's data into this node, then delete the next node, effectively making this node "become" its successor. O(1).

Worked example: list 1→2→3→4, delete the node holding 2: copy 3 into it (1→3→3→4), then unlink the original 3 node → 1→3→4.

Why this trick / its limit. Without the predecessor you can't unlink this node directly. Overwriting it with the successor's value and removing the successor achieves the visible effect in O(1). Limitation: it fails for the last node (no successor to copy from) — you can only truly delete a tail node if you can reach its predecessor.

Where you see it (Qualcomm). Removing a request/buffer descriptor when you only hold a handle to it (no head walk) — O(1) deletion in a hot path; the circular-list version (foundit/GfG Set-2) is the same idea but you must keep the ring intact.

Answer (code).

/* delete 'node' given only its pointer (node is NOT the tail) */
void delete_given(struct Node *node) {
    if (!node || !node->next) return;       // can't handle the last node this way
    struct Node *nxt = node->next;
    node->val  = nxt->val;                  // copy successor's data in
    node->next = nxt->next;                 // bypass the successor
    free(nxt);                              // delete the now-duplicate successor
}

Follow-ups / gotchas. Explicitly state the last-node limitation — interviewers probe it. For a circular list, the same copy-successor trick works except the single-node ring (a node pointing to itself) needs special handling. If the node carries non-trivial/owned data, copying it must be a proper deep copy. This is O(1) vs the O(n) head-walk delete.

Seen in: foundit #9 ("delete a node, given only a pointer to the node in a circular linked list"), GfG Set-2 #22 (circular-list delete), LeetCode kernel SWE #15 ("delete a given node from a linked list with code").

C6 · Q: Find the intersection point of two linked lists.¶

Frequency: 🔥🔥 Common (~2–3 reports) — "intersection of two linked lists," explicitly asked for two approaches.

Concept — the basis. Two lists that merge share a common tail; find the first shared node. Approaches: 1. Length-difference: measure both lengths, advance the longer list's pointer by the difference, then move both together until they're equal — O(m+n) time, O(1) space. 2. Two-pointer switch: pointer a walks list A then continues into B; b walks B then A. After at most m+n steps they align at the intersection (or both hit NULL). Same complexity, no length computation — elegant. 3. Hash set: store all of A's nodes, scan B for the first hit — O(m+n) time, O(m) space.

Worked example: A: 1→2→3→7→9, B: 4→7→9 intersect at node 7. The two-pointer method: a does 1,2,3,7,9,4,7…, b does 4,7,9,1,2,3,7… → they meet at 7.

Why the two-pointer trick works. Each pointer traverses len(A)+len(B) nodes total before reaching the intersection, so they arrive at the meeting node simultaneously. It removes the explicit length bookkeeping while staying O(1) space.

Where you see it (Qualcomm). Two request chains that converge on a shared sub-list; detecting that two handles alias the same underlying buffer chain; reference-graph analysis.

Answer (code — two-pointer switch).

struct Node *intersection(struct Node *a, struct Node *b) {
    if (!a || !b) return NULL;
    struct Node *pa = a, *pb = b;
    while (pa != pb) {
        pa = pa ? pa->next : b;     // switch to other list at the end
        pb = pb ? pb->next : a;
    }
    return pa;                      // intersection node, or NULL if none
}

Follow-ups / gotchas. Compare nodes by address, not value (two different nodes can hold equal values). If no intersection, both pointers become NULL simultaneously → loop ends, returns NULL. The O(n log n) "approach" the GfG candidate mentioned likely refers to sorting node addresses — the two-pointer/length methods are strictly better at O(n).

Seen in: GfG Graphics SWE #3 ("intersection point … two approaches: brute force and O(n log n)"), GfG ML & System #11 ("intersection of two linked lists in C").

C7 · Q: Find the nth node from the end of a linked list (and the middle).¶

Frequency: 🔥🔥 Common (~2 reports) — "nth node from the end (with multiple approaches)," "find middle of linked list."

Concept — the basis. Single-pass two-pointer (gap) technique: advance a lead pointer n nodes ahead, then move lead and trail together until lead hits the end — trail is now at the nth-from-end. O(n) time, single pass, O(1) space. Middle of the list is the same family: slow (1×) and fast (2×) pointers; when fast reaches the end, slow is at the middle.

Worked example: 1→2→3→4→5, n=2 → lead starts 2 ahead, both move → trail lands on 4 (2nd from end). Middle of 1→2→3→4→5 → 3.

Why one pass beats two. The naive way is: count length L (one pass), then walk L−n (second pass). The gap method does it in one pass by maintaining the fixed n-node distance — the "multiple approaches" the interviewer wanted, with the single-pass one as the good answer.

Where you see it (Qualcomm). "Last N entries" of a log/event list; finding a split point for list partition; the middle-finding is the first step of list merge sort and palindrome-list checks.

Answer (code).

struct Node *nth_from_end(struct Node *head, int n) {
    struct Node *lead = head, *trail = head;
    for (int i = 0; i < n; i++) { if (!lead) return NULL; lead = lead->next; }
    while (lead) { lead = lead->next; trail = trail->next; }
    return trail;                              // nth from the end
}
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, the 2nd middle
}

Follow-ups / gotchas. Validate n ≤ length (return NULL or error if lead runs off during the initial advance). For even-length lists, decide whether "middle" is the first or second of the two centre nodes (loop condition controls it). Deleting the nth-from-end uses the same gap with trail stopping one node before the target.

Seen in: GfG Associate-off-campus #12 ("nth node from the end … multiple approaches"), GfG off-campus #44 ("find middle of linked list").

C8 · Q: Reverse a linked list in groups of k (reverse nodes in k-group).¶

Frequency: 🔥🔥 Common (~2 reports, "Hard") — "Reverse Nodes in K-Group," a senior/experienced favourite.

Concept — the basis. Reverse every consecutive block of k nodes; if the final block has fewer than k nodes, leave it as-is (LeetCode-25 rule). You reverse k nodes (like C1), then recursively/iteratively connect the reversed block's tail to the result of the next block. O(n) time, O(1) extra (iterative) or O(n/k) stack (recursive).

Worked example (k=2): 1→2→3→4→5 → 2→1→4→3→5 (last 5 alone stays). For k=3: 3→2→1→4→5.

Why it's "hard." It combines local reversal with careful inter-block stitching and the leftover-tail rule — easy to lose nodes or reverse a short final block by mistake. It directly builds on C1 (reverse) and C9 (pairs = k=2).

Where you see it (Qualcomm). Processing a stream in fixed-size blocks with reversed intra-block order; chunked buffer manipulation; the kind of pointer-surgery stamina question senior interviewers use.

Answer (code).

/* check there are >= k nodes, reverse them, recurse on the rest */
struct Node *reverse_k(struct Node *head, int k) {
    struct Node *node = head;
    for (int i = 0; i < k; i++) { if (!node) return head; node = node->next; } // <k left → keep

    struct Node *prev = NULL, *cur = head;
    for (int i = 0; i < k; i++) {                  // reverse this block of k
        struct Node *next = cur->next;
        cur->next = prev; prev = cur; cur = next;
    }
    head->next = reverse_k(cur, k);                // head is now block tail; stitch
    return prev;                                   // new block head
}

Follow-ups / gotchas. The "fewer than k → leave as-is" rule is the spec interviewers check; some variants ask to reverse the leftover too — clarify. Iterative version avoids the O(n/k) recursion stack. Reverse-in-pairs (C9) is exactly k=2.

Seen in: CodingKaro Engineer-C++ #31 ("Reverse Nodes in K Group — Hard"), LeetCode Engineer-C++ #62 ("Reverse Nodes in K-Group").

C9 · Q: Reverse a linked list in pairs.¶

Frequency: 🔥 Occasional (~1–2 reports) — "reverse linked list in pairs."

Concept — the basis. Swap every two adjacent nodes: 1→2→3→4 becomes 2→1→4→3. It's the k=2 special case of C8, but the pairwise version has a particularly clean recursive form. O(n) time.

Worked example: 1→2→3→4→5 → 2→1→4→3→5 (odd tail 5 stays).

Why pairs specifically. It's the simplest non-trivial grouped reversal — interviewers use it as a gentler version of k-groups, or to test whether you can do clean two-node pointer swaps and stitch them.

Where you see it (Qualcomm). Swapping adjacency in a small fixed pattern (e.g. byte-pair / sample-pair reordering); a warm-up before the k-group generalization.

Answer (code).

struct Node *reverse_pairs(struct Node *head) {
    if (!head || !head->next) return head;
    struct Node *second = head->next;
    head->next   = reverse_pairs(second->next);   // recurse on rest
    second->next = head;                          // swap the pair
    return second;                                // new head of this pair
}

Follow-ups / gotchas. Odd-length list leaves the last node untouched (the base case handles it). Iterative version uses a dummy head and swaps via three temp pointers. This is literally reverse_k(head, 2).

Seen in: AmbitionBox Engineer #37 ("Reverse linked list in pairs"), GfG Technical-Profiles #24 ("Pairwise Swap Nodes of a given Linked List").

C10 · Q: Convert a sorted linked list to a balanced BST.¶

Frequency: 🔥 Occasional (~2 reports) — "convert a given single linked list to BST," explicitly in the embedded loop.

Concept — the basis. A sorted list is the in-order traversal of a balanced BST, so the middle element is the root, the left half forms the left subtree, the right half the right subtree — recursively. Two ways: 1. Array conversion: copy list → array (O(n)), then build BST from the middle index recursively — simple, O(n) time, O(n) space. 2. Inorder simulation (optimal): count n once, then build the tree bottom-up while advancing a single list pointer in sorted order — O(n) time, O(log n) stack, no array. The recursion consumes nodes left-to-right, so the list pointer always sits at the correct root when you need it. (Verified: this is the standard O(n) approach.)

Worked example: -10→-3→0→5→9 → root 0, left subtree from -10→-3, right from 5→9 → a height-balanced BST.

Why "balanced." Picking the middle as the root each time keeps left/right counts within 1, so height is O(log n) → BST operations stay O(log n). Building naively (each next element as a right child) would degrade to a linked list (O(n) height).

Where you see it (Qualcomm). Turning a sorted dataset into a searchable balanced index; the principle (balance for O(log n)) underlies why production code uses red-black/AVL trees.

Answer (code — array method, clearest to write live).

struct TNode { int val; struct TNode *left, *right; };

static struct TNode *build(int *a, int lo, int hi) {
    if (lo > hi) return NULL;
    int mid = lo + (hi - lo) / 2;
    struct TNode *root = calloc(1, sizeof *root);
    root->val   = a[mid];
    root->left  = build(a, lo, mid - 1);
    root->right = build(a, mid + 1, hi);
    return root;                                  // balanced by construction
}
struct TNode *sorted_list_to_bst(struct Node *head) {
    int n = 0; for (struct Node *p = head; p; p = p->next) n++;
    int *a = malloc(n * sizeof *a), i = 0;
    for (struct Node *p = head; p; p = p->next) a[i++] = p->val;
    struct TNode *root = build(a, 0, n - 1);
    free(a);
    return root;
}

Follow-ups / gotchas. For a sorted array the middle-as-root build is identical (no list copy needed). Mention the inorder-simulation as the optimal-space follow-up. Check malloc/calloc for NULL. Balanced height is the whole point — say "middle as root keeps it O(log n)."

Seen in: GfG Set-2 #22 ("convert a given single Linked list to BST").

C11 · Q: Types of linked lists; insert a node at a given position.¶

Frequency: 🔥🔥 Common (~3 reports) — "types of linked lists and use cases," "insert a node at a given position," "insert at beginning / kth location."

Concept — the basis. Types: singly (one next), doubly (next + prev, O(1) backward + O(1) delete given a node), circular (tail→head, good for round-robin/ring buffers), and circular-doubly. Insert at position k: walk to node k−1, splice the new node in by rewiring two pointers. O(k) to reach the spot.

Worked example: insert 9 at position 2 in 1→2→3 → walk to node 2 (the node before position 2, 0-indexed) → new->next = node->next; node->next = new → 1→2→9→3.

Why different types. Singly is smallest (one pointer/node). Doubly enables O(1) deletion given a node and backward traversal (used by LRU, J1). Circular suits cyclic scheduling/ring buffers (the lottery-machine "circular queue" in 10_lld_system_design.md).

Where you see it (Qualcomm). Request/event queues (singly or doubly); LRU recency list (doubly, J1); round-robin scheduler / ring buffer (circular); free-lists in allocators.

Answer (code — insert at 0-indexed position).

struct Node *insert_at(struct Node *head, int pos, int val) {
    struct Node *n = malloc(sizeof *n); n->val = val;
    if (pos == 0) { n->next = head; return n; }          // insert at head
    struct Node *cur = head;
    for (int i = 0; cur && i < pos - 1; i++) cur = cur->next;
    if (!cur) { free(n); return head; }                  // position out of range
    n->next = cur->next; cur->next = n;                  // splice in
    return head;
}

Follow-ups / gotchas. Inserting at the head (or position 0) is the special case — handle it. Inserting in sorted order (the GfG "dictionary order names" variant) means walk until cur->next->val >= val. Always check malloc. For doubly lists also fix prev pointers (4 rewirings, not 2).

Seen in: GfG Associate-off-campus #12 ("types of linked lists and use cases"), GfG SDE #20 ("insert a node at given position"), GfG off-campus #44 ("insert at beginning / kth location"), GfG FTE #19 ("insert a new name at the correct position").

D. Stacks & queues¶

D1 · Q: Implement a stack (all operations). What is a stack and where is it used?¶

Frequency: 🔥🔥 Common (~3 reports) — "implement the stack (any method)," "a working program for all operations in a stack," "what is a stack, its use."

Concept — the basis. A stack is a LIFO (last-in-first-out) container: push adds to the top, pop removes from the top, peek/top reads it, isEmpty/isFull query state — all O(1). Implement with either an array + top index (fixed capacity, cache-friendly) or a linked list (grows dynamically, push/pop at head).

Worked example: push 1,2,3 → top is 3; pop → 3 out, top is 2.

Why it exists. LIFO models nested/most-recent-first processing: the call stack (function returns in reverse call order), expression evaluation, undo, backtracking, and DFS. It's so fundamental the CPU has hardware support (01_c_programming.md D2).

Where you see it (Qualcomm). The function call stack itself; expression/parser evaluation; undo in a text editor (cross-link 10_lld_system_design.md); iterative DFS; the asteroid-collision problem (D4) is literally a stack.

Answer (code — array-based, the cleanest to write live).

#define CAP 1000
typedef struct { int data[CAP]; int top; } Stack;   // top = index of top element
void st_init(Stack *s){ s->top = -1; }
int  st_empty(Stack *s){ return s->top == -1; }
int  st_full (Stack *s){ return s->top == CAP - 1; }
int  st_push (Stack *s, int x){ if (st_full(s))  return 0; s->data[++s->top] = x; return 1; }
int  st_pop  (Stack *s, int *out){ if (st_empty(s)) return 0; *out = s->data[s->top--]; return 1; }
int  st_peek (Stack *s, int *out){ if (st_empty(s)) return 0; *out = s->data[s->top];   return 1; }

Follow-ups / gotchas. Always guard underflow (pop/peek on empty) and overflow (push on full, array version). Linked-list stacks never overflow (until OOM) but allocate per node. A queue is the FIFO sibling. Be ready to do balanced-parentheses or postfix-evaluation as a follow-up.

Seen in: GfG ML & System #11 ("clean implementation of the stack"), GfG Set-4 Intern #42 ("working program for all operations in a stack; what is a stack"), GfG Set-8 #40 ("stack and queue data structures").

D2 · Q: Implement a stack using two queues.¶

Frequency: 🔥 Occasional — standard "stack using queues" pairing (asked alongside stack/queue topics).

Concept — the basis. A queue is FIFO, a stack is LIFO — so you simulate one with the other. Two strategies: - Costly push: on push, enqueue to the empty queue, then move everything from the other queue behind it, so the newest is always at the front → push is O(n), pop is O(1). - Costly pop: push enqueues normally (O(1)); pop dequeues n−1 items to the other queue and returns the last → pop is O(n).

Worked example (costly-push): push 1 → [1]; push 2 → enqueue 2, move 1 behind → [2,1]; pop → 2. LIFO achieved.

Why this exercise. It tests whether you truly understand the FIFO/LIFO inversion and can reason about where to pay the O(n) cost. (You can do it with a single queue by rotating after each push.)

Where you see it (Qualcomm). Mostly a fundamentals probe; conceptually, adapting an available primitive (only a queue API) to get stack semantics.

Answer (code — costly push, single-queue trick).

/* one queue suffices: after enqueueing, rotate the older elements behind it */
typedef struct { int q[1000]; int head, tail, n; } Queue;   // ring buffer
void  q_init(Queue*Q){ Q->head=Q->tail=Q->n=0; }
void  q_push(Queue*Q,int x){ Q->q[Q->tail]=x; Q->tail=(Q->tail+1)%1000; Q->n++; }
int   q_pop (Queue*Q){ int v=Q->q[Q->head]; Q->head=(Q->head+1)%1000; Q->n--; return v; }

typedef struct { Queue q; } StackViaQ;
void stq_push(StackViaQ*s,int x){
    q_push(&s->q, x);
    for (int i = 0; i < s->q.n - 1; i++) q_push(&s->q, q_pop(&s->q)); // rotate
}
int  stq_pop(StackViaQ*s){ return q_pop(&s->q); }   // newest is at front → LIFO

Follow-ups / gotchas. State which op you made O(n) and why. The single-queue rotation is the slick answer. Mirror image of D3 (queue using stacks). Watch ring-buffer wraparound.

Seen in: standard stack/queue expectation (asked with "stack and queue data structures," GfG Set-8 #40, GfG SDE #20).

D3 · Q: Implement a queue using two stacks.¶

Frequency: 🔥 Occasional — the classic counterpart, and a clean amortized example.

Concept — the basis. Use an in-stack (for enqueue) and an out-stack (for dequeue). enqueue: push to in (O(1)). dequeue: if out is empty, pour all of in into out (which reverses order, so the oldest ends up on top), then pop out. Each element is moved at most once from in to out, so dequeue is O(1) amortized (A2). (Verified.)

Worked example: enqueue 1,2,3 → in=[1,2,3]. dequeue → pour into out=[3,2,1] (top is 1), pop → 1 (FIFO). Next dequeues pop 2, then 3 — no re-pour needed.

Why amortized O(1). A single dequeue that triggers the pour is O(n), but that pour happens only once per element across its lifetime, so over any sequence of m operations the total work is O(m) → O(1) each on average. This is the textbook amortized-analysis example.

Where you see it (Qualcomm). A fundamentals/amortized-analysis probe; conceptually, building FIFO semantics from LIFO primitives.

Answer (code).

typedef struct { Stack in, out; } QueueVia2S;          // Stack from D1
void q2_init(QueueVia2S*q){ st_init(&q->in); st_init(&q->out); }
void q2_enqueue(QueueVia2S*q,int x){ st_push(&q->in, x); }   // O(1)
int  q2_dequeue(QueueVia2S*q,int *out){
    if (st_empty(&q->out)) {                 // refill only when out is empty
        int v;
        while (st_pop(&q->in, &v)) st_push(&q->out, v);   // reverse order once
    }
    return st_pop(&q->out, out);             // amortized O(1)
}

Follow-ups / gotchas. Only refill out when it's empty (refilling early breaks FIFO order). State the amortized vs worst-case (O(n) single op) distinction — that's the point of the question. Mirror of D2.

Seen in: standard queue/stack expectation; amortized-analysis follow-up to D1/D2.

D4 · Q: Asteroid collision.¶

Frequency: 🔥🔥 Common (~2 reports, "Hard") — "Asteroid Collision," used as a follow-up after a candidate solved earlier problems fast.

Concept — the basis. Asteroids on a line: each has a size (magnitude) and direction (sign — positive moves right, negative moves left). Same-direction asteroids never collide; a collision happens only when a right-mover (+) is followed by a left-mover (−). On collision the smaller explodes; equal sizes both explode. Process left-to-right with a stack of survivors: a new left-mover keeps popping smaller positive tops until it's destroyed, survives, or the stack top is also left-moving / empty.

Worked example: [5,10,-10] → push 5, push 10; -10 meets +10 → equal → both explode; 5 survives (no opposing left-mover left) → [5]. [8,-8] → both explode → []. [-2,-1,1,2] → no collisions → unchanged.

Why a stack. Only the most recently surviving right-mover can collide with an incoming left-mover, and that's exactly the stack top — LIFO matches the collision dynamics perfectly. O(n) time, O(n) stack.

Where you see it (Qualcomm). A stack-discipline / simulation reasoning probe (collisions, cancellation). The pattern — "newest element annihilates compatible older ones" — also models bracket matching and certain merge/cancel passes.

Answer (code).

/* returns count of survivors written into out[]; +ve = right, -ve = left */
int asteroids(const int *a, int n, int *out) {
    int top = 0;                                   // out[] used as a stack
    for (int i = 0; i < n; i++) {
        int cur = a[i], alive = 1;
        /* collide only when top moves right (+) and cur moves left (-) */
        while (alive && top > 0 && out[top-1] > 0 && cur < 0) {
            if (out[top-1] < -cur)      top--;             // top smaller → it explodes, continue
            else if (out[top-1] == -cur){ top--; alive = 0; } // equal → both explode
            else                          alive = 0;        // top bigger → cur explodes
        }
        if (alive) out[top++] = cur;
    }
    return top;
}

Follow-ups / gotchas. The collision condition is specifically top > 0 (positive) AND cur < 0 — two same-sign or a − then + never collide. Use a while (one incoming − can destroy several +s). The break/continue logic on the three size cases is where bugs hide — dry-run [10,2,-5] (→ [10]).

Seen in: CodingKaro Engineer-C++ #31 ("Asteroid Collision — Hard"), LeetCode Engineer-C++ #62 ("Asteroid Collision similar").

E. Trees & BST¶

A binary tree node is struct TNode { int val; struct TNode *left, *right; };. A BST adds the ordering invariant: every left descendant < node < every right descendant. Qualcomm asks: insert, delete, max element, max path sum, left view, min distance between nodes, traversals, and "is this a BST."

E1 · Q: Write create and insert functions for a Binary Search Tree.¶

Frequency: 🔥🔥 Common (~3 reports) — "write create and insert functions for a BST."

Concept — the basis. Insert preserves the BST invariant: starting at the root, go left if the new value is smaller, right if larger, until you find an empty spot, and link the new leaf there. O(h) time (h = height: O(log n) if balanced, O(n) if degenerate).

Worked example: insert 5,3,8,1 into an empty BST → 5 is root; 3 < 5 → left; 8 > 5 → right; 1 < 5 → left of 5, 1 < 3 → left of 3.

Why the invariant. Keeping left < node < right makes search/insert/delete all O(h) and makes an in-order traversal yield sorted output — that's the whole value of a BST over an unsorted tree.

Where you see it (Qualcomm). An ordered, searchable in-memory index; conceptual basis for the balanced trees (red-black) inside std::map/kernel structures; sorted-list→BST (C10).

Answer (code).

struct TNode *new_node(int v){ struct TNode *n = calloc(1,sizeof *n); n->val=v; return n; }

struct TNode *bst_insert(struct TNode *root, int v) {
    if (!root) return new_node(v);               // found the spot
    if (v < root->val)      root->left  = bst_insert(root->left,  v);
    else if (v > root->val) root->right = bst_insert(root->right, v);
    /* v == root->val: ignore duplicate (or count it) */
    return root;
}

Follow-ups / gotchas. Decide a duplicate policy (ignore / count / go right). Recursive insert is O(h) stack; an iterative version is O(1) space. Unbalanced inserts (sorted input) degrade to O(n) — mention AVL/red-black self-balancing as the production fix. calloc zeroes the child pointers.

Seen in: GfG Graphics SWE #3 ("write create and insert functions for a Binary Search Tree").

E2 · Q: Delete a node from a BST.¶

Frequency: 🔥🔥 Common (~2–3 reports) — "delete a node," "deleting a node in a binary tree."

Concept — the basis. Find the node, then handle three cases: (1) leaf → just remove it; (2) one child → replace the node with its child; (3) two children → replace the node's value with its in-order successor (smallest in the right subtree), then delete that successor (which has at most one child). O(h).

Worked example: delete 5 (two children) from a BST → find the min of its right subtree (say 6), copy 6 up, delete the original 6 node.

Why the successor trick. Replacing a two-child node with its in-order successor (or predecessor) preserves the BST ordering, because the successor is the next larger value — it slots in legally and has no left child (so deleting it is the easy one-child case).

Where you see it (Qualcomm). Maintaining an ordered index under removals; the same case-analysis appears in any balanced-tree delete (with extra rebalancing).

Answer (code).

static struct TNode *min_node(struct TNode *n){ while (n->left) n = n->left; return n; }

struct TNode *bst_delete(struct TNode *root, int v) {
    if (!root) return NULL;
    if (v < root->val)      root->left  = bst_delete(root->left,  v);
    else if (v > root->val) root->right = bst_delete(root->right, v);
    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 = min_node(root->right); // two children
        root->val = succ->val;                      // copy successor up
        root->right = bst_delete(root->right, succ->val); // delete successor
    }
    return root;
}

Follow-ups / gotchas. Predecessor (max of left subtree) works equally. The two-children case reduces to a one-child delete of the successor — don't recurse infinitely. In a self-balancing tree you'd rebalance after delete. Plain binary tree (non-BST) deletion replaces with the deepest node instead.

Seen in: GfG Technical-Profiles #24 ("fix a BST with two swapped nodes" — related), GfG Set-6 on-campus #43 ("deleting a node in binary tree"), foundit #9 (BST validity/fix).

E3 · Q: Find the maximum element in a binary tree.¶

Frequency: 🔥🔥 Common (~2 reports) — "find the maximum element in a binary tree" (used as a Round-1 opener).

Concept — the basis. Two cases the interviewer may mean: (a) plain binary tree (no ordering) → you must visit every node and track the max — O(n); (b) BST → the max is the rightmost node (keep going right) — O(h). Clarify which! For a general tree, recurse: max(root, max(left), max(right)).

Worked example: general tree → check all nodes; BST [8;3,10;…,14] → walk right: 8→10→14 → max 14.

Why two answers. It's a clarifying-question test. If you assume BST and they meant a plain tree, you miss elements. The BST shortcut (O(h), just go right) vs the general O(n) full traversal shows you understand the structure's properties.

Where you see it (Qualcomm). Finding an extreme value in a hierarchy; the BST rightmost-is-max property (mirror: leftmost is min) is reused in delete (E2, in-order successor).

Answer (code — both).

/* general binary tree: must scan all nodes, O(n) */
int tree_max(struct TNode *root) {
    if (!root) return INT_MIN;
    int l = tree_max(root->left), r = tree_max(root->right);
    int m = root->val;
    if (l > m) m = l;
    if (r > m) m = r;
    return m;
}
/* BST shortcut: rightmost node, O(h) */
int bst_max(struct TNode *root){ while (root && root->right) root = root->right; return root ? root->val : INT_MIN; }

Follow-ups / gotchas. Ask "is it a BST?" first — that single question is what they're testing. Empty tree → define a sentinel (INT_MIN) or error. BST min is the symmetric leftmost walk.

Seen in: LeetCode Engineer-C++ #62 ("find the maximum element in a binary tree").

E4 · Q: Binary tree maximum path sum.¶

Frequency: 🔥🔥 Common (~2 reports, "Hard") — "Binary Tree Maximum Path Sum."

Concept — the basis. A path is any sequence of connected nodes (it can start and end anywhere, and may bend at one node); find the maximum sum of node values along such a path. Post-order recursion: for each node compute the best downward gain (node + max(0, left_gain, right_gain)) to pass up to its parent, while separately updating a global best with the bent path node + max(0,left) + max(0,right) (using both children). O(n).

Worked example: tree [-10; 9, 20; null,null,15,7] → best path 15→20→7 = 42.

Why two quantities. A node returns to its parent only a straight downward path (you can't pass through a node twice), but the answer at that node may bend through it using both subtrees. So you track the "return value" (one side) and the "global max" (both sides) separately. The max(0, …) drops negative subtrees (better to take nothing).

Where you see it (Qualcomm). A classic hard tree-DP that tests post-order accumulation and the "local return vs global update" pattern — the kind senior interviewers use to gauge depth.

Answer (code).

static int best;                                 // global max (init INT_MIN by caller)
static int gain(struct TNode *n) {
    if (!n) return 0;
    int l = gain(n->left);  if (l < 0) l = 0;    // drop negative contributions
    int r = gain(n->right); if (r < 0) r = 0;
    int bend = n->val + l + r;                   // path bending through n (both sides)
    if (bend > best) best = bend;                // update global answer
    return n->val + (l > r ? l : r);             // return straight path to parent
}
int max_path_sum(struct TNode *root){ best = INT_MIN; gain(root); return best; }

Follow-ups / gotchas. Initialize best = INT_MIN (all-negative trees). The return value uses one side (max(l,r)); the global update uses both. Single negative node → answer is that node, not 0. This is post-order (compute children before the node).

Seen in: CodingKaro Engineer-C++ #31 ("Binary Tree Maximum Path Sum — Hard"), LeetCode Engineer-C++ #62 ("Binary Tree Maximum Path Sum similar").

E5 · Q: Print the left view of a binary tree.¶

Frequency: 🔥🔥 Common (~2 reports) — "print left view of a binary tree," "Left View of Binary Tree."

Concept — the basis. The left view is the set of nodes visible when you look at the tree from the left — i.e. the first node at each level. Do a level-order (BFS) traversal and take the first node of each level; or a pre-order DFS that records a node when its depth first exceeds the max-depth-seen-so-far. O(n).

Worked example: tree [1; 2,3; 4,5,6,7] → left view 1, 2, 4.

Why first-per-level. Looking from the left, each level's leftmost node hides the rest of that level. BFS naturally groups by level (first dequeued per level = leftmost). The DFS trick works because pre-order visits the left child first, so the first node seen at a new depth is the leftmost.

Where you see it (Qualcomm). A traversal-control probe (BFS level handling / DFS depth tracking). The mirror — right view — is the symmetric "last per level / right-child-first DFS."

Answer (code — DFS, concise).

/* visit left child first; record when we reach a new max depth */
static void lv(struct TNode *n, int depth, int *maxd, int *out, int *k) {
    if (!n) return;
    if (depth > *maxd) { out[(*k)++] = n->val; *maxd = depth; }  // first at this level
    lv(n->left,  depth + 1, maxd, out, k);     // LEFT first
    lv(n->right, depth + 1, maxd, out, k);
}
int left_view(struct TNode *root, int *out){ int maxd = -1, k = 0; lv(root, 0, &maxd, out, &k); return k; }

Follow-ups / gotchas. Right view = visit right child first (or last-per-level in BFS). Top/bottom view need horizontal-distance bookkeeping (a map). BFS version: for each level, push the first dequeued node. Don't confuse "left view" with "all left children."

Seen in: GfG Set-8 #40 ("print left view of a binary tree"), GfG Technical-Profiles #24 ("Left View of Binary Tree").

E6 · Q: Find the minimum distance between two nodes of a binary tree.¶

Frequency: 🔥 Occasional (~1–2 reports) — "min distance between two given nodes of a binary tree" (with call-stack analysis requested).

Concept — the basis. The distance between two nodes is the number of edges on the path between them, which passes through their Lowest Common Ancestor (LCA): dist(a,b) = depth(a) + depth(b) − 2·depth(LCA). So: find the LCA, then sum the depths of each node measured from the LCA. O(n).

Worked example: in [1;2,3;4,5], distance(4,5): LCA is 2; depth(4 from 2)=1, depth(5 from 2)=1 → distance 2 (4→2→5).

Why via the LCA. The unique simple path between two tree nodes always goes up to the LCA and back down. Decomposing into "up from a to LCA" + "down from LCA to b" gives the edge count directly, and the LCA is found in one traversal.

Where you see it (Qualcomm). Hierarchy/relationship distance queries; the LCA technique itself recurs in many tree problems. The "call-stack analysis" the interviewer asked about probes that you understand recursion depth (O(h) stack).

Answer (code).

static struct TNode *lca(struct TNode *r, int a, int b) {
    if (!r || r->val == a || r->val == b) return r;
    struct TNode *L = lca(r->left, a, b), *R = lca(r->right, a, b);
    if (L && R) return r;                       // a and b split here → this is the LCA
    return L ? L : R;
}
static int depth_from(struct TNode *r, int v, int d) {   // edges from r to value v
    if (!r) return -1;
    if (r->val == v) return d;
    int l = depth_from(r->left, v, d + 1); if (l != -1) return l;
    return depth_from(r->right, v, d + 1);
}
int min_distance(struct TNode *root, int a, int b) {
    struct TNode *l = lca(root, a, b);
    return depth_from(l, a, 0) + depth_from(l, b, 0);
}

Follow-ups / gotchas. Recursion uses O(h) call-stack — the explicit "call-stack analysis" ask. In a BST the LCA is found faster by comparing values (go left/right). Handle a node not present (return error). "Distance" here is edge count; clarify if they mean node count.

Seen in: GfG Set-8 #40 ("min distance between two given nodes of a Binary Tree, call stack analysis requested").

E7 · Q: Explain the tree traversals (in-order, pre-order, post-order, level-order).¶

Frequency: 🔥🔥 Common — traversals underpin most tree questions ("graph traversal algorithms," BST checks, views).

Concept — the basis. Four canonical orders: - In-order (L, N, R): for a BST yields sorted output. Used to validate a BST (E8). - Pre-order (N, L, R): root first — used to copy/serialize a tree. - Post-order (L, R, N): children before parent — used to free/delete a tree (so you don't free a parent before its children). - Level-order (BFS): level by level using a queue — used for left/right view (E5), shortest unweighted paths.

Worked example (BST [8;3,10;1,6,…,14]): in-order → 1 3 6 8 10 14 (sorted); pre-order → 8 3 1 6 10 14; post-order → 1 6 3 14 10 8; level-order → 8 3 10 1 6 14.

Why each order exists. The position of the root visit relative to its subtrees determines the use: visit root last (post-order) to safely destroy bottom-up; root first (pre-order) to reconstruct top-down; root in the middle (in-order) to exploit BST ordering. BFS gives breadth/distance structure.

Where you see it (Qualcomm). Serializing/deserializing a config tree (pre-order); tearing down a resource tree safely (post-order); validating sorted structure (in-order); shortest-hop traversal (BFS).

Answer (code).

void inorder (struct TNode *r){ if(!r)return; inorder(r->left);  visit(r); inorder(r->right); }
void preorder(struct TNode *r){ if(!r)return; visit(r); preorder(r->left); preorder(r->right); }
void postorder(struct TNode*r){ if(!r)return; postorder(r->left); postorder(r->right); visit(r); }
/* level-order: enqueue root; while queue not empty: dequeue, visit, enqueue children */

Follow-ups / gotchas. Recursive traversals use O(h) stack; iterative versions use an explicit stack (DFS) or queue (BFS). In-order of a BST being sorted is the key fact behind E8. Post-order is the safe destruction order. Be ready to write the iterative in-order (stack-based).

Seen in: GfG Graphics SWE #3 ("graph traversal algorithms with code"), underpins E8/E5 and the BST questions.

E8 · Q: Check whether a binary tree is a BST.¶

Frequency: 🔥 Occasional (~2 reports) — "check whether a binary tree is BST or not," "fix a BST with two swapped nodes."

Concept — the basis. A tree is a BST iff an in-order traversal is strictly increasing. Either (a) do an in-order walk and check each value is greater than the previous, or (b) recurse with a (min, max) valid range that tightens as you descend, verifying every node lies inside its allowed range. O(n). The range method catches the subtle bug that a node must be greater/less than all ancestors on the correct side, not just its parent.

Worked example: root 10, left 5, right 15, and 15's left child is 6. The local check passes everywhere (6 < 15), but it is not a BST: 6 sits in 10's right subtree yet 6 < 10, violating the global invariant. The (min,max) range method catches it (when descending into 15's left, the allowed range is (10,15), and 6 falls below 10).

Why range, not just parent. A common wrong answer only checks left < node < right locally — but a deep left descendant could still exceed an ancestor. Passing down (min,max) bounds enforces the global invariant.

Where you see it (Qualcomm). Validating an index/tree structure's integrity; the in-order-sorted property is reused everywhere (E7, C10).

Answer (code — range method).

#include <limits.h>
static int valid(struct TNode *n, long lo, long hi) {
    if (!n) return 1;
    if (n->val <= lo || n->val >= hi) return 0;       // out of allowed range
    return valid(n->left, lo, n->val) && valid(n->right, n->val, hi);
}
int is_bst(struct TNode *root){ return valid(root, LONG_MIN, LONG_MAX); }

Follow-ups / gotchas. Use long/sentinels wider than int to avoid INT_MIN/INT_MAX edge bugs (or pass node pointers). Decide whether equal values are allowed (<= vs <). The in-order approach with a "previous" pointer is equally valid. The "two swapped nodes" variant finds the two out-of-order elements in the in-order sequence and swaps them back.

Seen in: GfG Technical-Profiles #24 ("Check if a Binary Tree is BST or not"; "two swapped nodes → fix"), foundit #9 ("check whether a binary tree is BST or not").

F. Hashing¶

F1 · Q: Implement a hash table. How do you handle collisions?¶

Frequency: 🔥🔥 Common (~3 reports) — "implementation of hash table," "difference between hashing and hash tables."

Concept — the basis. A hash table maps keys to values in O(1) average time. A hash function turns a key into an array index (index = hash(key) % capacity). Because many keys map to the same index (a collision), you need a resolution strategy: - Separate chaining: each bucket holds a linked list of entries; collisions append to the list. Simple, degrades gracefully. - Open addressing: store entries in the array itself; on collision, probe for the next free slot — linear probing (+1), quadratic probing (+i²), or double hashing. Cache-friendly, but needs careful deletion (tombstones) and a lower load factor.

Worked example: keys "cat"→2 and "act"→2 collide; with chaining, bucket 2 holds a list [cat, act]; lookup "act" walks that short list.

Why it exists / collisions are inevitable. Hashing trades space for speed: instead of searching, you compute where a key lives. Collisions are unavoidable (pigeonhole: more possible keys than buckets), so a resolution strategy is mandatory. Keep the load factor (entries/buckets) low (resize/rehash when it exceeds ~0.7) to preserve O(1) average.

Where you see it (Qualcomm). Symbol tables in tools; mapping sensor/buffer IDs → metadata; deduplication sets; any "have I seen this key?" check. std::unordered_map (cross-link 02_cpp_oop.md) is exactly this.

Answer (code — separate chaining).

#define NB 1024
typedef struct Entry { char *key; int val; struct Entry *next; } Entry;
typedef struct { Entry *buckets[NB]; int count; } HashMap;

static unsigned hash_str(const char *s){            // djb2
    unsigned h = 5381; while (*s) h = h*33 ^ (unsigned char)*s++;
    return h % NB;
}
void hm_put(HashMap *m, const char *key, int val) {
    unsigned i = hash_str(key);
    for (Entry *e = m->buckets[i]; e; e = e->next)
        if (!strcmp(e->key, key)) { e->val = val; return; }   // update
    Entry *e = malloc(sizeof *e);
    e->key = strdup(key); e->val = val;
    e->next = m->buckets[i]; m->buckets[i] = e;               // prepend, O(1)
    m->count++;
}
int hm_get(HashMap *m, const char *key, int *out) {
    for (Entry *e = m->buckets[hash_str(key)]; e; e = e->next)
        if (!strcmp(e->key, key)) { *out = e->val; return 1; }
    return 0;                                                  // not found
}

Follow-ups / gotchas. "Hashing" is the technique (the hash function); a "hash table" is the data structure using it — state that distinction. Worst case is O(n) if every key collides into one bucket (bad hash / adversarial keys). Resize/rehash when the load factor grows (amortized cost, A2). Open addressing needs tombstones so deletions don't break probe chains. A good hash spreads keys uniformly.

Seen in: GfG Associate-off-campus #12 ("implementation of hash table"), GfG Technical-Profiles #24 ("difference between hashing and hash tables"), GfG Embedded #41 ("HashMap … complexity").

G. Sorting & searching¶

G1 · Q: Explain merge sort and its complexity.¶

Frequency: 🔥🔥 Common (~3 reports) — "explain merge sort and quick sort with complexity," "implement merge sort."

Concept — the basis. Merge sort is divide & conquer: split the array in half, recursively sort each half, then merge the two sorted halves. Splitting gives log n levels; merging each level touches all n elements → O(n log n) in all cases (best, average, worst). It needs O(n) extra space for the merge buffer, and it is stable. (Verified.)

Worked example: [5,2,8,1] → split → [5,2],[8,1] → sort → [2,5],[1,8] → merge → [1,2,5,8].

Why merge sort. Guaranteed O(n log n) (no O(n²) worst case), stable, and the merge step works sequentially — which is why it's the natural choice for linked lists (no random access needed) and external sorting (data bigger than RAM, merged in streamed runs).

Where you see it (Qualcomm). Sorting linked lists (the FTE candidate's exact discussion); external/k-way merge of large datasets (ties to merge-k, C4); anywhere a stable, predictable sort is required.

Answer (code — array merge sort).

static void merge(int *a, int lo, int mid, int hi, int *tmp) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= = stable
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (k = lo; k <= hi; k++) a[k] = tmp[k];
}
void merge_sort(int *a, int lo, int hi, int *tmp) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(a, lo, mid, tmp);
    merge_sort(a, mid + 1, hi, tmp);
    merge(a, lo, mid, hi, tmp);
}