Interview Q&A

Short answer: Hash map from key → node plus a doubly linked list ordered by recency. get/put are O(1): move accessed node to front; on capacity eviction remove from tail. This is one of the most asked system-design-lite coding questions.

Interview approach

1. Clarify capacity and that both get and put must be O(1).
2. Explain why list alone or map alone is not enough.
3. Implement move-to-front and remove-tail helpers.
4. Handle update of existing key in put.

Complexity

get/put O(1) average; Space O(capacity).

Common follow-ups

• LFU Cache
• Thread-safe LRU
• TTL expiration

Mistakes to avoid

• Forgetting to update value on put for existing key
• Losing list pointers when removing

In C#, LinkedList + Dictionary is the standard interview implementation.

Short answer: DFS from each cell matching the first letter. Mark visited, explore 4 directions for the next character, then unmark (backtrack). Return true as soon as the word is completed.

Complexity

Time roughly O(N * 4^L) worst case (N cells, L word length); Space O(L) recursion.

Edge cases to mention

• Word longer than board cells
• Reuse of same cell (forbidden)
• Single-letter word

Emphasize marking/unmarking — that is the backtracking signature.

Short answer: Maintain inclusive or exclusive bounds consistently. Compute mid carefully (lo + (hi − lo) / 2) to avoid overflow. Decide whether you want lower-bound, upper-bound, or exact match before coding.

Complexity

Time O(log n), Space O(1).

Mistakes to avoid

• Off-by-one infinite loops
• Using (lo+hi)/2 overflow on large ints
• Mixing inclusive/exclusive bounds

State the loop invariant: “answer is always inside [lo, hi]”.

Short answer: Each node has children map/array[26] and an isEnd flag. insert/search/startsWith walk character by character. Tries shine for autocomplete and dictionary prefix queries.

Complexity

Time O(L) per operation (L = word length), Space O(total characters).

Common follow-ups

• Word Search II (Trie + backtracking)
• Replace Words

Ask if alphabet is lowercase English — array[26] is cleaner than Dictionary.

Short answer: Prioritize: Arrays/Hashing, Two Pointers, Sliding Window, Binary Search, Stack, Linked List, Trees (BFS/DFS), Graphs (BFS/DFS/topo), Heaps, Intervals, 1-D DP, Backtracking, and LRU-style design. Pattern recognition beats memorizing hundreds of problems.

Interview approach

1. Finish Blind 75 or NeetCode 150-style coverage once.
2. Timed practice: aim to solve mediums in ~25 minutes with explanation.
3. Always narrate brute force → optimize → complexity → edge cases.
4. Revisit company-tagged mediums from the last 6–12 months.

Depth on patterns beats shallow volume. Quality reps with explanation win offers.

Short answer: Clarify inputs/outputs/constraints first. Propose brute force, then optimize. Speak while coding, test with an example, and state complexity. Silence is riskier than imperfect code with clear thinking.

Interview approach

1. Restate the problem in one sentence.
2. Ask about constraints, duplicates, nulls, and expected complexity.
3. Outline approaches and pick one with justification.
4. Code incrementally; verify with a dry run.
5. Discuss trade-offs and follow-ups even if time ends.

Mistakes to avoid

• Jumping into code silently
• Ignoring edge cases
• Optimizing prematurely without a correct baseline

Interviewers hire teammates — communication is part of the score.

Short answer: Use preorder with null markers (e.g. "#") or level-order BFS with nulls. Deserialization consumes the same format with a queue/iterator. Clarify the string format with the interviewer first.

Complexity

Time O(n), Space O(n).

Pick one format and stick to it — inconsistency is a common fail point.

Short answer: BFS/DFS while maintaining a map from original node → clone. For each neighbor, clone if missing, then link clones. Prevents infinite loops on cycles.

Complexity

Time O(V + E), Space O(V).

The visited/clone map is mandatory — say it before writing loops.

Short answer: Min-heap of size k: O(n log k). Quickselect (partition) average O(n), worst O(n²). Sorting is O(n log n) — mention then improve.

Common follow-ups

• Kth largest in a stream
• Find median

If they care about worst-case, discuss heap; if average-case, mention Quickselect.

Short answer: Water at i is min(leftMax, rightMax) − height[i]. Compute with two arrays, or optimize with two pointers moving from ends while tracking leftMax/rightMax. Stack-based solution processes bars as histogram valleys.

Complexity

Two pointers O(n) time, O(1) space.

Relate it to Container With Most Water but stress per-index water units.

Short answer: Monotonic deque storing indices in decreasing height order. As the window slides, pop out-of-window indices from front and smaller values from back. Front is always the max. O(n).

Complexity

Time O(n), Space O(k).

This is a classic “monotonic queue” question — name the pattern.

Short answer: Model words as graph nodes; edges connect words differing by one letter. BFS from beginWord finds shortest transformation length. Bidirectional BFS is a strong optimization follow-up.

Complexity

Time roughly O(N * L * 26) with wildcards or neighbor generation.

BFS = shortest path in unweighted graph — say that sentence.

Short answer: Transpose the matrix, then reverse each row (for 90° clockwise). Alternatively rotate layer-by-layer swapping four cells. Both are O(n²) time and O(1) extra space.

Transpose + reverse is easier to get right under pressure.

Short answer: Diameter is the longest path between any two nodes (edges count). DFS returns height; at each node update global max of leftHeight + rightHeight. O(n).

Path may not pass through the root — that is the common trap.

Short answer: Keep a normal stack plus an auxiliary stack of current minima (or store pairs). push/pop/top/getMin all O(1). On push, push min(x, currentMin) onto the min stack.

Complexity

All operations O(1), Space O(n).

Do not scan the stack for getMin — that is O(n) and fails the prompt.

Short answer: Subsets: at each index choose include/exclude (or loop-based cascading). Permutations: swap/choose unused elements recursively. Always discuss time complexity exponential in n and when to prune.

Complexity

Subsets O(n * 2^n); Permutations O(n * n!).

Draw the decision tree for n=3 — it proves you understand recursion depth.

Short answer: BFS uses a queue and finds shortest paths in unweighted graphs / level order. DFS uses a stack/recursion and is natural for path existence, cycle detection, topological sort, and flood fill. Pick based on what “best” means.

If the question says “shortest” on an unweighted graph, default to BFS.

Short answer: DFS while tracking parent: visiting an already-visited neighbor that is not the parent means a cycle. Union-Find (Disjoint Set) also works for edge lists: union fails if both ends share a parent.

Complexity

Time O(V + E).

Do not reuse the directed-graph “gray node” story without adjusting for parent.

Short answer: 2-D DP: if s[i]==t[j], dp[i][j] = dp[i-1][j-1]+1 else max(skip either char). Classic O(m*n) table; can compress to two rows for space.

Common follow-ups

• Print the LCS string
• Longest Common Substring (different recurrence)
• Edit Distance

Contrast subsequence (not contiguous) vs substring (contiguous) immediately.