Essential DSA Interview Questions

How to Use This List

These are the most frequently asked questions across top tech companies. For each problem, I provide the key insight and approach hint — not the full solution. Your job is to implement them yourself. The act of struggling with implementation is what builds skill.

Arrays & Hashing (8 Questions)

1. Two Sum

Problem: Find two numbers in an array that add up to a target. Approach: Hash map storing complement → index. One pass: for each element, check if target - element exists in map. O(n) time, O(n) space.

2. Best Time to Buy and Sell Stock

Problem: Find maximum profit from one buy and one sell. Approach: Track minimum price seen so far. At each day, profit = current_price - min_so_far. Track maximum profit. O(n) time.

3. Contains Duplicate

Problem: Check if any value appears at least twice. Approach: Hash set. Add elements one by one; if already in set, return true. O(n) time, O(n) space.

4. Product of Array Except Self

Problem: Return array where each element is the product of all other elements, without division. Approach: Two-pass technique. Left pass computes prefix products, right pass computes suffix products. Multiply them for the answer. O(n) time, O(1) extra space if you use the output array for one pass.

5. Maximum Subarray (Kadane's Algorithm)

Problem: Find the contiguous subarray with the largest sum. Approach: Track current_sum and max_sum. At each element: current_sum = max(element, current_sum + element). If starting fresh is better, start fresh. O(n).

6. Merge Intervals

Problem: Merge all overlapping intervals. Approach: Sort by start time. Iterate: if current interval overlaps with last merged, extend the end. Otherwise, add as new interval. O(n log n).

7. Trapping Rain Water

Problem: Given elevation map, compute how much water it can trap. Approach: Two-pointer from both ends. Water at position i = min(max_left, max_right) - height[i]. Track running max from each side. O(n) time, O(1) space.

8. Longest Consecutive Sequence

Problem: Find the length of the longest consecutive elements sequence in O(n). Approach: Put all numbers in a hash set. For each number that is a sequence start (num-1 not in set), count consecutive elements. O(n).

Strings (5 Questions)

9. Valid Anagram

Problem: Check if two strings are anagrams. Approach: Frequency count with array of size 26 (for lowercase). Increment for string1, decrement for string2. Check all zeros. O(n).

10. Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring with all unique characters. Approach: Sliding window with hash map tracking last seen index of each character. When duplicate found, move left pointer past the previous occurrence. O(n).

11. Longest Palindromic Substring

Problem: Find the longest palindromic substring. Approach: Expand around center. Try each character (and each pair of adjacent characters) as the center, expand while characters match. O(n²) time, O(1) space.

12. Group Anagrams

Problem: Group strings that are anagrams of each other. Approach: Sort each string to get a canonical form. Use sorted string as hash map key, original strings as values. O(n * k log k) where k is max string length.

13. Minimum Window Substring

Problem: Find smallest substring of s containing all characters of t. Approach: Sliding window with character frequency matching. Expand right until all characters covered, then shrink left to minimize. Track "formed" count vs required. O(n).

Linked Lists (4 Questions)

14. Reverse Linked List

Problem: Reverse a singly linked list. Approach: Three pointers: prev=None, curr=head, next. At each step: save next, point curr.next to prev, advance prev and curr. O(n).

15. Detect Cycle in Linked List

Problem: Determine if a linked list has a cycle. Approach: Floyd's algorithm. Slow pointer moves 1 step, fast moves 2. If they meet, cycle exists. To find cycle start: reset slow to head, move both 1 step until they meet. O(n).

16. Merge Two Sorted Lists

Problem: Merge two sorted linked lists into one sorted list. Approach: Dummy head, compare current nodes from both lists, attach smaller one to result, advance that pointer. O(n + m).

17. LRU Cache

Problem: Design a cache with O(1) get and put, evicting least recently used. Approach: Hash map (key → node) + doubly linked list (order of use). On access, move node to front. On eviction, remove from tail. O(1) for both operations.

Trees (5 Questions)

18. Maximum Depth of Binary Tree

Problem: Find the maximum depth (height) of a binary tree. Approach: Recursion: return 1 + max(depth(left), depth(right)). Base case: null node returns 0. O(n).

19. Validate Binary Search Tree

Problem: Check if a tree is a valid BST. Approach: Inorder traversal should produce sorted sequence. Or recursive: each node must be within (min, max) bounds. Pass bounds down: left child gets (min, parent.val), right gets (parent.val, max). O(n).

20. Lowest Common Ancestor of BST

Problem: Find the LCA of two nodes in a BST. Approach: Exploit BST property. If both nodes are smaller than current, go left. If both larger, go right. Otherwise, current node is the LCA. O(h).

21. Binary Tree Level Order Traversal

Problem: Return nodes grouped by level. Approach: BFS with queue. Process one level at a time: record queue size, pop that many nodes, add their children for next level. O(n).

22. Serialize and Deserialize Binary Tree

Problem: Convert tree to string and back. Approach: Preorder traversal with null markers. Serialize: "1,2,null,null,3,4,null,null,5,null,null". Deserialize: recursive — consume one value, build node, recurse left then right. O(n).

Graphs (4 Questions)

23. Number of Islands

Problem: Count connected components of '1's in a 2D grid. Approach: BFS/DFS from each unvisited '1'. Mark visited cells. Each new BFS/DFS starts = one new island. O(m × n).

24. Course Schedule (Cycle Detection)

Problem: Given prerequisites, determine if all courses can be finished. Approach: Topological sort with Kahn's algorithm (BFS with in-degree) or DFS cycle detection. If all nodes are processed, no cycle exists. O(V + E).

25. Clone Graph

Problem: Deep copy a graph. Approach: BFS/DFS with hash map (original → clone). When visiting a neighbor, check if clone exists; if not, create it. O(V + E).

26. Word Ladder

Problem: Transform one word to another, changing one letter at a time, each intermediate word must be in dictionary. Approach: BFS where each word is a node, edges connect words differing by one letter. For efficiency, generate all one-letter variations rather than checking all dictionary pairs. O(n × k²) where k is word length.

Dynamic Programming (5 Questions)

27. Climbing Stairs

Problem: How many ways to reach the top with 1 or 2 steps at a time? Approach: DP: dp[i] = dp[i-1] + dp[i-2]. Same as Fibonacci. O(n) time, O(1) space with just two variables.

28. Coin Change

Problem: Minimum coins to make a target amount. Approach: DP: dp[amount] = min coins needed. For each amount from 1 to target, try all coin denominations: dp[i] = min(dp[i], dp[i-coin] + 1). O(amount × coins).

29. Longest Increasing Subsequence

Problem: Find the length of the longest strictly increasing subsequence. Approach: O(n²) DP: dp[i] = LIS ending at index i. Or O(n log n) with patience sorting: maintain a "tails" array and binary search for insertion point.

30. 0/1 Knapsack

Problem: Maximize value with weight capacity constraint. Approach: 2D DP: dp[i][w] = max value using first i items with capacity w. Transition: include current item (dp[i-1][w-weight] + value) or skip it (dp[i-1][w]). Space-optimized to 1D by iterating weights backwards.

31. Word Break

Problem: Can a string be segmented into dictionary words? Approach: DP: dp[i] = true if s[0..i-1] can be segmented. For each i, check all j < i: if dp[j] is true and s[j..i-1] is in dictionary, then dp[i] = true. O(n² × k).

Study Order Recommendation

1. Week 1-2: Arrays & Hashing (problems 1-8) + Strings (9-13)
2. Week 3: Linked Lists (14-17) + Trees (18-22)
3. Week 4: Graphs (23-26) + DP (27-31)
4. Week 5+: Revisit all problems from memory, add variations