-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
1735 lines (1725 loc) · 94.3 KB
/
index.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
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<title>7314c1ac615c86b08296bcb7843f29e6</title>
<script type="text/javascript">
function showhide(id)
{
var e = document.getElementById(id);
e.style.display = (e.style.display == 'block') ? 'none' : 'block';
}
</script>
<style>
rect {
transition: .6s fill;
fill: #D3D3D3;
opacity: 0;
}
rect:hover {
fill: #D3D3D3;
opacity: 0.2;
}
.outline {
clear: both;
}
.svg-container {
width: 100%;
max-width: 1188px;
margin-left: auto;
margin-right: auto;
display: block;
}
.svg-content {
width: 100%;
}
.container {
width: 100%;
}
</style>
</head>
<body>
<div class="container"><div class="spacer"> </div><div class="svg-container"><svg version="1.1" preserveAspectRatio="xMinYMin meet" class="svg-content" viewBox="0 0 1188 1456" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
<image width="1188" height="1456" xlink:href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/V1.0-7314c1ac615c86b08296bcb7843f29e6.png"></image>
</svg>
</div>
</div>
<br/>
<a href="javascript:showhide('outlineDiv')">Outline show/hide</a>
<div id="outlineDiv" style="display:none;">
<h1>V1.0</h1>
<h2>Problems</h2>
<h3>Binary Search (8)</h3>
<ul>
<li>
<p>Classical Binary Search<br />
Link: <a href="https://docs.google.com/document/d/1v2QDhpxkrOzNtHIEfdZstk3YBqp1Me2CAQa7zmVkEQI/edit">docs.google.com/document/d/1v2QDhpxkrOzNtHIEfdZstk3YBqp1Me2CAQa7zmVkEQI/edit</a></p>
<p>Given a target integer T and an integer array A sorted in ascending order, find the index i such that A[i] == T or return -1 if there is no such index.</p>
<p><strong>Assumptions</strong><br />
There can be duplicate elements in the array, and you can return any of the indices i such that A[i] == T.</p>
<p><strong>Examples</strong><br />
A = {1, 2, 3, 4, 5}, T = 3, return 2<br />
A = {1, 2, 3, 4, 5}, T = 6, return -1<br />
A = {1, 2, 2, 2, 3, 4}, T = 2, return 1 or 2 or 3</p>
<p><strong>Corner Cases</strong><br />
What if A is null or A is of zero length? We should return -1 in this case.</p>
<ul>
<li>
<p>ClassicalBinarySearch.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/952FB206-68C0-428A-AB77-0AAC17524725/ClassicalBinarySearch.java">ClassicalBinarySearch.java</a></p>
</li>
<li>
<p>ClassicalBinarySearch.mov<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/C602FE30-1D3E-4055-B9A0-E57E1BC046F1/ClassicalBinarySearch.mov">ClassicalBinarySearch.mov</a></p>
</li>
</ul>
</li>
<li>
<p>Search in Sorted Matrix I<br />
Link: <a href="https://docs.google.com/document/d/1LfLJWW-A8nJNBNbXbI6JpqGS0j5ZdcvLsmzzKGMIixo/edit">docs.google.com/document/d/1LfLJWW-A8nJNBNbXbI6JpqGS0j5ZdcvLsmzzKGMIixo/edit</a></p>
<p>Given a 2D matrix that contains integers only, which each row is sorted in an ascending order. The first element of next row is larger than (or equal to) the last element of previous row.<br />
Given a target number, returning the position that the target locates within the matrix. If the target number does not exist in the matrix, return {-1, -1}.</p>
<p><strong>Assumptions:</strong><br />
The given matrix is not null, and has size of N * M, where N >= 0 and M >= 0.</p>
<p><strong>Examples:</strong><br />
matrix = { {1, 2, 3}, {4, 5, 7}, {8, 9, 10} }<br />
target = 7, return {1, 2}<br />
target = 6, return {-1, -1} to represent the target number does not exist in the matrix.</p>
<ul>
<li>
<p>BinarySearchInSortedMatrixI(2DMappingTrick).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/C1E33C9E-A55C-42D8-84F7-50151EF2A30C/BinarySearchInSortedMatrixI(2DMappingTrick).java">BinarySearchInSortedMatrixI(2DMappingTrick).java</a></p>
</li>
<li>
<p>BinarySearchInSortedArrayI(TwoTimeBinarySearches).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/93BD49CE-1A0A-4607-901E-F47548D7E918/BinarySearchInSortedArrayI(TwoTimeBinarySearches).java">BinarySearchInSortedArrayI(TwoTimeBinarySearches).java</a></p>
</li>
<li>
<p>BinarySearchInSortedMatrix(TwoTimeBinarySearches).mov<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/0D744FEC-B956-4E4E-8291-2CBB135E190F/BinarySearchInSortedMatrix(TwoTimeBinarySearches).mov">BinarySearchInSortedMatrix(TwoTimeBinarySearches).mov</a></p>
</li>
</ul>
</li>
<li>
<p>Closest in Sorted Array<br />
Link: <a href="https://docs.google.com/document/d/1y9LGhGfDkuml4y-rFgBt0RJnqZgCQwELml3Fa3Jtuss/edit">docs.google.com/document/d/1y9LGhGfDkuml4y-rFgBt0RJnqZgCQwELml3Fa3Jtuss/edit</a></p>
<p>Given a target integer T and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to T.</p>
<p><strong>Assumptions</strong><br />
There can be duplicate elements in the array, and we can return any of the indices with same value.</p>
<p><strong>Examples</strong><br />
A = {1, 2, 3}, T = 2, return 1<br />
A = {1, 4, 6}, T = 3, return 1<br />
A = {1, 4, 6}, T = 5, return 1 or 2<br />
A = {1, 3, 3, 4}, T = 2, return 0 or 1 or 2</p>
<p><strong>Corner Cases</strong><br />
What if A is null or A is of zero length? We should return -1 in this case.</p>
<ul>
<li>ClosestInSortedArray.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/6AFFEF78-363D-4362-84A6-9A9DD0647058/ClosestInSortedArray.java">ClosestInSortedArray.java</a></li>
</ul>
</li>
<li>
<p>First Occurrence<br />
Link: <a href="https://docs.google.com/document/d/1I7g_lGkqKeJa-pznuiiOOW2Fg6e5JTQv1JTY_qDUyfs/edit">docs.google.com/document/d/1I7g_lGkqKeJa-pznuiiOOW2Fg6e5JTQv1JTY_qDUyfs/edit</a></p>
<p>Given a target integer T and an integer array A sorted in ascending order, find the index of the first occurrence of T in A or return -1 if there is no such index.</p>
<p><strong>Assumptions</strong><br />
There can be duplicate elements in the array.</p>
<p><strong>Examples</strong><br />
A = {1, 2, 3}, T = 2, return 1<br />
A = {1, 2, 3}, T = 4, return -1<br />
A = {1, 2, 2, 2, 3}, T = 2, return 1</p>
<p><strong>Corner Cases</strong><br />
What if A is null or A of zero length? We should return -1 in this case.</p>
<ul>
<li>FirstOccurence.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/5A7EFB26-B493-44FD-9EB5-4C9E539F7F1E/FirstOccurence.java">FirstOccurence.java</a></li>
</ul>
</li>
<li>
<p>Last Occurrence<br />
Link: <a href="https://docs.google.com/document/d/1uXvSnqtcBEuO5EfZeDpMKoY51Rifn-OEQlAcu0ksbM4/edit">docs.google.com/document/d/1uXvSnqtcBEuO5EfZeDpMKoY51Rifn-OEQlAcu0ksbM4/edit</a></p>
<p>Given a target integer T and an integer array A sorted in ascending order, find the index of the last occurrence of T in A or return -1 if there is no such index.</p>
<p><strong>Assumptions</strong><br />
There can be duplicate elements in the array.</p>
<p><strong>Examples</strong><br />
A = {1, 2, 3}, T = 2, return 1<br />
A = {1, 2, 3}, T = 4, return -1<br />
A = {1, 2, 2, 2, 3}, T = 2, return 3</p>
<p><strong>Corner Cases</strong><br />
What if A is null or A is array of zero length? We should return -1 in this case.</p>
<ul>
<li>LastOccurrence.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/2017323F-ED71-4CFE-810C-3531A86DB7EF/LastOccurrence.java">LastOccurrence.java</a></li>
</ul>
</li>
<li>
<p>K Closest in Sorted<br />
Link: <a href="https://docs.google.com/document/d/1y65IiA6ns_FgMzBzlfCBJFoxPCFz-0wPz7xKaw5cwJs/edit">docs.google.com/document/d/1y65IiA6ns_FgMzBzlfCBJFoxPCFz-0wPz7xKaw5cwJs/edit</a></p>
<p>Given a target integer T, a non-negative integer K and an integer array A sorted in ascending order, find the K closest numbers to T in A.</p>
<p><strong>Assumptions</strong><br />
A is not null<br />
K is guranteed to be >= 0 and K is guranteed to be <= A.length</p>
<p><strong>Return</strong><br />
A size K integer array containing the K closest numbers(not indices) in A, sorted in ascending order by the difference between the number and T. </p>
<p><strong>Examples</strong><br />
A = {1, 2, 3}, T = 2, K = 3, return {2, 1, 3} or {2, 3, 1}<br />
A = {1, 4, 6, 8}, T = 3, K = 3, return {4, 1, 6}</p>
<ul>
<li>KColsestInSortedArray.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/27CB90BB-F23B-4697-AF11-E7A34948471B/KColsestInSortedArray.java">KColsestInSortedArray.java</a></li>
</ul>
</li>
<li>
<p>Smallest Element Larger<br />
Link: <a href="https://docs.google.com/document/d/1WmfB3Ey7Gb4v03ZkFcp9GlYYAbtFh4De00AlyjAz6I0/edit">docs.google.com/document/d/1WmfB3Ey7Gb4v03ZkFcp9GlYYAbtFh4De00AlyjAz6I0/edit</a></p>
<p>Given a target integer T and an integer array A sorted in ascending order, find the index of the smallest element in A that is larger than T or return -1 if there is no such index.</p>
<p><strong>Assumptions</strong><br />
There can be duplicate elements in the array.</p>
<p><strong>Examples</strong><br />
A = {1, 2, 3}, T = 1, return 1<br />
A = {1, 2, 3}, T = 3, return -1<br />
A = {1, 2, 2, 2, 3}, T = 1, return 1</p>
<p><strong>Corner Cases</strong><br />
What if A is null or A of zero length? We should return -1 in this case.</p>
<ul>
<li>SmallestElementLargerThanTarget.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/1D970AFB-5FD4-447F-926E-3DC6CC52BA5F/SmallestElementLargerThanTarget.java">SmallestElementLargerThanTarget.java</a></li>
</ul>
</li>
<li>
<p>Search in Unknown Sized Sorted Array<br />
Link: <a href="https://docs.google.com/document/d/1xW_ayNKuVR-RKwh3Cn3MEyj1O8_1l7y_Bdw0O-mh2VY/edit">docs.google.com/document/d/1xW_ayNKuVR-RKwh3Cn3MEyj1O8_1l7y_Bdw0O-mh2VY/edit</a></p>
<p>Given a integer dictionary A of unknown size, where the numbers in the dictionary are sorted in ascending order, determine if a given target integer T is in the dictionary. Return the index of T in A, return -1 if T is not in A.</p>
<p><strong>Assumptions</strong><br />
dictionary A is not null<br />
dictionary.get(i) will return null(Java)/INT_MIN(C++)/None(Python) if index i is out of bounds</p>
<p><strong>Examples</strong><br />
A = {1, 2, 5, 9, ......}, T = 5, return 2<br />
A = {1, 2, 5, 9, 12, ......}, T = 7, return -1</p>
<ul>
<li>BinarySearchInUnknownSizedSortedArray.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/A6987BB1-0631-4C28-9A0A-59769B48826E/BinarySearchInUnknownSizedSortedArray.java">BinarySearchInUnknownSizedSortedArray.java</a></li>
</ul>
</li>
</ul>
<h3>Recursion I and Sorting (7)</h3>
<ul>
<li>
<p>Fibonacci number Lite<br />
Link: <a href="https://docs.google.com/document/d/1UKIi0zXGjvXBPSAylinzxsSFB6MFqRgDuo5jF6t2eZs/edit">docs.google.com/document/d/1UKIi0zXGjvXBPSAylinzxsSFB6MFqRgDuo5jF6t2eZs/edit</a></p>
<p>Get the Kth number in the Fibonacci Sequence. (K is 0-indexed, the 0th Fibonacci number is 0 and the 1st Fibonacci number is 1).</p>
<p><strong>Examples</strong><br />
0th fibonacci number is 0<br />
1st fibonacci number is 1<br />
2nd fibonacci number is 1<br />
3rd fibonacci number is 2<br />
6th fibonacci number is 8</p>
<p><strong>Corner Cases</strong><br />
What if K < 0? in this case, we should always return 0.<br />
Is it possible the result fibonacci number is overflowed? We can assume it will not be overflowed when we solve this problem on this online judge, but we should also know that it is possible to get an overflowed number, and sometimes we will need to use something like BigInteger.</p>
<ul>
<li>FibonacciLite.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/BF675BA2-2B7D-45F8-910C-F967CB686EF3/FibonacciLite.java">FibonacciLite.java</a></li>
</ul>
</li>
<li>
<p>a to the power of b<br />
Link: <a href="https://docs.google.com/document/d/1X9CSnX9KKMbfKEPTvZjqHhPsxvf8dyjSs5oFOFJJXKc/edit">docs.google.com/document/d/1X9CSnX9KKMbfKEPTvZjqHhPsxvf8dyjSs5oFOFJJXKc/edit</a></p>
<p>Evaluate a to the power of b, assuming both a and b are integers and b is non-negative.</p>
<p><strong>Examples</strong><br />
power(2, 0) = 1<br />
power(2, 3) = 8<br />
power(0, 10) = 0<br />
power(-2, 5) = -32</p>
<p><strong>Corner Cases</strong><br />
In this question, we assume 0^0 = 1.<br />
What if the result is overflowed? We can assume the result will not be overflowed when we solve this problem on this online judge.</p>
<ul>
<li>aToThePowerOfb.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/64913206-319C-496E-87DE-85D96184245F/aToThePowerOfb.java">aToThePowerOfb.java</a></li>
</ul>
</li>
<li>
<p>Selection Sort<br />
Link: <a href="https://docs.google.com/document/d/12j6uEC3a9B13vwCSQg_ubg5dqNAty3YW5Ga508OY0r4/edit">docs.google.com/document/d/12j6uEC3a9B13vwCSQg_ubg5dqNAty3YW5Ga508OY0r4/edit</a></p>
<p>Given an array of integers, sort the elements in the array in ascending order. The selection sort algorithm should be used to solve this problem.</p>
<p><strong>Examples</strong><br />
{1} is sorted to {1}<br />
{1, 2, 3} is sorted to {1, 2, 3}<br />
{3, 2, 1} is sorted to {1, 2, 3}<br />
{4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}</p>
<p><strong>Corner Cases</strong><br />
What if the given array is null? In this case, we do not need to do anything.<br />
What if the given array is of length zero? In this case, we do not need to do anything.</p>
<ul>
<li>SelectionSort.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/B55FD048-F573-46BF-8E8A-94F62B825689/SelectionSort.java">SelectionSort.java</a></li>
</ul>
</li>
<li>
<p>Merge Sort<br />
Link: <a href="https://docs.google.com/document/d/1uQSk_2T1ndTBrWdNDwDPddlSN_kOlIzYmy6wUI7pVbA/edit">docs.google.com/document/d/1uQSk_2T1ndTBrWdNDwDPddlSN_kOlIzYmy6wUI7pVbA/edit</a></p>
<p>Given an array of integers, sort the elements in the array in ascending order. The merge sort algorithm should be used to solve this problem.</p>
<p><strong>Examples</strong><br />
{1} is sorted to {1}<br />
{1, 2, 3} is sorted to {1, 2, 3}<br />
{3, 2, 1} is sorted to {1, 2, 3}<br />
{4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}</p>
<p><strong>Corner Cases</strong><br />
What if the given array is null? In this case, we do not need to do anything.<br />
What if the given array is of length zero? In this case, we do not need to do anything.</p>
<ul>
<li>
<p>MergeSort.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/6EB6214F-54B9-4981-A2BC-EED1EF97FDF4/MergeSort.java">MergeSort.java</a></p>
</li>
<li>
<p>MergeSort.mov<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/209D118C-3BF2-4AFC-9427-B53FCA350217/MergeSort.mov">MergeSort.mov</a></p>
</li>
</ul>
</li>
<li>
<p>Quick Sort<br />
Link: <a href="https://docs.google.com/document/d/1YwNOW-SgM0Q2niReOoXB9awK-8jc-VOkh-hAlA_HH-E/edit">docs.google.com/document/d/1YwNOW-SgM0Q2niReOoXB9awK-8jc-VOkh-hAlA_HH-E/edit</a></p>
<p>Given an array of integers, sort the elements in the array in ascending order. The quick sort algorithm should be used to solve this problem.</p>
<p><strong>Examples</strong><br />
{1} is sorted to {1}<br />
{1, 2, 3} is sorted to {1, 2, 3}<br />
{3, 2, 1} is sorted to {1, 2, 3}<br />
{4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}</p>
<p><strong>Corner Cases</strong><br />
What if the given array is null? In this case, we do not need to do anything.<br />
What if the given array is of length zero? In this case, we do not need to do anything.</p>
<ul>
<li>QuickSort.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/5EED390C-E396-4123-9CF3-B4104E5F9BFA/QuickSort.java">QuickSort.java</a></li>
</ul>
</li>
<li>
<p>Move 0s to the End I<br />
Link: <a href="https://docs.google.com/document/d/1uiGwdDyAeFsOPL6k-KRRRgA_6956PMymdOxXLXeNOfg/edit">docs.google.com/document/d/1uiGwdDyAeFsOPL6k-KRRRgA_6956PMymdOxXLXeNOfg/edit</a></p>
<p>Given an array of integers, move all the 0s to the right end of the array.<br />
The relative order of the elements in the original array does not need to be maintained.</p>
<p><strong>Assumptions:</strong><br />
The given array is not null.</p>
<p><strong>Examples:</strong><br />
{1} --> {1}<br />
{1, 0, 3, 0, 1} --> {1, 3, 1, 0, 0} or {1, 1, 3, 0, 0} or {3, 1, 1, 0, 0}</p>
<ul>
<li>Move0sToTheEndI.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/B5F874C1-1E8D-4668-94DC-750124F2F389/Move0sToTheEndI.java">Move0sToTheEndI.java</a></li>
</ul>
</li>
<li>
<p>Rainbow Sort<br />
Link: <a href="https://docs.google.com/document/d/1ODKG74bLYOaD2iRPrljEqoR8OHP8Aeis6s57M8NHk9Q/edit">docs.google.com/document/d/1ODKG74bLYOaD2iRPrljEqoR8OHP8Aeis6s57M8NHk9Q/edit</a></p>
<p>Given an array of balls, where the color of the balls can only be Red, Green or Blue, sort the balls such that all the Red balls are grouped on the left side, all the Green balls are grouped in the middle and all the Blue balls are grouped on the right side. (Red is denoted by -1, Green is denoted by 0, and Blue is denoted by 1).</p>
<p><strong>Examples</strong><br />
{0} is sorted to {0}<br />
{1, 0} is sorted to {0, 1}<br />
{1, 0, 1, -1, 0} is sorted to {-1, 0, 0, 1, 1}</p>
<p><strong>Assumptions</strong><br />
The input array is not null.</p>
<p><strong>Corner Cases</strong><br />
What if the input array is of length zero? In this case, we should not do anything as well.</p>
<ul>
<li>RainbowSort.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/C212E33F-B1EA-42F1-94E8-54B8CD9DA1A0/RainbowSort.java">RainbowSort.java</a></li>
</ul>
</li>
</ul>
<h3>Linked List (12)</h3>
<ul>
<li>
<p>Reverse Linked List</p>
<p>Reverse a singly-linked list.</p>
<p><strong>Examples</strong><br />
L = null, return null<br />
L = 1 -> null, return 1 -> null<br />
L = 1 -> 2 -> 3 -> null, return 3 -> 2 -> 1 -> null</p>
<ul>
<li>
<p>ReverseLinkedList(Iterative).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/2874B5B5-D868-43AF-AC81-ADA8D3810167/ReverseLinkedList(Iterative).java">ReverseLinkedList(Iterative).java</a><br />
Link: <a href="https://docs.google.com/document/d/1UfZzoduarCbtGz6KoBkbmL7FJFrQ-NqvHUIgWUPV2j8/edit">docs.google.com/document/d/1UfZzoduarCbtGz6KoBkbmL7FJFrQ-NqvHUIgWUPV2j8/edit</a></p>
</li>
<li>
<p>ReverseLinkedList(Recursive).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/3A62F26A-B952-40B3-834D-5430841F9CD6/ReverseLinkedList(Recursive).java">ReverseLinkedList(Recursive).java</a><br />
Link: <a href="https://docs.google.com/document/d/1lVkUxg4s-3x_ZZaEnL855d4nn6uBxM7jV9HSwTu2ok0/edit">docs.google.com/document/d/1lVkUxg4s-3x_ZZaEnL855d4nn6uBxM7jV9HSwTu2ok0/edit</a></p>
<ul>
<li>ReverseLinkedList(Recursive).mov<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/5490F6AB-256E-4F66-BFE5-3AB9415E08B0/ReverseLinkedList(Recursive).mov">ReverseLinkedList(Recursive).mov</a></li>
</ul>
</li>
</ul>
</li>
<li>
<p>Middle Node of Linked List<br />
Link: <a href="https://docs.google.com/document/d/1G2DWEEd5f2ium9rhTQDvJvQmgDLl8kWmRT2-GUbsii0/edit">docs.google.com/document/d/1G2DWEEd5f2ium9rhTQDvJvQmgDLl8kWmRT2-GUbsii0/edit</a></p>
<p>Find the middle node of a given linked list.</p>
<p><strong>Examples</strong><br />
L = null, return null<br />
L = 1 -> null, return 1<br />
L = 1 -> 2 -> null, return 1<br />
L = 1 -> 2 -> 3 -> null, return 2<br />
L = 1 -> 2 -> 3 -> 4 -> null, return 2</p>
<ul>
<li>FindMiddleNodeOfLinkedList.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/06A0E497-284B-444B-9A14-52C794D2A251/FindMiddleNodeOfLinkedList.java">FindMiddleNodeOfLinkedList.java</a></li>
</ul>
</li>
<li>
<p>Check If Linked List Has a Cycle<br />
Link: <a href="https://docs.google.com/spreadsheets/d/1DxUnGdTDhr3IOCP5-D2d5GXLuRVfeRG8BvF9xbHXNgo/edit#gid=0">docs.google.com/spreadsheets/d/1DxUnGdTDhr3IOCP5-D2d5GXLuRVfeRG8BvF9xbHXNgo/edit#gid=0</a></p>
<p>Check if a given linked list has a cycle. Return true if it does, otherwise return false.<br />
<br />
Assumption:<br />
You can assume there is no duplicate value appear in the linked list.</p>
<ul>
<li>CheckIfLinkedListHasACycle.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/94FA9AEB-25D9-4659-9A95-CD488536E6A5/CheckIfLinkedListHasACycle.java">CheckIfLinkedListHasACycle.java</a></li>
</ul>
</li>
<li>
<p>Insert in Sorted Linked List<br />
Link: <a href="https://docs.google.com/document/d/1Fya02WNyCBxpyYpRI7ZH2GWL6_DLDJpj7zv0BwTFZpo/edit">docs.google.com/document/d/1Fya02WNyCBxpyYpRI7ZH2GWL6_DLDJpj7zv0BwTFZpo/edit</a></p>
<p>Insert a value in a sorted linked list.</p>
<p><strong>Examples</strong><br />
L = null, insert 1, return 1 -> null<br />
L = 1 -> 3 -> 5 -> null, insert 2, return 1 -> 2 -> 3 -> 5 -> null<br />
L = 1 -> 3 -> 5 -> null, insert 3, return 1 -> 3 -> 3 -> 5 -> null<br />
L = 2 -> 3 -> null, insert 1, return 1 -> 2 -> 3 -> null</p>
<ul>
<li>InsertInSortedLinkedList.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/9B0B8076-8E7E-48C2-8C0D-84252B728069/InsertInSortedLinkedList.java">InsertInSortedLinkedList.java</a></li>
</ul>
</li>
<li>
<p>Merge Two Sorted Linked Lists<br />
Link: <a href="https://docs.google.com/document/d/1u4hzGDAHyKwYcCCZOzundrbL8OC1KYpIufeSLhjXs7U/edit">docs.google.com/document/d/1u4hzGDAHyKwYcCCZOzundrbL8OC1KYpIufeSLhjXs7U/edit</a></p>
<p>Merge two sorted lists into one large sorted list.</p>
<p><strong>Examples</strong><br />
L1 = 1 -> 4 -> 6 -> null, L2 = 2 -> 5 -> null, merge L1 and L2 to 1 -> 2 -> 4 -> 5 -> 6 -> null<br />
L1 = null, L2 = 1 -> 2 -> null, merge L1 and L2 to 1 -> 2 -> null<br />
L1 = null, L2 = null, merge L1 and L2 to null</p>
<ul>
<li>MergeTwoSortedLinkedList.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/3F8E95C1-8696-48C6-B4FA-50385B26ADAD/MergeTwoSortedLinkedList.java">MergeTwoSortedLinkedList.java</a></li>
</ul>
</li>
<li>
<p>ReOrder Linked List<br />
Link: <a href="https://docs.google.com/document/d/1k74ak7BpoEy60J5hXx0xQApuxUjI5LW8skN5VvPXIYw/edit">docs.google.com/document/d/1k74ak7BpoEy60J5hXx0xQApuxUjI5LW8skN5VvPXIYw/edit</a></p>
<p>Reorder the given singly-linked list N1 -> N2 -> N3 -> N4 -> … -> Nn -> null to be N1- > Nn -> N2 -> Nn-1 -> N3 -> Nn-2 -> … -> null</p>
<p><strong>Examples</strong><br />
L = null, is reordered to null<br />
L = 1 -> null, is reordered to 1 -> null<br />
L = 1 -> 2 -> 3 -> 4 -> null, is reordered to 1 -> 4 -> 2 -> 3 -> null<br />
L = 1 -> 2 -> 3 -> null, is reordred to 1 -> 3 -> 2 -> null</p>
<ul>
<li>ReorderLinkedList.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/48A21B5A-5C5B-41EF-94D7-F5F3622AE6C4/ReorderLinkedList.java">ReorderLinkedList.java</a></li>
</ul>
</li>
<li>
<p>Partition Linked List<br />
Link: <a href="https://docs.google.com/document/d/1vidX-QF_vgU7GHPi_2HR2nX1cNcIpbpYIVyTL5aVt1o/edit#">docs.google.com/document/d/1vidX-QF_vgU7GHPi_2HR2nX1cNcIpbpYIVyTL5aVt1o/edit#</a></p>
<p>Given a linked list and a target value T, partition it such that all nodes less than T are listed before the nodes larger than or equal to target value T. The original relative order of the nodes in each of the two partitions should be preserved.</p>
<p><strong>Examples</strong><br />
L = 2 -> 4 -> 3 -> 5 -> 1 -> null, T = 3, is partitioned to 2 -> 1 -> 4 -> 3 -> 5 -> null</p>
<ul>
<li>PartitionLinkedList.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/7F653FC8-8E72-455E-AEE8-D820218A3B40/PartitionLinkedList.java">PartitionLinkedList.java</a></li>
</ul>
</li>
<li>
<p>Merge Sort Linked List<br />
Link: <a href="https://docs.google.com/document/d/1HVQAZclbKwc-zvolzAZzwYhRj0BN07aUTwRinU3idvc/edit">docs.google.com/document/d/1HVQAZclbKwc-zvolzAZzwYhRj0BN07aUTwRinU3idvc/edit</a></p>
<p>Given a singly-linked list, where each node contains an integer value, sort it in ascending order. The merge sort algorithm should be used to solve this problem.</p>
<p><strong>Examples</strong><br />
null, is sorted to null<br />
1 -> null, is sorted to 1 -> null<br />
1 -> 2 -> 3 -> null, is sorted to 1 -> 2 -> 3 -> null<br />
4 -> 2 -> 6 -> -3 -> 5 -> null, is sorted to -3 -> 2 -> 4 -> 5 -> 6</p>
<ul>
<li>MergeSortLinkedList.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/47189D67-49E0-4BE1-826C-311D00FC6C28/MergeSortLinkedList.java">MergeSortLinkedList.java</a></li>
</ul>
</li>
<li>
<p>Add Two Numbers<br />
Link: <a href="https://docs.google.com/document/d/15VTkcZMAzdgE5mt6TIO_vU0AU9xyBWRcwZgxkZ4XH98/edit">docs.google.com/document/d/15VTkcZMAzdgE5mt6TIO_vU0AU9xyBWRcwZgxkZ4XH98/edit</a></p>
<p>You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. </p>
<p><strong>Example</strong><br />
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)<br />
Output: 7 -> 0 -> 8</p>
<ul>
<li>AddTwoNumbers.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/4C5D3978-DAD1-42AC-B541-1E048907B090/AddTwoNumbers.java">AddTwoNumbers.java</a></li>
</ul>
</li>
<li>
<p>Check If Linked List is Palindrome<br />
Link: <a href="https://docs.google.com/document/d/15ffQzrg7HtnfCiOAqbp6wyHxgbNDIfbgNPs9mYRNFlE/edit">docs.google.com/document/d/15ffQzrg7HtnfCiOAqbp6wyHxgbNDIfbgNPs9mYRNFlE/edit</a></p>
<p>Given a linked list, check whether it is a palindrome.</p>
<p><strong>Examples:</strong><br />
Input: 1 -> 2 -> 3 -> 2 -> 1 -> null<br />
output: true.<br />
Input: 1 -> 2 -> 3 -> null <br />
output: false.</p>
<p><strong>Requirements:</strong><br />
Space complexity must be O(1)</p>
<ul>
<li>CheckIfLinekdListIsPalindrome.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/804118AF-1721-421B-809D-5F617070A573/CheckIfLinekdListIsPalindrome.java">CheckIfLinekdListIsPalindrome.java</a></li>
</ul>
</li>
<li>
<p>Remove Linked List Elements<br />
Link: <a href="https://docs.google.com/document/d/1rNMLF1jzjIEzqtCcaa5MoI_pWTkw8NhHW8IAdeHONTQ/edit">docs.google.com/document/d/1rNMLF1jzjIEzqtCcaa5MoI_pWTkw8NhHW8IAdeHONTQ/edit</a></p>
<p>Remove all elements from a linked list of integers that have value <strong><em>val</em></strong>.</p>
<p><strong>Example</strong><br />
<strong><em>Given:</em></strong> 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, <strong><em>val</em></strong> = 6<br />
<strong><em>Return:</em></strong> 1 --> 2 --> 3 --> 4 --> 5</p>
<ul>
<li>RemoveLinkedListElements.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/2FF889FC-FF92-4E59-B94E-6BEDF3FC47D6/RemoveLinkedListElements.java">RemoveLinkedListElements.java</a></li>
</ul>
</li>
</ul>
<h3>Queue & Stack (5)</h3>
<ul>
<li>
<p>Sort With 2 Stacks<br />
Link: <a href="https://docs.google.com/document/d/1GjvzvGGOwBvYVnBG6dWKlPmeyTJhLT5nFEeHukn4kZk/edit">docs.google.com/document/d/1GjvzvGGOwBvYVnBG6dWKlPmeyTJhLT5nFEeHukn4kZk/edit</a></p>
<p>Given an array that is initially stored in one stack, sort it with one additional stacks (total 2 stacks).<br />
After sorting the original stack should contain the sorted integers and from top to bottom the integers are sorted in ascending order.</p>
<p><strong>Assumptions:</strong><br />
The given stack is not null.<br />
There can be duplicated numbers in the give stack.</p>
<p><strong>Requirements:</strong><br />
No additional memory, time complexity = O(n ^ 2).</p>
<ul>
<li>SortWithTwoStacks.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/0EFA3971-1DE0-4141-91D4-8C1A980E3F0A/SortWithTwoStacks.java">SortWithTwoStacks.java</a></li>
</ul>
</li>
<li>
<p>Queue by Two Stacks<br />
Link: <a href="https://docs.google.com/document/d/1znufTCzh1jcuDQNLQf7VZJ13X-649aoXnmk40C93_6w/edit">docs.google.com/document/d/1znufTCzh1jcuDQNLQf7VZJ13X-649aoXnmk40C93_6w/edit</a></p>
<p>Implement a queue by using two stacks. The queue should provide size(), isEmpty(), offer(), poll() and peek() operations. When the queue is empty, poll() and peek() should return null.</p>
<p><strong>Assumptions</strong><br />
The elements in the queue are all Integers.<br />
size() should return the number of elements buffered in the queue.<br />
isEmpty() should return true if there is no element buffered in the queue, false otherwise.</p>
<ul>
<li>QueueByTwoStacks.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/A8E402F1-0FA2-4382-8A2C-D3FDC3BABA9C/QueueByTwoStacks.java">QueueByTwoStacks.java</a></li>
</ul>
</li>
<li>
<p>Stack with min( )<br />
Link: <a href="https://docs.google.com/document/d/1ZchtSyimS7-tSs9IG7CsE02tAZg1wSe8zCpX2OumLEg/edit">docs.google.com/document/d/1ZchtSyimS7-tSs9IG7CsE02tAZg1wSe8zCpX2OumLEg/edit</a></p>
<p>Enhance the stack implementation to support min() operation. min() should return the current minimum value in the stack. If the stack is empty, min() should return -1.</p>
<p>push(int element) - push the element to top<br />
pop() - return the top element and remove it, if the stack is empty, return -1<br />
top() - return the top element without remove it, if the stack is empty, return -1<br />
min() - return the current min value in the stack.</p>
<ul>
<li>StackWithMin().java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/5BADB6B8-570F-47D6-B090-66B961FAE8A2/StackWithMin().java">StackWithMin().java</a></li>
</ul>
</li>
<li>
<p>Stack by Queue(s)</p>
<p>Implement a stack containing integers using queue(s). The stack should provide push(x), pop(), top() and isEmpty() operations.</p>
<p>If the stack is empty, then top() and pop() will return null.</p>
<ul>
<li>StackByQueue.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/BF67AB19-36AA-489A-9FF5-42166AC005F1/StackByQueue.java">StackByQueue.java</a></li>
</ul>
</li>
<li>
<p>Deque by Three Stacks<br />
Link: <a href="https://docs.google.com/document/d/1n-PdZSQfT5TYEWpRk7IPsKlJyPf0GAU3kadzi21fRdU/edit">docs.google.com/document/d/1n-PdZSQfT5TYEWpRk7IPsKlJyPf0GAU3kadzi21fRdU/edit</a></p>
<p>Implement a deque by using three stacks. The queue should provide size(), isEmpty(), offerFirst(), offerLast(), pollFirst(), pollLast(), peekFirst() and peekLast() operations. When the queue is empty, pollFirst(), pollLast(), peekFirst() and peek() should return null.</p>
<p><strong>Assumptions</strong><br />
The elements in the queue are all Integers.<br />
size() should return the number of elements buffered in the queue.<br />
isEmpty() should return true if there is no element buffered in the queue, false otherwise.<br />
The amortized time complexity of all operations should be O(1).</p>
<ul>
<li>DequeByThreeStacks.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/E453E70B-44A4-4C3B-9782-96FF903CB4A6/DequeByThreeStacks.java">DequeByThreeStacks.java</a></li>
</ul>
</li>
</ul>
<h3>Tree & Binary Search Tree (15)</h3>
<ul>
<li>
<p>Pre-order Traversal of Binary Tree</p>
<p>Implement a recursive, pre-order traversal of a given binary tree, return the list of keys of each node in the tree as it is pre-order traversed.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
Pre-order traversal is [5, 3, 1, 4, 8, 11]</p>
<p><strong>Corner Cases</strong><br />
What if the given binary tree is null? Return an empty list in this case.</p>
<ul>
<li>
<p>PreOrderTraversalOfBinaryTree(Iterative).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/EE3D8394-942F-4DAC-95E6-6AF84806CFF1/PreOrderTraversalOfBinaryTree(Iterative).java">PreOrderTraversalOfBinaryTree(Iterative).java</a><br />
Link: <a href="https://docs.google.com/document/d/1sskAbjggI5Y2WOcAOy_ozxJoKUA9JUs0gMM4U5v7vNE/edit">docs.google.com/document/d/1sskAbjggI5Y2WOcAOy_ozxJoKUA9JUs0gMM4U5v7vNE/edit</a></p>
</li>
<li>
<p>PreOrderTraversalOfBinaryTree(Recursive).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/2480D29D-C46F-4E10-8402-8EC2A1945576/PreOrderTraversalOfBinaryTree(Recursive).java">PreOrderTraversalOfBinaryTree(Recursive).java</a><br />
Link: <a href="https://docs.google.com/document/d/1kJrGjUA9LXwPzhU79g3PLh1pZQB8D6PwlMRpMRVGI0w/edit">docs.google.com/document/d/1kJrGjUA9LXwPzhU79g3PLh1pZQB8D6PwlMRpMRVGI0w/edit</a></p>
</li>
</ul>
</li>
<li>
<p>In-order Traversal of Binary Tree</p>
<p>Implement a recursive, in-order traversal of a given binary tree, return the list of keys of each node in the tree as it is in-order traversed.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
In-order traversal is [1, 3, 4, 5, 8, 11]</p>
<p><strong>Corner Cases</strong><br />
What if the given binary tree is null? Return an empty list in this case.</p>
<ul>
<li>
<p>InOrderTraversalOfBinaryTree(Iterative).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/F6BF5DDC-8079-4DEE-9DB0-929A251B222F/InOrderTraversalOfBinaryTree(Iterative).java">InOrderTraversalOfBinaryTree(Iterative).java</a><br />
Link: <a href="https://docs.google.com/document/d/1WLpWtt-QI8fT1bXV-mIV0CTYbsKAPQ6D0XJ3AMIEWOw/edit">docs.google.com/document/d/1WLpWtt-QI8fT1bXV-mIV0CTYbsKAPQ6D0XJ3AMIEWOw/edit</a></p>
</li>
<li>
<p>InOrderTraversalOfBinaryTree(Recursive).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/FABDF6F1-8C11-423E-A8B8-599AC3D9A7C6/InOrderTraversalOfBinaryTree(Recursive).java">InOrderTraversalOfBinaryTree(Recursive).java</a><br />
Link: <a href="https://docs.google.com/document/d/10_KNnKz7O1MSSbbfnPh0ZWZS_SYiwR_vnjtrW24MfgY/edit">docs.google.com/document/d/10_KNnKz7O1MSSbbfnPh0ZWZS_SYiwR_vnjtrW24MfgY/edit</a></p>
</li>
</ul>
</li>
<li>
<p>Post-order Traversal of Binary Tree</p>
<p>Implement a recursive, post-order traversal of a given binary tree, return the list of keys of each node in the tree as it is post-order traversed.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
Post-order traversal is [1, 4, 3, 11, 8, 5]</p>
<p><strong>Corner Cases</strong><br />
What if the given binary tree is null? Return an empty list in this case.</p>
<ul>
<li>
<p>PostOrderTraversalOfBinaryTree(Recursive).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/196A58C2-9E2E-4F9B-90D4-82A7F5A98DBA/PostOrderTraversalOfBinaryTree(Recursive).java">PostOrderTraversalOfBinaryTree(Recursive).java</a><br />
Link: <a href="https://docs.google.com/document/d/1kTcjehJMOIUoc6L0Ro3AYieTnDcByBl5cM98CAmbOXg/edit">docs.google.com/document/d/1kTcjehJMOIUoc6L0Ro3AYieTnDcByBl5cM98CAmbOXg/edit</a></p>
</li>
<li>
<p>PostOrderTraversalOfBinaryTree(Iterative).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/C47A48CF-C7A5-45FB-BD88-5B9BFE977772/PostOrderTraversalOfBinaryTree(Iterative).java">PostOrderTraversalOfBinaryTree(Iterative).java</a><br />
Link: <a href="https://docs.google.com/document/d/1I_-HD0wRgdu8YNu69zVXvNN6iRc7gVwbBFfYwNXMmhw/edit">docs.google.com/document/d/1I_-HD0wRgdu8YNu69zVXvNN6iRc7gVwbBFfYwNXMmhw/edit</a></p>
</li>
</ul>
</li>
<li>
<p>Height of Binary Tree<br />
Link: <a href="https://docs.google.com/document/d/1NJx6s3C8CG-iObVEAY5e7W0GGeiBAkofNVTXDF2vrgI/edit">docs.google.com/document/d/1NJx6s3C8CG-iObVEAY5e7W0GGeiBAkofNVTXDF2vrgI/edit</a></p>
<p>Find the height of binary tree.</p>
<p><strong>Examples:</strong><br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
The height of above binary tree is 3.</p>
<ul>
<li>HeightOfBinaryTree.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/6C025262-EAD6-4AA8-AA08-AB7C3FE85D64/HeightOfBinaryTree.java">HeightOfBinaryTree.java</a></li>
</ul>
</li>
<li>
<p>Check If Binary Tree is Balanced<br />
Link: <a href="https://docs.google.com/document/d/1NNmU3tOsNevsOyS0h_1hCy1n3hD6v9nautxda8TbMIY/edit">docs.google.com/document/d/1NNmU3tOsNevsOyS0h_1hCy1n3hD6v9nautxda8TbMIY/edit</a></p>
<p>Check if a given binary tree is balanced. A balanced binary tree is one in which the depths of every node’s left and right subtree differ by at most 1.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
is balanced binary tree,<br />
5<br />
/<br />
3<br />
/ \<br />
1 4<br />
is not balanced binary tree.</p>
<p><strong>Corner Cases</strong><br />
What if the binary tree is null? Return true in this case.</p>
<ul>
<li>CheckIfBinaryTreeIsBalanced.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/501927F1-B8A7-4B55-93C9-4121A8ACF7ED/CheckIfBinaryTreeIsBalanced.java">CheckIfBinaryTreeIsBalanced.java</a></li>
</ul>
</li>
<li>
<p>Symmetric Binary Tree<br />
Link: <a href="https://docs.google.com/document/d/1Om5ENnHPJGFA-ZbTJD2H-RVqF5N14NrP1Ut6YtCZCl4/edit">docs.google.com/document/d/1Om5ENnHPJGFA-ZbTJD2H-RVqF5N14NrP1Ut6YtCZCl4/edit</a></p>
<p>Check if a given binary tree is symmetric.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 3<br />
/ \ / \<br />
1 4 4 1<br />
is symmetric.<br />
5<br />
/ \<br />
3 3<br />
/ \ / \<br />
1 4 1 4<br />
is not symmetric.</p>
<p><strong>Corner Cases</strong><br />
What if the binary tree is null? Return true in this case.</p>
<ul>
<li>SymmetricBinaryTree.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/18D714FB-2505-4B28-BD23-8BF87E664477/SymmetricBinaryTree.java">SymmetricBinaryTree.java</a></li>
</ul>
</li>
<li>
<p>Tweaked Identical Binary Trees<br />
Link: <a href="https://docs.google.com/document/d/19p7-MB4vyJGsbBfhbmBRPYcZAobZ_RmnWXOBaITH-7o/edit">docs.google.com/document/d/19p7-MB4vyJGsbBfhbmBRPYcZAobZ_RmnWXOBaITH-7o/edit</a></p>
<p>Determine whether two given binary trees are identical assuming any number of ‘tweak’s are allowed. A tweak is defined as a swap of the children of one node in the tree.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \<br />
1 4<br />
and<br />
5<br />
/ \<br />
8 3<br />
/ \<br />
1 4<br />
the two binary trees are tweaked identical.</p>
<ul>
<li>TweakedIdenticalBinaryTree.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/E5A4D2F9-4A2C-4057-B5A8-518592F5CA96/TweakedIdenticalBinaryTree.java">TweakedIdenticalBinaryTree.java</a></li>
</ul>
</li>
<li>
<p>Is Binary Search Tree or Not<br />
Link: <a href="https://docs.google.com/document/d/1DGact6-7roZQkpUM4kqA0zEUC00iLCRGFOilYxWs_AE/edit">docs.google.com/document/d/1DGact6-7roZQkpUM4kqA0zEUC00iLCRGFOilYxWs_AE/edit</a></p>
<p>Determine if a given binary tree is binary search tree.There should no be duplicate keys in binary search tree.</p>
<p><strong>Assumptions</strong><br />
You can assume the keys stored in the binary search tree can not be Integer.MIN_VALUE or Integer.MAX_VALUE.</p>
<p><strong>Corner Cases</strong><br />
What if the binary tree is null? Return true in this case.</p>
<ul>
<li>IsBinarySearchTreeOrNot.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/5D51D760-1164-4377-8B09-020067D3F549/IsBinarySearchTreeOrNot.java">IsBinarySearchTreeOrNot.java</a></li>
</ul>
</li>
<li>
<p>Get Keys in Binary Search Tree in Given Range<br />
Link: <a href="https://docs.google.com/document/d/1B0UIkrhQ4WPGH1EeQgMP4stg9B9BdyzhYMK7XskxqIs/edit">docs.google.com/document/d/1B0UIkrhQ4WPGH1EeQgMP4stg9B9BdyzhYMK7XskxqIs/edit</a></p>
<p>Get the list of keys in a given binary search tree in a given range[min, max] in ascending order, both min and max are inclusive.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
get the keys in [2, 5] in ascending order, result is [3, 4, 5]</p>
<p><strong>Corner Cases</strong><br />
What if there are no keys in the given range? Return an empty list in this case.</p>
<ul>
<li>GetKeysInBinarySearchTreeInGivenRange.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/2A2A1DA3-0C23-41A1-BFF1-1D712B4FEE05/GetKeysInBinarySearchTreeInGivenRange.java">GetKeysInBinarySearchTreeInGivenRange.java</a></li>
</ul>
</li>
<li>
<p>Search in Binary Search Tree<br />
Link: <a href="https://docs.google.com/document/d/1MrSBES7ilpSrx8NrpqLoCnxciMDTSf3PZkfXQYAy1lA/edit">docs.google.com/document/d/1MrSBES7ilpSrx8NrpqLoCnxciMDTSf3PZkfXQYAy1lA/edit</a></p>
<p>Find the target key K in the given binary search tree, return the node that contains the key if K is found, otherwise return null.</p>
<ul>
<li>
<p>SearchInBinarySearchTree(Iterative).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/D4021F74-6F8B-4168-813A-CD93768F57BC/SearchInBinarySearchTree(Iterative).java">SearchInBinarySearchTree(Iterative).java</a></p>
</li>
<li>
<p>SerachInBinarySearchTree(Recursive).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/D595E70C-44AE-4E84-A407-99C6922A778E/SerachInBinarySearchTree(Recursive).java">SerachInBinarySearchTree(Recursive).java</a></p>
</li>
</ul>
</li>
<li>
<p>Insert in Binary Search Tree<br />
Link: <a href="https://docs.google.com/document/d/1d22owc9suDO5IvoE0Yg_01GNYB8IjJ6ejJ_wyvFUmWA/edit">docs.google.com/document/d/1d22owc9suDO5IvoE0Yg_01GNYB8IjJ6ejJ_wyvFUmWA/edit</a></p>
<p>Insert a key in a binary search tree if the binary search tree does not already contain the key. Return the root of the binary search tree.</p>
<p><strong>Assumptions</strong><br />
There are no duplicate keys in the binary search tree<br />
If the key is already existed in the binary search tree, you do not need to do anything</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \<br />
1 4<br />
insert 11, the tree becomes<br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
insert 6, the tree becomes<br />
5<br />
/ \<br />
3 8<br />
/ \ / \<br />
1 4 6 11</p>
<ul>
<li>
<p>InsertInBinarySearchTree(Iterative).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/CBF0241F-A273-48AF-A876-A57D43E8190F/InsertInBinarySearchTree(Iterative).java">InsertInBinarySearchTree(Iterative).java</a></p>
</li>
<li>
<p>InsertInBinarySearchTree(Recursive).java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/0E0026B3-30A5-4ADD-9EA2-49C628064B52/InsertInBinarySearchTree(Recursive).java">InsertInBinarySearchTree(Recursive).java</a></p>
</li>
</ul>
</li>
<li>
<p>Delete in Binary Search Tree<br />
Link: <a href="https://docs.google.com/document/d/1NxYuQxxTuSBcwsq64wFG0C8fGxR83NPsLnZ-eVTLuys/edit">docs.google.com/document/d/1NxYuQxxTuSBcwsq64wFG0C8fGxR83NPsLnZ-eVTLuys/edit</a></p>
<p>Delete the target key K in the given binary search tree if the binary search tree contains K. Return the root of the binary search tree.<br />
Find your own way to delete the node from the binary search tree, after deletion the binary search tree's property should be maintained.</p>
<p><strong>Assumptions</strong><br />
There are no duplicate keys in the binary search tree<br />
The smallest larger node is first candidate after deletion</p>
<ul>
<li>DeleteInBinarySearchTree.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/EBC8E123-8AAF-4ECC-9337-A011003CF370/DeleteInBinarySearchTree.java">DeleteInBinarySearchTree.java</a></li>
</ul>
</li>
</ul>
<h3>Heap & Graph Search I: BFS (5)</h3>
<ul>
<li>
<p>K Smallest in Unsorted Array<br />
Link: <a href="https://docs.google.com/document/d/1Nsrf9tnivy7-26hBKhc9AiCprHpGEH6Cm8OjrS3bO-0/edit">docs.google.com/document/d/1Nsrf9tnivy7-26hBKhc9AiCprHpGEH6Cm8OjrS3bO-0/edit</a></p>
<p>Find the K smallest numbers in an unsorted integer array A. The returned numbers should be in ascending order.</p>
<p><strong>Assumptions</strong><br />
A is not null<br />
K is >= 0 and smaller than or equal to size of A</p>
<p><strong>Return</strong><br />
an array with size K containing the K smallest numbers in ascending order</p>
<p><strong>Examples</strong><br />
A = {3, 4, 1, 2, 5}, K = 3, the 3 smallest numbers are {1, 2, 3}</p>
<ul>
<li>KSmallestInUnsortedArray.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/9CD5DF5A-B95A-45E1-B581-C1C96305156E/KSmallestInUnsortedArray.java">KSmallestInUnsortedArray.java</a></li>
</ul>
</li>
<li>
<p>Get Keys in Binary Tree Layer by Layer<br />
Link: <a href="https://docs.google.com/document/d/1yTsPjdwvL4sRWiQlvCSIyV94Hx8XBdvw2bQwkMDYlEI/edit">docs.google.com/document/d/1yTsPjdwvL4sRWiQlvCSIyV94Hx8XBdvw2bQwkMDYlEI/edit</a></p>
<p>Get the list of list of keys in a given binary tree layer by layer. Each layer is represented by a list of keys and the keys are traversed from left to right.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
the result is [ <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/C1E33C9E-A55C-42D8-84F7-50151EF2A30C/BinarySearchInSortedMatrixI(2DMappingTrick).java">5</a>, [3, 8], [1, 4, 11] ]</p>
<p><strong>Corner Cases</strong><br />
What if the binary tree is null? Return an empty list of list in this case.</p>
<ul>
<li>GetKeysInBinaryTreeLayerByLayer.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/344A9A48-E3D2-4657-AABB-80A340A4238D/GetKeysInBinaryTreeLayerByLayer.java">GetKeysInBinaryTreeLayerByLayer.java</a></li>
</ul>
</li>
<li>
<p>Bipartite<br />
Link: <a href="https://docs.google.com/document/d/1qacDdKphBqTMCCKhADjhpib607pbVxvtlChYNk_4OHU/edit">docs.google.com/document/d/1qacDdKphBqTMCCKhADjhpib607pbVxvtlChYNk_4OHU/edit</a></p>
<p>Determine if an undirected graph is bipartite. A bipartite graph is one in which the nodes can be divided into two groups such that no nodes have direct edges to other nodes in the same group.</p>
<p><strong>Examples</strong><br />
1 -- 2<br />
/ <br />
3 -- 4<br />
is bipartite (1, 3 in group 1 and 2, 4 in group 2).<br />
1 -- 2<br />
/ |<br />
3 -- 4<br />
is not bipartite.</p>
<p><strong>Assumptions</strong><br />
The graph is represented by a list of nodes, and the list of nodes is not null.</p>
<ul>
<li>Bipartite.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/7F2920FD-4A77-4764-9D44-5A2F88D81949/Bipartite.java">Bipartite.java</a></li>
</ul>
</li>
<li>
<p>Check If Binary Tree is Completed<br />
Link: <a href="https://docs.google.com/document/d/1vkXgUIGAWTxjOIS6KItAfh-qDZFSj4gBwRfjlCj3bA0/edit">docs.google.com/document/d/1vkXgUIGAWTxjOIS6KItAfh-qDZFSj4gBwRfjlCj3bA0/edit</a></p>
<p>Check if a given binary tree is completed. A complete binary tree is one in which every level of the binary tree is completely filled except possibly the last level. Furthermore, all nodes are as far left as possible.</p>
<p><strong>Examples</strong><br />
5<br />
/ \<br />
3 8<br />
/ \<br />
1 4<br />
is completed.<br />
5<br />
/ \<br />
3 8<br />
/ \ \<br />
1 4 11<br />
is not completed.</p>
<p><strong>Corner Cases</strong><br />
What if the binary tree is null? Return true in this case.</p>
<ul>
<li>CheckIfBinaryTreeIsCompleted.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/C10B6665-495C-4D1A-B362-AE92882C8706/CheckIfBinaryTreeIsCompleted.java">CheckIfBinaryTreeIsCompleted.java</a></li>
</ul>
</li>
<li>
<p>Kth Smallest Number in Sorted Matrix<br />
Link: <a href="https://docs.google.com/document/d/1GAzZFh2b9Z9IK4-A8z2AUtrJflyITAdXZTvhT1dZHW0/edit">docs.google.com/document/d/1GAzZFh2b9Z9IK4-A8z2AUtrJflyITAdXZTvhT1dZHW0/edit</a></p>
<p>Given a matrix of size N x M. For each row the elements are sorted in ascending order, and for each column the elements are also sorted in ascending order. Find the Kth smallest number in it.</p>
<p><strong>Assumptions</strong><br />
the matrix is not null, N > 0 and M > 0<br />
K > 0 and K <= N * M</p>
<p><strong>Examples</strong><br />
{ {1, 3, 5, 7},<br />
{2, 4, 8, 9},<br />
{3, 5, 11, 15},<br />
{6, 8, 13, 18} }<br />
the 5th smallest number is 4<br />
the 8th smallest number is 6</p>
<ul>
<li>KthSmallestNumberInSortedMatrix.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/78E63427-5FA4-401F-AA23-33E043787305/KthSmallestNumberInSortedMatrix.java">KthSmallestNumberInSortedMatrix.java</a></li>
</ul>
</li>
</ul>
<h3>Graph Search II: DFS (4)</h3>
<ul>
<li>
<p>All Subsets I<br />
Link: <a href="https://docs.google.com/document/d/1mdfq64UdZylb1xns675h5ByYLlcwrl3yQMwRdYah6gk/edit">docs.google.com/document/d/1mdfq64UdZylb1xns675h5ByYLlcwrl3yQMwRdYah6gk/edit</a></p>
<p>Given a set of characters represented by a String, return a list containing all subsets of the characters.</p>
<p><strong>Assumptions</strong><br />
There are no duplicate characters in the original set.</p>
<p><strong>Examples</strong><br />
Set = "abc", all the subsets are [“”, “a”, “ab”, “abc”, “ac”, “b”, “bc”, “c”]<br />
Set = "", all the subsets are [""]<br />
Set = null, all the subsets are []</p>
<ul>
<li>AllSubsetsI.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/D0642DF8-2BD9-403F-9EEE-906B00B90F74/AllSubsetsI.java">AllSubsetsI.java</a></li>
</ul>
</li>
<li>
<p>All Valid Permutations of Parentheses I<br />
Link: <a href="https://docs.google.com/document/d/1K1JX3Q34kezBOwy_uQl-gYW9zPyK_pGZHpIl3CD3N_Q/edit">docs.google.com/document/d/1K1JX3Q34kezBOwy_uQl-gYW9zPyK_pGZHpIl3CD3N_Q/edit</a></p>
<p>Given N pairs of parentheses “()”, return a list with all the valid permutations.</p>
<p><strong>Assumptions</strong><br />
N > 0</p>
<p><strong>Examples</strong><br />
N = 1, all valid permutations are ["()"]<br />
N = 3, all valid permutations are ["((()))", "(()())", "(())()", "()(())", "()()()"]</p>
<ul>
<li>AllValidPermutationsOfParenthesesI.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/206555CB-2FB9-43E9-9543-C5447BE96032/AllValidPermutationsOfParenthesesI.java">AllValidPermutationsOfParenthesesI.java</a></li>
</ul>
</li>
<li>
<p>Combinations of Coins<br />
Link: <a href="https://docs.google.com/document/d/1gocutclTuZ6umIOFsjCvSA6LHfkYuSvLz7C5KLVI8uA/edit">docs.google.com/document/d/1gocutclTuZ6umIOFsjCvSA6LHfkYuSvLz7C5KLVI8uA/edit</a></p>
<p>Given a number of different denominations of coins (e.g., 1 cent, 5 cents, 10 cents, 25 cents), get all the possible ways to pay a target number of cents.</p>
<p><strong>Arguments</strong><br />
coins - an array of positive integers representing the different denominations of coins, there are no duplicate numbers and the numbers are sorted by descending order, eg. {25, 10, 5, 2, 1}<br />
target - a non-negative integer representing the target number of cents, eg. 99</p>
<p><strong>Assumptions</strong><br />
coins is not null and is not empty, all the numbers in coins are positive<br />
target >= 0<br />
You have infinite number of coins for each of the denominations, you can pick any number of the coins.</p>
<p><strong>Return</strong><br />
a list of ways of combinations of coins to sum up to be target.<br />
each way of combinations is represented by list of integer, the number at each index means the number of coins used for the denomination at corresponding index.</p>
<p><strong>Examples</strong><br />
coins = {2, 1}, target = 4, the return should be<br />
[<br />
[0, 4], (4 cents can be conducted by 0 * 2 cents + 4 * 1 cents)<br />
[1, 2], (4 cents can be conducted by 1 * 2 cents + 2 * 1 cents)<br />
[2, 0] (4 cents can be conducted by 2 * 2 cents + 0 * 1 cents)<br />
]</p>
<ul>
<li>CombinationsOfCoins.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/2BFB418C-0ECB-4D3D-88B0-821825924DD8/CombinationsOfCoins.java">CombinationsOfCoins.java</a></li>
</ul>
</li>
<li>
<p>All Permutations I<br />
Link: <a href="https://docs.google.com/document/d/1QG8PM24Nl1J-4MdGrB2cvGJ6YyVglTdRTU8v1Q9rKRQ/edit">docs.google.com/document/d/1QG8PM24Nl1J-4MdGrB2cvGJ6YyVglTdRTU8v1Q9rKRQ/edit</a></p>
<p>Given a string with no duplicate characters, return a list with all permutations of the characters.<br />
Assume that input string is not null.</p>
<p><strong>Examples</strong><br />
Set = “abc”, all permutations are [“abc”, “acb”, “bac”, “bca”, “cab”, “cba”]<br />
Set = "", all permutations are [""]</p>
<ul>
<li>AllPermutationsI.java<br />
Attachment: <a href="V1.0-7314c1ac615c86b08296bcb7843f29e6-assets/19B8A150-2033-4F7B-AC5E-76B0F58148FB/AllPermutationsI.java">AllPermutationsI.java</a></li>
</ul>
</li>
</ul>
<h3>HashMap & String I (8)</h3>
<ul>
<li>
<p>Top K Frequent Words<br />
Link: <a href="https://docs.google.com/document/d/1SdHiOOr6kXgjT2xMm53Q36lRFV2adPM489GHD68k2sU/edit">docs.google.com/document/d/1SdHiOOr6kXgjT2xMm53Q36lRFV2adPM489GHD68k2sU/edit</a></p>