Q: How many distinct ways can you climb n stairs if you can take 1 or 2 steps at a time?

To reach stair n you must have come from stair n-1 (one step) or stair n-2 (two steps). So ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence. Starting from ways(1)=1, ways(2)=2, you iterate forward in O(n) time and O(1) space.

Q: You are a robber. Given an array of house values, find the maximum money you can rob without robbing two adjacent houses.

At each house you make one choice: rob it (and skip the previous) or skip it (and carry forward whatever you had). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Since you only look back two steps, two variables replace the full array, giving O(n) time and O(1) space.

Q: Find the contiguous subarray with the largest sum (Kadane's algorithm).

Scan left to right, carrying a running sum. At each element, decide: extend the existing subarray (add to the running sum) or start fresh (take just the current element). Whichever is larger becomes the new running sum. Track the global maximum throughout. One pass, O(n) time, O(1) space.

Q: Find the kth largest element in an unsorted array without fully sorting it.

Maintain a min-heap of size k. Stream every element through: push it onto the heap, then if the heap exceeds size k, pop the minimum. After processing all elements, the heap's minimum is the kth largest — it is the smallest among the top-k values seen so far.

Q: Detect whether a linked list has a cycle using Floyd's fast/slow pointer algorithm.

Two pointers start at the head — slow moves one step, fast moves two. If there is a cycle, fast laps slow and they meet inside the cycle. If fast reaches None, there is no cycle. This runs in O(n) time with O(1) space, no hash set needed.

Q: Find the maximum depth (height) of a binary tree.

The maximum depth is 1 plus the larger of the left and right subtree depths. A single recursive call naturally expresses this: at every node, ask both children for their depth and take the max. The base case is None, which returns 0.

Q: Merge two sorted linked lists into one sorted list.

Use a dummy head node to avoid special-casing the result's first element. Walk both lists with two pointers, always appending the smaller current node to the result. When one list is exhausted, append the remainder of the other. O(n + m) time, O(1) space.

Q: Design a stack that returns its minimum element in O(1).

Maintain a second 'min stack' in parallel: every push also records the current minimum at that moment. When you pop the main stack, pop the min stack too. The top of the min stack is always the current minimum — no scanning needed.

Q: How do you remove duplicates from a sorted array in place?

Use a slow pointer that tracks where the next unique value should be written, and a fast pointer that scans forward. Whenever the fast pointer finds a value different from the current unique one, copy it to the slow pointer's position and advance both. One pass, O(1) extra space.

Question 1

Implement binary search correctly — and explain the off-by-one traps.

Accepted Answer

Binary search halves the search space each iteration to find a target in O(log n). The tricky part is not the idea but the boundary conditions: closed vs. half-open intervals, how to update lo/hi, and when to use lo < hi vs. lo <= hi. One clean template eliminates all the classic bugs.

Question 2

How many distinct ways can you climb n stairs if you can take 1 or 2 steps at a time?

Accepted Answer

To reach stair n you must have come from stair n-1 (one step) or stair n-2 (two steps). So ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence. Starting from ways(1)=1, ways(2)=2, you iterate forward in O(n) time and O(1) space.

Question 3

You are a robber. Given an array of house values, find the maximum money you can rob without robbing two adjacent houses.

Accepted Answer

At each house you make one choice: rob it (and skip the previous) or skip it (and carry forward whatever you had). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Since you only look back two steps, two variables replace the full array, giving O(n) time and O(1) space.

Question 4

Find the contiguous subarray with the largest sum (Kadane's algorithm).

Accepted Answer

Scan left to right, carrying a running sum. At each element, decide: extend the existing subarray (add to the running sum) or start fresh (take just the current element). Whichever is larger becomes the new running sum. Track the global maximum throughout. One pass, O(n) time, O(1) space.

Question 5

Find the kth largest element in an unsorted array without fully sorting it.

Accepted Answer

Maintain a min-heap of size k. Stream every element through: push it onto the heap, then if the heap exceeds size k, pop the minimum. After processing all elements, the heap's minimum is the kth largest — it is the smallest among the top-k values seen so far.

Question 6

Detect whether a linked list has a cycle using Floyd's fast/slow pointer algorithm.

Accepted Answer

Two pointers start at the head — slow moves one step, fast moves two. If there is a cycle, fast laps slow and they meet inside the cycle. If fast reaches None, there is no cycle. This runs in O(n) time with O(1) space, no hash set needed.

Question 7

Find the maximum depth (height) of a binary tree.

Accepted Answer

The maximum depth is 1 plus the larger of the left and right subtree depths. A single recursive call naturally expresses this: at every node, ask both children for their depth and take the max. The base case is None, which returns 0.

Question 8

Merge two sorted linked lists into one sorted list.

Accepted Answer

Use a dummy head node to avoid special-casing the result's first element. Walk both lists with two pointers, always appending the smaller current node to the result. When one list is exhausted, append the remainder of the other. O(n + m) time, O(1) space.

Question 9

Design a stack that returns its minimum element in O(1).

Accepted Answer

Maintain a second 'min stack' in parallel: every push also records the current minimum at that moment. When you pop the main stack, pop the min stack too. The top of the min stack is always the current minimum — no scanning needed.

Question 10

How do you remove duplicates from a sorted array in place?

Accepted Answer

Use a slow pointer that tracks where the next unique value should be written, and a fast pointer that scans forward. Whenever the fast pointer finds a value different from the current unique one, copy it to the slow pointer's position and advance both. One pass, O(1) extra space.

Question 11

Reverse a singly linked list, iteratively and recursively.

Accepted Answer

Iteratively: walk the list with three pointers — prev, current, and next — rewiring each node's pointer as you go. Recursively: reverse the rest of the list, then attach the current head to the new tail. Both are O(n) time, O(1) and O(n) space respectively.

Question 12

Find the maximum average of any contiguous subarray of size k.

Accepted Answer

Compute the sum of the first k elements, then slide the window one step at a time — add the incoming element and subtract the outgoing element. Track the best sum seen and divide by k at the end. One pass, O(n) time, O(1) extra space.

Question 13

Given a sorted array, find two numbers that add up to a target — how do you do it in O(n) without extra space?

Accepted Answer

Because the array is sorted, you can place one pointer at the start and one at the end, then squeeze them inward. If the sum is too big, move the right pointer left; if too small, move the left pointer right. This converges in one pass with O(1) extra space.

Question 14

Check whether a string of brackets is valid.

Accepted Answer

Use a stack: push every opening bracket and pop when you see a closing bracket, checking that it matches the top. If the stack is empty at the end, the string is valid. This is the canonical stack problem — O(n) time, O(n) space.

Question 15

Return the level-order (BFS) traversal of a binary tree as a list of lists, one per level.

Accepted Answer

Use a queue (deque) to process nodes layer by layer. At each step, snapshot the current queue length to know exactly how many nodes belong to the current level, drain those, then enqueue their children. The result is a list of lists without any depth-tracking variable.

Question 16

Given a list of coin denominations and a target amount, find the fewest coins needed to make that amount (coin change).

Accepted Answer

Define dp[i] as the minimum coins to make amount i. For each amount from 1 to target, try every coin: if the coin value is at most i, dp[i] = min(dp[i], 1 + dp[i - coin]). Base case dp[0] = 0. Initialise all other entries to infinity so valid solutions propagate cleanly.

Question 17

Find all unique combinations of candidates that sum to a target, where each candidate may be used an unlimited number of times.

Accepted Answer

Use backtracking with a running total. At each step, try adding a candidate to the current path. If the total equals the target, record the path. If it exceeds the target, prune. Passing the same start index (not i+1) back into the recursion allows unlimited reuse of the same element.

Question 18

Given an array of heights, find two lines that together with the x-axis form a container that holds the most water.

Accepted Answer

Place one pointer at the far left and one at the far right, track the best area seen so far, then always move the pointer sitting at the shorter height inward. Moving the taller side inward could only reduce width without any chance of gaining height, so it's never optimal — this greedy squeeze finds the answer in O(n).

Question 19

For each day, how many days until a warmer temperature?

Accepted Answer

Use a monotonic decreasing stack of indices. When today's temperature beats the temperature at the stack's top index, that index has found its answer. Pop and record the gap. Days still on the stack at the end waited forever — their answer is 0.

Question 20

Group a list of words into anagrams.

Accepted Answer

Sort each word's characters to get a canonical key, then bucket words by that key using a hash map. This turns an O(n²) brute-force comparison into a clean O(n · k log k) single pass, where k is the max word length.

Question 21

Find the minimum eating speed for Koko to finish all bananas within h hours.

Accepted Answer

Binary search on the answer space (eating speed 1 through max pile size) rather than on the input array. For each candidate speed, greedily compute hours needed in O(n). The feasibility check is monotone — if speed k works, any speed above k also works — so binary search finds the minimum valid speed in O(n log m) time.

Question 22

Find the length of the longest common subsequence (LCS) of two strings.

Accepted Answer

Build a 2-D DP table where dp[i][j] is the LCS length of the first i characters of text1 and first j characters of text2. If the characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). The answer is dp[m][n].

Question 23

Find the length of the longest substring without repeating characters.

Accepted Answer

Use a variable-size sliding window with a hash map that records the most recent index of each character. When the right pointer hits a character already in the window, jump the left pointer to one past that character's last position — skipping over the repeat in one move rather than crawling one step at a time.

Question 24

Given a list of intervals, merge all overlapping intervals and return the result.

Accepted Answer

Sort intervals by start time. Then walk through them once: if the current interval's start is at or before the end of the last merged interval, merge by extending the end. Otherwise, the current interval is disjoint — push it onto the result. Sorting costs O(n log n); the merge pass is O(n).

Question 25

Find the minimum length of a contiguous subarray whose sum is at least a given target.

Accepted Answer

Use a variable sliding window: expand the right boundary to grow the sum, and once the sum meets the target, shrink from the left as much as possible while still staying at or above the target. Record the window length each time it qualifies. One O(n) pass.

Question 26

Given a 2-D grid of '1's (land) and '0's (water), count the number of islands (connected components of land).

Accepted Answer

Scan every cell. When you find a '1' that hasn't been visited, increment the island count and immediately flood-fill all connected land cells (DFS or BFS) so they won't be counted again. The total number of floods equals the number of islands.

Question 27

Generate all permutations of a list of distinct integers using backtracking.

Accepted Answer

At each recursion level, swap one of the remaining (unused) elements into the current position, recurse to fill the rest, then swap back to restore the state. Alternatively, track a 'used' set and build the permutation in a separate path list. The result is all n! orderings.

Question 28

Count the number of contiguous subarrays whose sum equals k.

Accepted Answer

Build prefix sums on the fly and store their frequencies in a hash map. For each new prefix sum P, a subarray ending at the current index has sum k if some earlier prefix sum equalled P - k. Look that up in the map in O(1). One pass, O(n) time and space.

Question 29

Return an array where each element is the product of all other elements, without using division.

Accepted Answer

Make two passes: a left pass where each position accumulates the product of everything to its left, then a right pass (using a rolling variable) that multiplies in everything to its right. The two passes together give the complete product-of-all-others in O(n) time and O(1) extra space (excluding output).

Question 30

Search for a target in a rotated sorted array in O(log n).

Accepted Answer

Even after rotation, one of the two halves around mid is always fully sorted. Check which half is sorted, then decide whether the target falls inside it. If yes, narrow to that half; if no, search the other. This keeps binary search's O(log n) guarantee.

Question 31

Generate all subsets of a set — the power set — using backtracking.

Accepted Answer

At each step of a recursive walk through the input, you make a binary choice: include the current element or skip it. Recording the current path at every node of the recursion tree (not just the leaves) collects all 2^n subsets. A `start` index prevents duplicates by ensuring elements are only considered left-to-right.

Question 32

Find all unique triplets in an array that sum to zero (3Sum).

Accepted Answer

Sort the array, then fix one element at a time and run a two-pointer search on the remaining right portion to find pairs that sum to its negation. Careful duplicate-skipping at both the outer loop and the inner pointers is what makes the result unique. Overall complexity is O(n²).

Question 33

Return the k most frequent elements in an array.

Accepted Answer

Count frequencies with a hash map, then use a min-heap of size k to track the top k elements in O(n log k) time. An alternative bucket-sort approach achieves O(n) by indexing buckets by frequency.