| Introduction |
|
1 | (5) |
| I The Interview |
|
6 | (33) |
|
|
|
7 | (6) |
|
2 Strategies For A Great Interview |
|
|
13 | (6) |
|
3 Conducting An Interview |
|
|
19 | (3) |
|
|
|
22 | (17) |
| II Problems |
|
39 | (318) |
|
|
|
40 | (14) |
|
5.1 Computing the parity of a word |
|
|
41 | (2) |
|
|
|
43 | (1) |
|
|
|
44 | (1) |
|
5.4 Find a closest integer with the same weight |
|
|
45 | (1) |
|
5.5 Compute x*y without arithmetical operators |
|
|
46 | (1) |
|
|
|
47 | (1) |
|
|
|
48 | (1) |
|
|
|
49 | (1) |
|
5.9 Check if a decimal integer is a palindrome |
|
|
50 | (1) |
|
5.10 Generate uniform random numbers |
|
|
51 | (1) |
|
5.11 Rectangle intersection |
|
|
52 | (2) |
|
|
|
54 | (30) |
|
6.1 The Dutch national flag problem |
|
|
56 | (3) |
|
6.2 Increment an arbitrary-precision integer |
|
|
59 | (1) |
|
6.3 Multiply two arbitrary-precision integers |
|
|
59 | (2) |
|
6.4 Advancing through an array |
|
|
61 | (1) |
|
6.5 Delete duplicates from a sorted array |
|
|
62 | (1) |
|
6.6 Buy and sell a stock once |
|
|
63 | (1) |
|
6.7 Buy and sell a stock twice |
|
|
63 | (1) |
|
6.8 Enumerate all primes to n |
|
|
64 | (2) |
|
6.9 Permute the elements of an array |
|
|
66 | (2) |
|
6.10 Compute the next permutation |
|
|
68 | (2) |
|
|
|
70 | (1) |
|
|
|
71 | (1) |
|
6.13 Compute a random permutation |
|
|
72 | (1) |
|
6.14 Compute a random subset |
|
|
73 | (1) |
|
6.15 Generate nonuniform random numbers |
|
|
74 | (2) |
|
6.16 The Sudoku checker problem |
|
|
76 | (2) |
|
6.17 Compute the spiral ordering of a 2D array |
|
|
78 | (2) |
|
|
|
80 | (2) |
|
6.19 Compute rows in Pascal's Triangle |
|
|
82 | (2) |
|
|
|
84 | (16) |
|
7.1 Interconvert strings and integers |
|
|
85 | (1) |
|
|
|
86 | (1) |
|
7.3 Compute the spreadsheet column encoding |
|
|
87 | (1) |
|
|
|
88 | (1) |
|
|
|
89 | (1) |
|
7.6 Reverse all the words in a sentence |
|
|
90 | (1) |
|
7.7 Compute all mnemonics for a phone number |
|
|
91 | (2) |
|
7.8 The look-and-say problem |
|
|
93 | (1) |
|
7.9 Convert from Roman to decimal |
|
|
94 | (1) |
|
7.10 Compute all valid IP addresses |
|
|
95 | (1) |
|
7.11 Write a string sinusoidally |
|
|
96 | (1) |
|
7.12 Implement run-length encoding |
|
|
97 | (1) |
|
7.13 Find the first occurrence of a substring |
|
|
98 | (2) |
|
|
|
100 | (18) |
|
8.1 Merge two sorted lists |
|
|
102 | (2) |
|
8.2 Reverse a single sublist |
|
|
104 | (1) |
|
|
|
105 | (1) |
|
8.4 Test for overlapping lists-lists are cycle-free |
|
|
106 | (2) |
|
8.5 Test for overlapping lists-lists may have cycles |
|
|
108 | (2) |
|
8.6 Delete a node from a singly linked list |
|
|
110 | (1) |
|
8.7 Remove the kth last element from a list |
|
|
110 | (1) |
|
8.8 Remove duplicates from a sorted list |
|
|
111 | (1) |
|
8.9 Implement cyclic right shift for singly linked lists |
|
|
112 | (1) |
|
8.10 Implement even-odd merge |
|
|
113 | (1) |
|
8.11 Test whether a singly linked list is palindromic |
|
|
114 | (1) |
|
8.12 Implement list pivoting |
|
|
115 | (1) |
|
8.13 Add list-based integers |
|
|
116 | (2) |
|
|
|
118 | (18) |
|
9.1 Implement a stack with max API |
|
|
119 | (3) |
|
9.2 Evaluate RPN expressions |
|
|
122 | (1) |
|
9.3 Test a string over "{,},(,),[ ,]" for well-formedness |
|
|
123 | (1) |
|
|
|
124 | (1) |
|
9.5 Search a postings list |
|
|
125 | (2) |
|
9.6 Compute buildings with a sunset view |
|
|
127 | (3) |
|
9.7 Compute binary tree nodes in order of increasing depth |
|
|
130 | (1) |
|
9.8 Implement a circular queue |
|
|
131 | (1) |
|
9.9 Implement a queue using stacks |
|
|
132 | (1) |
|
9.10 Implement a queue with max API |
|
|
133 | (3) |
|
|
|
136 | (23) |
|
10.1 Test if a binary tree is height-balanced |
|
|
138 | (2) |
|
10.2 Test if a binary tree is symmetric |
|
|
140 | (1) |
|
10.3 Compute the lowest common ancestor in a binary tree |
|
|
141 | (1) |
|
10.4 Compute the LCA when nodes have parent pointers |
|
|
142 | (1) |
|
10.5 Sum the root-to-leaf paths in a binary tree |
|
|
143 | (1) |
|
10.6 Find a root to leaf path with specified sum |
|
|
144 | (1) |
|
10.7 Implement an inorder traversal without recursion |
|
|
145 | (1) |
|
10.8 Implement a preorder traversal without recursion |
|
|
146 | (1) |
|
10.9 Compute the kth node in an inorder traversal |
|
|
147 | (1) |
|
10.10 Compute the successor |
|
|
148 | (1) |
|
10.11 Implement an inorder traversal with O(1) space |
|
|
149 | (1) |
|
10.12 Reconstruct a binary tree from traversal data |
|
|
150 | (2) |
|
10.13 Reconstruct a binary tree from a preorder traversal with markers |
|
|
152 | (1) |
|
10.14 Form a linked list from the leaves of a binary tree |
|
|
153 | (1) |
|
10.15 Compute the exterior of a binary tree |
|
|
154 | (1) |
|
10.16 Compute the right sibling tree |
|
|
155 | (2) |
|
10.17 Implement locking in a binary tree |
|
|
157 | (2) |
|
|
|
159 | (12) |
|
|
|
160 | (3) |
|
11.2 Sort an increasing-decreasing array |
|
|
163 | (1) |
|
11.3 Sort an almost-sorted array |
|
|
164 | (1) |
|
11.4 Compute the k closest stars |
|
|
165 | (1) |
|
11.5 Compute the median of online data |
|
|
166 | (1) |
|
11.6 Compute the k largest elements in a max-heap |
|
|
167 | (2) |
|
11.7 Implement a stack API using a heap |
|
|
169 | (2) |
|
|
|
171 | (19) |
|
12.1 Search a sorted array for first occurrence of k |
|
|
174 | (1) |
|
12.2 Search a sorted array for entry equal to its index |
|
|
175 | (1) |
|
12.3 Search a cyclically sorted array |
|
|
176 | (2) |
|
12.4 Compute the integer square root |
|
|
178 | (1) |
|
12.5 Compute the real square root |
|
|
179 | (1) |
|
12.6 Search in a 2D sorted array |
|
|
180 | (2) |
|
12.7 Find the min and max simultaneously |
|
|
182 | (1) |
|
12.8 Find the kth largest element |
|
|
183 | (2) |
|
12.9 Find the missing IP address |
|
|
185 | (2) |
|
12.10 Find the duplicate and missing elements |
|
|
187 | (3) |
|
|
|
190 | (25) |
|
13.1 Test for palindromic permutations |
|
|
194 | (1) |
|
13.2 Is an anonymous letter constructible? |
|
|
195 | (1) |
|
13.3 Implement an ISBN cache |
|
|
196 | (2) |
|
13.4 Compute the LCA, optimizing for close ancestors |
|
|
198 | (1) |
|
13.5 Compute the k most frequent queries |
|
|
199 | (1) |
|
13.6 Find the nearest repeated entries in an array |
|
|
199 | (1) |
|
13.7 Find the smallest subarray covering all values |
|
|
200 | (4) |
|
13.8 Find smallest subarray sequentially covering all values |
|
|
204 | (2) |
|
13.9 Find the longest subarray with distinct entries |
|
|
206 | (1) |
|
13.10 Find the length of a longest contained interval |
|
|
207 | (1) |
|
13.11 Compute the average of the top three scores |
|
|
208 | (2) |
|
13.12 Compute all string decompositions |
|
|
210 | (1) |
|
13.13 Test the Collatz conjecture |
|
|
211 | (2) |
|
13.14 Implement a hash function for chess |
|
|
213 | (2) |
|
|
|
215 | (18) |
|
14.1 Compute the intersection of two sorted arrays |
|
|
217 | (2) |
|
14.2 Merge two sorted arrays |
|
|
219 | (1) |
|
14.3 Remove first-name duplicates |
|
|
219 | (1) |
|
|
|
220 | (2) |
|
|
|
222 | (2) |
|
14.6 Compute the union of intervals |
|
|
224 | (2) |
|
14.7 Partitioning and sorting an array with many repeated entries |
|
|
226 | (2) |
|
|
|
228 | (2) |
|
14.9 Implement a fast sorting algorithm for lists |
|
|
230 | (1) |
|
14.10 Compute a salary threshold |
|
|
231 | (2) |
|
|
|
233 | (26) |
|
15.1 Test if a binary tree satisfies the BST property |
|
|
235 | (2) |
|
15.2 Find the first key greater than a given value in a BST |
|
|
237 | (1) |
|
15.3 Find the k largest elements in a BST |
|
|
238 | (1) |
|
15.4 Compute the LCA in a BST |
|
|
239 | (1) |
|
15.5 Reconstruct a BST from traversal data |
|
|
240 | (3) |
|
15.6 Find the closest entries in three sorted arrays |
|
|
243 | (2) |
|
15.7 Enumerate numbers of the form a + b Square root of 2 |
|
|
245 | (2) |
|
15.8 The most visited pages problem |
|
|
247 | (2) |
|
15.9 Build a minimum height BST from a sorted array |
|
|
249 | (1) |
|
15.10 Insertion and deletion in a BST |
|
|
250 | (2) |
|
15.11 Test if three BST nodes are totally ordered |
|
|
252 | (2) |
|
15.12 The range lookup problem |
|
|
254 | (2) |
|
|
|
256 | (3) |
|
|
|
259 | (20) |
|
16.1 The Towers of Hanoi problem |
|
|
260 | (2) |
|
16.2 Generate all nonattacking placements of n-Queens |
|
|
262 | (2) |
|
16.3 Generate permutations |
|
|
264 | (1) |
|
16.4 Generate the power set |
|
|
265 | (2) |
|
16.5 Generate all subsets of size k |
|
|
267 | (1) |
|
16.6 Generate strings of matched parens |
|
|
268 | (2) |
|
16.7 Generate palindromic decompositions |
|
|
270 | (1) |
|
16.8 Generate binary trees |
|
|
271 | (1) |
|
16.9 Implement a Sudoku solver |
|
|
272 | (2) |
|
16.10 Compute a Gray code |
|
|
274 | (2) |
|
16.11 Compute the diameter of a tree |
|
|
276 | (3) |
|
|
|
279 | (27) |
|
17.1 Count the number of score combinations |
|
|
282 | (2) |
|
17.2 Compute the Levenshtein distance |
|
|
284 | (3) |
|
17.3 Count the number of ways to traverse a 2D array |
|
|
287 | (2) |
|
17.4 Compute the binomial coefficients |
|
|
289 | (1) |
|
17.5 Search for a sequence in a 2D array |
|
|
290 | (2) |
|
17.6 The knapsack problem |
|
|
292 | (2) |
|
17.7 The bedbathandbeyond.com problem |
|
|
294 | (3) |
|
17.8 Find the minimum weight path in a triangle |
|
|
297 | (1) |
|
17.9 Pick up coins for maximum gain |
|
|
298 | (2) |
|
17.10 Count the number of moves to climb stairs |
|
|
300 | (1) |
|
17.11 The pretty printing problem |
|
|
301 | (2) |
|
17.12 Find the longest nondecreasing subsequence |
|
|
303 | (3) |
|
18 Greedy Algorithms and Invariants |
|
|
306 | (16) |
|
18.1 Compute an optimum assignment of tasks |
|
|
307 | (1) |
|
18.2 Schedule to minimize waiting time |
|
|
308 | (1) |
|
18.3 The interval covering problem |
|
|
309 | (3) |
|
|
|
312 | (1) |
|
18.5 Find the majority element |
|
|
313 | (2) |
|
|
|
315 | (2) |
|
18.7 Compute the maximum water trapped by a pair of vertical lines |
|
|
317 | (1) |
|
18.8 Compute the largest rectangle under the skyline |
|
|
318 | (4) |
|
|
|
322 | (22) |
|
|
|
326 | (2) |
|
19.2 Paint a Boolean matrix |
|
|
328 | (2) |
|
19.3 Compute enclosed regions |
|
|
330 | (2) |
|
|
|
332 | (2) |
|
|
|
334 | (1) |
|
19.6 Making wired connections |
|
|
335 | (1) |
|
19.7 Transform one string to another |
|
|
336 | (3) |
|
|
|
339 | (1) |
|
19.9 Compute a shortest path with fewest edges |
|
|
340 | (4) |
|
|
|
344 | (13) |
|
20.1 Implement caching for a multithreaded dictionary |
|
|
345 | (2) |
|
20.2 Analyze two unsynchronized interleaved threads |
|
|
347 | (1) |
|
20.3 Implement synchronization for two interleaving threads |
|
|
348 | (2) |
|
20.4 Implement a thread pool |
|
|
350 | (1) |
|
|
|
351 | (1) |
|
20.6 The readers-writers problem |
|
|
352 | (2) |
|
20.7 The readers-writers problem with write preference |
|
|
354 | (1) |
|
20.8 Implement a Timer class |
|
|
354 | (1) |
|
20.9 Test the Collatz conjecture in parallel |
|
|
355 | (2) |
| III Domain Specific Problems |
|
357 | (39) |
|
|
|
358 | (17) |
|
21.1 Design a spell checker |
|
|
359 | (1) |
|
21.2 Design a solution to the stemming problem |
|
|
360 | (1) |
|
|
|
361 | (1) |
|
21.4 Pair users by attributes |
|
|
361 | (2) |
|
21.5 Design a system for detecting copyright infringement |
|
|
363 | (1) |
|
|
|
363 | (1) |
|
21.7 Design a search engine |
|
|
364 | (1) |
|
|
|
365 | (1) |
|
21.9 Design TeraSort and PetaSort |
|
|
366 | (1) |
|
21.10 Implement distributed throttling |
|
|
367 | (1) |
|
21.11 Design a scalable priority system |
|
|
367 | (1) |
|
21.12 Create photomosaics |
|
|
368 | (1) |
|
21.13 Implement Mileage Run |
|
|
369 | (1) |
|
|
|
370 | (1) |
|
21.15 Design an online advertising system |
|
|
370 | (1) |
|
21.16 Design a recommendation system |
|
|
371 | (1) |
|
21.17 Design an optimized way of distributing large files |
|
|
372 | (1) |
|
21.18 Design the World Wide Web |
|
|
373 | (1) |
|
21.19 Estimate the hardware cost of a photo sharing app |
|
|
373 | (2) |
|
|
|
375 | (5) |
|
|
|
375 | (1) |
|
|
|
375 | (1) |
|
22.3 final, finally, and finalizer |
|
|
376 | (1) |
|
|
|
376 | (1) |
|
22.5 equals() and hashCode() |
|
|
376 | (1) |
|
22.6 List, ArrayList, and LinkedList |
|
|
377 | (1) |
|
22.7 String vs. StringBuilder |
|
|
377 | (1) |
|
|
|
378 | (1) |
|
22.9 Static initialization |
|
|
379 | (1) |
|
23 Object-Oriented Design |
|
|
380 | (6) |
|
23.1 Template Method vs. Strategy |
|
|
380 | (1) |
|
|
|
381 | (1) |
|
23.3 Push vs. pull observer pattern |
|
|
381 | (1) |
|
23.4 Singletons and Flyweights |
|
|
382 | (1) |
|
|
|
382 | (1) |
|
|
|
383 | (2) |
|
23.7 Libraries and design patterns |
|
|
385 | (1) |
|
|
|
386 | (10) |
|
24.1 Merging in a version control system |
|
|
386 | (2) |
|
|
|
388 | (1) |
|
24.3 Is scripting is more efficient? |
|
|
389 | (1) |
|
24.4 Polymorphism with a scripting language |
|
|
390 | (1) |
|
|
|
390 | (1) |
|
|
|
391 | (1) |
|
|
|
392 | (1) |
|
|
|
392 | (1) |
|
|
|
393 | (1) |
|
|
|
393 | (1) |
|
|
|
394 | (1) |
|
|
|
395 | (1) |
| IV The Honors Class |
|
396 | (75) |
|
|
|
397 | (74) |
|
25.1 Compute the greatest common divisor |
|
|
397 | (1) |
|
25.2 Find the first missing positive entry |
|
|
398 | (2) |
|
25.3 Buy and sell a stock k times |
|
|
400 | (1) |
|
25.4 Compute the maximum product of all entries but one |
|
|
400 | (3) |
|
25.5 Compute the longest contiguous increasing subarray |
|
|
403 | (1) |
|
|
|
404 | (2) |
|
25.7 Identify positions attacked by rooks |
|
|
406 | (2) |
|
|
|
408 | (1) |
|
25.9 Implement list zipping |
|
|
409 | (1) |
|
25.10 Copy a postings list |
|
|
410 | (2) |
|
25.11 Compute the longest substring with matching parens |
|
|
412 | (1) |
|
25.12 Compute the maximum of a sliding window |
|
|
413 | (2) |
|
25.13 Implement a postorder traversal without recursion |
|
|
415 | (2) |
|
25.14 Compute fair bonuses |
|
|
417 | (3) |
|
25.15 Search a sorted array of unknown length |
|
|
420 | (1) |
|
25.16 Search in two sorted arrays |
|
|
421 | (1) |
|
25.17 Find the kth largest element-large n, small k |
|
|
422 | (1) |
|
25.18 Find an element that appears only once |
|
|
423 | (1) |
|
25.19 Find the line through the most points |
|
|
424 | (3) |
|
25.20 Find the shortest unique prefix |
|
|
427 | (2) |
|
25.21 Find the most visited pages in a window |
|
|
429 | (1) |
|
25.22 Convert a sorted doubly linked list into a BST |
|
|
430 | (2) |
|
25.23 Convert a BST to a sorted doubly linked list |
|
|
432 | (1) |
|
|
|
433 | (1) |
|
25.25 The view from above |
|
|
434 | (3) |
|
25.26 Implement regular expression matching |
|
|
437 | (3) |
|
25.27 Synthesize an expression |
|
|
440 | (2) |
|
|
|
442 | (2) |
|
|
|
444 | (2) |
|
25.30 Measure with defective jugs |
|
|
446 | (2) |
|
25.31 Compute the maximum subarray sum in a circular array |
|
|
448 | (2) |
|
25.32 Determine the critical height |
|
|
450 | (2) |
|
25.33 Find the maximum 2D subarray |
|
|
452 | (3) |
|
25.34 Implement Huffman coding |
|
|
455 | (4) |
|
|
|
459 | (1) |
|
25.36 Search for a pair-sum in an abs-sorted array |
|
|
460 | (3) |
|
25.37 The heavy hitter problem |
|
|
463 | (2) |
|
25.38 Find the longest subarray whose sum < or equal to k |
|
|
465 | (1) |
|
|
|
466 | (2) |
|
25.40 Test if arbitrage is possible |
|
|
468 | (3) |
| V Notation, and Index |
|
471 | (1) |
| Notation |
|
472 | (2) |
| Index of Terms |
|
474 | |
