forked from ahangchen/dirtysalt.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
cracking-the-coding-interview.html
1587 lines (1437 loc) · 89.3 KB
/
cracking-the-coding-interview.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Cracking The Coding Interview</title>
<meta name="generator" content="Org-mode" />
<meta name="author" content="dirtysalt" />
<link rel="shortcut icon" href="http://dirtysalt.info/css/favicon.ico" />
<link rel="stylesheet" type="text/css" href="./css/site.css" />
</head>
<body>
<div id="content">
<h1 class="title">Cracking The Coding Interview</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#orgheadline1">1. Foreword</a></li>
<li><a href="#orgheadline2">2. Introduction</a></li>
<li><a href="#orgheadline8">3. Behind the Scenes</a>
<ul>
<li><a href="#orgheadline3">3.1. The Microsoft Interview</a></li>
<li><a href="#orgheadline4">3.2. The Amazon Interview</a></li>
<li><a href="#orgheadline5">3.3. The Google Interview</a></li>
<li><a href="#orgheadline6">3.4. The Apple Interview</a></li>
<li><a href="#orgheadline7">3.5. The Yahoo Interview</a></li>
</ul>
</li>
<li><a href="#orgheadline12">4. Before the Interview</a>
<ul>
<li><a href="#orgheadline9">4.1. Resume Advice</a></li>
<li><a href="#orgheadline10">4.2. Behavioral Preparation</a></li>
<li><a href="#orgheadline11">4.3. Technical Preparation</a></li>
</ul>
</li>
<li><a href="#orgheadline19">5. The Interview and Beyond</a>
<ul>
<li><a href="#orgheadline13">5.1. Handling Behavioral Questions</a></li>
<li><a href="#orgheadline14">5.2. Handling Technical Questions</a></li>
<li><a href="#orgheadline15">5.3. Five Algorithm Approaches</a></li>
<li><a href="#orgheadline16">5.4. The Offer and Beyond</a></li>
<li><a href="#orgheadline17">5.5. Top Ten Mistakes Candidates Make</a></li>
<li><a href="#orgheadline18">5.6. Frequently Asked Questions</a></li>
</ul>
</li>
<li><a href="#orgheadline40">6. Interview Questions</a>
<ul>
<li><a href="#orgheadline20">6.1. Arrays and Strings</a></li>
<li><a href="#orgheadline21">6.2. Linked Lists</a></li>
<li><a href="#orgheadline22">6.3. Stacks and Queues</a></li>
<li><a href="#orgheadline23">6.4. Trees and Graphs</a></li>
<li><a href="#orgheadline24">6.5. Bit Manipulation</a></li>
<li><a href="#orgheadline25">6.6. Brain Teasers</a></li>
<li><a href="#orgheadline26">6.7. Object Oriented Design</a></li>
<li><a href="#orgheadline27">6.8. Recursion</a></li>
<li><a href="#orgheadline28">6.9. Sorting and Searching</a></li>
<li><a href="#orgheadline29">6.10. Mathematical</a></li>
<li><a href="#orgheadline30">6.11. Testing</a></li>
<li><a href="#orgheadline31">6.12. System Design and Memory Limits</a></li>
<li><a href="#orgheadline32">6.13. C++</a></li>
<li><a href="#orgheadline33">6.14. Java</a></li>
<li><a href="#orgheadline34">6.15. Databases</a></li>
<li><a href="#orgheadline35">6.16. Low Level</a></li>
<li><a href="#orgheadline36">6.17. Networking</a></li>
<li><a href="#orgheadline37">6.18. Threads and Locks</a></li>
<li><a href="#orgheadline38">6.19. Moderate Additional Review Problems</a></li>
<li><a href="#orgheadline39">6.20. Hard Additional Review Problems</a></li>
</ul>
</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline1" class="outline-2">
<h2 id="orgheadline1"><span class="section-number-2">1</span> Foreword</h2>
<div class="outline-text-2" id="text-1">
<p>
As you get ready for your interviews, consider these suggestions:
</p>
<ul class="org-ul">
<li>Write Code on Paper</li>
<li>Know Your Resume</li>
<li>Don’t Memorize Solutions</li>
<li>Talk Out Loud</li>
</ul>
<p>
Receiving an offer is not about solving questions flawlessly (very few candidates do!), but rather, <b>it is about answering questions better than other candidates.</b> So don’t stress out when you get a tricky question - everyone else probably thought it was hard too!
</p>
</div>
</div>
<div id="outline-container-orgheadline2" class="outline-2">
<h2 id="orgheadline2"><span class="section-number-2">2</span> Introduction</h2>
</div>
<div id="outline-container-orgheadline8" class="outline-2">
<h2 id="orgheadline8"><span class="section-number-2">3</span> Behind the Scenes</h2>
<div class="outline-text-2" id="text-3">
</div><div id="outline-container-orgheadline3" class="outline-3">
<h3 id="orgheadline3"><span class="section-number-3">3.1</span> The Microsoft Interview</h3>
<div class="outline-text-3" id="text-3-1">
<ul class="org-ul">
<li>Microsoft wants smart people Geeks. People who are passionate about technology.</li>
<li>You'll have a short interview with a recruiter where he or she will give you a sample question. Your recruiter is usually there to prep you, and not to grill you on techni- cal questions. Be nice to your recruiter. Your recruiter can be your biggest advocate, even pushing to re-interview you if you stumbled on your first interview. They can fight for you to be hired - or not!</li>
<li>During the day, you'll do four or five interviews, often with two different teams Unlike many companies.</li>
<li>Depending on the team, interviewers may or may not share their feedback on you with the rest of the interview loop.</li>
<li>When you complete your interviews with a team, you might speak with a hiring manager. If so, that’s a great sign! It likely means that you passed the interviews with a particular team. It’s now down to the hiring manager’s decision.</li>
<li>You might get a decision that day, or it might be a week. After one week of no word from HR, send them a friendly email asking for a status update.</li>
</ul>
<p>
Definitely Prepare: <b>“Why do you want to work for Microsoft?”</b>
</p>
<p>
In this question, Microsoft wants to see that you’re passionate about technology. A great answer might be, “I’ve been using Microsoft software as long as I can re- member, and I'm really impressed at how Microsoft manages to create a product that is universally excellent. For example, I’ve been using Visual Studio recently to learn game programming, and it’s APIs are excellent.” Note how this shows a passion for technology!
</p>
</div>
</div>
<div id="outline-container-orgheadline4" class="outline-3">
<h3 id="orgheadline4"><span class="section-number-3">3.2</span> The Amazon Interview</h3>
<div class="outline-text-3" id="text-3-2">
<ul class="org-ul">
<li>Amazon’s recruiting process usually begins with one or two phone screens in which you in- terview with a specific team. The engineer who interviews you will usually ask you to write simple code and read it aloud on the phone They will ask a broad set of questions to explore what areas of technology you’re familiar with.</li>
<li>Next, you fly to Seattle for four or five interviews with one or two teams which have selected you based on your resume and phone interviews. You will have to code on a whiteboard, and some interviewers will stress other skills. Interviewers are each assigned a specific area to probe and may seem very different from each other.</li>
<li>They can not see other feedback until they have submitted their own and they are discouraged from discussing it until the hiring meeting.</li>
<li>Amazon’s “bar raiser” interviewer is charged with keeping the interview bar high. If one interview seems significantly harder and different, that’s most like- ly the bar raiser This person has both significant experience with interviews and veto power in the hiring decision.</li>
<li>While Amazon’s recruiters are excellent at following up with candidates, occa- sionally there are delays. If you haven’t heard from Amazon within a week, we recommend a friendly email.</li>
</ul>
<p>
Definitely Prepare:
</p>
<ul class="org-ul">
<li>Amazon is a web-based company, and that means they care about scale. Make sure you prepare for questions in “Large Scale.” You don’t need a background in distributed systems to answer these questions. See our recommendations in the System Design and Memory Limits Chapter.</li>
<li>Additionally, Amazon tends to ask a lot of questions about object oriented design. Check out the Object Oriented Design chapter for sample questions and suggestions.</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline5" class="outline-3">
<h3 id="orgheadline5"><span class="section-number-3">3.3</span> The Google Interview</h3>
<div class="outline-text-3" id="text-3-3">
<ul class="org-ul">
<li>However, because Google HR can be a little disorganized, we recommend being proactive in com- munication.</li>
<li>A Google engineer performs the first phone screen, so expect tough technical questions.</li>
<li>On your on-site interview, you'll interview with four to six people, one of whom will be a lunch interviewer. Interviewer feedback is kept confidential from the other interviewers, so you can be assured that you enter each interview with blank slate. Your lunch interviewer doesn’t submit feedback, so this is a great opportunity to ask honest questions.</li>
<li>Written feedback is submitted to a hiring committee of engineers to make a hire/no-hire recommendation. Feedback is typically broken down into four categories (Analytical Ability, Coding, Experience and Communication) and you are given a score from 1.0 to 4.0 overall.</li>
<li>The hiring committee understands that you can’t be expected to excel in every interview, but if multiple people raise the same red flag (arrogance, poor coding skills, etc), that can disqualify you. A hiring committee typically wants to see one interviewer who is an “enthusiastic en- dorser”. In other words, a packet with scores of 3.6, 3.1, 3.1 and 2.6 is better than all 3.1s. Your phone screen is usu- ally not a strong factor in the final deci- sion.</li>
<li>The Google hiring process can be slow. If you don’t hear back within one week, politely ask your recruiter for an up- date. A lack of response says nothing about your performance.</li>
</ul>
<p>
Definitely Prepare:
</p>
<ul class="org-ul">
<li>As a web-based company, Google cares about how to design a scalable system. So, make sure you prepare for questions from “System Design and Memory Limits” Additionally, many Google interviewers will ask questions involving Bit Ma- nipulation, so please brush up on these questions.</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline6" class="outline-3">
<h3 id="orgheadline6"><span class="section-number-3">3.4</span> The Apple Interview</h3>
<div class="outline-text-3" id="text-3-4">
<ul class="org-ul">
<li>Much like the company itself, Apple’s interview process has minimal beaucracy.</li>
<li>The inter- viewers will be looking for excellent technical skills, but a passion for the position and com- pany is also very important. While it’s not a prerequisite to be a Mac user, you should at least be familiar with the system.</li>
<li>The interview process typically begins with a recruiter phone screen to get a basic sense of your skills, <b>followed up by a series of technical phone screens with team members.</b></li>
<li>Once you’re invited on campus, you'll typically be greeted by the recruiter who provides an overview of the process. You will then have 6-8 interviews with members of the team for which you’re interviewing, as well as key people with whom your team works.</li>
<li>You can expect a mix of 1-on-1 and 2-on-1 interviews. Be ready to code on a whiteboard and make sure all of your thoughts are clearly communicated. Lunch is with your potential future manager and appears more casual, but is still an interview. Each interviewer is usually fo- cused on a different area and is discouraged from sharing feedback unless there’s something they want subsequent interviewers to drill into.</li>
<li>Towards the end of the day, your inter- viewers will compare notes and if ev- eryone still feels you’re a viable candi- date, you'll interview with the director and then VP of the organization you’re applying to. While this decision is rath- er informal, it’s a very good sign if you make it. This decision also happens be- hind the scenes and if you don’t pass, you'll simply be escorted out of the building without ever having been the wiser (until now)</li>
<li>If you made it to the director and VP interviews, all of your interviewers will gather in a conference room to give an official thumbs up or thumbs down The VP typically won’t be present, but can still veto the hire if they weren’t im- pressed.</li>
<li>Your recruiter will usually fol- low up a few days later, but feel free to ping your recruiter for updates.</li>
</ul>
<p>
Definitely Prepare:
</p>
<ul class="org-ul">
<li>If you know what team you’re interview- ing with, make sure you read up on that product. What do you like about it? What would you improve? Offering specific recommendations can show your passion for the job.</li>
<li>Also, Apple employees are huge Apple fans. You should show this same passion in your interview.</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline7" class="outline-3">
<h3 id="orgheadline7"><span class="section-number-3">3.5</span> The Yahoo Interview</h3>
<div class="outline-text-3" id="text-3-5">
<ul class="org-ul">
<li>While Yahoo tends to only recruit at the top 10 – 20 schools, other candidates can still get interviewed through Yahoo’s job board (or – better yet – if they can get an internal referral). If you’re one of the lucky ones selected, your interview process will start off with a phone screen. Your phone screen will be with a senior employee (tech lead, manager, etc)</li>
<li>You will typically interview with 6 – 7 people on the same team for 45 minutes each Each interviewer will have an area of focus. Interviews will often be composed as follows:
<ul class="org-ul">
<li>5 minutes: General conversation Tell me about yourself, your projects, etc</li>
<li>20 minutes: Coding question For example, implement merge sort</li>
<li>20 minutes: System design For example, design a large distributed cache These ques- tions will often focus on an area from your past experience or on something your interviewer is cur-rently working on</li>
</ul></li>
<li>At the end of the day, you will likely meet with a Program Manag- er or someone else for a general con- versation (product demos, concerns about the company, your competing offers, etc). Meanwhile, your interview- ers will discuss your performance and attempt to come to a decision The hiring manager has the ultimate say and will weigh the positive feedback against the negative.</li>
<li>If you have done well, you will often get a decision that day, but this is not always the case. There can be many reasons that you might not be told for several days – for example, the team may feel it needs to interview several other people.</li>
</ul>
<p>
Definitely Prepare:
</p>
<ul class="org-ul">
<li>Yahoo, almost as a rule, asks questions about system design, so make sure you prepare for that. They want to know that you can not only write code, but that you can design software. Don’t worry if you don’t have a background in this - you can still reason your way through it!</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-orgheadline12" class="outline-2">
<h2 id="orgheadline12"><span class="section-number-2">4</span> Before the Interview</h2>
<div class="outline-text-2" id="text-4">
</div><div id="outline-container-orgheadline9" class="outline-3">
<h3 id="orgheadline9"><span class="section-number-3">4.1</span> Resume Advice</h3>
<div class="outline-text-3" id="text-4-1">
<p>
Resume screeners look for the same things that interviewers do:
</p>
<ul class="org-ul">
<li><b>Are you smart?</b></li>
<li><b>Can you code?</b></li>
</ul>
<p>
That means that you should present your resume to show those two things. Your love of tennis, traveling, or magic cards won’t do much to show that, so it’s likely just wasting space.Keep in mind that recruiters only spend a fixed amount of time (about 20 seconds) looking at your resume. If you limit the content to the best, most impressive, most relevant items, they’ll jump out at the recruiter Weak items only dilute your resume and distract the re- cruiter from what you’d like them to see.
</p>
<hr />
<p>
<b>Writing Strong Bullets:</b>
</p>
<ul class="org-ul">
<li>For each role, try to discuss your accomplishments with the following approach: “Accom- plished X by implementing Y which led to Z” Here’s an example:</li>
<li>“Reduced object rendering time by 75% by applying Floyd’s algo- rithm, leading to a 10% reduction in system boot time”</li>
<li>“Increased average match accu- racy from 1.2 to 1.5 by implement- ing a new comparison algorithm based on windiff”</li>
</ul>
<p>
Not everything you did will fit into this approach, but the principle is the same: show what you did, how you did it, and what the results were Ideally, you should try to make the results “measurable” somehow.
</p>
<hr />
<p>
<b>Advice for Non-Native English Speakers and Internationals:</b>
</p>
<ul class="org-ul">
<li>Proofreading: Some companies will throw out your resume just because of a typo. Please get at least one native English speaker to proofread your resume.</li>
<li>Personal Information: For US positions, do not include age, marital status, or nationality. This sort of personal information is not appreciated by companies, as it creates a legal liabil- ity for them However, you may want to include your current work authorization / visa status, particularly when applying to smaller companies who may be unable to sponsor candidates.</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline10" class="outline-3">
<h3 id="orgheadline10"><span class="section-number-3">4.2</span> Behavioral Preparation</h3>
<div class="outline-text-3" id="text-4-2">
<p>
Behavioral questions are asked for a variety of reasons
</p>
<ul class="org-ul">
<li>They can be asked either to get to know your personality,</li>
<li>to more deeply understand your resume,</li>
<li>or just to ease you into an interview Either way,</li>
</ul>
<p>
these questions are important and can be prepared for.
</p>
<p>
Behavioral questions are usually of the form “tell me about a time when you ”, and may ask for an example from a specific project or position. I recommend filling in the following “preparation grid” as shown below:
</p>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<colgroup>
<col class="org-left" />
<col class="org-left" />
<col class="org-left" />
<col class="org-left" />
<col class="org-left" />
</colgroup>
<thead>
<tr>
<th scope="col" class="org-left"> </th>
<th scope="col" class="org-left">Project1</th>
<th scope="col" class="org-left">Project2</th>
<th scope="col" class="org-left">Project3</th>
<th scope="col" class="org-left">Project4</th>
</tr>
</thead>
<tbody>
<tr>
<td class="org-left">Most Challenging</td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
</tr>
<tr>
<td class="org-left">What You Learned</td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
</tr>
<tr>
<td class="org-left">Most Interesting</td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
</tr>
<tr>
<td class="org-left">Hardest Bug</td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
</tr>
<tr>
<td class="org-left">Enjoyed Most</td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
</tr>
<tr>
<td class="org-left">Conflicts with Teammates</td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
<td class="org-left"> </td>
</tr>
</tbody>
</table>
<p>
In each cell, put the corresponding story. We recommend reducing each story to just a couple keywords that you can write in each cell This will make the grid easier to study
</p>
<hr />
<p>
<b>What questions should you ask the interviewer?</b>
</p>
<ul class="org-ul">
<li>Genuine Questions: These are the questions you actually want to know ideas of questions that are valuable to many candidates:
<ul class="org-ul">
<li>“How much of your day do you spend coding?”</li>
<li>“How many meetings do you have every week?”</li>
<li>“What is the ratio of testers to developers to product managers? What is the interac- tion like? How does project planning happen on the team?”</li>
</ul></li>
<li>Insightful Questions: These questions are designed to demonstrate your deep knowledge of programming or technologies.
<ul class="org-ul">
<li>“I noticed that you use technology X How do you handle problem Y?”</li>
<li>“Why did the product choose to use the X protocol over the Y protocol? I know it has benefits like A, B, C, but many companies choose not to use it because of issue D”</li>
</ul></li>
<li>Passion Questions: These questions are designed to demonstrate your passion for technol- ogy.
<ul class="org-ul">
<li>“I’m very interested in scalability Did you come in with a background in this, or what opportunities are there to learn about it?”</li>
<li>“I’m not familiar with technology X, but it sounds like a very interesting solution Could you tell me a bit more about how it works?”</li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline11" class="outline-3">
<h3 id="orgheadline11"><span class="section-number-3">4.3</span> Technical Preparation</h3>
<div class="outline-text-3" id="text-4-3">
<ul class="org-ul">
<li>Memorizing or trying to learn specific questions won’t help you!</li>
<li>Try to solve the problem on your own.</li>
<li>Write the code for the algorithm on paper.</li>
<li>Type your paper code as-is into a computer.</li>
<li>*Do a mock interview. CareerCup offers a mock interview</li>
</ul>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<colgroup>
<col class="org-left" />
<col class="org-left" />
<col class="org-left" />
</colgroup>
<thead>
<tr>
<th scope="col" class="org-left">Data Structures</th>
<th scope="col" class="org-left">Algorithms</th>
<th scope="col" class="org-left">Concepts</th>
</tr>
</thead>
<tbody>
<tr>
<td class="org-left">Linked Lists</td>
<td class="org-left">Breadth First Search</td>
<td class="org-left">Bit Manipulation</td>
</tr>
<tr>
<td class="org-left">Binary Trees</td>
<td class="org-left">Depth First Search</td>
<td class="org-left">Singleton Design Pattern</td>
</tr>
<tr>
<td class="org-left">Tries</td>
<td class="org-left">Binary Search</td>
<td class="org-left">Factory Design Pattern</td>
</tr>
<tr>
<td class="org-left">Stacks</td>
<td class="org-left">Merge Sort</td>
<td class="org-left">Memory (Stack vs Heap)</td>
</tr>
<tr>
<td class="org-left">Queues</td>
<td class="org-left">Quick Sort</td>
<td class="org-left">Recursion</td>
</tr>
<tr>
<td class="org-left">Vectors / ArrayLists</td>
<td class="org-left">Tree Insert / Find / etc</td>
<td class="org-left">Big-O Time</td>
</tr>
<tr>
<td class="org-left">Hash Tables</td>
<td class="org-left"> </td>
<td class="org-left"> </td>
</tr>
</tbody>
</table>
</div>
</div>
</div>
<div id="outline-container-orgheadline19" class="outline-2">
<h2 id="orgheadline19"><span class="section-number-2">5</span> The Interview and Beyond</h2>
<div class="outline-text-2" id="text-5">
</div><div id="outline-container-orgheadline13" class="outline-3">
<h3 id="orgheadline13"><span class="section-number-3">5.1</span> Handling Behavioral Questions</h3>
<div class="outline-text-3" id="text-5-1">
<ul class="org-ul">
<li>Be Specific, Not Arrogant</li>
<li>Limit Details</li>
<li>Ask Good Questions</li>
<li>Structure Answers Using S.A.R(Situation, Action, Response)</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline14" class="outline-3">
<h3 id="orgheadline14"><span class="section-number-3">5.2</span> Handling Technical Questions</h3>
<div class="outline-text-3" id="text-5-2">
<p>
A technical interview question can be solved utilizing a five step approach:
</p>
<ol class="org-ol">
<li>Ask your interviewer questions to resolve ambiguity</li>
<li>Design an Algorithm</li>
<li>Write pseudo-code first, but make sure to tell your interviewer that you’re writing pseudo-code! Otherwise, he/she may think that you’re never planning to write “real” code, and many interviewers will hold that against you</li>
<li>Write your code, not too slow and not too fast</li>
<li>Test your code and carefully fix any mistakes</li>
</ol>
</div>
</div>
<div id="outline-container-orgheadline15" class="outline-3">
<h3 id="orgheadline15"><span class="section-number-3">5.3</span> Five Algorithm Approaches</h3>
</div>
<div id="outline-container-orgheadline16" class="outline-3">
<h3 id="orgheadline16"><span class="section-number-3">5.4</span> The Offer and Beyond</h3>
<div class="outline-text-3" id="text-5-4">
<ul class="org-ul">
<li><b>Negotiating.</b> It’s Always Negotiable! Ok, maybe not always, but usually an offer is negotiable even if a recruiter tells you otherwise. It helps if you have a competing offer But, <b>don’t lie – Microsoft knows what Google offers, so it just won’t be realistic if you make up numbers.</b> Also, technol- ogy is a small world, and people talk. Be honest.</li>
<li><b>What’s the money like, really?</b> Think about the full offer package Many companies will have impressive salaries, but small annual bonuses Other companies will have huge annual bonuses, but lower salaries Make sure you look at the <b>full package (salary, signing bonus, health care benefits, raises, annual bonus, relocation, stock, promotions, etc)</b> It’s very confusing, and it’s often not clear which company is offering more</li>
<li><b>What about your career options?</b> I can’t give you some magical formula to compute which offer to accept, but here’s what I’d recommend thinking about (in no particular order):
<ul class="org-ul">
<li>Career Path: Make a plan for your career What do you want to do 5, 10 and 15 years out? What skills will you need to develop? Which company or position will help you get there?</li>
<li>Promotion Opportunity: Do you prefer to move into management, or would you prefer to become an increasingly senior developer?</li>
<li>Money and Benefits: Of course, the money matters (but if you’re early in your career, it probably doesn’t matter much). As mentioned above, make sure you look at the full package.</li>
<li>Happiness: Did you like the people? The products? The location? It’s hard to tell, of course, before you work there. What are the options to change teams if you’re unhappy?</li>
<li>Brand Name: The company’s brand name can mean a lot for your future career Some company names will open doors, while others will not as much.</li>
<li><b>What about company stability? Personally, I think it matters much less than most people think. There are so many software companies out there. If you get laid off and need to find a new job, will it be difficult to find a new one? Only you can answer that.</b></li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline17" class="outline-3">
<h3 id="orgheadline17"><span class="section-number-3">5.5</span> Top Ten Mistakes Candidates Make</h3>
<div class="outline-text-3" id="text-5-5">
<ul class="org-ul">
<li>Practicing on a Computer</li>
<li>Not Rehearsing Behavioral Questions</li>
<li>Not Doing a Mock Interview</li>
<li>Trying to Memorize Solutions</li>
<li>Talking Too Much</li>
<li>Talking Too Little</li>
<li>Rushing</li>
<li>Not Debugging</li>
<li>Sloppy Coding</li>
<li>Giving Up</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline18" class="outline-3">
<h3 id="orgheadline18"><span class="section-number-3">5.6</span> Frequently Asked Questions</h3>
<div class="outline-text-3" id="text-5-6">
<p>
<b>Should I tell my interviewer if I know a question?</b>
</p>
<p>
Yes! You should definitely tell your interviewer if you’ve previously heard the question This seems silly to some people - if you already know the question (and answer), you could ace the question, right? Not quite
</p>
<p>
Here’s why we strongly recommend that you tell your interviewer that you’ve heard the question:
</p>
<ol class="org-ol">
<li>Big honesty points. This shows a lot of integrity That’s huge. Remember that the interviewer is evaluating you as a potential teammate I don’t know about you, but I personally prefer to work with honest people!</li>
<li>The question might have changed ever-so-slightly. You don’t want to risk repeating the wrong answer</li>
<li>If you easily belt out the right answer, it’s obvious to the interviewer. They know how hard a problem is supposed to be. It’s very hard to “pretend” to struggle through a question, because you just can’t approach it the same way other candidates do.</li>
</ol>
</div>
</div>
</div>
<div id="outline-container-orgheadline40" class="outline-2">
<h2 id="orgheadline40"><span class="section-number-2">6</span> Interview Questions</h2>
<div class="outline-text-2" id="text-6">
<ul class="org-ul">
<li>Data Structures</li>
<li>Concepts and Algorithms</li>
<li>Knowledge Based</li>
<li>Additional Review Problems</li>
</ul>
</div>
<div id="outline-container-orgheadline20" class="outline-3">
<h3 id="orgheadline20"><span class="section-number-3">6.1</span> Arrays and Strings</h3>
<div class="outline-text-3" id="text-6-1">
<ul class="org-ul">
<li>1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?</li>
<li>1.2 Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.)</li>
<li>1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.</li>
<li>1.4 Write a method to decide if two strings are anagrams or not.</li>
<li>1.5 Write a method to replace all spaces in a string with ‘%20’.</li>
<li>1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees Can you do this in place?</li>
<li>1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.</li>
<li>1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”).</li>
</ul>
<hr />
<p>
1.6
</p>
<div class="org-src-container">
<pre class="src src-C++"><span class="org-type">int</span> <span class="org-variable-name">m</span>[N][N];
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">k</span>=0;k<N/2;k++) {
<span class="org-type">int</span> <span class="org-variable-name">r</span> = k;
<span class="org-type">int</span> <span class="org-variable-name">last</span> = n - 1 - r;
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">c</span> = r; c <= last; c++) {
<span class="org-comment-delimiter">// </span><span class="org-comment">[r,c], [N-1-c,r], [N-1-r,N-1-c], [c,N-1-r]</span>
<span class="org-type">int</span> <span class="org-variable-name">tmp</span> = m[r][c];
m[r][c] = m[c][N-1-r];
m[c][N-1-r] = m[N-1-r][N-1-c];
m[N-1-r][N-1-c] = m[N-1-c][r];
m[N-1-c][r] = tmp;
}
}
</pre>
</div>
</div>
</div>
<div id="outline-container-orgheadline21" class="outline-3">
<h3 id="orgheadline21"><span class="section-number-3">6.2</span> Linked Lists</h3>
<div class="outline-text-3" id="text-6-2">
<p>
Questions:
</p>
<ul class="org-ul">
<li>2.1 Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?</li>
<li>2.2 Implement an algorithm to find the nth to last element of a singly linked list.</li>
<li>2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.</li>
<li>2.4 You have two numbers represented by a linked list, where each node contains a sin- gle digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.</li>
<li><p>
(x) 2.5 Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop.
</p>
<ul class="org-ul">
<li>Assume P,Q at head. P proceeds 1 step, and Q proceed 2 step. There is k nodes before entry node of the circular list. And they takes u step to meet each other at p in the circular list. So we have following equations.
<ol class="org-ol">
<li>k + xn + p= 2u # Q position.</li>
<li>k + yn + p = u # P position.</li>
<li>u = zn # using 1 and 2.</li>
<li>(k + p) = z'n # using 2 and 3.</li>
<li>k % n = (n-p) # done.</li>
</ol></li>
</ul>
<ul class="org-ul">
<li>see leetcode <a href="https://oj.leetcode.com/problems/linked-list-cycle/">https://oj.leetcode.com/problems/linked-list-cycle/</a> and <a href="https://oj.leetcode.com/problems/linked-list-cycle-ii/">https://oj.leetcode.com/problems/linked-list-cycle-ii/</a></li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline22" class="outline-3">
<h3 id="orgheadline22"><span class="section-number-3">6.3</span> Stacks and Queues</h3>
<div class="outline-text-3" id="text-6-3">
<p>
Questions:
</p>
<ul class="org-ul">
<li>3.1 Describe how you could use a single array to implement three stacks.</li>
<li>3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.</li>
<li>3.5 Implement a MyQueue class which implements a queue using two stacks.</li>
<li>3.6 Write a program to sort a stack in ascending order. You should not make any assump- tions about how the stack is implemented.</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline23" class="outline-3">
<h3 id="orgheadline23"><span class="section-number-3">6.4</span> Trees and Graphs</h3>
<div class="outline-text-3" id="text-6-4">
<ul class="org-ul">
<li>Trees
<ul class="org-ul">
<li>Not all binary trees are binary search trees</li>
<li>In-Order: Traverse left node, current node, then right</li>
<li>Pre-Order: Traverse current node, then left node, then right node</li>
<li>Post-Order: Traverse left node, then right node, then current node</li>
<li><b>AVL Tree, RB Tree.</b></li>
<li><b>Construct Tree by using Orders</b></li>
</ul></li>
<li>Graphs
<ul class="org-ul">
<li>Depth First Search</li>
<li>Breadth First Search</li>
<li><b>Dijkstra,Floyd,Prim,Kruskal.</b></li>
</ul></li>
</ul>
<p>
Questions:
</p>
<ul class="org-ul">
<li>4.1 Implement a function to check if a tree is balanced.</li>
<li>4.2 Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.</li>
<li>4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.</li>
<li>4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).</li>
<li>4.5 Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.</li>
<li>4.6 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.</li>
<li>4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hun- dreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.</li>
<li>4.8 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value.</li>
</ul>
<hr />
<p>
4.6
</p>
<div class="org-src-container">
<pre class="src src-C++"><span class="org-type">TreeNode</span>* <span class="org-function-name">ancestor</span>(<span class="org-type">TreeNode</span>* <span class="org-variable-name">root</span>,<span class="org-type">TreeNode</span>* <span class="org-variable-name">p</span>,<span class="org-type">TreeNode</span>* <span class="org-variable-name">q</span>,<span class="org-type">int</span>& <span class="org-variable-name">cond</span>) {
<span class="org-keyword">if</span>(root == <span class="org-constant">NULL</span>) <span class="org-keyword">return</span> <span class="org-constant">NULL</span>;
<span class="org-keyword">if</span>(root == p || root == q) {
cond++; <span class="org-comment-delimiter">// </span><span class="org-comment">root is p or q, find one.</span>
}
<span class="org-comment-delimiter">// </span><span class="org-comment">check left.</span>
<span class="org-type">int</span> <span class="org-variable-name">c</span> = 0;
<span class="org-type">TreeNode</span>* <span class="org-variable-name">t</span> = ancestor(root->left, p, q, c);
<span class="org-keyword">if</span>(c == 2) {
cond = 2;
<span class="org-keyword">return</span> t;
}
cond += c;
<span class="org-keyword">if</span>(cond == 2) {
<span class="org-keyword">return</span> root;
}
<span class="org-comment-delimiter">// </span><span class="org-comment">check right.</span>
c = 0;
t = ancestor(root->right, p, q, c);
<span class="org-keyword">if</span>(c == 2) {
cond = 2;
<span class="org-keyword">return</span> t;
}
cond += c;
<span class="org-keyword">if</span>(cond == 2) {
<span class="org-keyword">return</span> root;
}
<span class="org-comment-delimiter">// </span><span class="org-comment">maybe cover one.</span>
<span class="org-keyword">return</span> root;
}
<span class="org-type">TreeNode</span>* <span class="org-function-name">ancestor</span>(<span class="org-type">TreeNode</span>* <span class="org-variable-name">root</span>, <span class="org-type">TreeNode</span>* <span class="org-variable-name">p</span>, <span class="org-type">TreeNode</span>* <span class="org-variable-name">q</span>) {
<span class="org-type">int</span> <span class="org-variable-name">cond</span>;
<span class="org-keyword">return</span> ancestor(root, p, q, cond);
}
</pre>
</div>
</div>
</div>
<div id="outline-container-orgheadline24" class="outline-3">
<h3 id="orgheadline24"><span class="section-number-3">6.5</span> Bit Manipulation</h3>
<div class="outline-text-3" id="text-6-5">
<div class="figure">
<p><img src="./images/bitop.png" alt="bitop.png" />
</p>
</div>
<p>
Questions:
</p>
<ul class="org-ul">
<li>5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j Write a method to set all bits between i and j in N equal to M. Input: N = 10000000000, M = 10101, i = 2, j = 6. Output: N = 10001010100</li>
<li>5.2 Given a (decimal - e g 3 72) number that is passed in as a string, print the binary rep- resentation If the number can not be represented accurately in binary, print “ERROR”</li>
<li>5.3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.</li>
<li>5.4 Explain what the following code does: ((n & (n-1)) == 0).</li>
<li>5.5 Write a function to determine the number of bits required to convert integer A to integer B.</li>
<li>5.6 Write a program to swap odd and even bits in an integer with as few instructions as possible (e g , bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).</li>
</ul>
<hr />
<p>
5.3
</p>
<div class="org-src-container">
<pre class="src src-C++"><span class="org-preprocessor">#include</span> <span class="org-string"><cstdio></span>
<span class="org-preprocessor">#include</span> <span class="org-string"><cassert></span>
<span class="org-type">int</span> <span class="org-function-name">previous</span>(<span class="org-type">int</span> <span class="org-variable-name">number</span>) {
<span class="org-type">int</span> <span class="org-variable-name">n</span> = number;
<span class="org-type">int</span> <span class="org-variable-name">c1</span> = 0;
<span class="org-type">int</span> <span class="org-variable-name">c0</span> = 0;
<span class="org-comment-delimiter">// </span><span class="org-comment">find 0.</span>
<span class="org-keyword">while</span>(n & 0x1) {
n >>= 1;
c1++;
}
<span class="org-comment-delimiter">// </span><span class="org-comment">find 1.</span>
<span class="org-keyword">while</span>(<span class="org-negation-char">!</span>(n & 0x1)) {
n >>= 1;
c0++;
}
<span class="org-comment-delimiter">// </span><span class="org-comment">rearrange following 1 and 0.</span>
<span class="org-comment-delimiter">// </span><span class="org-comment">10 with c0-1{0} and c1{1}</span>
<span class="org-comment-delimiter">// </span><span class="org-comment">change to 01 c1{1} c0-1{0}</span>
n = ((n >> 1) << 1) + 1;
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">i</span>=0;i<c1;i++) {
n = (n << 1) + 1;
}
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">i</span>=1;i<c0;i++) {
n = (n << 1);
}
<span class="org-keyword">return</span> n;
}
<span class="org-type">int</span> <span class="org-function-name">next</span>(<span class="org-type">int</span> <span class="org-variable-name">number</span>) {
<span class="org-type">int</span> <span class="org-variable-name">n</span> = number;
<span class="org-type">int</span> <span class="org-variable-name">c1</span> = 0;
<span class="org-type">int</span> <span class="org-variable-name">c0</span> = 0;
<span class="org-comment-delimiter">// </span><span class="org-comment">find 1.</span>
<span class="org-keyword">while</span>(<span class="org-negation-char">!</span>(n & 0x1)) {
n >>= 1;
c0++;
}
<span class="org-comment-delimiter">// </span><span class="org-comment">find 0.</span>
<span class="org-keyword">while</span>(n & 0x1) {
n >>= 1;
c1++;
}
<span class="org-comment-delimiter">// </span><span class="org-comment">rearrrange following 1 and 0.</span>
<span class="org-comment-delimiter">// </span><span class="org-comment">change to 1 c0+1{0} c1-1{1}.</span>
n += 1;
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">i</span>=0;i<=c0;i++) {
n = (n << 1);
}
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">i</span>=1;i<c1;i++) {
n = (n << 1) + 1;
}
<span class="org-keyword">return</span> n;
}
<span class="org-type">int</span> <span class="org-function-name">main</span>() {
<span class="org-type">int</span> <span class="org-variable-name">n</span> = (1 << 5) + (1 << 1) + 1;
<span class="org-type">int</span> <span class="org-variable-name">m</span> = (1 << 4) + (1 << 3) + (1 << 2);
assert(previous(n) == m);
assert(next(m) == n);
<span class="org-keyword">return</span> 0;
}
</pre>
</div>
</div>
</div>
<div id="outline-container-orgheadline25" class="outline-3">
<h3 id="orgheadline25"><span class="section-number-3">6.6</span> Brain Teasers</h3>
<div class="outline-text-3" id="text-6-6">
<ul class="org-ul">
<li>Don’t panic when you get a brain teaser. Interviewers want to see how you tackle a problem; they don’t expect you to immediately know the answer. Start talking, and show the inter- viewer how you approach a problem</li>
<li>In many cases, you will also find that the brain teasers have some connection back to funda- mental laws or theories of computer science.</li>
<li>If you’re stuck, we recommend simplifying the problem. Solve it for a small number of items or a special case, and then see if you can generalize it.</li>
</ul>
<p>
Questions:
</p>
<ul class="org-ul">
<li>6.1 Add arithmetic operators (plus, minus, times, divide) to make the following expres- sion true: 3 1 3 6 = 8. You can use any parentheses you’d like.</li>
<li>(x) 6.2 There is an 8x8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?</li>
<li>6.3 You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water?</li>
<li>(x) 6.4 A bunch of men are on an island. A genie comes down and gathers everyone to- gether and places a magical hat on some people’s heads (i e , at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those(and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.</li>
<li>(x) 6.5 There is a building of 100 floors If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs Find N, while minimizing the number of drops for the worst case.
<ul class="org-ul">
<li>dp[t][s][e] = 1 + min{ i=[s,e], max(dp[t-1][s][i-1], dp[t][i+1][e]) }. if(s>e) 0 else if(t==0) e-s+1</li>
<li>#note: not easy to deduce actions from dp</li>
<li>#note: and only one step can be decided. I've attached the code below.</li>
</ul></li>
<li>(x) 6.6 There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e g , he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?
<ul class="org-ul">
<li>only n = p * p have been flipped with odd number and final status is open.</li>
</ul></li>
</ul>
<hr />
<p>
6.5
</p>
<div class="org-src-container">
<pre class="src src-C++"><span class="org-preprocessor">#include</span> <span class="org-string"><cstdio></span>
<span class="org-preprocessor">#include</span> <span class="org-string"><algorithm></span>
<span class="org-keyword">using</span> <span class="org-keyword">namespace</span> <span class="org-constant">std</span>;
<span class="org-keyword">const</span> <span class="org-type">int</span> <span class="org-variable-name">N</span> = 100;
<span class="org-keyword">const</span> <span class="org-type">int</span> <span class="org-variable-name">R</span> = 2;
<span class="org-type">int</span> <span class="org-variable-name">dp</span>[R][N+1][N+1];
<span class="org-type">int</span> <span class="org-function-name">get</span>(<span class="org-type">int</span> <span class="org-variable-name">t</span>,<span class="org-type">int</span> <span class="org-variable-name">s</span>,<span class="org-type">int</span> <span class="org-variable-name">e</span>) {
<span class="org-keyword">if</span>(s>e) <span class="org-keyword">return</span> 0;
<span class="org-keyword">if</span>(dp[t][s][e] != 0) {
<span class="org-keyword">return</span> dp[t][s][e];
}
<span class="org-type">int</span> <span class="org-variable-name">v</span> = -1;
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">i</span>=s;i<=e;i++) {
<span class="org-type">int</span> <span class="org-variable-name">r</span> = 1 + max(get(t,i+1,e),dp[t-1][s][i-1]);
<span class="org-keyword">if</span>(v == -1 || r < v) {
v = r;
}
}
dp[t][s][e] = v;
<span class="org-keyword">return</span> v;
}
<span class="org-type">void</span> <span class="org-function-name">foo</span>() {
memset(dp,0,<span class="org-keyword">sizeof</span>(dp));
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">i</span>=1;i<=N;i++) {
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">j</span>=i;j<=N;j++) {
dp[0][i][j] = (j-i+1);
}
}
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">t</span>=1;t<R;t++) {
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">s</span>=1;s<=N;s++) {
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">e</span>=1;e<=N;e++) {
get(t,s,e);
}
}
}
}
<span class="org-type">void</span> <span class="org-function-name">reverse</span>() {
<span class="org-type">int</span> <span class="org-variable-name">t</span> = R-1;
<span class="org-type">int</span> <span class="org-variable-name">v</span> = dp[t][1][N];
printf(<span class="org-string">"%d\n"</span>,v);
<span class="org-type">int</span> <span class="org-variable-name">s</span> = 1;
<span class="org-type">int</span> <span class="org-variable-name">c</span> = 1;
<span class="org-type">bool</span> <span class="org-variable-name">changed</span> = <span class="org-constant">true</span>;
<span class="org-keyword">while</span>(changed) {
changed = <span class="org-constant">false</span>;
<span class="org-keyword">for</span>(<span class="org-type">int</span> <span class="org-variable-name">i</span>=s;i<=N;i++) {
<span class="org-comment-delimiter">// </span><span class="org-comment">search first point that egg breaks.</span>
<span class="org-comment-delimiter">// </span><span class="org-comment">and to my intuition, there will be only one point.</span>
<span class="org-keyword">if</span>(v == (c + dp[t-1][s][i-1])) {
printf(<span class="org-string">"below %d\n"</span>,i);
s = i+1;
c++;
changed = <span class="org-constant">true</span>;
<span class="org-keyword">break</span>;
}
}
}
}
<span class="org-type">int</span> <span class="org-function-name">main</span>() {
foo();
reverse();
<span class="org-keyword">return</span> 0;
}
</pre>
</div>
</div>
</div>
<div id="outline-container-orgheadline26" class="outline-3">
<h3 id="orgheadline26"><span class="section-number-3">6.7</span> Object Oriented Design</h3>
</div>
<div id="outline-container-orgheadline27" class="outline-3">
<h3 id="orgheadline27"><span class="section-number-3">6.8</span> Recursion</h3>
<div class="outline-text-3" id="text-6-8">
<ul class="org-ul">
<li>All problems that can be solved recursively can also be solved iteratively (though the code may be much more complicated). Before diving into a recursive code, ask yourself how hard it would be to implement this algorithm iteratively. Discuss the trade-offs with your interviewer.</li>
<li>Recursive algorithms can be very space inefficient. Each recursive call adds a new layer to the stack, which means that if your algorithm has O(n) recursive calls then it uses O(n) memory Ouch! This is one reason why an iterative algorithm may be better.</li>
</ul>
<p>
Questions:
</p>
<ul class="org-ul">
<li>8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid The robot can only move in two directions: right and down How many possible paths are there for the robot?
<ul class="org-ul">
<li>Imagine certain squares are “off limits”, such that the robot can not step on them Design an algorithm to get all possible paths for the robot</li>
</ul></li>
<li>8.3 Write a method that returns all subsets of a set.</li>
<li>8.4 Write a method to compute all permutations of a string.</li>
<li>8.5 Implement an algorithm to print all valid (e g , properly opened and closed) combi- nations of n-pairs of parentheses.</li>
<li>8.7 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.</li>
<li>8.8 Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.</li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline28" class="outline-3">
<h3 id="orgheadline28"><span class="section-number-3">6.9</span> Sorting and Searching</h3>
<div class="outline-text-3" id="text-6-9">
<ul class="org-ul">
<li>Bubble Sort</li>
<li>Selection Sort</li>
<li>Merge Sort</li>
<li>Quick Sort</li>
<li>Bucket Sort</li>
<li><b>Binary Search</b></li>
</ul>
<p>
Questions:
</p>
<ul class="org-ul">
<li>(x) 9.1 You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B Write a method to merge B into A in sorted order.</li>
<li>9.3 Given a sorted array of n integers that has been rotated an unknown number of times,give an O(logn) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order. EXAMPLE: Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14) Output: 8 (the index of 5 in the array)</li>
<li>9.4 If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?</li>
<li>9.5 Given a sorted array of strings which is interspersed with empty strings, write a meth- od to find the location of a given string
<ul class="org-ul">
<li>Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4</li>
<li>Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1</li>
</ul></li>
<li>9.6 Given a matrix in which each row and each column is sorted, write a method to find an element in it.</li>
<li>9.7 A circus is designing a tower routine consisting of people standing atop one anoth- er’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of peo- ple in such a tower. EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)</li>
</ul>
<hr />
<p>
9.3
</p>
<div class="org-src-container">
<pre class="src src-C++"><span class="org-preprocessor">#include</span> <span class="org-string"><vector></span>
<span class="org-preprocessor">#include</span> <span class="org-string"><cstdio></span>
<span class="org-keyword">using</span> <span class="org-keyword">namespace</span> <span class="org-constant">std</span>;