Algorithms

1.A file has 2 million log lines. You need the 10 lines with the largest byte counts, and you may read the file once. What do you keep?

2.User ids arrive once each on a stream you cannot rewind. You must say, as soon as it happens, whether the id you just read already appeared. What do you store?

3.Forty million account ids sit in a sorted array in memory. You look up one id. Why is a scan the wrong first choice?

4.You need two appointment lengths that add to exactly 60, and the array is not sorted. You may use extra memory. What avoids sorting?

5.The same pair-sum problem is already sorted, and you must return the two indexes. Why do two pointers from the ends work?

6.For every window of 8 consecutive latencies you need the maximum. Rescanning each window is too slow at this volume. What stays in the deque?

7.A string mixes (), [], and {}. A single counter of open minus close is proposed. What does the counter miss?

8.The brackets are only parentheses, never brackets or braces. A reviewer still demands a stack. What is a sufficient check?

9.A maze has open cells and walls. Each step costs the same. You need the fewest steps from the entrance to the exit. Why is depth-first search the wrong search?

10.Edges cost either 1 or 2. Plain breadth-first search treats every edge as one step. What breaks?

11.One road in a map has a negative toll, meaning taking it reduces the total. Someone runs Dijkstra. What assumption did they use that this map violates?

12.Courses point at the courses that must come first. You need to know whether a full order exists. Why is union-find the wrong tool?

13.You only need to know whether two servers are in the same undirected cluster after a series of cables are plugged in. Why is union-find a fit?

14.A function checks a binary tree by comparing each node only with its parent. It accepts a tree where the left child of the right child is smaller than the root. What rule was skipped?

15.You walk a binary search tree in order and the values are 4, 9, 7. What does that walk prove?

16.You need the 6th smallest key in a binary search tree of a million nodes, and you may stop early. Why sort a copied array?

17.You are merging 40 sorted lists of packet timestamps. A reviewer concatenates them and sorts. What do you keep in a heap instead?

18.Latencies arrive one by one. After each arrival you must report the median. Why are two heaps enough?

19.An LRU cache of capacity 100 must get and put in constant time on average. A reviewer stores timestamps and scans for the oldest. What is missing?

20.You have a dictionary and many queries of the form 'does any word start with this prefix?' A hash set of the full words answers exact lookup. What does it not answer cheaply?

21.Ages of a million people are integers from 0 through 120. A comparison sort is proposed. What bound are they ignoring?

22.You must sort a million arbitrary strings from user bios. Why is counting sort no longer the tool?

23.You sort players by score descending, and players with the same score must keep the order of their names from an earlier sort. An unstable sort by score is used. What can change?

24.A quicksort always pivots on the first element. The input arrives already sorted. What running time should you expect?

25.Mergesort of n customer records uses a second array of n records. An interviewer asks what you bought with that memory.

26.Binary search computes the middle as (low + high) / 2 on 32-bit indexes. low and high are both above two billion. What can go wrong?

27.Your binary search uses inclusive bounds and sets low = mid when the target is greater than the middle value. On which input can it loop forever?

28.A sorted array was rotated, for example 5, 6, 1, 2, 4. You look at the middle. How do you know which half still has ordinary sorted order?

29.The rotated array may contain duplicates, such as 2, 2, 2, 3, 2. The middle equals both ends. Why can you lose the logarithmic bound?

30.3sum asks for unique triplets that add to zero. After sorting, two pointers find a triplet. Why skip the next equal value?

31.Two lines from the ends of a height array form a container. You move the pointer at the shorter line inward. Why not move the taller one?

32.Next-greater temperatures are solved with a stack of indexes. The stack's temperatures increase as you look from the top down toward the bottom. Why pop the top when today is warmer?

33.Largest rectangle in a histogram is coded as 'for each bar, scan left and right until a shorter bar.' On a histogram of a million bars that are non-decreasing, what is the cost?

34.You need the shortest subarray whose sum is at least 20. All numbers are positive. Why may the left end only move right?

35.The numbers may be negative, and you still want a shortest subarray with sum at least 20. Why does the same two-pointer window fail?

36.Kadane's scan keeps the best suffix ending at each index. Every value in the array is negative. A version that resets to zero when the running sum drops below zero returns 0. What should it return?

37.House values along a street are 5, 1, 1, 5. You cannot rob two neighboring houses. Taking every other house from the first yields 6. What does that stride miss?

38.Coin denominations are 1, 3, and 4. The amount is 6. A greedy cashier takes the largest coin that fits and produces 4, then 1, then 1. What is the objection?

39.A 0/1 knapsack lets you take each package at most once. An unbounded version lets you take a package any number of times. You reuse the unbounded loop order on the 0/1 data. What can the table claim?

40.Edit distance between 'cat' and 'cut' is 1, a replacement. Someone charges 2 because they delete t and insert u as two operations, after already matching the shared letters wrong. What should a cell represent?

41.A recursive Fibonacci without a cache recomputes fib(5) many times on the way to fib(10). What is the cache storing?

42.An interviewer says the language will optimize your recursive Fibonacci into a loop because the call is in tail position. Why do you not rely on that in the interview?

43.Appending one character at a time to a string builds 'ab', then 'abc', then 'abcd', copying the whole prefix each time. For n characters, what did you pay?

44.A dynamic array doubles when it fills. One append is sometimes expensive, because it copies. Why do you still call append amortized constant time?

45.You insert at the head of a linked list and at index 0 of an array, a million times. Which structure wins, and why?

46.You need the element at index 500000 in a structure that is either an array or a linked list. Why does the array win?

47.A hash map's average lookup is constant, and a colleague says the worst case is also constant. When is the worst case linear?

48.You use a list as a key in a hash map, then append to that list. Lookups for the old contents fail. What changed?

49.A city map has 10,000 intersections and 25,000 roads. An adjacency matrix is proposed. What are you paying for that you will mostly not use?

50.Breadth-first search marks a cell visited when it is dequeued, not when it is enqueued. A neighbor gets pushed twice before anyone marks it. What goes wrong?

51.Depth-first search is written as recursion on a graph that is a single path of a million nodes. The result is a crash, not a wrong answer. What ran out?

52.A course graph has two valid orders, A then B then C, and A then C then B. Topological sort returns one of them. A test demands both. What should you say?

53.You add an edge that creates a directed cycle. The indegree loop finishes with a node still at indegree 1, and the output list is short. What do you report?

54.Dijkstra pushes a new heap entry every time you relax a node, instead of decreasing the old key. The heap holds several entries for one node. When is the first time you pop a node the right time to freeze it?

55.You compute a minimum spanning tree and then read the path it gives between two cities as the shortest path. The tree path is longer than another route that uses a discarded edge. How can that happen?

56.Bellman-Ford runs one extra pass after |V|-1 rounds and a distance still improves. What is in the graph?

57.You need the shortest path between every pair of 400 cities. Floyd-Warshall is suggested. Why is that a sane default here, and a bad one for 100,000 cities?

58.Union-find with path compression and union by rank answers whether two sockets are connected. An interviewer then asks for the list of cables between them. Why is that a different question?

59.You color a graph with two colors as you walk. A neighbor already has your color. What did you find?

60.Permutations of four distinct tiles are generated by swapping the current index with each later index, then recursing, then swapping back. Why swap back?

61.Combinations of 3 toppings out of 8 are generated. A version that permutes all 8 and takes the first 3 emits the same trio several times. What index do you pass down to stop that?

62.The menu has two identical onions. Your combination generator emits onion, onion as two different results because the onions are different objects in the array. The caller wanted unique combinations. What do you skip?

63.N-queens places a queen per row. A version checks only the column. Two queens sit on a diagonal and the function accepts the board. What else is occupied?

64.Word search on a board marks a cell visited for the whole search, not just for the current path. A later word that needed that cell fails. When do you unmark?

65.Word break asks whether a string can be cut into dictionary words. Pure recursion tries every cut and repeats the same suffix. What do you store?

66.A digit string '10' is decoded with A=1 through Z=26. One reading is 'J' from 10. A bug also counts a decode that uses '0' as a letter. Why is a lone 0 illegal?

67.Unique paths on a grid with one blocked cell. A formula for an empty grid is used unchanged. What does the formula assume that the block breaks?

68.A grid DP only reads the previous row. You keep the entire history of rows. What can you drop?

69.You serialize a binary tree as 1, 2, null, null, 3. A decoder without the nulls sees 1, 2, 3 and cannot tell whether 3 is the right child of 1 or of 2. What are the nulls for?

70.Lowest common ancestor in a binary tree is solved with the binary-search-tree rule 'go left if both targets are smaller.' The tree is not a search tree. Why can that walk miss the ancestor?

71.The diameter of a tree is defined as the longest path between any two nodes. A function returns the height of the root's left plus the height of the root's right. A longer path lives entirely in the left subtree. What did the function forget?

72.Level-order traversal pushes children and then prints the whole queue as one level. Why snapshot the queue size before the inner loop?

73.You clone a directed graph. A node points back at an ancestor. A clone function that does not remember nodes already copied recurses forever. What do you store?

74.Number of islands flips every land cell to water as you visit it. A second island-count later in the program sees an empty ocean. When is the mutation acceptable?

75.Rotting oranges: several rotten oranges spread in one minute to their neighbors. You start breadth-first search from only the first rotten orange in the input. Fresh oranges near a later rotten one take too long. What should the initial queue hold?

76.Cheapest flights within k stops. Dijkstra by price alone pops a cheap route that has already used every allowed stop and then refuses to expand. A pricier route with stops left never gets considered. What state belongs in the heap?

77.You need range sums on an array that never changes after it is built. A segment tree is written first. What simpler table answers the queries?

78.The array now receives point updates between the sum queries. Prefix sums are kept anyway, and each update rewrites the prefix from that index to the end. On a million elements and a million mixed operations, why is that painful?

79.A sparse table answers static range-minimum queries in constant time after an n log n build. Someone uses it on an array that changes. What promise did they drop?

80.Rabin-Karp reports a hash match for a pattern inside a document. You return that index without comparing characters. A different string with the same hash is accepted. What check is missing?

81.Naive string search slides the pattern by one after a mismatch near the end. On a pattern of a thousand a's against a document of a thousand a's plus a b, how much work do the repeated comparisons do?

82.An interviewer asks whether a log line starts with the exact characters 'ERROR '. A colleague reaches for a regular expression. What are you paying for that this question does not need?

83.You detect a cycle in a singly linked list by storing every node you have seen. The interviewer limits you to a few pointers and no extra memory proportional to the list. What two speeds do you use?

84.Reverse a singly linked list in place. A version builds a new list by reading values, which uses a second chain of nodes. The constraint was the original nodes, rewired. What three pointers do you walk with?

85.Two numbers are stored as digits in reverse order in linked lists, so 2 -> 4 means 42. You add them. A bug drops the final carry when both lists end. 5 and 5 become 0 instead of 10. Where does the extra node come from?

86.A list node has a next pointer and a random pointer. You clone next first, then set random by searching the original list for a match each time. On a long list, what is the cost you just accepted?

87.Merge two sorted linked lists by building a new node per value, copying digits. The interviewer asked you to reuse the existing nodes. What do you swing?

88.You must find the middle of a singly linked list once, without a length field. Counting to the end and walking halfway is two passes. How do you do it in one?

89.A palindrome check on a singly linked list copies the values into an array and uses two indexes. Extra memory is forbidden beyond a few pointers. What do you reverse?

90.Sort a linked list with quicksort that indexes the middle as an array would. Why is mergesort the usual choice instead?

91.An in-place constraint means you may use a handful of variables, not a second array of n. A solution allocates a boolean array of n flags and calls itself in place. Is the constraint met?

92.You solve two-sum with a nested loop and say it is correct but quadratic. The interviewer asks for the linear version and you refuse because the nested loop already works. What did you fail to do?

93.A problem asks for any duplicate in an array of n+1 integers, each in 1..n. You sort a copy. They then say the array is read-only and you may use only a few integers of memory. Which idea survives?

94.Binary search is written on a linked list by starting at the head and walking halfway each time. You claim it is logarithmic. How many nodes do you actually visit to reach the middle, then the quarter, and so on?

95.A heap is built by inserting n items one by one, each taking up to log n. Floyd's build-heap sifts from the middle downward. Why is the second one linear?

96.You need the k smallest items from an unordered array, and k is 20 while n is a million. Sorting the million is proposed. What do you stop early?

97.Quickselect is average linear and worst-case quadratic with a naive pivot. The interviewer wants a worst-case linear selection. What pivot idea are they pointing at?

98.Interval merge: meetings [1,3], [2,4], [6,8]. You merge in the order given and produce [1,4] and [6,8], which happens to be right. Then [6,8] comes before [1,3] in the input and your running merge misses the overlap that is not adjacent in that order. What must you do first?

99.Meeting rooms: given intervals, how many rooms do you need? You sort starts and ends separately and walk both. A start before the next end means a room is taken. Why not just merge overlaps and count the merged blocks?

100.You implement a stack with an array and a queue with two stacks. The interviewer asks for the queue's worst-case dequeue if you move elements only when the out-stack is empty. One dequeue can move n items. Why do you still call it amortized constant?

101.A ring buffer of fixed capacity implements a queue. The head and tail indexes meet. How do you tell full from empty?

102.A recursive subset generator prints the subset after both the include branch and the skip branch. Each subset appears twice, and the empty subset appears more than once. Where should the print go?

103.Bitmask dynamic programming on a set of 40 features is proposed, one bit per feature. What is 2 to the 40th in round numbers, and why is that the stop sign?

104.Meet in the middle splits 40 numbers into two halves of 20, enumerates every subset sum of each half, and looks for pairs that add to the target. Why is that not the same as enumerating all 40-bit subsets?

105.You finish an algorithms interview by naming a bound you did not prove. The code is a nested loop over the same n with an early break that rarely fires. You call it linear. What should you call it?