Data Structures & Algorithms interview questions

How to approach thisUse the two-pointer technique: start with one pointer at the beginning and one at the end. If the sum is too small, advance the left pointer. If too large, retreat the right pointer. This runs in O(n) time and O(1) space, which is better than a hash map approach for sorted input.

How to approach thisUse Floyd's tortoise and hare algorithm: one pointer moves one step at a time, the other moves two steps. If they meet, there is a cycle. To find the cycle start, reset one pointer to the head and advance both one step at a time; they meet at the cycle entry. O(n) time, O(1) space.

How to approach thisCombine a hash map (for O(1) key lookup) with a doubly linked list (for O(1) insertion and removal at both ends). On get: move the node to the head. On put: insert at head, evict from tail if over capacity. Each hash map entry points to the corresponding list node.

How to approach thisAverage case: O(1) for get, put, and delete. Worst case: O(n) if all keys hash to the same bucket. Collisions are handled by chaining (linked list per bucket) or open addressing (probing for the next empty slot). Good hash functions and load factor management keep performance near O(1).

How to approach thisThree approaches: sort and index (O(n log n)), use a min-heap of size k (O(n log k)), or use Quickselect (O(n) average, O(n^2) worst). Quickselect partitions the array like QuickSort but only recurses into the relevant half. For interviews, know all three and discuss trade-offs.

How to approach thisStack (LIFO): undo operations, expression evaluation, DFS traversal, parentheses matching. Queue (FIFO): BFS traversal, task scheduling, message processing, breadth-first printing. A deque (double-ended queue) supports both patterns. Knowing which data structure matches the problem is half the interview answer.

How to approach thisUse preorder traversal, encoding null children as a sentinel value (e.g., '#'). Serialize: visit root, serialize left, serialize right, recording values and nulls. Deserialize: read values sequentially, building nodes recursively, consuming a null marker when a subtree is empty. BFS (level-order) also works well.

How to approach thisDP applies when a problem has overlapping subproblems and optimal substructure. If you find yourself solving the same subproblem multiple times in a recursive solution, DP can help. Start with a recursive solution, add memoization (top-down), or identify the recurrence relation and build a table (bottom-up). Classic examples: Fibonacci, coin change, longest common subsequence.

How to approach thisA balanced tree has subtrees whose heights differ by at most 1 at every node. Use a recursive approach that returns the height at each node. If any subtree is unbalanced, short-circuit by returning -1. This runs in O(n) time with a single pass, compared to O(n^2) if you compute heights separately at each level.

How to approach thisA hash map has O(1) average lookup for exact keys but cannot do prefix searches. A trie (prefix tree) supports efficient prefix queries (autocomplete), lexicographic ordering, and shared prefix storage. Tries use more memory due to pointers. Use a hash map for exact lookup, a trie when you need prefix matching or sorted iteration.

How to approach thisBFS explores level by level (uses a queue), finding the shortest path in unweighted graphs. DFS explores as deep as possible first (uses a stack/recursion). Use BFS for shortest path, level-order traversal, and when the solution is close to the root. Use DFS for topological sort, cycle detection, and when you need to explore all paths.

How to approach thisUse the sliding window technique: maintain a window [left, right] and a set of characters in the window. Expand right, adding characters. When a duplicate is found, shrink left until the duplicate is removed. Track the maximum window size. O(n) time, O(min(n, alphabet_size)) space.