-
Notifications
You must be signed in to change notification settings - Fork 0
/
questions2_(1300 results).txt
2694 lines (1347 loc) · 396 KB
/
questions2_(1300 results).txt
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
algorithm Facebook Senior Engineer On-site 2017 1st Round Question 1: Binary tree to doubly linked list. Question 2: Read 4 (Given the read4 API, read an entire file) 2nd Round Culture fit. No coding. 3rd Round Question: System Design POI (Point of Interest. Given a point, find things within a radius). Lunch 4th Round Question 1: Decode way Question 2: Random max index 5th Round Question: System design + component-wise design on download manager
algorithm 5th Round Open-ended question What happens when you type a url in the browser and hit enter? Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.
algorithm You are given an array of integers both negative and positive. Print the maximum continuous sum of the array and if all the elements are negative, print the smallest of them. Ex : [-20, -5, -2, -9] :> -2(-2) Ex : [20, -19, 6, 9, 4] :-> 20(20) Ex : [10, -3, 4, -2, -1, 10] -> 18 (10, -3, 4, -2, -1, 10) Thanks velu007 for pointing out the mistake
algorithm Given some email ids, and a similarity function which says whether two email ids are similar, determine all the sets of email ids that are similar to each other.
algorithm Given a list of URLs entered by a user write a program to print unique and most recently used URLs. For example if user entered the following: - 1. google.com 2. yahoo.com 3. wsj.com 4. google.com The output should be :- 1. google.com 2. wsj.com 3.yahoo.com
algorithm Given a sorted array, find all the numbers that occur more than n/4 times.
algorithm In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously. Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward. e.g. @INPUT (String) "OLLAOOOLLO" @RETURN (Boolean) False The student does not qualify for reward because "LLA" means he was late for 3 times in a row. @INPUT (String) "OLLOAOLLO" @RETURN (Boolean) True Follow-up: If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.
algorithm Given an array it can be of 4 types (a) Ascending (b) Descending (c) Ascending Rotated (d) Descending Rotated Find out which kind of array it is
algorithm The following code has a bug, find it and fix it
algorithm Write a function that receives a string an returns a list of all the substrings (of length >= 2) composed by consecutive characters. E.g input : "BCCDE" , output: ["BC","CD","CDE","DE"]
algorithm /** * Given a nested list of integers, returns the sum of all integers in the list weighted by their REVERSED depth. * For example, given the list {{1,1},2,{1,1}} the deepest level is 2. Thus the function should return 8 (four 1's with weight 1, one 2 with weight 2) * Given the list {1,{4,{6}}} the function should return 17 (one 1 with weight 3, one 4 with weight 2, and one 6 with weight 1)
algorithm Early on I prefer to post the interview questions with a simplified description or only present the algorithmic part of it. Because it's hard for our students to memorize the full description of a problem. Therefore often times only the algorithm behind the question is given. But somehow a user of this site @concernedCoder gets unhappy with it. So from today on, we will try to recover the original version of the question as much as possible. We assure you all of the questions we posted are real questions that you have a good chance to come across during a coding interview. Anyone who has experience in a coding interview should be able to see that. Here is the full description of a recent Amazon OA question. The reason why we are able to provide the full description is because it's the online assessment. But for an on-site interview it's almost impossible to recover the questions perfectly. Title: Item Recommendations Amazon wants to recommend items to a customer who has just made a purchase. Amazon's recommendation algorithm is based on item 'connection'. Two items are 'strongly connected' if a single customer bought both of them. Two items are 'weakly connected' if they are both strongly and weakly connected to some other third item. Your task is to determine the number of the items strongly and weakly connected to a given item. You are provided the item id represented as a string, as well as the list of customer purchases represented as an array of strings. Each element in the array consists of a customer id(represented as a string) and an item id (also represented as a string). The two ids are separated by a colon. For example, if they element in the array is "ABJA:Z42G" then that means customer ABJA purchased item Z42G. Your output consists of an array, where the first element in the array represents the number of items strongly connected to the provided item id and the second element represents the number of items weakly connected to the provided item id. For example, if you were provided with the following input: determineRecommendation("ABC",["first:ABC", "first:HIJ", "sec:HIJ", "sec:KLM", "third:NOP", "fourth:ABC", "fourth:QRS", "first"DEF", "fifth:KLM", "fifth:TUV"]) You would return the following array: [3, 2] since ABC is strongly connected to 3 items: DEF, HIJ and QRS and is weakly connected to 2 items: KLM and TUV Although the description is long, the problem is just asking for 'search (with either DFS or BFS) in a graph'.
algorithm On google search, how to enable key word auto completion after a few letters typed. Follow-up: How to rank the words if they are weighted by frequency?
algorithm Find largest sub-array?
algorithm You have two servers. Both of these servers have an identical file with billion characters except for one single character. These servers are connected over a very slow connection. How do you find the different character? My ans: split those files in to batches of characters of 10,000 (say), now calculate checksum and compare the checksums for the chunks of 10,000 character lines. So now you are just comparing 'ints' and not the files per say. (remember the connection is very slow) His question: How do you optimize this?
algorithm Given a set of possibly overlapping rectangles in different levels (All of which are "not rotated", can be uniformly represented as (left-bottom,right-top) tuplets), return a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area. The rectangle at lower level has more priority than at higher levels.
algorithm Write a function that receives a position in 2 dimensional (x,y) array, which was initially initialized with 'o' (signals "water"), the function changes the value/state of that position to 'x' (signals "land") and returns the number of isles in the board. For example, for 3x3 board, it will initially look like the following: o o o o o o o o o After calling the function with the position (1,2), the board will look like the following: o o x o o o o o o and the functions returns 1 An isle is defined as 'x' surrounded horizontally and vertically with 'o' In the following board there is only one isle o o o o x x o x o
algorithm I got my interview yesterday and the problem they asked me was: Giving a method intToEnglish that receives an int as a parameter, how do you return its representation in english words. The number can be of any size but no more than around 2 billion since the parameter is an int 232
algorithm # There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room. # For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words: # Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals. # For example: # input = [(1,4), (2,3)] # > 3 # input = [(4,6), (1,2)] # > 3 # input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}} # > 11
algorithm Find the median of an unsorted array. Have to do better than O(nlogn) time. e.g. Given [2, 6, 1] return 2 Given [2, 6, 1, 4] return 3 which is sum of the two elements in middle over 2
algorithm Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string. eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple" I was thinking of the following approach, Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far. This should take O( N * k) where N is length of S.
algorithm /** Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order. eg: coins(10, 15, 55) print: 10 15 20 25 30 . . . 1000 */
algorithm Find all comments in the Java (it could be Python or any other language of your choice) codes thats parsed in as a string. You may assume the codes given is valid. Input is a single string, e.g. String codes = /* file created by aonecode.com\\n + welcome to the tech blog*/ \\n + //main method\\n + public static void main(String[] args) { \\n + System.out.println(//welcome); //output\\n + } Output is a list of strings List<String> ret = [ file created by anecode.com\n welcome to the tech blog, main method, output ]
algorithm Q: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C] and then another series [A != C, D != H, ..., F != A ] Check whether the equations combined is valid. For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.
algorithm Calculate and replace repeated characters in a string with their number of occurrences. Example : aaaggbbbbc 3a2g4b1c
algorithm Sort elements by frequency, print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.
algorithm Write a program which will bold the sub-string found in string (HTML Style).
algorithm Write code to decode strings. For example, String str = "3[a2[bd]g4[ef]h]", the output should be "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh". My solution is as follows.
algorithm Print first pair of mis-matching leaves (first pair as in in-order) given two pre-order traversal arrays of BSTs. e.g.
algorithm Randomly select one of the weighted items from a linked list. (you may only go through the list once) e.g. weight 1.6 -> weight 0.2-> ... -> weight 3.4 randomly select one item based on the weight. The higher the weight is, the more likely to be selected
algorithm Given a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages. e.g. a relies on b b relies on c then a valid sequence is [c, b, a]
algorithm Q: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.
algorithm Q: List all comments in the given segment of codes. It's pretty tricky since there is a lot of things to be considered, especially the escape characters.
algorithm Given two strings needle and haywards that contains ASCII characters,write an algorithm to output a list of 0-based indices of the occurances of all anagrams of needle in haystacks
algorithm down vote favorite Consider the following series: A := 1 B := A*2 + 2 C := B*2 + 3 and so on... Write a program that: -outputs the number corresponding to a given letter; -given a string of letters like 'GREP', computes the sum of the numbers corresponding to all the letters in the string (i.e., G + R + E + P), as given by the above series; and -given a large number (that would fit into a standard 32-bit integer), finds the shortest string of letters corresponding to it. You may use a greedy approach for the last part. Compute the values of the numbers corresponding to letters as and when required and DO NOT pre-compute beforehand and store them in a data structure.
algorithm An interesting question asked in Googles phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation. Follow up: Minimize steps needed. ex: {1 2 3 -1 4 5} move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5} push 1 to the output list because you move car 1 to the empty spot suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.
algorithm Given points on a plane like (0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2). How many rectangles can be formed ?
algorithm Given a singly linked list: 1->2->3->4->5 Change it to 1->5->2->4->3 using O(1) space
algorithm given a stream of natural numbers , and a array J contains integers in increasing orders operations performed J = [2,3,4] 1 2 3 4 5 6 7 8 9 10..27....100...1111 first operation J[0] = 2 => remove every 2nd integer now the stream is 1 3 5 7 27 J[1] = 3 remove every 3rd stream is now 1 3 7 3rd given a natural number n , find if it will survive given J, or at what index it will die.
algorithm Return the length of longest possible chunked palindrome string. Examples : Input : VOLVO Output : 3 Explanation : (VO)L(VO) Input : merchant Output : 1 Explanation : No chunks possible. Input : ghiabcdefhelloadamhelloabcdefghi Output : 7 Explanation : (ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)
algorithm Given a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}. Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>
algorithm A producer continuously produces a stream of characters. There are multiple consumer threads which read the chars and match to one of known strings and increment the counter for that pattern. Write the consumer function. Show how you will synchronize and maintain parallelism. Ex: Producer: abcdegabccaabbaacv ...... Known strings[] = {"ab", "aa", "fff" ... } patternMatchCount[] = {3, 2, 0 ... }
algorithm Given a dictionary and an char array print all the valid words that are possible using char from the array. Ex- char[] arr = {'e','o','b', 'a','m','g', 'l'} Dict - {"go","bat","me","eat","goal", "boy", "run"} Print - go, me, goal. We can pre-compute as much we want but the query time must be optimal.
algorithm Given a pattern and a string - find if the string follows the same pattern Eg: Pattern : [a b b a], String : cat dog dog cat
algorithm Given a binary tree and a target number, return whether or not there exist a path that can create target number. All inputs are integers. Target is not a string. NOTE:: this is not path sums to target number ex: 3 4 5 6 7 8 9 359 = return true 38 = return false 47 = return true 6 = return true
algorithm Tom works in a warehouse. A billion (1,000,000,000) boxes are arranged in a row. They are numbered from one to one billion (from left to right). Some boxes contain a basketball (at most one basketball in each box). In total, there are N basketballs.Tom wants to organize the warehouse. He would like to see all the basketballs arranged next to each other (they should occupy a consistent interval of boxes). In one move, Tom can take one basketball and move it into an empty box. What is the minimum number of moves needed to organize the basketballs in the warehouse? Write a function:
algorithm You are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price. When facing each enemy you can either: 1) Fight him (if your strength is enough). You keep your money. 2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours. Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible). This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?
algorithm Finding biggest plus sign "+" in a sparse matrix(matrix with elements 0 and 1) For example, the biggest plus sign for following matrix is located at (2,2), with length 1 for each edge(Yes, each edge should have same length) 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 Hint: use DFS/BFS
algorithm Given a list of coin values, and quantity of each type of coin. Write a program to return the set of all possible sums which can be made using those coins. ex. coins = [10, 50, 100, 500] quantity = [5, 3, 2, 2] sum could be 400 , 300 ,200 , 100
algorithm Given a function getRandom that returns a random double in [0,1). Write a function getRandomPermutation(int n) that takes a positive integer n as argument and returns a random permutation of first n natural numbers.
algorithm Define amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized. Example 1: 0, 1, 2, 3 Ouptut: 0. When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number. Example 2: 1, 0 , 0 Output: 1. When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number. If there are multiple positions, return the smallest one. should get a solution with time complexity less than O(N^2)
algorithm Given 'n' circles (each defined by center and radius) Write an algorithm to detect if circles intersect with any other circle in the same plane Better than O(n^2) complexity
algorithm Given the village of a map represented as a 2D grid containing houses,bushes and open-spaces, write a program to find a point for conducting a meeting in the map. Such point should be minimum from all the houses in the village. Eg.
algorithm Using that data structure, devise an algorithm to compute the dot product between two sparse matrices.
algorithm Magical binary strings are non-empty binary strings if the following two conditions are true: The number of 0's is equal to the number of 1's. For every prefix of the binary string, the number of 1's should not be less than the number of 0's. A magical string can contain multiple magical substrings. If two consecutive substrings are magical, then we can swap the substrings as long as the resulting string is still a magical string. Given a magical binary string, str, perform zero or more swap operations on its consecutive magical substrings such that the resulting string is aslexicographically large as possible. Two substrings are considered to be consecutive if the last character of the first substring occurs exactly one index before the first character of the second substring. ----- Input Format a single binary string, str. Constraints It is guaranteed that str is a binary string of 1's and 0's only. 1 length(str) 50 It is guaranteed that str is a magical string. Output Format Find a string denoting the lexicographically largest magical string that can be formed from str. Sample Input 0 11011000 Sample output 11100100 Explanation of sample Given the magical string str = 11011000, we can choose two consecutive magical substrings, 1100 and 10, to swap such that the resultant string, str' = 11100100, is the lexicographically largest possible magical string possible. Thus, we return the value of str', which is 11100100, as our answer. .
algorithm Given the root of a Binary Tree along with two integer values. Assume that both integers are present in the tree. Find the LCA (Least Common Ancestor) of the two nodes with values of the given integers. 2 pass solution is easy. You must solve this in a single pass.
algorithm You are given 2 lists - List 1: List<Demand> is a list of Demand objects. List 2: List<Supply> is a list of Supply objects. Return a result fulfillment List<Demand,List<Supply>>. This means each demand could be satisfied by more than one supplies.
algorithm Given a string with only parenthesis. Check if the string is balanced. ex - 1) "<({()})[]> is balanced 2) "<({([)})[]> is not balanced
algorithm Given an array of integers and a sum 'S'. Find 2 integers in the array that add up to S.
algorithm Each test file starts with an integer t - the number of testcases. In each of the next t lines, you are given a string of n characters [ either ( or ) or * ]. Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the * with either ( or ) or removing the * Note : You have to replace each * with one of ( or ) or remove it. If removed, assume the string has reduced by 1 character. Duplicate strings are not allowed. The final expressions to be counted have to be distinct As the answer may be large, please output it modulo 1000000007 (10^9+7) Output one integer per line corresponding to each testcase. Constraints : 1 <= t <= 20 1 <= n <= 100 0 <= Number of * in the input string <= min(n,10) Sample Input: 2 (*(*)*) *(*(**)* Sample Output 5 9 Explanation The five possible valid solutions are for the first input are : ((())) ()(()) ()()() (())() (()) The nine possible valid solutions are for the second input are : (((()))) (()(())) (()()()) (()()) ((())) ()(()) ()()() ()() (())
algorithm /* # There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room. # For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words: # Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals. # For example: # input = [(1,4), (2,3)] # > 3 # input = [(4,6), (1,2)] # > 3 # input = [(1,4), (6,8), (2,4), (7,9), (10, 15)] # > 11 */
algorithm find first not-repeating character by iterating through the length of the string only once and by using constant space.
algorithm Given a string "2-4a0r7-4k", there are two dashes which we can split into 3 groups of length 1, 5, 2. If we want each group to be length 4, then we get "24A0-R74k" Given a String A and an int K, return a correctly formatted string. IF A is "2-4A0r7-4k" and B is 4, string is "24A0-R74K" IF K is 3, string is "24-A0R-74K" as the first grp could be shorter.
algorithm determine whether a word is in a stored list; the list doesn't fit into memory; no disk access allowed, for lookups, memory access only; no false positives allowed, false negatives ok
algorithm Find the shortest path between a start node and end node in a undirected +ve weighted graph. You are allowed to add at max one edge between any two nodes which are not directly connected to each other. ex: From | To | Weight 1 2 2 1 4 4 2 3 1 3 4 3 4 5 1 start node = 1, end node = 5. extra edge weight = 2.
algorithm Given infinite supply of coins of denominations 25, 10, 5 and 1, find the distinct number of ways to use the coins to sum up to the given value
algorithm Given an array of 1 billion numbers with just a few 100 missing, find all the missing numbers. you have only enough memory to store only 10k elements
algorithm Write a program to check whether it is a valid binary tree or not. Check all test cases (e.g. No left Node case).
algorithm count the duplicates in a array of strings??
algorithm Given an Array A with n elements. Pick maximum number of elements from given array following the rule: 1. We cannot pick A[i] and A[j] if absolute value of (A[i] - A[j]) > absolute value of (i - j) Example: {13,5,4} Ans: 2 Pick 5 and 4.
algorithm A frequent traveller collects all his travel tickets. A ticket has only 2 attributes, Start Journey Location name and Destination Name. Example from Delhi to Mumbai. At the end of the year, the traveller gets all his tickets together and tries to map his journey across the year. Print his travel route in a readable format. He does not remember his start location. Edit: he can visit a location multiple times, and can also go back and forth a place several times.
algorithm Given a directed graph G, duplicate the graph using minimum space.
algorithm A list of words is given and a bigger string given how can we find whether the string is a permutation of the smaller strings. eg- s= badactorgoodacting dict[]={'actor','bad','act','good'] FALSE eg- s= badactorgoodacting dict[]={'actor','bad','acting','good'] TRUE The smaller words themselves don't need to be permuted. The question is whether we can find a ordering of the smaller strings such that if concatenated in that order it gives the larger string One more constraint - some words from dict[] may also be left over unused
algorithm Suppose you have a list of Dishes, where each dish is associated with a list of ingredients. Group together dishes with common ingredients. E.g: Input: "Pasta" -> ["Tomato Sauce", "Onions", "Garlic"] "Chicken Curry" --> ["Chicken", "Curry Sauce"] "Fried Rice" --> ["Rice", "Onions", "Nuts"] "Salad" --> ["Spinach", "Nuts"] "Sandwich" --> ["Cheese", "Bread"] "Quesadilla" --> ["Chicken", "Cheese"] Output: ("Pasta", "Fried Rice") ("Fried Rice, "Salad") , ("Chicken Curry", "Quesadilla") ("Sandwich", "Quesadilla") Follow up: What is the time and space complexity?
algorithm Mr. Kim has to deliver refrigerators to N customers. From the office, he is going to visit all the customers and then return to his home. Each location of the office, his home, and the customers is given in the form of integer coordinates (x,y) (0x100, 0y100) . The distance between two arbitrary locations (x1, y1) and (x2, y2) is computed by |x1-x2| + |y1-y2|, where |x| denotes the absolute value of x; for instance, |3|=|-3|=3. The locations of the office, his home, and the customers are all distinct. You should plan an optimal way to visit all the N customers and return to his among all the possibilities. You are given the locations of the office, Mr. Kims home, and the customers; the number of the customers is in the range of 5 to 10. Write a program that, starting at the office, finds a (the) shortest path visiting all the customers and returning to his home. Your program only have to report the distance of a (the) shortest path. You dont have to solve this problem efficiently. You could find an answer by looking up all the possible ways. If you can look up all the possibilities well, you will get a perfect score. [Constraints] 5N10. Each location (x,y) is in a bounded grid, 0x100, 0y100, and x, y are integers. [Input] You are given 10 test cases. Each test case consists of two lines; the first line has N, the number of the customers, and the following line enumerates the locations of the office, Mr. Kims home, and the customers in sequence. Each location consists of the coordinates (x,y), which is reprensented by x y. [Output] Output the 10 answers in 10 lines. Each line outputs the distance of a (the) shortest path. Each line looks like #x answer where x is the index of a test case. #x and answer are separated by a space. [I/O Example] Input (20 lines in total. In the first test case, the locations of the office and the home are (0, 0) and (100, 100) respectively, and the locations of the customers are (70, 40), (30, 10), (10, 5), (90, 70), (50, 20).) 5 Starting test case #1 0 0 100 100 70 40 30 10 10 5 90 70 50 20 6 Starting test case #2 88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14 10 Starting test case #3 39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36 ... Output (10 lines in total) #1 200 #2 304 #3 366
algorithm Given two integer arrays list1 and list2 and an int target value. WAP to check if there exists such a sum, where one number taken from list1 and other from list2 to add up to become the target value. Return true if so, else return false.
algorithm Given a sparse matrix, implement below two methods: void set(int row, int col, int val) /*Update value at given row and col*/ int sum(int row, int col) /*give sum from top left corner to given row, col sub-matrix*/
algorithm A company is looking for algorithm to show item recommendations. If a customer bought A and B items and another buys A item, B should come as recommendations. There are two types of recommendations based on the connections 1) Two items are strongly connected if a customer buys those items. 2) Two items are weakly connected if each items are strongly/weakly connected to another third item. Provided the sample input ABC 10 first:ABC first:HIJ sec:HIJ sec:KLM third:NOP fourth:ABC fourth:QRS first:DEF fifth:KLM fifth:TUV first, sec, third.. represents the customer names ABC, HIJ... represents the item codes For the Input item Id "ABC", since "ABC" is strongly connected to HIJ, DEF, QRS and whereas ABC is weakly connected to KLM and TUV the output should be count of strong and weak connection i.e., [3,2]
algorithm Lets say someone accidentally deleted all the whitespaces from a sentence. Write a program to reconstruct the sentence from that stripped out string. Assume you have access to a dictionary function that returns if a given string is a valid word or not. Example input: thisisavalidsentence Output: this is a valid sentence If multiple solutions are possible, any one valid solution should be given. Assume there is always a valid solution. No invalid input will be given.
algorithm * Given an unsorted integer array, place all zeros to the end of the array without changing the sequence of non-zero * elements. (i.e. [1,3,0,8,12, 0, 4, 0,7] --> [1,3,8,12,4,7,0,0,0])
algorithm Given a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's Example: findStrings(3) returns 19 since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb and the invalid combinations are: abb,bab,bba,bbb,bbc,bcb,cbb,ccc
algorithm Convert a number to English representation. Ex: Input : 100 Output : One Hundred.
algorithm There are n+1 loading docks. a permutation of boxes 1->n is placed on the first n. there is a fork that can move one box to an empty location at a time. Give an algorithm to sort then boxes with minimum number of moves. Follow up: minimum distance
algorithm Given a Pattern and a dictionary, print out all the strings that match the pattern. where a character in the pattern is mapped uniquely to a character in the dictionary ( this is what i was given first). e.g 1. ("abc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "cdf" 2. ("acc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "too", "paa"
algorithm We define a subarray of array to be a contiguous block of a's elements having a length that is less than or equal to the length of array a. For example, the subarray of array a = [1,2,3] are [1], [2], [1,2], [2,3], and [1,2,3]. Now, let's say we have an integer, k = 3. The subarrays of a having elements that sum to a number <=k are [1], [2], and [1,2]. The longest of these subarrays is [1,2], which had a length of 2. Complete the maxLength function in the editor. It has 2 parameters : 1. An array of integers, a. 2. An integer, k The function must return the length of the longest subarray elements that sum to a number less than or equal to k. Input Format Locked stub code in the editor reads the following input from stdin and passes it to the function: The first line contains a single ineteger n, denoting the number of elements in array a. Each line i of the n subsequent lines (where 0 <=i < n) contains an integer describing elements i in array a. Each line i of the n subsequent lines (where 0 <= i <= n) contains an integer describing elements i in array a. The last line contains an integer, k. Constraints 1 <= n <= 10^5 1 <= a[i] < 10^3 1 <= k <= 10^9
algorithm Swap the elements in Kth position from the start and end of a link list. ex: input: list: 1,2,4,5,7,8 & K=2 output: 1,7,4,5,2,8
algorithm Given an array of numbers, find the maximum and minimum sum of sub sequences at a distance > m Example arr = {3, 4, -2, 1, -2, 4, 6, -3, 5} & m = 2 Solution max = 13 {4 + 4 + 5}, min = -5 {-2-3}
algorithm Given a string return the longest palindrome that can be constructed by removing or shuffling characters. Example: 'aha' -> 'aha' 'ttaatta' -> ' ttaaatt' 'abc' -> 'a' or 'b' or 'c' 'gggaaa' -> 'gaaag' or 'aggga' Note if there are multiple correct answers you only need to return 1 palindrome.
algorithm Find the height difference between two nodes in a binary tree.
algorithm GIven a list of words, and the number of rows and columns, return the number of words that can be fit into the rows and columns by stringing together each consecutive word. If the next word doesn't fit in the same line, it should move to the next line. Find an efficient solution for this. For eg. List of words: { "Do", "Run" } Number of columns: 9 Number of rows: 2 First row: "Do Run Do" (7 letters + 2 spaces fit into 9 columns) Second row: "Run Do" (Only 2 words fit into 9 columns)
algorithm You want to design a Cab system which will show you nearest 5 taxis. Each taxi will continuously emit (x,y) coordinates. You need to print the nearest taxi from (p,q).
algorithm You want to design a Cab system which will show you nearest 5 taxis. Each taxi will continuously emit (x,y) coordinates. You need to print the nearest 5 taxis from (p,q).
algorithm You are given an old touch smartphone numbers having dial pad and calculator app. The goal is to type a number on dialpad. Calculator have 1-9 and +,-,*,/,= as operations. But as phone is old, some of the numbers and some operations can't be touched. But you can always make a number using other numbers and operations. There could be multiple ways of making a number. You have to find minimum operation for making a number. For ex: lets say 1,4,6,7,8,9 works and +,-,* works. 2,3,5 and / doesn't work. If you have to type 18-> 2 operations. (Each touch is considered an operation) If you have to type 5 -> '1+4=' that requires 4 operations. There could be other ways to make '5'. The goal is to find minimum operations.
algorithm Given a read only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times.
algorithm Chess Knight Problem: - It deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location.
algorithm You are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order. Find number of 0-s in the given matrix. Example:
algorithm Alternate sorting: Given an array of integers, rearrange the array in such a way that the first element is first maximum and second element is first minimum. Eg.) Input : {1, 2, 3, 4, 5, 6, 7} Output : {7, 1, 6, 2, 5, 3, 4}
algorithm You have rand2() function which returns 0 or 1 with equal probability. You should implement rand3() using rand2().
algorithm Given an array of n integers. MaxPrefix is defined as count of elements those are greater than the element and in the right side of array wrt to the element. Write a program to give the max of MaxPrefix Ex. Input 10 -4 6 2 8 9 4 Output is 5
algorithm Write a class to take in a large arbitrary number, also provide a function to increment the number. The number will be passed on as an array of integers.
algorithm Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c). Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above. Note: all coordinates are real numbers (a,b) |----------------------------------------------| |.......................................................|end |.......................................................| |start................................................| |.......................................................| |----------------------------------------------|(c,d) Edit: You have to avoid sensors. Also u can move in any direction any time.
algorithm # take an array and print non over lapping in order pairs. example:
algorithm You are given a range [first, last], initially white. You need to paint it black. For this purpose you have a set of triples [(f, l, cost), ...] - where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers). Find minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible Example:
algorithm Given an array of length N and an integer K, sort the array as much as possible such that no element travels more than k positions to its left - an element however can travel as much as it likes to its right.
algorithm Given a binary tree, whose leaf nodes are connected, 1 / \ 2 3 / \ / 4 5 6 Now 4,5,6 are leaf nodes in the above BT, 4->5->6 4's left is pointing to 6 and 6's right is pointing to 4. We have a circular DLL of leaf nodes. We need to find the height of this tree?
algorithm given 2 strings A and B. generate all possible solutions when B is merged in A. Ex: A = "hey" B: "sam" then solutions are : heysam,hseaym,hesaym,sahemy etc. notice that order should be the same for both of strings while merging.
algorithm A museum was represented by a square matrix that was filled with O, G, and W where O represented open space G represented guards, and W represented walls. Write a function that accepts the square matrix and returns another square matrix where all of the O's in the matrix are replaced with the number of how many spaces they are away from a guard, without being able to go through any walls.
algorithm You are given a string "abc" which is encoded like "123" where alphabets are mapped like a => 1 to z => 26. Now find out how many string can be formed by reverse engineering encode string "123". For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23). for string "1234" we have following possible combinations, I might be missing some of them but you get the idea {12, 3, 4} {1, 23, 4} {1, 2, 3, 4}
algorithm Select Kth largest value in the array. Given an unsorted array of size n, and a value k. Select the kth largest value from the array. For example: Array is [5, 3, 9, 1], n is 4 k = 0 => 9 k = 1 => 5 k = 3 => 1
algorithm Write a program to find all duplicate files within a folder.
algorithm WAP to take one element from each of the array add it to the target sum. Print all those three-element combinations. /* A = [1, 2, 3, 3] B = [2, 3, 3, 4] C = [1, 2, 2, 2] target = 7 */ Result: [[1, 2, 4], [1, 3, 3], [1, 3, 3], [1, 3, 3], [1, 3, 3], [1, 4, 2], [2, 2, 3], [2, 2, 3], [2, 3, 2], [2, 3, 2], [3, 2, 2], [3, 2, 2]]
algorithm You are designing a system the records website visits. The interface for this system is: void recordHit(); long getCount(); `getCount()` returns the amount of hits to the site for only the last 5 minutes. Your task is to code `recordHit()` and `getCount()`
algorithm This is a question I received in an online challenge. A list of numbers are given. We need to find the total number of groups in which the digits of each number have same frequency. For example if numbers are: 1 10 3 33 There are 4 groups: G1={1}has one 1. G2={3} has one 3. G3={10}has one 1 and one 0. G4={33}as two 3s.
algorithm Find the anagrams from a list of strings Input : {"tea", "ate", "eat", "apple", "java", "vaja", "cut", "utc"} Output : {"tea", "ate", "eat","java", "vaja", "cut", "utc"}
algorithm You are given a graph, some edges are black, some are red. Find a spanning tree with one restriction: if we take some node as root, every path from it to some leaf node must consist of alternating red-black-red-black edges. That is, no path from root to leaf must contain sequential black-black edges or red-red edges. You are guaranteed that such spanning tree exists.
algorithm Given a string S, print the longest substring P such that P > S lexicographically. You may assume that such substring exists.
algorithm Given a number print the number of combinations you can derive from the number. 1=A, 2=B, 26=Z, 0=+. For example: 1123 can be represented by 1,1,2,3 which would stand for AABC. Another representation - 11,23 - JW Another representation - 1,1,23 - AAW Another representation - 11,2,3 - JBC For number 1123, there will be 5 combinations.
algorithm what is the best sorting algorithm in terms of complexity and why?
algorithm Given a million list of co-ordinates in the form of longitude and latitude just as Google maps .How will you print closest k cities to a given location .
algorithm Given a 2D matrix of integers, sort it such that: - every row is sorted in ascending order from left to right - every column is sorted in ascending order from top to down - all items in the same row are unique You may assume the input matrix is always valid, meaning that such a sort is always possible. For example: for input matrix
algorithm |X XX | | X X | | X | | |
algorithm Given a string where in each word letters were randomly shuffled and after that words were written without spaces (lets call it X). Also you have a dictionary. The task is to return all possible strings S that can be transformed into the string X and all words in S are from dictionary.
algorithm Given an array of 0s and 1s, and k, Find the longest continuous streak of 1s after flipping k 0s to 1s. E.x array is {1,1,0,0,1,1,1,0,1,1} k = 1 (which means we can flip k one 0 to 1) Answer: 6 (if we flip 0 at index 7, we get the longest continuous streak of 1s having length 6)
algorithm Given two arrays/Lists (choose whatever you want to) with sorted and non intersecting intervals. Merge them to get a new sorted non intersecting array/list. Eg: Given: Arr1 = [3-11, 17-25, 58-73]; Arr2 = [6-18, 40-47]; Wanted: Arr3 = [3-25, 40-47, 58-73];
algorithm Define a function that can detect whether the characters of a string can be shuffled without repeating same characters as one other's neighbors. E.g. : apple >> alpep, so valid a >> a, valid aa >> aa, invalid/impossible aab >> aba, valid aaaabbcc >> acabacab, valid etc. You do not have to find one representation, just have to detect if it is possible or not!
algorithm Check if an integer array is arithmetic sequence. Example: 1, 2, 3, 4, 5, 6, 7, 8 => true 1, 3, 5, 7, 9 => true Array may not be sorted.
algorithm Second Least common element from an Integer array. Example: [5,5,4,5,4,6,6,6,1,3,3,4,4,5,4] Answer: 3 Reason: {1=1, 3=2, 4=5, 5=4, 6=3}
algorithm Task schedule: given a sequence of task like A B C(means 3 different tasks), and a coldtime, which means you need to wait for that much time to start next [same] task. Now---- Input: string, n Output: the best task-finishing sequence. eg. input: AAABBB, 2 Output: AB_AB_AB ( "_" represents do nothing and wait)
algorithm You are given a function bool rand_bit_p() that returns true with some unknown probability p and false with probability 1 - p. Write function rand_bit() using rand_bit_p that will return true and false with equal probability (that is, implement a fair coin, given unfair coin)
algorithm Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.(Using DP)
algorithm Given a non-directed, strongly connected graph where the node values are letters of the alphabet, write an algorithm that prints out all possible permutations of strings. What is this called? For example: V = A,B,C Printout ABC ACB BAC BCA CAB CBA BAC etc.
algorithm Given a sorted integer array, write a method that builds a balanced binary search tree. What is the runtime complexity? Hint: Recursion. Follow-up: Non-recursive solution
algorithm Given a decimal number, write a function that returns its negabinary (i.e. negative 2-base) representation as a string.
algorithm Given 4 teams and 3 gamedays, create an algorithm such that each team plays another team every gameday and by the end of the 3 game days each team should have played one game with every other team.
algorithm Given a number (integer) as a string turn in into a number: E.g. "One million two hundreds thousands fifty seven" => shoud return 1200057. How to model it and how to test it? What data structures would you use. Deep testing (corner cases)
algorithm Given a number N, write all possible sums of consecutive numbers that add up to N. That is: return all pairs (a, k) such that a+(a+1)+...+(a+k)=n After that: 1. what if N is negative or a is negative; 2. what if N is real and the possible implications of this
algorithm Given an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.
algorithm Find if a given binary tree has duplicate sub trees or not. (Two leaf nodes of a parent do not count as subtree)
algorithm Image an airport with the control tower having a constantly rotating radar scanning for airplanes. The radar's coordinates in the 2-d plane are (0,0). The radar has an API: void scan(const Plane &P) that is called periodically whenever the radar detects a plane. You can imagine that the Plane structure has x,y coordinates for that plane. You should fill in the function Scan, such that at any given time you are able to return the 100 closest planes to the tower (0,0).
algorithm Find missing element in the A.P.
algorithm Given integer k and a subset S of set {0, 1, 2, ..., 2^k - 1} Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a) & here is bit-wise and. Do it faster than O((2^k)^2), assume k <= 16 Example: 0b111 0b101 0b010 Answer: 2 0b110 0b011 0b101 Answer: 0
algorithm We have a long string. We label some substrings with tags. - A tag entry is [startIndex, endIndex, tag]. - Query: 1 or more tags - Output: all blocks/ranges with all queried tags. Example tag entries: [23, 72, 0] // label [23, 72) with tag 0 [34, 53, 1] // label [34, 53) with tag 1 [100, 128, 0] Query and Output: 0 => [23, 72], [100, 128] 0,1 => [34,53] // [34, 53) matches both tag 0 and 1 Give an efficient algorithm. Please describe your algorithm before posting code. **Edit**: To add some difficulties, partial overlap is treated the same as full overlap, ONLY the overlapped part matches both tags. E.g. if we have entries: [23, 72, 0] // label [23, 72) with tag 0 [10, 53, 1] // label [34, 53) with tag 1 Query and Output: 0,1 => [23,53] // [23, 53) matches both tag 0 and 1 Minor detials: Note in the comments we used open range on the right, i.e. if the string named "str", [23, 72, 0] includes str[23] but NOT str[72]; and there's no overlap between the following entries: [23, 72, 0] [10, 23, 0]
algorithm Given a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on. For Ex - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Print- 1 15 14 13 12 11 10 9 8 2 3 7 6 5 4 Follow up question - Extend the algorithm to n-ary tree.
algorithm You know result of a soccer match, print all the possible ways that this game ends up with this result. Example: final score 1 - 1: 0 - 0 0 - 1 1 - 1 0 - 0 1 - 0 1 - 1 Another example if the final score is 2 - 3 there are many possibilities for reaching to that score: 2 - 3 0 - 0 1 - 0 2 - 0 2 - 1 2 - 2 2 - 3 0 - 0 1 - 0 1 - 1 1 - 2 2 - 2 2 - 3 0 - 0 0 - 1 0 - 2 0 - 3 ...
algorithm Given a singly connected linked list, find the largest palindrome in the list in O(1) space.
algorithm Given a linked list consisting of String in each Node . Given just a pointer to the head Node find whether the resultant String formed by combining all the Nodes of the linked list is a palindrome or not in O(1) space and O(n) time. eg Consider this linked List structure aba -> cd -> efe -> d -> caba Hence this structure is palindrome .
algorithm Face to face Q3) stream of numbers coming, get 'n' min elements at any point of time
algorithm Given a long string s and short strings t1, t2, t3 (which can have different length) find the shortest substring of s which contains t1, t2 and t3.
algorithm Given N balloons, if you burst ith balloon you get Ai1AiAi+1 coins and then (i-1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather. Assume that we have extra 1 at left most and right most positions. (don't take in answer just for boundary positions) Hence if we have left or right boundary positions we multiply 1.
algorithm for given array
algorithm We have an iterator class as below:
algorithm Google is conducting a contest where they display a special doodle to the user submitting the billionth query of the day. Design a system to achieve this. (NOTE: Google has thousands of servers and each query can hit a different server). Optimise it. How will you handle server failures?
algorithm You are given two arrays of length M and N having elements in range 0-9.Your task is to create maximum number of length K from elements of these two arrays such that relative order of elements is same in the final number as in the array, they are taken from i.e. If two elements a,b are taken from array1 and and a comes before b in array1 so in the final number a should come before b (Relative order kept same) . Example: N=4 and M =6 Array1 = { 3 , 4 , 6,5} Array2 ={9,1,2,5,8,3} Suppose K = 5, then number will be {9,8,6,5,3} You can see {9,8,3} are taken from array2 in the same order as they are in Array2. Similarly {6,5} are taken from Array1 in the same order and number 98653 is maximum possible number.
algorithm I had two interviews with Google first) one with US person...he asked decent question with lot of hints...experience : positive and then second) interview with person from India...I prepared for one month but he asked me very tough one graph/tree question...never gave single hint and based on that one question he judged my seven years of experience in Software Development (I never experienced what they say...Google looks for approach and not final answer) Q.1 : Arrange array in wave form A1 > a2 < a3 > a4 ... O(n.log-n) (Note: its not A1 >= A2) Q.2 : Given Graph with Tree characteristics, find one node as root so that height of tree will be minimum
algorithm Given a 4*n block, find number of different ways of filling it with 1*2 smaller blocks. Rotation of smaller blocks is allowed.
algorithm Given an array of numbers, for every index i, find nearest index j such that a[j] > a[i].If such an index doesnt exist for i, 1 should be printed.
algorithm Imagine a man reading a book. He can perform only 2 possible actions of reading: 1) read a page in a minute (careful reading), 2) read two pages in a minute (look through). Nothing else is permitted. Calculate the number of all possible combinations of book reading ways with given number of pages. Example: given 3 pages. Answer is 3 combinations, as follows: 1st: Careful reading (1) - careful reading (1) - careful reading (1), 2nd: Careful reading (1) - look through (2), 3rd: Look through (2) - careful reading (1).
algorithm Given-an-array-of-length-n-having-integers-0-to-n-1-in-unsorted-order-we-have-to-modify-this-array-such-that-the-value-at-a-n-becomes-a-a-n-for-example-if-a-0-contains-5-then-a-0-will-have-value-a-5-and-so-on-condition-is-that-this-should-take-O-n-time-complexity
algorithm What is the fastest way to compute cube root?
algorithm Write a function to test if the given set of brackets are balanced or not. e.g. {{}}{)([][]
algorithm Check given Number is same after 180 degree rotation? i/p: 69 o/p: True i/p: 916 o/p: True i/p: 123 o/p: False
algorithm How do we achieve (google news) personalization.
algorithm Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T. example: S='adobecodebanc' T='abc' answer='banc'
algorithm Given an infinite stream of characters and a list L of strings, create a function that calls an external API when a word in L is recognized during the processing of the stream. Example: L = ["ok","test","one","try","trying"] stream = a,b,c,o,k,d,e,f,t,r,y,i,n,g............. the call to external API (let's call it some function callAPI()) would be called when the 'k' is encountered, again when the 'y' is encountered, and again at 'g'.
algorithm There is a circular train (the head is connected to the tail) where each car of the train contains a light bulb. Initially, the bulbs are randomly switched on/off. You need to determine the size of the train (the number of cars) by going from one car to another and switching the light bulbs
algorithm Given a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number. E.g., prime set = {2, 3} expressible number = {1,2,3,4,6,8, 9, 12...} non-expressible number = {5, 10... } The primes in the prime set are ordered in an increasing order, and can include a prime < 10^4 (don't remember the exact range), and n can also be as large as 1-10^6.
algorithm Given an array of positive integers (excluding zero) and a target number. Detect whether there is a set of consecutive elements in the array that add up to the target. Example: a = {1, 3, 5, 7, 9} target = 8 output = true ({3, 5}) or target = 15 output = true : {3, 5, 8} but if target = 6, output would be false. since 1 and 5 are not next to each other.
algorithm Given a dictionary containing a list of words, a starting word, and an ending word, return the minimum number of steps to transform the starting word into the ending word. A step involves changing one letter at a time to a valid word that is present in the dictionary. Return null if it is impossible to transform the starting word into the ending word using the dictionary. Example: Starting word: cat Ending word: dog cat -> cot -> cog -> dog ('cot' and 'cog' are in the dictionary) return 3
algorithm Write a function to detect the number of cycles in a directed graph. The graph is passed as an adjacency matrix.
algorithm Given an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array. Brute force is obvious, but must be done faster than O(n^2) Ex. [3,4,5,9,2,1, 3] Return [3, 2, 1, 0, 1, 1, 0] First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc
algorithm Given a set of values 0-9, return all permutations of that set of length n. Example: n=2, set ={2,3,4} Return: {2,2}, {3,3}, {4,4}, {2,3}, {3,2}, {3,4}, {4,3}, {2,4}, {4,2}
algorithm Given a pattern and a string, return a boolean of whether the string matches the pattern. Each character in pattern represents one of more characters in string. Method: is_match(pattern, string) Sample Testcases is_match('abba', 'dogfishfishdog') -> True is_match('aba', 'dogfishdog') -> True is_match('a', 'acdefghijk') -> True is_match('ab', 'acdefghijk') -> True is_match('aba', 'dogfishfish') -> False is_match('aba', 'dogfishhorse') -> False Preferable use Python, and say the Big O runtime and space.
algorithm Given a string and two words which are present in the string, find the minimum distance between the words Eg: "the brown qucik frog quick the", "the" "quick" O/P -> 1 "the quick the brown quick brown the frog", "the" "the" O/P -> 2
algorithm Given a linkedlist, write an algorithm to divide the linkedlist into two linkedlists, the first contains the Fibonacci numbers in the list and the second contains the non-Fibonacci numbers. Test the algorithm after developing the code
algorithm You are given a set of points on x axis (consumers) Also you are given a set of points on a plane (producer) For every consumer print the nearest producer. Wanted something better than O(n^2) time. Example: consumers: 1 5 7 producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100) Answer: for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2) Follow-up question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm?
algorithm Find a counter example proving that the following substring algorithm is incorrect:
algorithm Input argument of a method is a list of char array. The method have to print all the possible combination of input char(s)...For example if the input argument has ['A','B','C','D'] the output should be A,B,C,AB,AC,AD,BC,BD,CD,ABC,ACD,BCD,ABCD
algorithm Given an array of "array range", return an optimized array by deleting subarrays. NOTE: Array range (2,6) represents (2,3,4,5,6) INPUT: [(2,6),(3,5),(7,21),(20,21)] OUTPUT: [(2,6),(7,21)] Reason: (3,5) is a subarray of (2,6) and (20,21) is a subarray of (7,21)
algorithm Given a sentence in a form of a string, reverse the words in the string and return a string. Handle a case where there might be period at the end of the sentence. If there is a period, the period has to come to the end of the reversed sentence. Discuss the time complexity of your algorithm. INPUT: "This is a sentence" OUTPUT: "sentence a is This" INPUT2: "This one has period." OUTPUT2: "period has one This."
algorithm 1. Balanced Parentheses Given a string s of parentheses (ex: (()), return the minimum number of parentheses that need to be inserted to make it into a well formed string A well formed (balanced) string of parentheses is defined by the following rules: The empty string is well formed. If s is a well formed string, (s) is a well formed string. If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string. Implement int MinNumInsersertionsForBalancing(const string& s)
algorithm Sort an array of 0s, 1s and 2s Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last. Example Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}; Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2} The problem is similar to http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/ But they have added 1 trick into the question, You cannot use high = n; It means don't calculate the length of array. Can anyone help me in writing the code for this problem ?
algorithm Rearrange characters in a string so that no character repeats twice. Input: aaabc Output: abaca Input: aa Output: No valid output Input: aaaabc Output: No valid output
algorithm There are several people sitting in the cinema, some of them are couples, some are not, they decide to swap their seats so that the couples can seat together, please calculate the minimal swap numbers. 1. the swap can happen between any two position. 2. E.g. AABCCDB -> AADCCBB, ans is 1
algorithm there are N cities (numbered from 1 to N) in the game and connect them by N-1 highways. It is guaranteed that each pair of cities are connected by the highways directly or indirectly.The game has a very important value called Total Highway Distance (THD) which is the total distances of all pairs of cities. Suppose there are 3 cities and 2 highways. The highway between City 1 and City 2 is 200 miles and the highway between City 2 and City 3 is 300 miles. So the THD is 1000(200 + 500 + 300) miles because the distances between City 1 and City 2, City 1 and City 3, City 2 and City 3 are 200 miles, 500 miles and 300 miles respectively. During the game the length of some highways may change. you want to know the latest THD. sample input 3 5 1 2 2 2 3 3 QUERY EDIT 1 2 4 QUERY EDIT 2 3 2 QUERY sample output 10 14 12
algorithm You are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3}; Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, k-th order statistic on slice [a:b] of arr. E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it - get [0,1,5] and take k-th element, that is - 5. Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls.
algorithm Given a string which may contain parenthesis. We must verify the validity of the string. ex- 1) "<ad675+-fkmfd>" is a valid string 2) "<[((kskfhdbh7)" is invalid 3) "[<<((shfs8))>>]" is valid Extension to the question - Suppose you had a hash table that told you how a parenthesis starts and how it ends as a key value pair, how would you then validate the string. ex - <key,value> = < '(' , ')' > indicates '(' is a start parenthesis and ')' should be the end of that paranthesis. <'A','&'> indicates that 'A' is a start parenthesis and '&' is the end parenthesis. Note: Validity means a parenthesis that starts, must end.
algorithm Find the largest substring palindrome in a given string. ex: input: abbac output: abba Solution: Use Hashmap
algorithm Design and implement the constructor for the minesweeper game that takes in the dimension of the field and number of mines as input
algorithm You are given large numbers of logs, each one of which contains a start time (long), end time (long) and memory usage (int). The time is recorded as MMDDHH (100317 means October 3rd 5PM) Write an algorithm that returns a specific time (hour) when the memory usage is the highest. If there are multiple answers, return the first hour. e.g. 100207 100208 2 100305 100307 5 100207 100209 4 111515 121212 1 Answer: 100207 (Need to consider different scenarios like the time slots could be very sparse)
algorithm Print first and last node of all the levels of a tree. Ex if tree is - root->data = 1 root->left->data = 2 root->right->data = 3 root->left->right->data = 4 root->right->right->data = 6 root->right->left->data = 5 root->right->left->left->data = 7 root->right->left->left->right->data = 8 Output - 1 2 3 4 6 7 8
algorithm Write a program to process the matrix. If an element is 0 at ith row and jth column, then make the whole ith row and jth column to 0. Constraints: Space complexity should be O(1) Time complexity - Only single pass is allowed. Note that single pass is not O(n). This is single pass : An element will read and written only ones. Edit: Recursion is not allowed since it is O(n) space on stack
algorithm Given three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|+|b-c| +|c-a| is minimum.
algorithm Given an array of task and k wait time for which a repeated task needs to wait k time to execute again. return overall unit time it will take to complete all the task. Example: 1. A B C D and k = 3 ans: 4 (execute order A B C D) 2. A B A D and k = 3 ans: 6 (execute order A B . . A D) 3. A A A A and k =3 ans: 13 (A . . . A . . . A . . . A) 4. A B C A C B D A and k = 4 ans: 11 (A B C . . A .C B D A )
algorithm Post order traversal for an N-ary tree iterative way. Given, struct Node { int val; vector<Node*> children; }; Without modifying original structure.
algorithm . Given n strings consisting of R and B. Two strings can be only combined if last character of first string and first character of second string are same. Given n strings, you have to output the maximum length possible by combining strings. I/P RBR BBR RRR output : 9
algorithm Design an algorithm to find all the common elements in two sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2, 5, 5.
algorithm Given a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest. i.e: bcabc You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest. ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case: cbacdcbc. answer is acdb not adcb I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.
algorithm $a = [3, 1, 4, 5, 19, 6];
algorithm You are given a list of n float numbers x_1, x_2, x_3, ... x_n, where x_i > 0. A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise) Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting) e.g. 2 1 1 2 -> crosses 1 2 3 4 -> doesn't cross
algorithm BST is given. Calculate and return array with a sum of every level. For example, 1 2 3 4 5 1 2 Output should be [1, 5, 12].
algorithm Given an array of positive integers(>0) , you have to insert '+','*','(',')' signs basically plus multiply and brackets such that value of resultant expression becomes maximum. Hint: Consider case of continuous ones You have to print the resulting expression
algorithm Write all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5] in at least O(n^2) complexity
algorithm Given a binary N X N matrix, return the size of the largest '+' of ones. input: 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 output: 5 (binary search is not allowed)
algorithm This is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution. Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property. For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further. Input: A Single number N for which we want to produce the sequence. Output: A space separated list of sequence or NA if there is no possible sequence. Example Input: 3 Example Output: 2 3 1 2 1 3 Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).
algorithm I came across this problem online. > Given an integer:N and an array int arr[], you have to add some > elements to the array so that you can generate from 1 to N by using > (add) the elements in the array. Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the count of the least adding numbers. For example: N=6, arr = [1, 3] 1 is already in arr. add 2 to the arr. 3 is already in arr 4 = 1 + 3 5 = 2 + 3 6 = 1 + 2 + 3 So we return 1 since we only need to add one element which is 2. Can anyone give some hints?
algorithm Device an algorithm to find duplicates in array where each duplicate can occur k times. The algorithm must be of O(n) time and space complexity at max
algorithm On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.
algorithm Given an array A with n integers. Rearrange array such that A[0]<=A[1]>=A[2]<=A[3]>=A[4]<=A[5] and so on Edit: Array is not sorted You have to do it in linear time O(N)
algorithm Generate all possible sorted arrays from alternate elements of two given sorted arrays. Given two sorted arrays A and B, generate all possible arrays such that once first element is taken from A then from B then from A and so on in increasing order till the arrays exhausted. Then first element is taken from B then From A, and do same as above.
algorithm Find an algorithm to find a word ladder between 2 words by changing just one letter at a time. All the words formed should be valid dictionary words. Eg. FOOL ->POOL->POLL->POLE->PALE->SALE->SAGE COLD CORD CARD WARD WARM
algorithm Write a program in that determines the members and parents of nested groups without using recursion. These are the requirements. 1. A group can have 0 or more members. 2. A group can be member of one or more groups 3. A group can be member of itself. 4. If there is a path from a group either directly or through multiple hops, then that user is considered as member of the group. 5. A group can have users or groups as members EX: Input looks like this
algorithm Reverse string except spaces. A string has mix of alphabets and spaces. Your task is to reverse the string, but preserve the positions of spaces. For example, reverse of " a if" is " f ia".
algorithm Given a matrix containing 0 and 1. Consider 1 as 'Land' and 0 as 'Water'. Find out the number of 'Islands' in the matrix. That is, set of all adjacent 1 will make up for an island. For example: [ 0 1 1 0 1 ] [ 1 1 1 0 0 ] [ 0 0 0 1 1 ] [ 1 0 0 1 0 ] This problem has 4 islands. ( consider set of 1s, vertically, horizontally and diagonally ).
algorithm Given an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).
algorithm Find a duplicates in an array of length n. The values are positive integers in the range between 1 .. n-1
algorithm Count triangles in an undirected graph where a triangle is a unique set of three vertices connected to one another.
algorithm Given two sorted arrays find the element which would be N-th in their merged and sorted combination.
algorithm Given a BST with unique values find in a given tree a value closest to a given value X.
algorithm A car rental company which rents car by per hour basis wants to know the time period for maximum number cars that are rented. ie you are given the list of rental start time and return times of all rented cars in the day for all cars in a day find the maximum time period in which cars are on the road.
algorithm Round 6 Question 3 : You are given a word document, you have to print the words with frequencies. Now print the kth rank word in terms of frequency. Print top k words as well by frequencies
algorithm The "surpasser" of an element in an array is defined as the number of elements that are to the "right" and bigger than itself. Example: Array: [2, 7, 5, 5, 2, 7, 0, 8, 1] The "surpassers" are [5, 1, 2, 2, 2, 1, 2, 0, 0] Question: Find the maximum surpasser of the array. In this example, maximum surpasser = 5
algorithm Find the longest common prefix in a list of phrases. For instance; "i love all dogs", "i love cats" should return "i love".
algorithm How will you serialize the binary tree ?
algorithm There's a function that concatenates two strings and returns the length of the resultant string. When called upon a series of strings how do we minimize the cost of using this function. Let's say we have 3 strings, A= "abc", B="def", C = "gh". Now cost of merging AB = 6 and cost of merging the resultant string with C is 8. Thus the total cost is 6 + 8 = 14. However, if we merge A and C, then the cost is 5 and then merge B with this, the cost is 8, so the total cost is 13. Find an algorithm that minimizes the cost of adding such a series of strings.
algorithm Given a binary tree, implement an iterator that will iterate through its elements.
algorithm Given a binary tree (not search tree), find the path which adds up to given sum.
algorithm Tech Screening Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry. Interviewer was expecting O(N) solution for N asks. Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks. and integers are not given in a array, every time only one integer will be passed as input to your method.
algorithm Print the level of friendship. Given a person and list of his friends, print all his friends by level of association. The text file will be like one below A: B,C,D D: B,E,F E: C,F,G If the input is A, the out put should be: Level 1 - B,C,D Level 2 - E,F Level 3 - G
algorithm Given a start string, end string and a set of strings, find if there exists a path between the start string and end string via the set of strings. A path exists if we can get from start string to end string by changing (no addition/removal) only one character at a time. The restriction is that the new string generated after changing one character has to be in the set. start: "cog" end: "bad" set: ["bag", "cag", "cat", "fag", "con", "rat", "sat", "fog"] one of the paths: "cog" -> "fog" -> "fag" -> "bag" -> "bad"
algorithm You are given a bunch of nodes evenly spaced in a rectangular shape. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand corner and node B is at the bottom right hand corner. How many different paths are there from A to B? What is a brute-force solution? What is better than a brute force solution?
algorithm std C library has pow(x, n) function - implement that function
algorithm Shuffle a given array such that each position is equally likely.
algorithm Given a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.
algorithm Given a file, read last n lines from the file string ReadNLines(sttring fileName, int n);
algorithm Assume we have a very large file containing millions of lines of data. Only 2 lines are identical, rest are unique. Each line is long enough that they may not fit in memory. Design an efficient algorithm to determine identical lines? And, then generalize it for 'n' identical lines.
algorithm Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 <= n <= 12, which is the number of courses in this data set and m, 2 <= m <= 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered ('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 <= p <= 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
algorithm Design and implement LRU Cache.
algorithm Array = {5, 2, 1} circular rotate array, calculate sum by multiplying each array elements with index and find minimum sum from all of rotated arrays. Time Complexity should be O(n) 5x index + 2 x index + 1xindex = Sum Step 1: 5x1 + 2x2 + 1x3 = 5+4+3 ==> 12 Step 2: (rotate array) {2,1,5} 2x1 + 1x2 + 5x3 = 2+2+15 ==> 19 Step 3: (rotate array) { 1,5, 2} 1x1 + 5x2 + 2x3 = 1+10+ 6 ==> 17 Step 4: (rotate array) {5,2,1} same as input array stop and print minimum sum 1.e 12
algorithm Given a string left rotate it by given number of times with O(n) solution
algorithm Given a array where each element is maximum +-k index away from it's sorted position, find an algorithm to sort such array.
algorithm Say you have a keypad that has keys for the numbers 0 through 9 and the correct code is some sequence of 5 digits. This keypad does *not* reset after entering an incorrect sequence of 5 digits. ie. If the correct sequence is 12345, entering 7512345 will succeed in opening it because it ends in the correct sequence. If the keypad actually resets after every 5 digits pressed, then it would not succeed b/c it would interpret the above sequence as "75123" then "45". 1. Write an algorithm that will try to find the correct code for this keypad. Assume you have an API similar to KeyPad.pressKey(int n) where you pass in a number (0...9) and it returns true if the keypad unlocks and false if it's still locked. Note that you could easily enter all digits of all numbers 00000 through 99999 resulting in 5*100000 key presses, but remember that the panel does not reset after every sequence of 5 digits, so find a way to do this more efficiently. Notice for example that entering the stream 3791283780 will test the length 5 sequences 37912, 79128, 91283, 12837, 28378, 83780; not only the two disjoint sequences 37912 and 83780. Think of this keypad as remembering the last 4 keys pressed (and the order pressed); when the next key is pressed, if the last 4 keys + the current key equal the correct code, the keypad will unlock. Assume the keypad does all this internally, so you can just keep feeding it keypresses and it will eventually unlock if the last 5 keypresses entered is the correct code. 2. Generalize your algorithm to work for a keypad where you don't know the length of the correct sequence in advance.
algorithm In the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players try to remove them one-by-one without disturbing the other straws. In the question here, we are concerned with the following, related problem: First n straws are dumped on the table. Next, for every pair of straws, we want to determine if the straws are connected by a path of touching straws. In other words, given a list of the endpoints for n > 1 straws (as if they were dumped on a large piece of graph paper), determine all the pairs of straws that are connected. Note that touching is connecting, but also two straws can be connected indirectly via other connected straws. Give an algorithm to compute all the pairs of straws that are connected. Here is some additional information that you can use: As a basic step you need to determine whether two straws directly touch (intersect), i.e., whether straw ab with end points a and b intersects with straw cd (with end points c and d). To get full credit also explain how the elementary step i) can be done. If you cannot find an algorithm for this step, assume an O(n 2 ) algorithm and explain how to find all pairs of straws that are connected. Analyse and explain the worst-case computational complexity of your algorithm in terms of n.
algorithm Given a lane where there are various houses each containing a fixed amount of gold. Now a robber has to rob the houses such that when he robs a house the adjacent one cannot be robbed.Calculate the maximum amount of gold collected by him.
algorithm Given a review paragraph and keywords, find minimum length snippet from paragraph which contains all keywords in any order.
algorithm Given the array of integers containing equal number of even and odd numbers. Rearrange the array such that even number is at even place and odd number is at odd place. Example : [2,1,3,4,7,9,24,98] Answer : 1,2,3,4,7,24,9,98
algorithm Implement cycle detection for a spreadsheet with the characteristics outline below. Your solution should include working data structures to represent the spreadsheet and operate on a "entire" spreadsheet to indicate which cells have circular dependencies. Spreadsheet The spreadsheet is a collection of cells within a 2-D space of columns and rows. Columns are defined with a letter and rows are defined by a number. You can assume an upper limit of 26 columns for simplicity. Cell values are either a number (long or double) or an expression containing numbers, operators, and references to other cells (i.e. B2 means the second column [B] and second row [2]). You can ignore the parsing of expressions for this exercise. Instead, your solution can define the data you will work with after expressions have been parsed. Cycles A cycle occurs when a cell refers to itself either directly or indirectly via an expression.
algorithm Given an array of integer nos. All numbers are distinct. WAP to find the two longest non-intersecting continuous subarrays of equal size s.t. *all* elements of one of them are smaller than that of the other subarray: a[i..i + k - 1] and a[j..j+k-1] where i + k <= j s.t. a[i..i + k - 1] < a[j..j+k-1] or a[i..i + k - 1] > a[j..j+k-1] and k is maximal Example: a = {1,2,3, 7, 9, 8} then we have: {1, 2, 3} and {7, 9, 8} a = {6, 5, 4, 1, 3, 7} then we have: {6, 5} and {4, 1} or {6, 5} and {1, 3} or {5, 4} and {1, 3} ...
algorithm Given a big rectangular plot of land that has rectangular or square sized buildings (all sides of every building are parallel to the big rectangular plot)... find the location and dimensions of the largest square that can be built in this rectangular plot
algorithm Given an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO], please reconstruct the itinerary in order, for example: [ CDG, MUC, LHR, SFO, SJC ]. //tickets can be represented as nodes
algorithm Given a list of queries and their counts, write a function that returns one of the queries at random such that over time it returns an equal distribution based on the counts provided in the input.
algorithm Given an array of integers and a number. WAP to find the pairs which sum of upto given number. I solved it. Then he asked about writing test cases for this function. I wrote below test cases 1.) All the elements should be number. 2.) Length of array should not be 0. 3.) Array itself should not be null. 4.) Given number, arrayLength can be represented by 32bits or 64 bits. 5.) number should not be negative. 6.) Input does not has pair, It should return false 7.) Input has pair, It should return true 8.) Input has all negative values and pair exists, then function should return true 9.) Input has all negative values and pair does not exists, function should return false He told that he is looking for more test cases. Can you guys think of some more complex test cases.
algorithm You are given a list of word. Find if two words can be joined to-gather to form a palindrome. eg Consider a list {bat, tab, cat} Then bat and tab can be joined to gather to form a palindrome. Expecting a O(nk) solution where n = number of works and k is length There can be multiple pairs
algorithm You are given a catalog of books, which have following attributes :- Name, Author, Publisher, Publish year, Category, Price, Count (sold) Implement following APIs on top of this catalog - 1) addBookToCatalog(Book) 2) searchBook(by partial book name/author) 3) getMostSoldBooks(by author name/category, limit) Expectations: Maintain DB on memory Code should be readable. Design, handle naming convention,handle exceptions & should be running
algorithm You have to compress a string in the following format. eg 1- : input : aasasatb output : 2a2sa1t1b eg2 -: input: abcdbcdff output :- 1a2bcd2f
algorithm write a merge sort algorithm to sort a file which can't be loaded into the memory. Assume you can only load 10 items in the memory at a time and there are 100 items to sort.
algorithm 0 1 ? ? wildcard for 0 or 1 "01?" 010 011 Example: 01?0? Will produce 01000 01100 01001 01101
algorithm We know a string is Palindrome if it is the same reading from both sides. Now we define the following string also Palindrome: A man, a plan, a canal, Panama! Write a code that returns if an string is palindrome and it should return true for above input. (Without directly saying, I should conclude that I have to only consider alphanumerical characters in a string). In addition, we assume the string is very long and we can not keep a copy of this string or even a copy of preprocessed version of this string. Therefore the result should be returned with the first sweep of the string.
algorithm there are 1 billion stars and you are standing at the earth. From the earth , you know the distance of all 1billion stars. Find the nearest 1 million stars from the earth.
algorithm There are discounts on particular time period suppost Day1 - Day5 => 10% Day2 - Day 8 => 5% Day4 - Day6 => 20 % find the period where maximum discounts is available. For above example the period is Day4 - Day5 => 10+5+20 that means 35% Provide the generalize solution. Period can be time also.
algorithm write a function:
algorithm Find and fix the bugs in the following function that is supposed to remove the head element from a singly linked list. void RemoveHead (node * head) { free(head); head = head - > next; }
algorithm Write a function that takes a string as an input and outputs an integer, e.g. turning "1234" into 1234.
algorithm Given a String find the first non repeating char in a single pass of the string. Assume a big character set like utf-8 (eleminate use of char[256]) Avoid any subloop to have a very optimal solution
algorithm you have a interface called Op and a Filter interface interface Op<T> { public boolean hasNext(); public boolean<T> next(); } interface Filter<T1, T2> { public boolean filter(T1 t1, T2 t2); } design a MutualOp that has below API, MutualOp should return the ops that combine op1 and op2, also should meet with the filter class MutualOp implements Op{ public MutualOp(Op left, Op right, Filter<Op, Op> filter) { this.left = left; this.right = right; this.filter = filter; } public boolean hasNext { ...... } public T next { ...... } }
algorithm Assuming you're playing one game that you need guess a word from a dictionary. You're given a machine you can try to guess the word, the machine will return how many characters has been matched by your guess. Design a system to crack the word.
algorithm Permutate a list of string this question is supposed permutate the characters instead of who string, as input example {"red", "fox", "super" }, the expected output is rfs rfu rfp rfe rfr ros rou rop roe ror rxs rxu rxp rxe rxr efs efu efp efe efr eos eou eop eoe eor exs exu exp exe exr dfs dfu dfp dfe dfr dos dou dop doe dor dxs dxu dxp dxe dxr
algorithm A 2D array filled with integer, define a flow from one point to its neighbor only if the value of current point is not less than its neighbor's value. Consider up edge and left edge as east coast, bottom edge and right edge as west coast, find all position that it can flow to east coast and west cost both
algorithm Let's assume that there's an array that has nonzero natural numbers where all the numbers repeat an even number of times, except for one value that repeats an odd number of times. Can you write me a function that takes this array, and returns the value that occurs the odd number of times? Ex : - [ 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 ]
algorithm /* For each node in a binary tree find the next right node on the same depth. Write a function that takes root node and populates "next" with the answer for each node. A / \ B -> C / / \ D -> F-> G / \ H -> I class Node { Node left; Node right; Node next; // <-- answer should be stored here }; B.next = C D.next = F F.next = G H.next = I {A, C, G, I}.next = null */
algorithm Given an array of numbers, find a pair whose sum is closest to zero.
algorithm Given a dictionary that contains mapping of employee and his/her manager like this Dictionary<string, string> employees = new Dictionary<string, string>() { { "A","C" }, { "B","C" }, { "C","F" }, { "D","E" }, { "E","F" }, { "F","F" } }; Write a function to get no of employees under each manager in the hierarchy not just their direct reports. In the above dictionary the root node/ceo is listed as reporting to himself. Output should be a Dictionary<string,int> that contains this A - 0 B - 0 C - 2 D - 0 E - 1 F - 5
algorithm N queen problem. In NXN chess board, you have to arrange N queens such that they do not interfere each other. Following is how you define interference of queens. 1. Two queens cannot be on the same diagonal 2. Two queens cannot be in same horizontal or vertical line 3. Queen can jump like a knight. So, two queens cannot be at a position where they can jump two and half steps like a knight and reach the other queen. You should return the possible ways to arrange N queens on a chess board. This was a tech screen, but since I was local, they called me in their office rather than phone interview. Hint: Don't try too hard, the best solution is n!
algorithm public interface Triangle { /** * Three segments of lengths A, B, C form a triangle iff * * A + B > C * B + C > A * A + C > B * * e.g. * 6, 4, 5 can form a triangle * 10, 2, 7 can't * * Given a list of segments lengths algorithm should find at least one triplet of segments that form a triangle (if any). * * Method should return an array of either: * - 3 elements: segments that form a triangle (i.e. satisfy the condition above) * - empty array if there are no such segments */ int[] getTriangleSides(int[] segments); }
algorithm Given an array such that every next element differs from the previous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The interviewer mentioned one more condition that the min or max should be non-edge elements of the array Example: 1 2 3 4 5 4 3 2 1 -> Local max is 5 1 2 3 4 5 -> No local max or min exists 5 4 3 2 1 -> No local max or min exists
algorithm Given an array of int return the maximum difference of any pair of numbers such that larger number of the pair occurs at higher index than the smaller.
algorithm Graph problem: Critical node: If a node reaches another node only through one node. Eg: A-C-B and A-E-B are critical nodes. (A reach B through one node which is C or E) If A reaches B through more than one node, then they are not critical nodes. 1) A-C-B A-D-E-B (A reach B thro C which might lead to critical node but A has another path to B thro D and E, so they are not critical nodes). 2) X-Y-Z X-A-Z (X and Z are critical nodes) Now find all critical nodes.
algorithm Given an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter. For Ex: Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100] n -> 2 Out put -> [100, 0] or [100, 2] Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2
algorithm write a function that detects conflicts in given meeting schedules input: a list of intervals, [(s1, e1), (s2, e2), ] output: return True if there's any conflict, False otherwise
algorithm You are given printouts from an algorithm which ran over an unsorted binary tree. One printout is from an in-order run and another from a pre-order run. Can you reconstruct the tree? If so, then write an algorithm.
algorithm You are given printouts from an algorithm which ran over a sorted binary tree. One printout is from an in-order run and another from a pre-order run. Can you reconstruct the tree? If so, then write an algorithm.
algorithm You have N points on a 2D surface. List K points at a shortest distance to the point (0, 0).
algorithm Assume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor. As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21... so the pair sequence is: [1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ... Write a function to output the first n pairs of this sequence. void Outputpairs(int n)
algorithm You are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering. *** SPOILER ALERT *** The question was pusposefully underspecified - upon questioning it was revealed that the string O might not necessarily include all characters used in string T - the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order).
algorithm You are given two arrays - A & B. The length of the arrays is the same - N. The values in the arrays are integers from 0 to N - 1 in random order and no number is repeated. You need to list a sequence of two-element swaps required to reorder the array A into the order of the array B. Additionally, at each step of the sequence you are allowed to swap two elements only if one of them is 0.
algorithm Given a Integer, find the maximum number that can be formed from the digits. Input : 8754365 output : 8765543 I told solution in nlogn. He asked me optimize further.
algorithm Write a method that takes the root of a tree as input and check if the tree is a Binary Search Tree (BST).
algorithm given an expression like 3*4 + 8-9 (only +, - , * operators) as a string evaluate it strictly from left to right
algorithm Check if the given binary tree is a unival tree. (all nodes have same value) Follow up- Count the number of unival subtrees in a binary tree.
algorithm You are given a function: List<TimeSlot> getTimeSlots (String friend) Assume getTimeSlots() returns available times for a friend, sorted in order, with no overlap. Assume TimeSlot has comparable function You want to schedule a meeting among all of your friends, such that all can attend. Implement a function to get the first 3 common TimeSlots among all your friends: List<TimeSlot> get3CommonTimeSlots (List<String> friends) user1 1-2pm, 3-4pm, 7-8pm user2 1-2pm, 5-6pm
algorithm You are tasked with implementing a method that returns the lowest possible number that could be generated after removing n characters from a string of digits. The method signature should look like:
algorithm You are given a 2d rectangular array of positive integers representing the height map of a continent. The "Pacific ocean" touches the left and top edges of the array and the "Atlantic ocean" touches the right and bottom edges. - Find the "continental divide". That is, the list of grid points where water can flow either to the Pacific or the Atlantic. Water can only flow from a cell to another one with height equal or lower. Example: Pacific ~ ~ ~ ~ ~ |__ ~ 1 2 2 3 (5) ~ ~ 3 2 3 (4)(4) ~ ~ 2 4 (5) 3 1 ~ ~ (6)(7) 1 4 5 ~ __ (5) 1 1 2 4 ~ |~ ~ ~ ~ ~ Atlantic The answer would be the list containing the coordinates of all circled cells: [(4,0), (3,1), (4,1), (2,2), (0,3), (1,3), (0,4)]
algorithm Problem Statement Diameter The diameter of a graph is the maximum shortest path between any two nodes. At the beginning, there is a simple grpah contains exactly 1 node. Then we add new nodes one by one to the graph. Each time when we add a new node to the graph, we also add exactly one edge to connect this node to another node which already exists. We want to find the diameter of the graph each time we add a new node. Note that each edge cost 1. Input Format: First line of the input contains one integer N, indicating how many new nodes we will add. Then following N lines. The ith line contains an integer X, which means we add the ith node and an edge connecting the Xth node and ith node. The original node is the 0th node. Output Format: Output N lines. The ith line is an integer indicating the diameter of the graph after adding the ith node. Constraints: 0 < N <= 100000 0 <= Xi < i i is counting from 1 Sample Input: 5 0 0 1 1 1 Sample Output: 1 2 3 3 3 Explanation: Firstly the graph contains only node 0. The first line of output is 1 because the diameter becomes 1 when node 1 is added and connected to node 0. Diameter becomes 2 after adding node 2 to node 0. Then adding node 3, 4, 5, all of them are connecting to node 1, caculate the shortest path of all pairs of nodes, the maximum shortest path is 3, so the last 3 lines of output are all 3.
algorithm You are given a class name Person that looks like this
algorithm Write a function that takes an integer as input and produces an output string. Some sample Input/outputs are as follows i/p o/p 1 - A 2 - B 3 - AA 4 - AB 5 - BA 6 - BB 7 - AAA 8 - AAB 9 - ABA 10 - ABB 11 - BAA 12 - BAB 13 - BBA 14 - BBB 15 - AAAA
algorithm A robot has to move in a grid which is in the form of a matrix. It can go to 1.) A(i,j)--> A(i+j,j) (Down) 2.) A(i,j)--> A(i,i+j) (Right) Given it starts at (1,1) and it has to go to A(m,n), find the minimum number of STEPS it has to take to get to (m,n) and write public static int minSteps(int m,int n) For instance to go from (1,1) to m=3 and n=2 it has to take (1, 1) -> (1, 2) -> (3, 2) i.e. 2 steps
algorithm Consider a social network graph like facebook. You are throwing a party and want to invite some of your friends. Design a algorithm to select top n friends from m friends using the social graph.
algorithm Given an m x n matrix where each row element is sorted, but the columns do not appear in sorted order, write a function to print each matrix element in sorted order. Example matrix: matrix = [ [20, 40, 80], [5, 60, 90], [45, 50, 55] ] Your function should print 5, 20, 40, 45, 50, 55, 60, 80, 90. Add on: Assume that we are space-constrained such that we can only hold one row in memory at a time. Optimize your function to work under such constraints as efficiently as possible.
algorithm Given a matrix of integers where each row is sorted but the columns are not sorted, print each matrix element in sorted order. Here's an example matrix:
algorithm Question: Given two strings, find number of discontinuous matches. Example: cat, catapult Output: 3 => CATapult, CatApulT, CAtapulT
algorithm You have a function rand5(). This function returns numbers between 1 and 5 randomly with equal probability. Implement a function rand7() which makes use of rand5 to return a number between 1 and 7 randomly with equal probability.
algorithm Question: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T Example [23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20 [1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8 [1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7
algorithm Find popular item in sorted array of natural numbers. An item is popular is if its repeated n/4 times or more. For Ex: Input: 123444445678 Popular item is 4. Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.
algorithm given a string without space "iamstudent" output "i am student" u are provided with a dictionary to check words
algorithm A plumber working for a company as a contractor. His job is attend services and submit the bill to get his salary on basis of daily work including his service charge 500 rupees. For a typical plumbing work he need pipes with different lengths. But in market he will get new pipe with standard size 100m of cost 100 rupees. (no small or large sized pipes available) Now , he need 10 , 40 , 60, 70 lengths of pipes for a jobwork. Generally company gives him (4 pipes * 100 rupees) + 500rupees as service charge = 900 rupees. but plumber bought only 2 pipes cut as follows and get his job done... 1st pipe => 40+60 2nd pipe => 10+70 + extra left(20) By buying only 2 pipes he get his job done. remaining 2 pipes money saved. write an efficient algorithm to calculate minimum number of standard size pipes required for given number of different pipes lengths: Input: N => total pipes for jobwork arr[N] => lengths of pipes. (for simplicity, pipe size will be either smaller or equal to standard size) outpud: minimum statdard sized(100m) pipes required constraint: you can only cut them can not join them back as follows say he need 10 95 95, with two pipes 100 100 = > 95+5 95+5 => 95 95 (5+5)// this is not accepted EX: Input: 5 20 30 50 60 80 output: 3 Input: 5 10 10 10 15 20 35 55 60 70 75 75 80 output: 6
algorithm Which is best Merge Sort or QuickSort? Why and How?
algorithm Amazon wants to implement a new backup system, in which files are stored into data tapes. This new system must follow the following 2 rules: 1. Never place more than two files on the same tape. 2. Files cannot be split across multiple tapes. It's guaranteed that all tapes have the same size and that they will always be able to store the largest file. Every time this process is executed, we already know the size of each file, and the capacity of the tapes. Having that in mind, we want to design a system that is able to count how many tapes will be required to store the backup in the most efficient way. The parameter of your function will be a structure that will contain the file sizes and the capacity of the tapes. You must return the minimum amount of tapes required to store the files. Example: Input: Tape Size = 100; Files: 70, 10, 20 Output: 2
algorithm Given a list of employees and their bosses as a text file , write a function that will print out a hierarchy tree of the employees. Sample input = Sam, Ian, technical lead, 2009 / Ian, NULL, CEO,2007/ Fred, Sam, developer, 2010 The format is name, supervisor, designation, year of joining The output should be Ian CEO 2007 -Sam Technical lead 2009 - -Fred Developer 2010
algorithm You are given a set of unique characters and a string. Find the smallest substring of the string containing all the characters in the set. ex: Set : [a, b, c] String : "abbcbcba" Result: "cba"
algorithm write an algorithm to find sum of numbers which are smaller than N and divisible by 3 or 5 Example: N = 9 => 3 + 5 + 6 = 14 N = 10 => 3 + 5 + 6 + 9 = 23
algorithm design and implement a calculater that can calculate expressions like: + 2 4 * 8 ( + 7 12) ( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) (PS:all items are space delimetered.) Example answers + 2 4 => 2 + 4 = 6 * 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152 ( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148
algorithm there are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who) Write two methods called "getNumber" and "requestNumber" as follows Number getNumber(); boolean requestNumber(Number number); getNumber method should find out a number that did not assigened than marks it as assiged and return that number. requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true. design a data sturucture to keep those numbers and implement those methods
algorithm {{ There are 3 machines M1, M2 and M3. Each machine is 90% full of its capacity with integers. Now you have to sort all the integers combined and then store the first 1/3rd in M1, second 1/3rd in M2 and last 1/3rd in M3. Your objective is to minimize the number of sort operations and number of data transfer operations. Each sort operation/data transfer operation is counted as 1 irrespective of the count of values that are being sorted/transferred. }}
algorithm How to find efficiently the minimum of an array of integers that is the maximum of other arrays? Example: A = [126, 110, 130] B = [125] C = [105, 115] The minimum element of array A that is the maximum of B and C is 126
algorithm Write a function that receives a stream of pairs: id (some unique integer) + weight (positive real number). The stream ends with the special pair {0,0}. The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights sum when stream has ended). Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption. Example: If this was the stream: {1,2},{2,2},{3,4},{4,10}, then id 2 would be returned with probability 1/9.
algorithm Write a class that receives in the constructor a vector of strings representing a browser history (URLs), and a method for "auto-complete": The method that receives a string representing a partial URL typed by the user and returns a vector of all possible completions of this partial URL (prefix).
algorithm You have a binary search tree and you have to return the two nodes such that there sum i equal to K. Pseudo code is to be given. O(n)time & O(n) sppace is easy but challenge O(n) time & O(1) space.
algorithm You are given a 2D Array that contains only 0s and 1s in sorted order. i.e. First Os and then 1s. Array: 0 0 0 1 1 1 1 1 0 0 1 1 0 1 1 1 You have to figure out the row that contains maximum number of 1s. e.g. in above case we have row 2 as the answer.
algorithm Given two sorted arrays, mergesort them into 2nd array that has enough space to accommodate both.
algorithm Given row on N house, each is marked either R or B. And each house having some gems. You have to collect gems from these house with some constraint: You can choose gems from any blue house but you have to choose even number of red house ( either from 2 Red houses or from 4 red houses) each time you take gem from one house, you will multiply gems received with gems currently, you have. You have to choose continuous houses. You have to return start point and end point of house (remember this should be continuous )
algorithm you have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray. You have to return sum of max M subarray of size K (non-overlapping) N = 7, M = 3 , K = 1 A={2 10 7 18 5 33 0} = 61 subsets are: 33, 18, 10 (top M of size K) M=2,K=2 {3,2,100,1} = 106 - subsets are: (3,2), (100,1) 2 subsets of size 2
algorithm Design a data structure for following operations in O(1) time.: insert remove (FIFO) find MODE
algorithm Given an array of integers find the element for which the sum of left = sum of right. example -1 100 1 98 1 should return index of 1 i.e 2 Answer: First told him about Brute Force approach and then told him if we can iterate once and get the total sum
algorithm Inplace reverse a sentence You given a sentence of english words and spaces between them. Nothing crazy: 1) no double spaces 2) no empty words 3) no spaces at the ends of a sentence
algorithm The closest common ancestor in a tree forest.
algorithm 3> write program to find wrong no of "(()" parenthesis in expression "((B+a)" give error for "((A))" - for unnecessary brackets
algorithm 1> write program to calculate power(x,n) in log(n) time
algorithm Given a 4 X 4 game slot that has random alphabets in all the slots Write a function that takes the keyboard and the word as input and returns true if the word can be formed False otherwise. A word can be formed on the board by connecting alphabets adjacent to each other (horizontal, vertical and diagonally) Same alphabet should not be reused.
algorithm Design a TinyURL like Service.
algorithm You have String array like{'cat','good','tac','act''....} like some 1000 words. So if i give input tac ,output should be cat and act.. How can we implement with less complexity
algorithm Given an array of integers, return true if there're 3 numbers adding up to zero (repetitions are allowed) {10, -2, -1, 3} -> true {10, -2, 1} -> true -2 + 1 +1 =0
algorithm Print all subset of a given set which sums up to ZERO {8,3,5,1,-4,-8} so ans will be : {8,-8} {3,5,-8} {3,1,-4} size of set can be upto 50 but elemet of set can be as big as 18 digit number
algorithm Given a binary search tree (BST), write a mehtod that will convert this BST into a doubly linked list that is sorted (ascending or descending order) and returns the first element in this list. You may assume you are given following Node class:
algorithm Given a Tree:
algorithm boolean checkPattern(String str) { // Implementation } Implement the method checkPattern. str is a string argument. Return true: if the string is following any pattern example: xyzxyzxyz Here "xyz" is the pattern return false: String is not following pattern example: xyzxyzA A is not in part of pattern.
algorithm Design and Implement a Telephone database structure in which a Customer Entry has PhoneNum,Name,Address. a) Given any PhoneNum return all the Customer details b) Given any Name list all the Entries (As Name can be duplicate, only PhoneNum is unique) c) Also Name searching should support Prefix Based.
algorithm Given an array of ages (integers) sorted lowest to highest, output the number of occurrences for each age. For instance: [8,8,8,9,9,11,15,16,16,16] should output something like: 8: 3 9: 2 11: 1 15: 1 16: 3 This should be done in less than O(n).
algorithm Constructing Bridges: A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river. Construct as many Non-Crossing Bridges as possible. Input: Above Bank >> 7 4 3 6 2 1 5 Below Bank >> 5 3 2 4 6 1 7 are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7) Output: (1,1) (3,2) (4,3) (6,4) (7,5)
algorithm You are given a file which contains 3 values - start time, end time, amount of water flowing between the start time and end time for one day The start time and end time may overlap and are inclusive. The times are not in a sorted order Example: 0,10,100 10,15,300 16,20,400 5,15,200 Find the max flow of water at any instant of time. In the above example, the answer is 600 ( at instant 10)
algorithm Print a BST such that it looks like a tree (with new lines and indentation, the way we see it in algorithms books).
algorithm Write a function that takes the following inputs and gives the following outputs. Input: A list of points in 2-dimensional space, and an integer k Output: The k input points closest to (5, 5), using Euclidean distance Example: Input: {(-2, -4), (0, 0), (10, 15), (5, 6), (7, 8), (-10, -30)}, k = 2 Output: {(5, 6), (7, 8)}
algorithm given a vector of integers, v[i] represent the stock price on day i. Now you may do at most K transactions. you must sell your stock before you buy it again and that means you can NOT have two stocks at the same time. write a program to find max profit you can get.
algorithm Given a staircase that has 'n' step, and you climb the staircase by jumping over the steps. You can cover at max of 'k' steps in a single jump. List all the possible sequence of jumps you could take to climb the staircase. input: n=4, k=2 output: 1,1,1,1 1,1,2 1,2,1 2,1,1 2,2
algorithm Given a list of strings, return a list of lists of strings that groups all anagrams. Ex. given {trees, bike, cars, steer, arcs} return { {cars, arcs}, {bike}, {trees, steer} } m = # of words n = length of longest word I solved this in O(m * n * log n) time.
algorithm You have a chess board of size NxN. You have a horse at a given starting position. You also have a function that gives you all the positions that the horse can reach from it's current position. Given an ending position, find the path to it that uses the minimum number of moves.
algorithm Given two input string check if anyone is substring of other. example aaaaaabbb, aaaabbb return true PS: Don't use any internal string library :)
algorithm Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target. If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]| You can assume each number in the array is a positive integer and not greater than 100 Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.
algorithm Give you a list of Modules of Dependencies, A --> B,C B --> D,E,F D --> F And please return back a correct build order of Module (input)
algorithm Give an 2d-characters Grid, char[][] A, and a dictionary, List<String> dict. Search all possible words in the 2d-Grid.
algorithm Take a list of integers (left to right order) and return an integer of the number of identical binary trees that can be created from the same list. Input: [10, 8, 15, 6, 9, 4, 5] Output: 24 Input: [12, 6, 19, 15, 5] Output: 6 Input: [44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64] Output: 1 I wrote a brute-force 'solution', creating a binary tree for each permutation of the list (with the same root as Input list) and compared each to the binary tree from the Input list. For large input lists (length > 10), my 'solution' is useless.
algorithm Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting input: increasing sequence of pair of numbers per1: (1,5) (10, 14) (19,20) (27,30) per2: (3,5) (12,15) (18, 21) (23, 24) ouput: (6,9) (16,17) (22,22) (25,26)
algorithm Given an array of integers. Move all non-zero elements to the left of all zero elements.
algorithm There's a new language which uses the latin alphabet. However, you don't know the order among letters. It could be: a b c d ... as it could also be: b e z a m i ... You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language.
algorithm There are different buildings standing close to each other. These are of same width but different height. Suppose if rainfall happens, what will be the volume of water that get trapped on top of all these buildings together. ? INPUT (Example) No: of buildings : 4 heights of the buildings(in any units): 3 4 3 4
algorithm Given a array of positive integers, find all possible triangle triplets that can be formed from this array. eg: 9 8 10 7 ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10 Note : array not sorted, there is no limit on the array length
algorithm Given an array of type:- 1. Increasing 2. Decreasing. 3. Increase-Decrease 4. Decrease-Increase Find:- 1. Type of array in minimum steps ? 2. Maximum element from array in min steps?
algorithm Question was "Given a pattern and a string input - find if the string follows the same pattern and return 0 or 1. Examples: 1) Pattern : "abba", input: "redbluebluered" should return 1. 2) Pattern: "aaaa", input: "asdasdasdasd" should return 1. 3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0. I can think of a brute-force solution for this question where we add the character in the pattern and n length of the string to a hashmap and recurse over the pattern array and string. But is there anything more efficient? This was a pretty difficult question in my opinion.
algorithm There are multiple rooms in a floor. There are one or more fire exits. Each door can be designed with an option of pull or push. For fire safety, a door should be designed so as to open (push) towards the fire exit. Design a data structure to represent the floor and door design. A person could start from any room and moves towards fire exit. Write an algorithm to check if all the doors are designed to be pushed towards fire exit.
algorithm Given a large array of unsigned ints, quickly find two who's sum is 10 Then the interviewer asked me to write test cases. Followed by how to implement this on a distributed system, where multiple systems can read/write simultaneously on a shared cache (HINT: It is ok if you do not return the first instance)
algorithm There is a string whose characters can only be either a, b or _ (there can be only one _ in the string). At each step, we can modify the string as follows: 1. _ can be swapped with its adjacent character, example a_ba can be changed to either _aba or ab_a. 2. Two characters adjacent to _ (both on the same side of _) can be reversed along with the _ if both characters are different, example, aa_ba can be changed to aaab_ but not to _aaba because both characters are a. You are given two strings, the initial state and the final state (lengths will be same), you have to output the minimum number of steps required to change the string in initial state to the string in the final state. example: input: a_b ab_ output: 1 input: abaa_a b_aaaa output: 4 reason for example 2:- abaa_a -> aba_aa -> ab_aaa -> _baaaa -> b_aaaa
algorithm You have a sorted array containing the age of every person on Earth. [0, 0, 0, 0, ..., 1, 1, ..., 28, 28, ..., 110, ...] Find out how many people have each age.
algorithm Write a program to find pattern. 0: 1 1: 11 2: 21 3: 1211 4: 111221 5: 312211 Iterate over the previous number, and find count for same number number. Append that count before number. e.g., public String pattern(int input){} If input = 4, function should return 111221.
algorithm Minesweeper question: Given an n x m grid holding individual mine co-ordinates, identify all of the mine clusters. A mine cluster is the largest collection of neighboring mines. Example input: 0 1 2 3 --------- 0|0|1|0|1 1|0|0|1|1 2|0|0|0|0 3|1|1|0|0 Expected output: [cluster 1] (0,1),(1,2),(1,3),(0,3) [cluster 2] (3,0),(3,1)
algorithm Let's say there is a double square number X, which can be expressed as the sum of two perfect squares, for example, 10 is double square because 10 = 3^2 + 1^2 Determine the number of ways which it can be written as the sum of two squares
algorithm Sort the elements inside a stack using only push and pop opperation. Is it possible to do it only with one additional stack?
algorithm given a range of number 1 through N, where N >=3. you have to take an array of length 2N and place each number ( from the range 1 to N) twice. such a that the distance between two indexes of a number is equal to the number. example N=3 ( 3, 1, 2, 1, 3, 2 ) I know we can Use Backtracking but is there any other solution.
algorithm We have words and there positions in a paragraph in sorted order. Write an algorithm to find the least distance for a given 3 words. eg. for 3 words job: 5, 9 , 17 in: 4, 13, 18 google: 8, 19, 21 ... ... Answer: 17, 18, 19 Can you extend it to "n" words? Context: In Google search results, the search terms are highlighted in the short paragraph that shows up. We need to find the shortest sentence that has all the words if we have word positions as mentioned above.
algorithm Given a M * N matrix, if the element in thematrix is larger than other 8 elements who stay around it, then named thatelement be mountain point. Print all the mountain points.
algorithm The cows and bulls game, Player A chooses a word and player B guesses a word. You say bulls when a character in the player B's guess match with a character in player A's word and also it is in the corect position as in A's word. You say cows, when a character in the player B's word match the character in player A, but it is not in the correct position. The characters are case insensitive. Given two words player A's and player B's,Write a function that return the number of bulls and no of cows. For example, A - Picture B- Epic, bulls -0, cows - 4 A - forum B - four, bulls - 3 cows - 1
algorithm Find Maximum sum subarray such that no elemnt in subarray is repeated https://www.facebook.com/photo.php?fbid=10152820917104183&set=pcb.1523587287892659&type=1&theater
algorithm Asked at Walmart Labs ---------------------------------- There is a row of seats. Assume that it contains 15 seats adjacent to each other. There is a group of people who are already seating in that row randomly. i.e. some are sitting together & some are scattered. Take the row as a String in java. The seat which is occupied is marked with a character 'X' & which is not occupied is marked with a dot '.' Now your target is to make the whole group sit together i.e. next to each other and without having any vacant seat between them in such a way that the total number of hops or jumps at the end of the grouping them together should be minimum. Ok let me try to explain you in details. Here is the row having 15 seats represented by the String (0, 1, 2, 3, ......... , 14) - . . . . x . . x x . . . x . . Now to make them sit together one of approaches is - . . . . . . x x x x . . . . . Following are the steps to achieve this - 1 - Move the person sitting at 4th index to 6th index - Number of jumps by him = (6 - 4) = 2 2 - Bring the person sitting at 12th index to 9th index - Number of jumps by him = (12 - 9) = 3 ------------------------------------------------------------------------------------------------------------------------------------------------------------ So now the total number of jumps made = ( 2 + 3) = 5 which is the minimum possible jumps to make them seat together. There are also other ways to make them sit together but the number of jumps will exceed 5 & that will not be minimum. For example bring them all towards the starting of the row i.e. start placing them from index 0. In that case the total number of jumps will be ( 4 + 6 + 6 + 9 ) = 25 which is very costly and not an optimized way to do this movement. Now write an algorithm which will return the minimum number of jumps required to make them sit together.
algorithm write code to validate if the input string has redundant braces? ((a+b)) - Has redundant braces. (a+(b+c)) - This doesn't has redundant braces.
algorithm Find the unique number that is present only once in array while all the others are present three times. Example: 2,3,5,1,2,2,5,3,5,3 Answer : 1 as 2,3,5 are repeated three times Complexity should be better than O(nlogn)
algorithm Given the relative positions (S, W, N, E, SW, NW, SE, NE) of some pairs of points on a 2D plane, determine whether it is possible. No two points have the same coordinates. e.g., if the input is "p1 SE p2, p2 SE p3, p3 SE p1", output "impossible".
algorithm Given an array of integer, find the number of un-ordered pairs in that array, say given {1, 3, 2}, the answer is 1 because {3, 2} is un-ordered, and for array {3, 2, 1}, the answer is 3 because {3, 2}, {3, 1}, {2, 1}. Obviously, this can be solved by brute force with O(n^2) running time, or permute all possible pairs then eliminate those invalid pairs. My question is does any body have any better solution and how would you do it because it seems like a dynamic programming problem. A snippet of code would be helpful
algorithm given expression with operands and operators (OR , AND , X-OR) , in how many ways can u evaluate the expression to true, by grouping in different ways? Operands are only true and false. for example true & false | true ^ false can be grouped to true & ((false | true) ^ false) and so on.. the following wiki of the above question http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
algorithm Suppose we are given a set L of n line segments in the plane, where the endpoints of each segment lie on the unit circle x^2 + y^2 = 1, and all 2n endpoints are distinct. Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects.
data-structures 1. Difference between arrays and link list 1.1 How to prepend each of the above with extra data 2. Hash-table. What datastructure to use to create one. How to resolve collision
data-structures given preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ? @Anonymous Thanks for the reply! Please try other use cases like, only single leaf node
data-structures Given a set of possibly overlapping rectangles in different levels (All of which are "not rotated", can be uniformly represented as (left-bottom,right-top) tuplets), return a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area. The rectangle at lower level has more priority than at higher levels.
data-structures Given an integer target and binary tree (not a binary search tree!) each of whose nodes contains an integer (which may be positive or negative), find the set of all subtrees whose sum equals the given target. The sum of a subtree is just the sum of the integers contained in its nodes. Note that the subtree does not have to contain all child nodes - it can be any set of connected nodes.
data-structures Print the longest path from root to leaf in a Binary tree (Basically the nodes that lie on the height path).
data-structures You are given a function getNum() that returns a random number in the range 1 to 10 million with repetitions. However, it may also return -1 when it no longer provides numbers. Write a function that calls getNum() continuously until it returns -1 (if a repetition, should not store it); as soon as u see -1, stop calling getnum() and print all the numbers seen so far in a sorted way. Condition: You have got very limited memory to work with.
data-structures A program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35
data-structures Given two sorted linked lists of integers write an algorithm to merge the two linked lists such that the resulting linked list is in sorted order. You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.
data-structures This is was asked in Amazon SDE online test from Hacker rank. Initech is a company which has CEO Bill and a hierarchy of employees. Employees can have a list of other employees reporting to them, which can themselves have reports, and so on. An employee with at least one report is called a manager. Please implement the closestCommonManager method to find the closest manager (i.e. farthest from the CEO) to two employees. You may assume that all employees eventually report up to the CEO. Tree structure: Bill -> Dom, Samir, Michael Dom -> Bob, Peter, Porter Peter -> Milton, Nina Sample Data: CEO Bill has 3 employees reporting to him: {Dom, Samir, Michael} Dom has three reports { Peter, Bob, Porter} Samir has no reports {} Michael has no reports {} Peter has 2 reports {Milton, Nina} Bob has no reports {} Porter has no reports {} Milton has no reports {} Nina has no reports {} Sample calls: closestCommonManager(Milton, Nina) = Peter closestCommonManager(Nina, Porter) = Dom closestCommonManager(Nina, Samir) = Bill closestCommonManager(Peter, Nina) = Peter
data-structures How to find middle element in a linked list without knowing the length of the linked list
data-structures Design a data structure which could perform the following operations in O(1): - Insert(), Delete(), Search(), getRandom() getRandom() should pick a "random" element from your data structure, and should not be predictable (for instance always picking the "first" element from your DS)
data-structures You are given a stream of incoming strings. Design a data structure, which at any instant, could tell the 100 most repeated words in constant time.
data-structures Given a 4*n block, find number of different ways of filling it with 1*2 smaller blocks. Rotation of smaller blocks is allowed.
data-structures Given an array of numbers, for every index i, find nearest index j such that a[j] > a[i].If such an index doesnt exist for i, 1 should be printed.
data-structures Data structure which supports both map operations and array operations without time complexity penalty.
data-structures How to find if a given expression is a valid arithmetic expression? Eg:(())()) - Invalid expression, (()()) - Valid expression
data-structures Given a linkedlist, write an algorithm to divide the linkedlist into two linkedlists, the first contains the Fibonacci numbers in the list and the second contains the non-Fibonacci numbers. Test the algorithm after developing the code
data-structures Suppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read. The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.
data-structures Design a data structure which should have following operation. Insert, Delete, Random access
data-structures Design a data structure in which we can do all CRUD operations in O(1) ? CRUD- Create, Retrieve, Update, Delete
data-structures A single-elimination tournament with 64 teams. Before the tournament, fans construct fantasy brackets for their tournament predications. Design a data structure for storing fan brackets and algorithm to score their brackets against a winning bracket. Assume we will then need to quickly score a players predictions (1 point per successful round prediction) and your solution should be optimal enough to handle millions of fan brackets with minimal data.
data-structures Design a data structure that supports kind of full text search but in numbers. We are given file with lot of 10-digits numbers, for example: 1234 567 890 4124 123 123 3123 123 322 On a given number X we should return all numbers that contain X. For example, if the number 123 was given, we should return all numbers (from the list above) because 123 is in all of them. If the number 41 was given we should return only the middle number - because the number 41 is only in it.
data-structures Tech Screening Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry. Interviewer was expecting O(N) solution for N asks. Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks. and integers are not given in a array, every time only one integer will be passed as input to your method.
data-structures How would you increase efficiency of a hive query?
data-structures Given an array of integers and a number. WAP to find the pairs which sum of upto given number. I solved it. Then he asked about writing test cases for this function. I wrote below test cases 1.) All the elements should be number. 2.) Length of array should not be 0. 3.) Array itself should not be null. 4.) Given number, arrayLength can be represented by 32bits or 64 bits. 5.) number should not be negative. 6.) Input does not has pair, It should return false 7.) Input has pair, It should return true 8.) Input has all negative values and pair exists, then function should return true 9.) Input has all negative values and pair does not exists, function should return false He told that he is looking for more test cases. Can you guys think of some more complex test cases.
data-structures Write a function that accepts root of a binary tree and print zigzag level order traversal, each level print in new line. For example, Given tree: 1 2 3 4 5 6 7 8 9 output: 1 2 3 7 6 5 4 8 9
data-structures Write a function that accepts root of a binary tree and return true if it is foldable otherwise return false. A binary tree is foldable if left subtree of root is mirror image if right subtree. For example: Given tree, 1 2 3 4 5 5 4 6 6 output: trus
data-structures Write a function that accepts root of a binary tree and print zigzag level order traversal, each level print in new line. For example, Given tree: 1 2 3 4 5 6 7 8 9 output: 1 2 3 7 6 5 4 8 9
data-structures Write a function that accepts two character arrays each represents a floating point number and return their sum in character array. For example function accepts "23.45" and "2.5" and return their sum "25.95". Restriction: We cannot use predefined functions / methods or parsing. We have to go with basic operations.
data-structures You are given two objects, Student and Course, and there exist a many to many relation between them. One student can be enrolled for more than one course and there can be many students enrolled for a single course. Design an effective data structure to store such data keeping in mind that the time complexity for search should be optimum. A search can be for the list of students enrolled for a single course, or for the list of courses a single student is enrolled.
data-structures Find the depth of Binary search tree without using recursion?
data-structures Implement a program to reverse the linear linked list in pairs. it should handle both even number of nodes and odd number of nodes. if odd number of nodes, the last node will be the last node after reversion. Do not move the data in the nodes. Do manipulate node pointers/references. the nodes themselves need to be manipulated, not just the data in the nodes. For example, if the initial linear linked is, 1->2->3->4->5 after reverse it should be, 2->1->4->3->5
data-structures Implement a function that checks if the given binary tree is binary search tree(BST). Use tree operations to solve this. do not try solving by pre-order traversal of the tree and then checking if the array is sorted. instead, traverse the tree for checking if it is BST.
data-structures Design a data structure to keep track of top k elements out of 2 billion records. Each record is numberd with a key which is 30 bit and a number which is count of how many times the customer has visited us. Come up with an data structure so that the updation of element in 2 billion records will be faster. Getting top k element will be faster
data-structures How can you determine if an array is pre order representation of a binary tree. I started with the logic of creating binary tree using a pre order array and failure to create the tree will mean that the array is not a pre order representation, but got stuck in middle.
data-structures New data structure where tree is reversed. Leaves are at the top and root at the bottom. Given two nodes in such DS find the least common ancestor in such tree.
data-structures Phone Interview with Collabedit. /** Compute the value of an expression in Reverse Polish Notation. Supported operators are "+", "-", "*" and "/". * Reverse Polish is a postfix mathematical notation in which each operator immediately follows its operands. * Each operand may be a number or another expression. * For example, 3 + 4 in Reverse Polish is 3 4 + and 2 * (4 + 1) would be written as 4 1 + 2 * or 2 4 1 + * * * @param ops a sequence of numbers and operators, in Reverse Polish Notation * @return the result of the computation * @throws IllegalArgumentException ops don't represent a well-formed RPN expression * @throws ArithmeticException the computation generates an arithmetic error, such as dividing by zero * * <p>Some sample ops and their results: * ["4", "1", "+", "2.5", "*"] -> ((4 + 1) * 2.5) -> 12.5 * ["5", "80", "40", "/", "+"] -> (5 + (80 / 40)) -> 7 */
data-structures design and implement a calculater that can calculate expressions like: + 2 4 * 8 ( + 7 12) ( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) (PS:all items are space delimetered.) Example answers + 2 4 => 2 + 4 = 6 * 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152 ( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148
data-structures there are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who) Write two methods called "getNumber" and "requestNumber" as follows Number getNumber(); boolean requestNumber(Number number); getNumber method should find out a number that did not assigened than marks it as assiged and return that number. requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true. design a data sturucture to keep those numbers and implement those methods
data-structures You are given a binary search tree and a positive integer K. Return the K-th element of the tree. No pre-processing or modifying of the tree is allowed.
data-structures You are given a double linked list and an array of pointers to elements in this list (no assumptions can be made on the array - number of pointers, order and duplicates allowed). Return the number of sequences of elements (groups of consecutive elements), pointed by the array. For example, if this is the array (number relates to index in the list, not the actual pointer value): 9,1,3,7,8,5,2. Then output is 3, representing these sequences: [1,2,3], [5], [7,8,9]
data-structures Write a function that does an in-order traversal of a tree and prints out the contents (Assume each node has 1 piece of content which is an integer). Write this function without using recursion (you can assume a library that has stack/queue/list objects with some standard methods is available for use by you). What is the maximum size your stack can grow to and what is the expected size that your data structure can grow to assuming that the tree has n nodes?
data-structures Design a TinyURL like Service.
data-structures How can you design a data structure that can do the following operations in O(1) time: Insert, Delete, Search, Max which returns the maximum number I know delete, search and insert can be done O(1) time in a hashmap with a proper hash function. But not sure Max is even possible in O(1) with the presence of delete operation?
data-structures Constructing Bridges: A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river. Construct as many Non-Crossing Bridges as possible. Input: Above Bank >> 7 4 3 6 2 1 5 Below Bank >> 5 3 2 4 6 1 7 are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7) Output: (1,1) (3,2) (4,3) (6,4) (7,5)
data-structures Given a 2^31 x 2^31 tic tac toe board, describe how you would store the state of the game to check if there is a winner.
data-structures A binary tree represent an organization hierarchy. The root node is the CEO and etc. design a algorithm to print the tree level by level.
data-structures Implement a vector-like data structure from scratch. This question was to be done in C or C++. Discussion topics: 1. Dealing with out of bounds accesses. 2. What happens when you need to increase the vector's size? 3. How many copies does the structure perform to insert n elements? That is, n calls to vector.push_back
data-structures Given a string (1-d array) , find if there is any sub-sequence that repeats itself. Here, sub-sequence can be a non-contiguous pattern, with the same relative order. Eg: 1. abab <------yes, ab is repeated 2. abba <---- No, a and b follow different order 3. acbdaghfb <-------- yes there is a followed by b at two places 4. abcdacb <----- yes a followed by b twice The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time. In the sense, it should be checked for every pair of characters in the string.
data-structures Write a program to implement Double Linked List from Stack with min. complexity.
data-structures The stepping number: A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 8,343,545 are stepping numbers. While 890, 098 are not. The difference between a 9 and 0 should not be considered as 1. Given start number(s) and an end number(e) your function should list out all the stepping numbers in the range including both the numbers s & e.
data-structures You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of values that satisfy A+B = C + D, where A,B,C & D are integers values in the array. Eg: Given [3,4,7,1,2,9,8] array The following 3+7 = 1+ 9 satisfies A+B=C+D so print (0,2,3,5)
data-structures We have 'n' patients and 'm' problems. The problems are of boolean type. Eg diabetes problem would be 'T' if a patient has it or 'F' otherwise. Suggest the data structure you would store this scenario on? Q: We have a set of problems {diabetes, liver disease, kidney disease} find all the patients who have at least the 3 problems from the set. The number of patients can be huge (n). The number of problems not comparatively huge (m). Which would be the best data structure to store these kind of records, so that we have a better search time.
data-structures How to impliment Google map Data Structure and algorithm. 1. Zoom in/out 2. horizontal/ vertical. Assumtion - all the image of earth with pixel\Any other assumption is allowed
data-structures How google map implemented ? zoom in , zoom out, moving horizontal and moving vertically. Give data Structure and algorithm. Given all the data from satellite which revolve around earth in spiral way.
data-structures Given a Sorted integer array which is rotated N number of times. You have no idea what that N is. An element in the array can occur more for any number of time. Write a method to search the position of a given element. If there are more than one of the same element, return the position of the first element.
data-structures JAVA: Given an array say of length 1000; Pick up every value from every 20th index and store it in a separate array. Make sure to loop through all the elements in the array. Example: newArray1 = {0, 20, 40, 60, ..}; newArray2 = {1, 21,41, 61, ..};
data-structures How will you design, and what data structure will you use for a contact list in a cell Phone. It should support insert/modify/delete/search functionality like that provided in a cell phone. Suppose some of the entries are Aman Amazon Neha Aman and we type 'ama' then the result should show all the above three enteries. Also it should be possible to search using phone numbers.
data-structures Design a telephone directory for large ppl (he gave example like design for India). fields will be , first name , last name , number . this should be searchable with first name , last name , number as welll. later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations.
data-structures Given a complete binary tree, Find a Max element
data-structures Write a program to return minimum number of swaps required to convert this binary tree into a BST.
data-structures Create the data structure for a component that will receive a series of numbers over the time and, when asked, returns the median of all received elements. (Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is 2, 7, 4, 9, 1, 5, 8, 3, 6 then the median is 5.) Model the data structure for a component that would have these two methods:
data-structures Implement LRU cache of size 10 which can store Key, Value pair. (get(key) & put(key,value) methods) - If we try to add 11th element, the least recently used element should get removed. - If key already present, overwrite it and mark it as most recently used.
data-structures For a given binary search tree, replace each node with sum of all node which are greater then of equal to current node.
data-structures give me the code for : Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such. Eg: O/p should be "I ma a namuh gnieb" I somewhat wrote the code, but i was asked what if there are extra spaces etc. (i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence) let me know the best and optimised way of writing this code. Also i suggest people to aviod using inbuilt functions as much as possible My Answer is as below in perl
data-structures Given an excel column number convert it to excel column alphabet and reverse. Example : If column number(starts from 0) = 26 : Column alpha = AA.
data-structures Print all paths of a binary tree from root to leaf. Later, extend the solution to work with graphs, careful attention to cycles which you should print as paths as well (without printing visited nodes twice).
data-structures You are given a large set of integers, which are not sorted. Figure out a method to retrieve the largest 1000 elements, in O(n) run time
data-structures Find your own method to balance an unbalanced binary tree.(you must not use existing methods like AVL, red black or b trees)
data-structures Write a function in C to create a new BST which is the mirror image of a given tree.
data-structures I was asked a question in an interview. On an office floor , there are e entities - Walls , Cubicles , Coffee Rooms. In what data structure we should store this design that when a new member joins the company , the cubicle number which is empty and next closest to any coffee room should be assigned to it. Basically , data structure DS.pop() should return that cubicle number in the most efficient way. A Person can walk through cubicles to reach a coffee room but not through walls.
data-structures Write a function to remove all redundant characters in a given string with minimum space and time complexity
data-structures Given a sorted array of integers, write a function that will return the number with the biggest number of repetitions. (Asked to refine the solution to be more efficient)
data-structures Suppose you are supplied with a file containing a list of words like ABC, BCD , CAB ( say each word in new line ). now you have to suggest algorithm for this problem - When a user type some character, we have to suggest him next character and basis of suggestion is that the character you are going to suggest should have maximum occurrence at that position among all these words. For example , Let's say words are ABC BCD CBA Now if user types 'A' we have to suggest him 'B' as next character because if you see at second position in all words 'B' is occurring most number of times ( 2 times ). similarly if he types 'AB' then we need to suggest him third character as 'C' as in third index all words have same occurrence but 'C' comes first.
data-structures Given two (dictionary) words as Strings, determine if they are isomorphic. Two words are called isomorphic if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all occurrences of it with another letter while the ordering of the letters remains unchanged. No two letters may map to the same letter, but a letter may map to itself. Example: given "foo", "app"; returns true we can map 'f' -> 'a' and 'o' -> 'p' given "bar", "foo"; returns false we can't map both 'a' and 'r' to 'o' given "turtle", "tletur"; returns true we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' -'r' given "ab", "ca"; returns true we can map 'a' -> 'c', 'b'
data-structures Suppose you have to maintain the stock values of various companies during various periods and return minimum stock value of a particular company over a given period of time.what data structure is best for this.
data-structures Complete the below function which takes an arraylist and displays the list in the expected output public class TreePrinter { public static void printTree(Iterable<Relation> rs) { // your code } } public static class Relation { String parent; String child; public Relation(String parent, String child) { ... } } } Example input: List<Relation> input = newArrayList(); input.add(new Relation(animal, mammal)); input.add(new Relation(animal, bird)); input.add(new Relation(lifeform, animal)); input.add(new Relation(cat, lion)); input.add(new Relation(mammal, cat)); input.add(new Relation(animal, fish)); TreePrinter.printTree(input); Expected output: line 1: lifeform line 2: animal line 3: mammal line 4: cat line 5: lion line 6: bird line 7: fish
data-structures Given an n x n matrix A(i,j) of integers, find maximum value A(c,d) - A(a,b) over all choices of indexes such that both c > a and d > b. Required complexity: O(n^2)
data-structures Given two trees, find if tree 2 is the mirror image of tree 1.
data-structures It was a pretty interesting question. Assume that you are given a fixed set of floating point numbers. Now given a new floating point number 'x', the goal is to efficiently find the number that is closest to 'x' from the fixed set. Question is: what data structure will you actually use for storing the fixed set of floating point numbers to achieve this? Edit: I missed to add. The interviewer further mentioned that I can not sort and that I can use any amount of time for creating the data structure (meaning this need not be efficient). Since, I am not allowed to 'sort', I assumed that I can not use BST as I will have to compare numbers while populating the tree. But I didn't clarify it with him; I should have in hindsight.
data-structures A link list contains following elements
data-structures You are given a sorted skewed binary tree. How can you create a binary search tree of minimum height from it?
data-structures A standard chess knight (it moves in its standard way i.e. L shaped OR 2.5 moves) is sitting at the position a1 on an N x N chess board. What is the minimum number of moves it will take to reach the diagonally opposite corner? P.S. - If it were a 8 x 8 chess board, the final destination for the knight would be h8
data-structures Considering a stream of integers coming in. Design a datastructre to store only n of them. Insert if if does not exist in the datastructre. And if it reaches n, remove the first one inserted into the datastructure. Datastructure should provide, addition, deletion and search all in O(1) time.
data-structures I have a list of several million words unsorted. How can you find the largest and the smallest words that can be typed by a single hand on a qwerty-style keyboard? Following the rules of finger placement, a word can either be typed fully on the left-hand side of the keyboard, the right-hand side, or both. Find the largest and smallest left-hand word(s), and the largest and smallest right-hand word(s). given: millions of words, unsorted given: set of left-hand chars - a,s,d,f,... given: set of right-hand chars - j,k,l...
data-structures In a Binary Tree, weight of each node is described by the value of the node multiplied by the level (i.e. for root node value is 1* value in root node), And the weight of tree is sum of all the node weights. Find the minimum tree weight out of all the binary trees possible from a given set of numbers. P.S: No input and no sample data provided
data-structures I need to store countries, its states and cities in a data structure. The following queries might be used to fetch details 1) find list of states for a country. 2) find list of cities for a state. 3) find the name of the country and state for a city. eg: 1) India -> Gujarat, UP, MP MP -> bhopal,indore Gujarat-> Surat,Ahmedabad, Baroda 2) USA -> Texas, California.. and so on. Which is the best data structure that can be used to store these details.
data-structures Implement Object Pool for database connections in the following interface
data-structures What is the difference between a tree and a map ?
data-structures How can we implement spell checker.
data-structures Implement T9 dictionary for mobile phone
data-structures Two files containing large number, one in each. You have only fopen(), int read(fp), fclose(), fwrite(). Add these two numbers and write in third file with the help of given functions only.
data-structures Given a server that has requests coming in. Design a data structure such that you can fetch the count of the number requests in the last second, minute and hour.
data-structures Check if the given binary tree is BST or not.
data-structures How to find in a binary tree, whether all leaves are at same level or not, and return a boolean value after identifying this.
data-structures Given a binary tree, a complete path is defined as a path from root to a leaf. The sum of all nodes on that path is defined as the sum of that path. Given a number K, you have to remove (prune the tree) nodes from the tree which lie on a path having sum less than K. Note: A node can be part of multiple paths. So we have to delete it only in case when all paths from it have sum less than K.
data-structures Given two sorted arrays, find the median of each array. The length of the arrays are m and n and we should not use extra buffer. We should find the median and time complexity should be less than 0(M+N);
data-structures Print the sum of all nodes of a binary tree, excluding leaf node values.
data-structures Write a class that will have following functions: long CheckOut() CheckIn(long) Range of values is 1 to LONG_MAX At any given point in time checkout should return the minimum available LONG number Checkin can return the value back No need to check for border conditions (e.g. check out when all values are exhausted) Implement: 1. long checkout() 2. void checkIn(long input)
data-structures Q: If you have all the companies that are traded, and live inputs are coming of which company is being traded and what is the volume, how do you maintain the data, so that you can carry out operation of giving the top 10 most traded companies by volume of shares most efficiently. A: I juggled between Hash Map and Max Heap. I said Max Heap, since I can take out top 10 companies in a jiffy with a Max Heap. But then he asked you will need to find a company everytime there is a trade, which will take quite some time in Heap. He pointed out that in real world scenario, number of trades happening, and hence searching of the company and updating it, will be many times more than finding top 10. Which bought me to HashMap. Updations can happen in Real time, while finding top 10 can be done in O(n) or O(nlog(n)) time. Even that wasn't optimal obviously. The interviewer was very nice and friendly type guy. He stressed that at every trade, at most, only 1 company will change in my top 10. This hit me and got me to the correct answer that we keep all actual data in HashMap, but also maintain a MinHeap of 10 most traded company.
data-structures Q: If I give you a new book, and ask you to create the index which is found at the end of the book, how will you do it. A: I said for constant addition time of words (and page numbers) in the data structure, we can use Hashmap or TRIE. But since output has to be in alphabetic order, we will use a Trie DS, where at the end of each word, we simple store a list of page numbers.
data-structures You are given the task of creating the address book application for a smart phone. There are some of the top level features you must implement. 1.There will be 1000+ phone book entries and user must get very quick response. 2.On default screen it shows the names of all people in alphabetical ascending order. 3.Using the search option, user can search and it will show only those names starting with those characters which are typed in the search box. You are supposed to compare two different data structures and list down the pros and cons of each and finally recommend the best suited data structure.
data-structures How will you store a million phone numbers in a space efficient way?
data-structures Give the algorithm and code to get the depth of the deepest odd level leaf node in a binary tree.
data-structures There are 2 sorted sets.Find the common elements of those sets e.g. A={1,2,3,4,5,6} B={5,6,7,8,9} o/p C={5,6} Complexity should ne 0(n+m) where n and m is the size of the first and second set respectively Which data structure should be used to store the output
data-structures Design a phonebook dictionary which on input any characters gives names and phone number of all the matching names(prefix) For instance Rihana 233222232 Ricky 134242444 Peter 224323423 Ron 988232323 If you give R as input it should list Rihana Ricky and Ron which their contact numbers If you give ri as input it should list Rihana, Ricky which their contact numbers
data-structures Given two arrays of ints that are sets, create a function to merge them to create a new set. A set must pass on these three conditions: - All values are positive - Sorted - Non-duplicates
data-structures You have a link list with the following structure: struct Node{ Node*next; Node*other; } next pointer points to next node, but "other" pointer points to any node in the list, it can be itself or null. you receive the header of a list with this structure. you have to copy it(allocate new memory) , you cannot modify the structure, you can not modify the list you are given.
data-structures Round 3 : Q 5 : You are given a binary search tree, and a value(data item), you need to tell the left most right cousin in as minimum time and as minimum space ?(need to minimize actual time complexity, he need minimum order of complexity as well as number of node access should be minimum)
data-structures How can you efficiently implement three stacks in a single array, such that no stack overflows until there is no space left in the entire array space.
data-structures Print a binary tree in vertical order using singly linked list...complexity should be O(n)
data-structures Given a seria of points (Xi, Yi), find the line containing the highest number of points from the list. Per my question he mentioned that I can assume that there is a given function that receives two points and returns the a and b of the line euqation (aX+b)
data-structures We have n number of sorted array for fixed length. Now we have to merge these and need to save finaly result array into given array. Note- we can't use extra space except the given array.
data-structures Given an array containing sequence of bits (0 or 1), you have to sort this array in the ascending order i.e. all 0' in first part of array followed by all 1's. The constraints is that you can swap only the adjacent elements in the array. Find the minimum number of swaps required to sort the given input array. Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3. Note: You just need to complete the function given below for this task. The function is given a binary string as input and returns the required answer.
data-structures There is a given linked list where each node can consist of any number of characters :- For example a-->bcd-->ef-->g-->f-->ed-->c-->ba. Now please write a function where the linked list will return true if it is a palindrome . Like in above example the linked list should return true
data-structures Implement a thread-safe Blocking queue in C/C++(POSIX) or Java
data-structures Generate a grey code sequence given the number of digits as input. eg: input=2 output= 00 01 11 10 use minimum space and time complexity
data-structures Write a C function to print all the elements less than the key element in binary search tree
data-structures How to stop recursion stack as soon as we find a result. e.g. in a Tree recurion where the Order of the algo is O(n) and suppose we find the result just after 4 calls, can we empty the recursion stack and stop the ececution right away...
data-structures User inputs a sequence of digits. Every digit is a keystroke, that is equivalent to some character out of a sequence of characters. Digit zero and five mean NULL. The table is given below 0 - NULL 1 - v, t, f, r, q 2 - f, t, k 3 - w, z, b, g 4 - r, s 5 - NULL 6 - f, i, r 7 - p 8 - l, o 9 - p Generate all possible character sequence for a given sequence of digits. Ex - If the user input 9801, your program should generate {plv, plt, plf, plr, plq, pov, pot, pof, por, poq} (not necessarily in this order). This problem is somewhat similar to the SMS problem. It basically boils down to generating a cartesian product of the character sets corresponding to keys.
data-structures Implement the plusplus operator when we are getting the input as integer array = { 9,9,9,9 }.output will be {1,0,0,0,0}
data-structures Given an array which contains the parent of the ith element in the n-ary tree.Parent[i] = -1 for root. Find the height of the tree. Gave O(n2) ,space O(1). Expected Complexity- Linear You can use extra space if you want. Example- {-1 0 1 6 6 0 0 2 7} 0 1 2 3 4 5 6 7 8 0 is the root here. 0 is the parent of 1 5 6 1 is parnt of 2 6 is parent of 3 4 2 is of 7 which is parent of 8.
data-structures Q1.- Written exam (Amazon, Bangalore) Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases. Sample Input: 1->2->3->4->5->6->7->8 and K = 3 Sample Output : 1->2->6->4->5->3->7->8 Sample Input: 1->2->3->4->5->6->7->8 and K = 10 Sample Output: print error "LIST IS OF LESSER SIZE".
data-structures Q3. Written Exam Amazon(Bangalore) Given a singly linked list which may or may not contain loop and loop may or may not start from the head node. Count the number of elements in the linked list.