-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpending-coding-questions.txt
313 lines (212 loc) · 12.7 KB
/
pending-coding-questions.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
-----------------------------------------------------------------------------------------
Systems Design:
-----------------------------------------------------------------------------------------
1: Design Distributed KV store
2: NEST like system
3: Design / Modify current APIs so that Alexa kind of skills can be built.
4: Design Restatability feature
5: Design publish subscribe
6: Design asqynchronous queue
7: Design google maps
8: Design netflix
9: Design HTTP proxy
10: Design http sniffer (datadog)
11: Design yourtube
12: Design fb live video system
13: URL shortner
14: Design event based system
15: MVC architecutre
-----------------------------------------------------------------------------------------
Coding:
-----------------------------------------------------------------------------------------
1: Given nearly sorted array sort it in n(log k)
2: Given sorted array, and target number, find that how many times number is repeated
-> is it int array
-> how many time client is going to call (can use hash table)
-> how big is the array ? can it fit in memory ?
3: Given Binary tree, print reverse inorder traversal
4: heaight of Binary tree (iterative and recursive)
5: page fault, RAID, seg fault
6: drone , nearest drone question
7: Design NEST like system
8: Desing cache , DB system
9: Given a String, sort using the most frequent chars in them , + alphabetical order
GAURAV --> AAGURV
Sub Problem :
maintain the order or chars after sorting based on frequency.
10: find intersection of sorted arrays. (Liner search and binary search)
11: """
Imagine you have a list of pairs:
Joyce 0
Terry 1
Paul 20
Molly 9
Liz 60
Brian 3
...
The first element is a person's name (string) and second element is a score (natural number). Implement a function `choose` that randomly chooses one of the names. Assume that you have a function in scope, `randomRange`, that takes input two integers and randomly yields an integer between them.
"""
"""
Now implement `weightedChoose`, a function with the same signature as `choose`, but names are proportionally more likely to be chosen based on their accompanying score. So, given the pairs above...
- Brian (3) is three times more likely to be chosen than Terry (1)
- Molly (9) is three times more likely to be chosen than Brian (3)
- Joyce (0) will never be chosen
"""
"""
Implement a new function, `weigtedChooseN`, that takes as input...
- An integer, "n"
- A list of pairs of length "l", where each score is 0 <= score <= s
The function must yield a list of "n" elements, where each element represents an invocation of `weightedChoose`. Feel free to change the signature and implementation of `weightedChoose`, while maintaining its general functionality.
"""
12: Find longest substring containing at most K characters.
http://www.geeksforgeeks.org/find-the-longest-substring-with-k-unique-characters-in-a-given-string/
13: Given 7 digit phone number, generate all possible strings.
0 = "" , 1 = "ABC" and so on
14: Solve sudoku
15: max path sum in binary tree - Mock interview
16: random pointer tree copy of that - Mock interview
17: Check whether matrix , which has all the digonal elements are equal
18: Design server to accept 7 digit number and display most frequent numbers
19: Lonely member in matrix :
Lonely Pixel
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))
20: Define iterator which only jumps to next number which is multiple of 5
21: Word graph : Arrive at target word from start word , using given dictionary in minimum number of passes. Each pass allows you to change only one alphabet at a time.
22: Foo Bar baz , and print FooBarBaz only when all are divisable. very nice problem
23: If u look at binary tree from right, print element u will see it
24: SSH is not working for bigger ls , for small ls command it works. : solution is MTU
25: given two strings whether they are Isomorphic strings or not . abc-pqr , egg-abb, abc-ppp
26: 0-A, 1-A.... 25-Z,
1234 -> (1,2,3,4), (1,23,4), (12,3,4) - total 3 possiblities.
Given number find how many possibilities are available
27: numbers are coming. Find avrage of numbers which u have seen so far.
28:
There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball's start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
Example 1
Input 1: a maze represented by a 2D array
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)
Output: 12
Explanation: One shortest way is : left -> down -> left -> down -> right -> down -> right.
The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.
29: Binary tree serialization. (No need to inorder / postorder etc)
30: Given codec of english works determine encoding scheme.
31: Longest non repeating substring , return length and actual string.
32: When you text "Hello" occasionally it gets typed as "Gello".
Helper Functions:
char[] getNearbyChar(char input) -> gives nearby chars
isWord(String word) -> True or False
Implement : nearbyWords(String word) -> Given word list of out all possible nearby words.
33: Given multiple deck of cards write algorithm / DS for retriving random card from all of those cards
33: Implement merge sort (where data does not fit on one computer)
34: Find number of cluster in a given Graph. Cluster is group of nodes where it has edges from each of node.
consider this as DG.
35: Huffman coding question
36: Find top K elements from the given stream of array
36: Given preorder and inorder Construct binary tree
37: Given 5 million files each one is sorted by timestamp, write tool which does search
./search <t1-t2> component name and priority
38 :
A phrase can be single word or multiple words.
Given a string S write a program that finds all of the words of the
phrase P in the string S. “Exact match” can be defined as all of the words
of P found in S in the same order consecutively. “Broad match” can be defined
as all of the words of P found in S in the same order but they don’t have to
be consecutive. “Best match” will be the “Exact match” if present or the best
“Broad Match”. The best "Broad match" will be the "Broad Match" with the
least number of non-phrase words. Return the startIdx, endIdx of the
best match in string S.
Example:
Take the following string S,
Lorem ipsum dolor sit amet, eu tristique dolor nullam id, amet augue risus,
et id, conubia eget taciti vel vel ante, nec nunc mauris vel. Ridiculus
tincidunt lorem sed conubia suspendisse, arcu lacus fringilla a metus,
magna nibh. Risus dolor et consectetuer et pede volutpat. Orci pede dolor
aenean volutpat arcu, semper arcu velit praesent turpis sed senectus,
ullamcorper curabitur doloribus. Interdum libero. A sed quis enim eu
molestias ut, interdum nec, elit suspendisse elementum pede dolor volutpat
elit nulla, bibendum adipiscing sed a.
If the phrase P is “pede volutpat”, “pede volutpat” would be exact match
and “pede dolor aenean volutpat” and “pede dolor volutpat”
would be broad matches. And the best broad match would be
“pede dolor volutpat” since that has the least number of non-phrase words.
39: Cohesity
Split string into palidrome fashion
abbaccd
a|b|b|a|c|c|d
a|bb|a|cc|d
abba|a|cc|d
40: Sort already N sroted arrays Cohesity
41: Shotest substring including all strings from given set. Order does not matter
MainString: ababdlshfrlsa
Sample: abd
Output: 3 (abd) from main string
41: BFS : code quality Cohesity
42: Hash table design Cohesity
43: Given a file and dir path find all the paths file is present - Paypal
[[/], [/foo/bar],[/foo/bar/baz]]
44: find duplicates in array using binary search kind of approach. total N-1 numbers from 1 to N-1 and array contain N numbers - Paypal
-----------------------------------
Google from Blind
-----------------------------------
Expression evaluator, but with multiplication, addition and subtraction
Select a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid). There was more follow up on this. This was not that hard.
3. A DP problem on balloons, which just boiled down to Matrix chain multiplication problem that we did in the course for DP homework.
4. Palindrom pairs. I got this exact problem at AirBnB also. This was also in the course.
5. KV Store, with high write volume. That big fat instructor from LinkedIn covered KV store in IK class. It was amazing detail and explanation. I was able to answer the tweak.
I also saw that these companies also paid attention to communication skills. Accurate english speaking/writing impressed them.
Expression evaluator, but with multiplication, addition and subtraction
Select a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid). There was more follow up on this. This was not that hard.
3. A DP problem on balloons, which just boiled down to Matrix chain multiplication problem that we did in the course for DP homework.
4. Palindrom pairs. I got this exact problem at AirBnB also. This was also in the course.
5. KV Store, with high write volume. That big fat instructor from LinkedIn covered KV store in IK class. It was amazing detail and explanation. I was able to answer the tweak.
I also saw that these companies also paid attention to communication skills. Accurate english speaking/writing impressed them.
------------------------------------
Recursion
------------------------------------
Recursion
It will pay very much to practice Recursion. It’s pervasive in interview problems and nearly every single topic we’ll take, will include problems that are solved using Recursion. Plus, only if you are decent at recursion, that you’ll be better at Trees, Graphs and DP.
Recursion basics: https://www.youtube.com/watch?v=Mv9NEXX1VHc
Call Stack:
1. Call Stack with Recursion: https://www.youtube.com/watch?v=ozmE8G6YKww.
2. Just the Call Stack by itself: https://www.youtube.com/watch?v=Q2sFmqvpBe0
3. This one goes into assembly language, and may feel arcane, but it's short and instructive still: https://www.youtube.com/watch?v=PrDsGldP1Q0
Counting principle, Permutations and Combinations: https://www.youtube.com/watch?v=s_LfN4ItCs4
Then watch Lectures 8, 9, 10 and 11 here:
https://www.youtube.com/watch?v=gl3emqCuueQ&list=PLFE6E58F856038C69&index=8
Then you should practice some problems:
Basic recursion problems: http://codingbat.com/java/Recursion-1
Interview-level recursion problems: http://codingbat.com/java/Recursion-2
If you are a book-person, then the only book that admits that recursion is hard, and helps you do recursive thinking, is written by Eric Roberts at Stanford. It’s freely available: https://drive.google.com/folderview?id=0Bx7fd6RqI1ddLWcyVTV0LU04RFU&usp=sharing
---------------------------------------------------
Quora:
---------------------------------------------------
4 Week Online Bootcamp: InterviewCamp.io
Coding Interview Questions
Grokking the System Design Interview
LeetCode
Coderust 2.0: Faster Coding Interview Preparation using Interactive Visualizations
Programming Interview Questions | CareerCup
GeeksforGeeks | A computer science portal for geeks
HiredInTech's Training Camp for Coding Interviews
http://highscalability.com/
Cracking the Coding Interview: 189 Programming Questions and Solutions: Gayle Laakmann McDowell
Programming - InterviewBit
Refdash - when you feel ready, interview with an senior engineer
Grokking the System Design Interview
Coderust 2.0: Faster Coding Interview Preparation using Interactive Visualizations
LeetCode
Programming Interview Questions | CareerCup
GeeksforGeeks | A computer science portal for geeks
http://highscalability.com/
Interview Kickstart: A structured, multi-month course for DS/Algos and Large Scale Systems Design prep:
Start reading this book: Data Structure and Algorithm by Narasimha Karumanchi
GeekyPrep - Hub for Geeks
4 Week Online Bootcamp - Self-Paced, Mentor Led - InterviewCamp.io