InterviewSkill
Data structures and algorithms for coding rounds in software, data, ML, and AI interviews.
Use a hash map to store values you have seen and check whether the complement exists.
For each number x, compute target - x. If that complement is already in the map, you found the pair. This reduces the brute-force O(n^2) approach to O(n) time with O(n) extra space.
Use sliding window for contiguous subarray or substring problems where you can update the answer as the window moves.
Instead of recomputing each range from scratch, maintain state such as sum, counts, or distinct characters while expanding and shrinking the window. This often turns O(n^2) work into O(n).
Two pointers use two indexes that move through a sequence to avoid nested loops.
It is common for sorted arrays, palindrome checks, merging, partitioning, and pair-sum problems. The key is knowing how pointer movement changes the search space.
Use a stack: push opening brackets and pop when a matching closing bracket appears.
The stack stores the most recent unmatched opening bracket. If a closing bracket does not match the top of the stack, the string is invalid. At the end, the stack must be empty.
Use binary search when the search space is sorted or has a monotonic true/false condition.
Binary search repeatedly discards half the search space. It works not only on arrays but also on answer ranges, such as finding the minimum capacity that satisfies a condition.
Iterate through the list and reverse each node's next pointer using previous, current, and next references.
At each step, save current.next, point current.next to previous, then move previous and current forward. The final previous pointer becomes the new head.
BFS explores level by level using a queue; DFS explores deeply along a path using recursion or a stack.
BFS is useful for shortest path in unweighted graphs and level-order traversal. DFS is useful for connectivity, cycle detection, backtracking, and exploring components.
They are DFS traversal orders: preorder visits node-left-right, inorder visits left-node-right, and postorder visits left-right-node.
Inorder is especially useful for binary search trees because it returns values in sorted order. Preorder can serialize tree structure, and postorder is useful when children must be processed before the parent.
Look for overlapping subproblems and an optimal answer that can be built from smaller answers.
DP is useful when recursion repeats the same work. Define the state, recurrence, base cases, and fill order. Interviews often start with a brute-force recursion before adding memoization.
Describe how runtime and memory grow as input size increases, usually using Big O notation.
Focus on dominant terms and ignore constants. A clear answer explains loops, nested loops, recursion depth, extra data structures, and tradeoffs between time and memory.