Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Tài liệu đang bị lỗi
File tài liệu này hiện đang bị hỏng, chúng tôi đang cố gắng khắc phục.
Elements of Programming Interviews in Java
Nội dung xem thử
Mô tả chi tiết
ELEMENTS OF
PROGRAMMING
INTERVIEWS w
Java
ADNAN AZIZ
TSUNG-HSIEN LEE
AMIT PRAKASH
A
¥
Elements of
Programming
Interviews in Java
The Insiders' Guide
Adnan Aziz
Tsung-Hsien Lee
Amit Prakash
ElementsOfProgramminglnterviews.com
Adnan Aziz is a Research Scientist at Facebook. Previously, he was a professor at
the Department of Electrical and Computer Engineering at The University of Texas
at Austin, where he conducted research and taught classesin applied algorithms. He
received his Ph.D. from The University of California at Berkeley; his undergraduate
degree is from Indian Institutes of Technology Kanpur. He has worked at Google,
Qualcomm, IBM, and severalsoftware startups. When not designing algorithms, he
plays with his children, Laila, Imran, and Omar.
Tsung-Hsien Lee is a Senior Software Engineer at Uber. Previously, he worked
as a Software Engineer at Google and as Software Engineer Intern at Facebook.
He received both his M.S. and undergraduate degrees from National Tsing Hua
University. He has a passion for designing and implementing algorithms. He likes
to apply algorithms to every aspect of his life. He takes special pride in helping to
organize Google Code Jam 2014 and 2015.
Amit Prakash is a co-founder and CTO of ThoughtSpot, a Silicon Valley startup.
Previously, he was a Member of the Technical Staff at Google, where he worked
primarily on machine learning problemsthatarise in thecontext of online advertising.
Before that he worked at Microsoft in the web search team. He received his Ph.D.
from The University of Texas at Austin; his undergraduate degree is from Indian
Institutes of Technology Kanpur. When he is not improving businessintelligence, he
indulges in his passion for puzzles, movies, travel, and adventures with Nidhi and
Aanya.
Elements of Programming Interviews: The Insiders' Guide
by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash
Copyright © 2015 Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. All rights
reserved.
No part of this publication may be reproduced,stored in a retrievalsystem, or trans¬
mitted, in any form, or by any means, electronic, mechanical, photocopying, record¬
ing, or otherwise, without the prior consent of the authors.
The views and opinions expressed in this work are those of the authors and do not
necessarily reflect the official policy or position of their employers.
We typeset this book using PTpX and the Memoir class. We used TikZ to draw figures.
Allan Ytac created the cover, based on a design brief we provided.
The companion website for the book includes contact information and a list of known
errors for each version of the book. If you come across an error or an improvement,
please let us know.
Version 2.0.0
Website: http://elementsofprogramminginterviews.com
To my father, Ishrat Aziz,
forgiving me my lifelong love of learning
Adnan Aziz
To my parents, Hsien-Kuo Lee and Tseng-Hsia Li,
for the everlasting support and love they give me
Tsung-Hsien Lee
To my parents, Manju Shree and Arun Prakash,
the most loving parents I can imagine
Amit Prakash
Table of Contents
Introduction 1
I The Interview 6
1 Getting Ready 7
2 Strategies For A Great Interview 13
3 Conducting An Interview 20
4 Problem Solving 24
II Problems 43
5 Primitive Types 44
5.1 Computing the parity of a word 45
5.2 Swap bits 48
5.3 Reverse bits 49
5.4 Find a closest integer with the same weight 50
5.5 Compute x X y without arithmetical operators 51
5.6 Compute x/y 52
5.7 Compute xv 53
5.8 Reverse digits 54
5.9 Check if a decimal integer is a palindrome 55
5.10 Generate uniform random numbers 56
5.11 Rectangle intersection 57
6 Arrays 60
6.1 The Dutch national flag problem 62
6.2 Increment an arbitrary-precision integer 65
I
6.3 Multiply two arbitrary-precision integers 66
6.4 Advancing through an array 68
6.5 Delete duplicatesfrom a sorted array 69
6.6 Buy and sell a stock once 70
6.7 Buy and sell a stock twice 71
6.8 Enumerate all primesto n 72
6.9 Permute the elements of an array 74
6.10 Compute the next permutation 76
6.11 Sample offline data 78
6.12 Sample online data 79
6.13 Compute a random permutation 81
6.14 Compute a random subset 82
6.15 Generate nonuniform random numbers 83
6.16 The Sudoku checker problem 85
6.17 Compute the spiral ordering of a 2D array 87
6.18 Rotate a 2D array 90
6.19 Compute rowsin Pascal's Triangle 92
7 Strings 94
7.1 Interconvertstrings and integers 95
7.2 Base conversion 96
7.3 Compute the spreadsheet column encoding 98
7.4 Replace and remove 98
7.5 Test palindromicity 100
7.6 Reverse all the wordsin a sentence 101
7.7 Compute all mnemonicsfor a phone number 102
7.8 The look-and-say problem 104
7.9 Convert from Roman to decimal 105
7.10 Compute all valid IP addresses 106
7.11 Write a string sinusoidally 107
7.12 Implement run-length encoding 108
7.13 Find the first occurrence of a substring 109
8 Linked Lists 112
8.1 Merge two sorted lists 115
8.2 Reverse a single sublist 116
8.3 Test for cyclicity 117
8.4 Test for overlapping lists—lists are cycle-free 119
8.5 Test for overlapping lists—lists may have cycles 121
8.6 Delete a node from a singly linked list 122
8.7 Remove the kth last element from a list 123
8.8 Remove duplicatesfrom a sorted list 124
8.9 Implement cyclic rightshift for singly linked lists 125
8.10 Implement even-odd merge 126
8.11 Test whether a singly linked list is palindromic 127
ii
8.12 Implement list pivoting 128
8.13 Add list-based integers 129
9 Stacks and Queues 131
9.1 Implement a stack with max API 132
9.2 Evaluate RPN expressions 135
9.3 Test a string over for well-formedness 137
9.4 Normalize pathnames 138
9.5 Search a postings list 139
9.6 Compute buildings with a sunset view 140
9.7 Compute binary tree nodesin order of increasing depth 143
9.8 Implement a circular queue 145
9.9 Implement a queue using stacks 146
9.10 Implement a queue with max API 147
10 Binary Trees 150
10.1 Test if a binary tree is height-balanced 152
10.2 Test if a binary tree issymmetric 154
10.3 Compute the lowest common ancestor in a binary tree 155
10.4 Compute the LCA when nodes have parent pointers 157
10.5 Sum the root-to-leaf pathsin a binary tree 158
10.6 Find a root to leaf path with specified sum 159
10.7 Implement an inorder traversal without recursion 160
10.8 Implement a preorder traversal without recursion 161
10.9 Compute the fcth node in an inorder traversal 162
10.10 Compute the successor 163
10.11 Implement an inorder traversal with 0(1)space 164
10.12 Reconstruct a binary tree from traversal data 165
10.13 Reconstruct a binary tree from a preorder traversal with markers . 167
10.14 Form a linked list from the leaves of a binary tree 168
10.15 Compute the exterior of a binary tree 169
10.16 Compute the rightsibling tree 171
10.17 Implement locking in a binary tree 173
11 Heaps 175
11.1 Merge sorted files 177
11.2 Sort an increasing-decreasing array 179
11.3 Sort an almost-sorted array 180
11.4 Compute the k closeststars 181
11.5 Compute the median of online data 182
11.6 Compute the k largest elementsin a max-heap 184
11.7 Implement a stack API using a heap 185
12 Searching 187
12.1 Search a sorted array for first occurrence of k 190
iii
12.2 Search a sorted array for entry equal to itsindex 191
12.3 Search a cyclically sorted array 192
12.4 Compute the integersquare root 194
12.5 Compute the realsquare root 195
12.6 Search in a 2D sorted array 196
12.7 Find the min and max simultaneously 198
12.8 Find the fcth largest element 199
12.9 Find the missing IP address 202
12.10 Find the duplicate and missing elements 203
13 Hash Tables 207
13.1 Test for palindromic permutations 212
13.2 Is an anonymousletter constructible? 213
13.3 Implement an ISBN cache 214
13.4 Compute the LCA, optimizing for close ancestors 216
13.5 Compute the k most frequent queries 217
13.6 Find the nearest repeated entriesin an array 217
13.7 Find the smallestsubarray covering all values 218
13.8 Find smallestsubarray sequentially covering all values 222
13.9 Find the longestsubarray with distinct entries 224
13.10 Find the length of a longest contained interval 225
13.11 Compute the average of the top three scores 227
13.12 Compute allstring decompositions 228
13.13 Test the Collatz conjecture 230
13.14 Implement a hash function for chess 231
14 Sorting 234
14.1 Compute the intersection of two sorted arrays 236
14.2 Merge two sorted arrays 238
14.3 Remove first-name duplicates 239
14.4 Render a calendar 240
14.5 Merging intervals 242
14.6 Compute the union of intervals 244
14.7 Partitioning and sorting an array with many repeated entries . . . 246
14.8 Team photo day—1 248
14.9 Implement a fastsorting algorithm for lists 250
14.10 Compute a salary threshold 252
15 Binary Search Trees 254
15.1 Test if a binary tree satisfies the BST property 256
15.2 Find the first key greater than a given value in a BST 259
15.3 Find the k largest elementsin a BST 260
15.4 Compute the LCA in a BST 261
15.5 Reconstruct a BST from traversal data 262
15.6 Find the closest entriesin three sorted arrays 265
IV
15.7 Enumerate numbers of the form a + bÿJl 267
15.8 The most visited pages problem 269
15.9 Build a minimum height BST from a sorted array 271
15.10 Insertion and deletion in a BST 272
15.11 Test if three BST nodes are totally ordered 275
15.12 The range lookup problem 276
15.13 Add credits 279
16 Recursion 282
16.1 The Towers of Hanoi problem 283
16.2 Generate all nonattacking placements of n-Queens 285
16.3 Generate permutations 287
16.4 Generate the powerset 289
16.5 Generate allsubsets of size k 291
16.6 Generate strings of matched parens 292
16.7 Generate palindromic decompositions 293
16.8 Generate binary trees 295
16.9 Implement a Sudoku solver 296
16.10 Compute a Gray code 298
16.11 Compute the diameter of a tree 300
17 Dynamic Programming 303
17.1 Count the number of score combinations 306
17.2 Compute the Levenshtein distance 309
17.3 Count the number of waysto traverse a 2D array 312
17.4 Compute the binomial coefficients 314
17.5 Search for a sequence in a 2D array 315
17.6 The knapsack problem 317
17.7 The bedbathandbeyond.com problem 320
17.8 Find the minimum weight path in a triangle 323
17.9 Pick up coinsfor maximum gain 324
17.10 Count the number of moves to climb stairs 326
17.11 The pretty printing problem 327
17.12 Find the longest nondecreasing subsequence 330
18 Greedy Algorithms and Invariants 333
18.1 Compute an optimum assignment of tasks 334
18.2 Schedule to minimize waiting time 335
18.3 The interval covering problem 336
18.4 The 3-sum problem 340
18.5 Find the majority element 341
18.6 The gasup problem 343
18.7 Compute the maximum water trapped by a pair of vertical lines . . 345
18.8 Compute the largest rectangle under the skyline 347
v
19 Graphs 350
19.1 Search a maze 354
19.2 Paint a Boolean matrix 357
19.3 Compute enclosed regions 359
19.4 Deadlock detection 361
19.5 Clone a graph 363
19.6 Making wired connections 364
19.7 Transform one string to another 366
19.8 Team photo day—2 369
19.9 Compute a shortest path with fewest edges 370
20 Parallel Computing 374
20.1 Implement caching for a multithreaded dictionary 376
20.2 Analyze two unsynchronized interleaved threads 378
20.3 Implementsynchronization for two interleaving threads ......379
20.4 Implement a thread pool 381
20.5 Deadlock 382
20.6 The readers-writers problem 383
20.7 The readers-writers problem with write preference 385
20.8 Implement a Timer class 385
20.9 Test the Collatz conjecture in parallel 386
III Domain Specific Problems 388
21 Design Problems 389
21.1 Design a spell checker 391
21.2 Design a solution to the stemming problem 391
21.3 Plagiarism detector 392
21.4 Pair users by attributes 393
21.5 Design a system for detecting copyright infringement 394
21.6 Design TpX 395
21.7 Design a search engine 396
21.8 Implement PageRank 397
21.9 Design TeraSort and PetaSort 398
21.10 Implement distributed throttling 399
21.11 Design a scalable priority system 400
21.12 Create photomosaics 401
21.13 Implement Mileage Run 401
21.14 Implement Connexus 403
21.15 Design an online advertising system 404
21.16 Design a recommendation system 405
21.17 Design an optimized way of distributing large files 406
21.18 Design the World Wide Web 406
21.19 Estimate the hardware cost of a photo sharing app 407
vi
22 Language Questions 409
22.1 The JVM 409
22.2 throw vs. throws 409
22.3 final,finally, and finalizer 410
22.4 equalsO vs. == 410
22.5 equalsO and hashCodeO 411
22.6 List, ArrayList, and LinkedList 411
22.7 String vs. StringBuilder 412
22.8 Autoboxing 413
22.9 Static initialization 413
23 Object-Oriented Design 415
23.1 Template Method vs. Strategy 415
23.2 Observer pattern 416
23.3 Push vs. pull observer pattern 416
23.4 Singletons and Flyweights 417
23.5 Adapters 418
23.6 Creational Patterns 419
23.7 Libraries and design patterns 421
24 Common Tools 422
24.1 Merging in a version controlsystem 422
24.2 Hooks 424
24.3 Isscripting more efficient? 426
24.4 Polymorphism with a scripting language 426
24.5 Dependency analysis 427
24.6 ANT vs. Maven 427
24.7 SQL vs. NoSQL 428
24.8 Normalization 429
24.9 SQL design 429
24.10 IP, TCP, and HTTP 430
24.11 HTTPS 431
24.12 DNS 432
IV The Honors Class 434
25 Honors Class 435
25.1 Compute the greatest common divisor ©> 435
25.2 Find the first missing positive entry Q< 437
25.3 Buy and sell a stock k times O' 438
25.4 Compute the maximum product of all entries but one O .....439
25.5 Compute the longest contiguous increasing subarray O......441
25.6 Rotate an array O' 443
25.7 Identify positions attacked by rooks O 445
vii
25.8 Justify text O' 447
25.9 Implement list zipping O 448
25.10 Copy a postingslist O 449
25.11 Compute the longestsubstring with matching parens O......451
25.12 Compute the maximum of a sliding window O 452
25.13 Implement a postorder traversal without recursion O 454
25.14 Compute fair bonuses O 456
25.15 Search a sorted array of unknown length O 459
25.16 Search in two sorted arrays O 460
25.17 Find the kth largest element—large n,small k O 462
25.18 Find an element that appears only once O 463
25.19 Find the line through the most points O 464
25.20 Find the shortest unique prefix O' 467
25.21 Find the most visited pagesin a window O' 469
25.22 Convert a sorted doubly linked list into a BST O 470
25.23 Convert a BST to a sorted doubly linked list O 472
25.24 Merge two BSTs O 473
25.25 The view from above ©> 475
25.26 Implement regular expression matching O 478
25.27 Synthesize an expression ©> 481
25.28 Count inversions O 483
25.29 Draw the skyline O 485
25.30 Measure with defective jugs O 488
25.31 Compute the maximum subarray sum in a circular array ©'•••• 490
25.32 Determine the critical height O 492
25.33 Find the maximum 2D subarray O' 493
25.34 Implement Huffman coding 497
25.35 Trapping water ©> 501
25.36 Search for a pair-sum in an abs-sorted array ©> 502
25.37 The heavy hitter problem O 505
25.38 Find the longestsubarray whose sum < k & .....507
25.39 Road network O' 509
25.40 Test if arbitrage is possible O' 511
V Notation, and Index 513
Notation 514
Index of Terms 516
Introduction
And it ought to be remembered that there is nothing more
difficult to take in hand, more perilous to conduct, or
more uncertain in its success, than to take the lead in the
introduction of a new order of things.
— N. MACHIAVELLI, 1513
Elements of Programming Interviews (EPI) aims to help engineers interviewing for
software development positions. The primary focus of EPI is data structures, al¬
gorithms, system design, and problem solving. The material is largely presented
through questions.
An interview problem
Let's begin withFigure1below. It depictsmovementsin the share price of a company
over 40 days. Specifically, for each day, the chart shows the daily high and low, and
the price at the opening bell (denoted by the white square). Suppose you were asked
in an interview todesign an algorithm that determinesthe maximum profit that could
have been made by buying and then selling a single share over a given day range,
subject to the constraint that the buy and the sell have to take place at the start of the
day. (This algorithm may be needed to backtest a trading strategy.)
You may want to stop reading now, and attempt this problem on your own.
First clarify the problem. For example, you should ask for the input format.
Let's say the input consists of three arrays L,H, and S, of nonnegative floating point
numbers, representing the low, high, and starting pricesfor each day. The constraint
that the purchase and sale have to take place at the start of the day means that it
suffices to consider S. You may be tempted to simply return the difference of the
Day 0 Day 5 Day 10 Day 15 Day 20 Day 25 Day 30 Day 35 Day 40
Figure 1: Share price as a function of time.
i
minimum and maximum elements in S. If you try a few test cases, you willsee that
the minimum can occur after the maximum, which violates the requirement in the
problem statement—you have to buy before you can sell.
At this point, a brute-force algorithm would be appropriate. For each pair of
indices i and j > i, if S[/] - S[i] is greater than the largest difference seen so far,
update the largest difference to S[/]-S[i], You should be able to code this algorithm
using a pair of nested for-loops and test it in a matter of a few minutes. You should
also derive its time complexity as a function of the length n of the input array. The
outer loop is invoked n— 1 times, and the ith iteration processes n — 1 — i elements.
Processing an element entails computing a difference, performing a compare, and
possibly updating a variable, all of which take constant time. Hence, the run time is
proportional to Yj"=o(n - 1 - 0 = i.e., the time complexity of the brute-force
algorithm is 0(n2). You should also consider the space complexity, i.e., how much
memory your algorithm uses. The array itself takes memory proportional to n, and
the additional memory used by the brute-force algorithm is a constant independent
of n—a couple of iterators and one floating point variable.
Once you have a working algorithm, try to improve upon it. Specifically, an
0(n2) algorithm is usually not acceptable when faced with large arrays. You may
have heard of an algorithm design pattern called divide-and-conquer. It yields the
following algorithm for this problem. Split S into two subarrays, S[0 : Lf J] and
S[Lf J + 1 : n - 1]; compute the best result for the first and second subarrays; and
combine these results. In the combine step we take the better of the resultsfor the two
subarrays. However, we also need to consider the case where the optimum buy and
sell take place in separate subarrays. When this is the case, the buy must be in the
first subarray, and the sell in the second subarray,since the buy must happen before
the sell. If the optimum buy and sell are in different subarrays, the optimum buy
price is the minimum price in the first subarray, and the optimum sell price is in the
maximum price in the second subarray. We can compute these prices in 0(n) time
with a single pass over each subarray. Therefore, the time complexity T(n) for the
divide-and-conquer algorithm satisfies the recurrence relation T(n) = 2T(|) + 0(n),
which solves to0(n log «).
The divide-and-conquer algorithm is elegant and fast. Its implementation entails
some corner cases, e.g., an empty subarray, subarrays of length one, and an array in
which the price decreases monotonically, but it can still be written and tested by a
good developer in 20-30 minutes.
Looking carefully at the combine step of the divide-and-conquer algorithm, you
may have a flash of insight. Specifically, you may notice that the maximum profit
that can be made by selling on a specific day is determined by the minimum of the
stock prices over the previous days. Since the maximum profit correspondsto selling
on some day, the following algorithm correctly computesthe maximum profit. Iterate
through S, keeping track of the minimum element m seen thus far. If the difference
of the current element and m is greater than the maximum profit recorded so far,
update the maximum profit. This algorithm performs a constant amount of work per
array element, leading to an 0(n) time complexity. It uses two float-valued variables
(the minimum element and the maximum profit recorded so far) and an iterator, i.e.,
2