Core Topics Tested

Expect questions on trees, graphs, hashing, and DP, with emphasis on time/space complexity analysis and real-world applications.

• Binary trees: Level order traversal (BFS queue), max depth (recursion), invert tree (DFS swap children).

• Graphs: BFS/DFS traversal, detect cycle (colored nodes or stack), shortest path (BFS).

• DP basics: Fibonacci (memoization vs tabulation), longest common subsequence (2D table).

• Sorting/searching: Merge intervals (sort + merge), search rotated array (modified binary search).

Key Questions & Answers

These are commonly asked for mid-level roles; practice coding and explaining.

Q - Find middle of linked list in one pass. ​

A - Use two pointers: slow (1 step), fast (2 steps). Meet at middle. Time: O(n), Space: O(1).​

Q - Detect cycle in graph. ​

A - DFS with three colors (white/gray/black) or BFS levels. Gray revisit detects cycle. O(V+E).​

Q - Implement LRU Cache. ​

A - Hash map + doubly linked list. O(1) get/put: move to front on access, evict tail.​

Q - Merge k sorted lists.

A - Min-heap of list heads. Pop min, add next. Time: O(n log k), n total nodes.​

Q - Longest increasing subsequence. ​

A - DP array: dp[i] = length ending at i. Max over all. O(n²); optimize to O(n log n) with binary search.

Preparation Tips

Mock interviews should include verbal walkthroughs: "For LRU, hash gives O(1) access; DLL handles order without O(n) shifts." Analyze complexities aloud.