Core Data Structures, Algorithms, And Complexity

What's being tested

You need to recognize the right data structure, algorithmic pattern, and complexity bound from constraints, then implement cleanly under interview pressure. Expect arrays/strings, trees, heaps, hash maps, graphs, and scheduling-style dependency problems where the interviewer probes both correctness and tradeoffs.

Patterns & templates

• Sliding window over contiguous arrays/strings — fixed-size or dynamic expand/contract; usually O(n) time, O(1) or O(k) space.

• Hash map indexing — precompute value-to-index maps for O(1) lookup; watch duplicates, missing keys, and stable ordering assumptions.

• Binary tree reconstruction — postorder root is last; split inorder by root index; recurse right before left when consuming postorder backward.

• Heap / priority queue for repeated best-choice selection — O(log n) per insert/pop; use lazy deletion for changing multisets.

• Graph scheduling — model tests as a DAG, run topological sort with in-degree counts; detect cycles when processed nodes < n.

• Complexity comparison — arrays give O(1) indexing, linked lists give O(1) splice with node pointer, hash tables average O(1), trees O(log n) if balanced.

• Greedy load balancing — assign next ready task to earliest available executor using a min-heap; optimality may fail with heterogeneous runtimes.

Common pitfalls

Pitfall: For dynamic sliding windows, shrinking only once instead of while invalid leaves illegal windows in the answer.

Pitfall: Tree reconstruction fails when you scan inorder every recursion; build an index map first to avoid accidental O(n^2).

Pitfall: In scheduling problems, ignoring cycle detection produces a partial schedule that looks valid but silently drops blocked tasks.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.