21. Remove duplicates from a sorted array
You remove duplicates in place from the sorted array below using a slow and fast pointer, returning the count k of unique values. What is k?
[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
- A.4
- B.6
- C.5
- D.10
Show answer
Answer: C. 5
The unique values are 0, 1, 2, 3 and 4, so k = 5 and the first five slots become [0, 1, 2, 3, 4]. The slow pointer marks where the next unique value goes, and the fast pointer scans, copying only when it sees a new value.
22. Subarrays with product under k
How many contiguous subarrays of [10, 5, 2, 6] have a product strictly less than 100?
- A.8
- B.7
- C.10
- D.6
Show answer
Answer: A. 8
With a sliding window, each new right end adds (right - left + 1) subarrays ending there: 1 for [10], 2 for [5] and [10, 5], 2 for [2] and [5, 2] after [10, 5, 2] = 100 forces left forward, and 3 for [6], [2, 6], [5, 2, 6]. Total 1 + 2 + 2 + 3 = 8.
23. Intersect two schedules
Two sorted lists of free slots are A = [[0, 2], [5, 10]] and B = [[1, 5], [8, 12]]. What is their intersection?
- A.[[1, 2], [8, 10]]
- B.[[1, 2], [5, 5], [8, 10]]
- C.[[0, 12]]
- D.[[1, 5], [8, 10]]
Show answer
Answer: B. [[1, 2], [5, 5], [8, 10]]
Each overlap is [max(starts), min(ends)] when that is not empty. [0, 2] with [1, 5] gives [1, 2]; [5, 10] with [1, 5] gives [5, 5]; [5, 10] with [8, 12] gives [8, 10]. Advance whichever interval ends first.
24. Minimum of a rotated sorted array
To find the minimum of [4, 5, 6, 7, 0, 1, 2] in O(log n), which comparison decides the side?
- A.If a[mid] > a[lo], the minimum is left of mid
- B.If a[mid] is even, go left
- C.If a[mid] > a[hi], the minimum is right of mid
- D.If a[mid] < target, go right
Show answer
Answer: C. If a[mid] > a[hi], the minimum is right of mid
If a[mid] > a[hi], the drop from large to small happens after mid, so set lo = mid + 1. Otherwise the minimum is at mid or left of it, so set hi = mid. Here the search ends on 0.
25. Largest sum of a contiguous block
Daily profit changes are [-2, 1, -3, 4, -1, 2, 1, -5, 4]. What is the largest sum of any contiguous block of days?
- A.4
- B.5
- C.6
- D.7
Show answer
Answer: C. 6
Kadane’s algorithm keeps the best sum ending at each day: either extend the previous block or start fresh. The best block is [4, -1, 2, 1], which sums to 6. It runs in one O(n) pass with O(1) memory.
26. Stock trading with a cooldown day
You may trade many times, but after selling you must wait one day before buying. For prices [1, 2, 3, 0, 2], what is the largest profit?
- A.3
- B.2
- C.4
- D.5
Show answer
Answer: A. 3
Buy at 1, sell at 2, rest on the day priced 3, buy at 0, sell at 2: 1 + 2 = 3. The DP keeps three states per day: holding, just sold, and resting. Ignoring the cooldown would allow 2 + 2 = 4, which breaks the rule.
27. Direction of the capacity loop
In the 1D 0/1 knapsack, dp[w] = max(dp[w], dp[w - wt] + val). Why must w go from W down to wt?
- A.Going up would let an item be reused
- B.Going up gives an index out of range
- C.Going down is faster for the CPU cache
- D.Going up skips the base case
Show answer
Answer: A. Going up would let an item be reused
When w goes up, dp[w - wt] may already include the current item from earlier in the same loop, so the item gets reused. Going down means dp[w - wt] still holds the value from before this item. Looping up is exactly the unbounded knapsack.
28. Finding any key in a binary heap
A min-heap of 1 million delivery tasks is keyed by deadline. How long does it take to check whether a specific deadline exists in it?
- A.O(log n), by following the heap path
- B.O(1), because the heap is an array
- C.O(n), because a heap orders only parent and child
- D.O(log^2 n), using binary search on each level
Show answer
Answer: C. O(n), because a heap orders only parent and child
A heap only guarantees that each parent is not larger than its children; siblings and cousins are in no useful order. So finding an arbitrary key means scanning the array. Heaps are fast for the minimum (O(1)) and for push and pop (O(log n)), not for search.
29. When a graph cannot be two-coloured
You try to split players into two teams so that rivals are always on different teams, using BFS 2-colouring. When must it fail?
- A.When the graph has any cycle at all
- B.When some player has more than two rivals
- C.When the graph is disconnected
- D.When the rivalry graph has a cycle of odd length
Show answer
Answer: D. When the rivalry graph has a cycle of odd length
Colours must alternate along every edge, so walking around an odd cycle forces a node to have both colours. A graph is bipartite exactly when it has no odd cycles. Disconnected graphs are fine if you start a new BFS in each component.
30. A JavaScript BFS that gets slow
This BFS on a graph with 10^6 nodes is far slower than expected. What is the main cause?
const queue = [start]
while (queue.length) {
const u = queue.shift()
for (const v of adj[u]) if (!seen[v]) { seen[v] = true; queue.push(v) }
}- A.push() is O(n) on large arrays
- B.The seen array should be a Set to be correct
- C.for...of cannot iterate arrays efficiently
- D.shift() can be O(n), so the loop can become O(V^2)
Show answer
Answer: D. shift() can be O(n), so the loop can become O(V^2)
Removing the first element of a JavaScript array can move every remaining element, so with a large queue each shift() is costly. Keep a head index and read queue[head++] instead, or use a ring-buffer queue. That keeps BFS at O(V + E).
31. Order of steps in Two Sum
In one-pass Two Sum, why do you look up target - x before adding x to the map?
- A.So x is never paired with itself
- B.Because lookups are faster than inserts
- C.So the map stays sorted
- D.To use less memory
Show answer
Answer: A. So x is never paired with itself
For target 6 and nums [3, 2, 4], inserting 3 first and then looking up 3 would wrongly pair index 0 with itself. Checking first means the map only holds earlier indexes, while [3, 3] still works because the first 3 is already there when the second arrives.
32. Longest subarray with equal 0s and 1s
Treating 0 as -1, you track the first index of each running sum. What is the longest subarray of [0, 1, 0] with equal 0s and 1s?
- A.3
- B.1
- C.0
- D.2
Show answer
Answer: D. 2
Running sums with 0 as -1 are -1, 0, -1. The sum -1 first appears at index 0 and again at index 2, giving length 2; the sum 0 is seeded at index -1 and appears at index 1, also length 2. Storing only the first index of each sum gives the longest span.
33. Bulls and Cows hint
The secret is "1807" and the guess is "7810". Bulls are right digit in the right place; cows are right digit in the wrong place. What is the hint?
- A.2A2B
- B.1A2B
- C.1A3B
- D.0A4B
Show answer
Answer: C. 1A3B
Only 8 is in the same position, so 1 bull. The remaining secret digits 1, 0, 7 and guess digits 7, 1, 0 match as a multiset, so 3 cows. Count unmatched digits from each side and add the minimum per digit.
34. Inverting a map with repeated values
You invert { Asha: 'Dubai', Ravi: 'Pune', Meena: 'Dubai' } into city → name with a simple loop. What is the result?
- A.{ Dubai: 'Asha', Pune: 'Ravi' }
- B.{ Dubai: ['Asha', 'Meena'], Pune: 'Ravi' }
- C.{ Dubai: 'Meena', Pune: 'Ravi' }
- D.It throws a duplicate key error
Show answer
Answer: C. { Dubai: 'Meena', Pune: 'Ravi' }
Both Asha and Meena map to Dubai, so the later write overwrites the earlier one and Asha is lost silently. When values can repeat, invert into city → list of names instead.
35. Finding the final city of a trip
Routes are [["London", "New York"], ["New York", "Lima"], ["Lima", "Sao Paulo"]]. Which city has no outgoing route?
- A.London
- B.Sao Paulo
- C.Lima
- D.New York
Show answer
Answer: B. Sao Paulo
Put every starting city in a Set, then return the destination not in that Set. London, New York and Lima all have an outgoing route, so the trip ends in Sao Paulo, in O(n).
36. Why quick sort uses a random pivot
An API sorts user lists with a quick sort that always picks the first element as the pivot. Requests with already sorted lists are very slow. What is the standard fix?
- A.Switch the pivot to always be the second element
- B.Sort the list twice to warm up the CPU cache
- C.Reverse the list before sorting it
- D.Choose the pivot at random or by median-of-three
Show answer
Answer: D. Choose the pivot at random or by median-of-three
A fixed first or last pivot gives the worst split on sorted or reverse-sorted input. A random pivot, or the median of first, middle and last, makes bad splits very unlikely, giving expected O(n log n). Reversing just moves the problem to another input pattern.
37. Solving T(n) = 4T(n/2) + n
Using the master theorem, what does T(n) = 4T(n/2) + O(n) solve to?
- A.O(n log n)
- B.O(n^2)
- C.O(n^2 log n)
- D.O(n)
Show answer
Answer: B. O(n^2)
Here a = 4 and b = 2, so n^(log2 4) = n^2. That grows faster than the O(n) combine work, so the leaves dominate and the result is O(n^2). Splitting into four half-size problems doubles the work at each level.
38. Running time of quickselect
Quickselect finds the k-th smallest value by partitioning and recursing into only one side. What are its average and worst-case times?
- A.O(n) average, O(n^2) worst
- B.O(n log n) average, O(n log n) worst
- C.O(log n) average, O(n) worst
- D.O(n) average, O(n) worst
Show answer
Answer: A. O(n) average, O(n^2) worst
With random pivots, the sizes shrink geometrically: n + n/2 + n/4 + ... is about 2n, so the average is O(n). Consistently bad pivots shrink the size by one each time, which gives O(n^2).
39. Stock span problem
The stock span on a day is the number of days in a row, ending today, with price at or below today's. For prices [100, 80, 60, 70, 60, 75, 85], what is the span on the day the price is 75?
- A.2
- B.5
- C.3
- D.4
Show answer
Answer: D. 4
Going back from 75: 60, 70 and 60 are all at or below 75, but 80 is higher, so the span covers 4 days including today. A stack holding (price, span) pairs merges spans as it pops, giving O(n) overall.
40. Merging two sorted linked lists
You merge two sorted linked lists of sizes m and n by relinking nodes. What are the time and extra space?
- A.O(m x n) time, O(1) extra space
- B.O(m + n) time, O(m + n) extra space
- C.O(m + n) time, O(1) extra space
- D.O((m + n) log(m + n)) time, O(1) space
Show answer
Answer: C. O(m + n) time, O(1) extra space
Each step compares the two current heads and links the smaller one onto the result, so each node is handled once. No new nodes are created, so the extra space is just a few pointers when done iteratively.
