Interview questions with answer breakdowns — Page 51 of 52
Browse page 51 of Offer.cc interview question and answer breakdowns with reasoning, implementation details, follow-ups, and public sources.
Coding Interview: Find the Kth Largest Element in an Array
Derive the kth-largest answer from sorting and a bounded heap to randomized three-way quickselect, with a precise partition invariant, duplicate handling, complexity trade-offs, and executable tests.
Coding Interview: Copy a Linked List with Random Pointers
Learn how to deep-copy a linked list with random pointers using an identity map, then derive the interleaving optimization, prove its invariants, and restore the original list safely.
Coding Interview: Find All Critical Connections in a Network
Find every bridge in an undirected graph with discovery times and low-link values, then prove the strict bridge condition and implement a stack-safe iterative DFS.
Coding Interview: Reverse Nodes in k-Group
Solve reverse nodes in k-group with a dummy node, complete-group lookahead, and bounded pointer reversal, then prove why an incomplete tail stays unchanged.
Coding Interview: How Do You Find the Largest Rectangle in a Histogram?
Derive the largest-rectangle-in-a-histogram algorithm from nearest-smaller boundaries, implement a one-pass monotonic stack, and prove its correctness and linear complexity.
Coding Interview: How Do You Calculate Edit Distance with Dynamic Programming?
Derive the edit-distance recurrence over string prefixes, prove its three transitions, and implement a rolling-row TypeScript solution with O(mn) time and O(min(m, n)) space.
Coding Interview: How Do You Find the Longest Increasing Subsequence?
Derive the minimum-tail invariant from quadratic dynamic programming, then use binary search, predecessor indices, and property tests to implement and prove an O(n log n) longest increasing subsequence algorithm.
Coding Interview: How Do You Solve Word Ladder with Bidirectional BFS?
Model Word Ladder as an implicit unweighted graph, derive BFS from the shortest-sequence contract, and implement a smaller-frontier bidirectional search with a precise proof, cost model, and adversarial tests.
Coding Interview: How Do You Implement an O(1) LFU Cache?
Implement an LFU cache with a key index, frequency buckets, per-bucket doubly linked lists, and a minimum-frequency pointer, then prove expected O(1) get and put.
Coding Interview: How Do You Solve Minimum Window Substring?
Derive a variable-length sliding window from the quadratic baseline, track required frequencies and satisfied character classes, and verify an executable TypeScript solution against duplicates, impossible inputs, and a brute-force oracle.
Coding Interview: How Do You Solve Trapping Rain Water with Two Pointers?
Derive prefix arrays and a two-pointer solution from the per-column water formula, prove why the smaller known boundary is safe to advance, and implement and verify O(n) time with O(1) auxiliary space.
Coding Interview: How Do You Merge K Sorted Linked Lists?
Derive an O(N log k) merge from the frontier invariant, implement it with a size-k min-heap, prove correctness, and compare it with scanning, sequential merging, sorting, and divide-and-conquer.
Coding Interview: Implement Dijkstra's Shortest Path Algorithm
Implement Dijkstra with an adjacency list, lazy heap deletion, and path reconstruction; prove its greedy invariant and explain early exit, complexity, and negative-edge boundaries.
Coding Interview: How Do You Implement Union-Find and Track Connected Components?
Derive Union-Find from dynamic connectivity queries, implement union, connected, and component counting with union by size and path halving, and explain correctness, amortized complexity, tests, and deletion limits.
Coding Interview: How Do You Solve Sliding Window Maximum with a Monotonic Deque?
Derive a monotonic deque from brute-force and heap approaches, prove O(n) time with domination, invariants, and amortized analysis, and implement a TypeScript circular deque that truly uses O(k) space.
Coding Interview: Find the Lowest Common Ancestor of a Binary Tree
Derive a one-pass postorder solution from the path baseline, prove it with a subtree-return invariant, and handle duplicate values, missing targets, deep trees, and repeated queries.
Coding Interview: Serialize and Deserialize a Binary Tree
Design a reversible preorder encoding with explicit null markers, prove why the decoder consumes exactly one subtree, and handle malformed input, deep trees, and alternative formats.
Coding Interview: Find the Median from a Data Stream
Maintain the lower half in a max-heap and the upper half in a min-heap, derive O(log n) insertion and O(1) queries from explicit invariants, and handle correctness, edge cases, and sliding-window follow-ups.
Coding Interview: Find the First and Last Position with Binary Search
Use lower and upper bounds to handle duplicates, empty arrays, and missing targets uniformly, then prove the O(log n) solution with half-open interval invariants.
Coding Interview: How Do You Merge Overlapping Intervals?
Merge overlapping closed intervals with sorting and a greedy scan, then justify the endpoint rule, correctness invariant, complexity, and non-mutating contract while handling nested, chained, and streaming follow-ups.
How Do You Solve Course Schedule II with Topological Sort?
Derive Kahn's topological sort from course prerequisites, prove its zero-indegree invariant and cycle check, and handle follow-ups about multiple orders, duplicate edges, and parallel semesters.
Implement a Trie with Insert, Search, Prefix, and Delete
Derive a Trie from exact-match and prefix requirements, implement safe deletion without damaging shared paths, and verify the terminal-marker invariant, complexity, and adversarial cases.
Design a Data Structure for Dynamic Top-K Frequent Items
Derive an exact dynamic top-k data structure from the read-write ratio, with runnable frequency-bucket code, invariants, and complexity, then define when bounded memory requires Space-Saving or Count-Min Sketch.
Implement a Thread-Safe Bounded Blocking Queue
Implement a bounded blocking queue with a ring buffer, one lock, and two conditions, then prove its correctness through state invariants, linearization points, spurious wakeups, and interruption semantics.