· 7 years ago · Sep 09, 2018, 04:20 PM
1Facebook Interview TODO:
2- GeeksForGeeks
3- Algorithms Book (recurrences and master theorem)
4- EPI book difficult questions.
5- This file
6- System design
7 - Gather statistics about Facebook: # of users, photos uploaded, videos, etc
8 - Familiarize yourself with all Facebook services and products
9- Behavioral Interview
10 - Hard problems, good designs
11 - How to improve team.
12 - Conflicts, etc
13- Review everything in resume.
14- C#/Data structures
15- C++/STL
16- Make sure to visit every question in EPI and geeksforgeeks to get a glimpse of the idea
17- Prepare smart and interesting questions to ask them about facebook.
18
19Plan:
203/17 Algorithms book review
213/18 Review C# and C++ data structures and algorithms. Watch Google training video.
223/19 Read Google's interview preparation material.
23Weekly 20 coding questions.
24Weekly 2 system design questions.
25Review Interviews.txt
26Review EPI book.
27Leetcode subscription.
28Other text files in this directory.
29Behavioral questions, best projects, datastructure classes, etc
30
31Interview preparation components:
32 1. Algorithms and data structures. 10PM
33 2. C/C++ with STL 2
34 3. OS
35 4. Python/Java
36 5. Linux OS 2
37 6. System Design
38 7. Networks and security
39 8. Misc: Regex, Make, bash commands, svn, SQL. 4
40 9. How to evolve product X.
41 10. Personal questions, why this job, career goals, etc.
42 11. This file
43 12. Top coder
44 13. Misc 2: testing, OOP
45
46
47Good code characteristics:
48- Correctness: Edge and corner cases, validate input
49- Readability: Good method/variable names
50- Maintainability: be modular
51- Performance
52
53Common design patterns: Observer, Monitor, Visitor, Singleton, Adapter, Decorator
54
551. Kadane's algorithm for the maximum subarray: DONE
562. Maximum submatrix: Revise https://www.youtube.com/watch?v=yCQN096CwWM
573. longest non-decreasing subsequence.
584. Compute the power set. Use a counter and then check for individual bits if they are set or not.
595. Implement a hash table: DONE
606. How to implement a hash function: Revise
617. Why do you want to work at Google?: Revise
628. What are hard problems that you faced?: Revise
639. Rotating an array: DONE
6410. Finding median, kth smalles/largest number in O(n) time: DONE
6511. String search algorithms
66 A. Rabin Karp (See my own implementation in cpp)
67 B. KMP
68 C. Boyer Moore
6912. Longest common subsequence: DONE
7013. In-order traversal with O(1) space. See EPI 9.5: DONE
7114. Longest non-decreasing subarray (differet from subsequence): DONE
7215. Sequence alignment in algorithms design book section 6.6
7316. Segmented least square in algorithms design book section 6.3
7417. Search for "most common greedy", "most common DP algorithms", etc.
7518. MRU, LRU cache: DONE
7619. Write functions that print all permutations of chars in a string. Do another algorithm for combinations: DONE
7720. Rubikee Cube algorithm
7821. External sort: DONE
7922. SQL interview Questions
8023. Java Interview Questions
8124. Python Interview Questions
8225. Algorithms Design Book.
8326. LFU cache: DONE
8427. Queue with unique elements: DONE
8528. Distributed systems interview questions.
8629. Skip lists: DONE
8730. Bit manipulation tricks: DONE
8831. Geometric algorithms: DONE
8932. Given System X of Google/Microsoft/etc, how would you evolve it.
9033. Regular expressions
9134. String operations interview questions.
9235. Update/Delete from BST, rotations Revise
9336. Red-Black Trees.
9437. Suffix trees: http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/ : Revise
9538. C++ Standard Library vs STL Revise
9639. Online hiring problem: Introduction to algorithms p139
9740. Backtracking solutions in Dynamic programming algorithms.
9841. Towers of Hanoi DONE
9942. Distributed Hash Table
10043. Min-Max Heap and its applications on wikipedia
10144. Solve maze using recursion. Get optimal path. DONE
10245. String matching homework questions.
10346. Clock synchronization in a distributed system
10447. Google system design questions. Read about the design of search engines, streaming services, cloud storage, email system, social network, online market, advertising system, file sharing, DFS, P2P, web browser, akamai, DNS, paypal, etc.
10548. Trie data structure.
10649. Multi-dimensional BSTs (such as Quad-trees, k-d trees).
10750. Write a program to make a deep copy of a graph.
10851. Super recursion
10952. Bloom filter
11053. Agile/Scrum
11154. Screws and bolts
11255. Combinations of size k out of n.
11356. Rotate mxn array.
114
115Definitions:
116Anagrams: the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once.
117Palindrome: A word that reads the same forwards or backwords like mom, dad, deed.
118Powerset: all possible subsets, # of sets in a powerset = 2^n
119Permutations: All possible permutations of size n = n!. Permutations of size r = n!/(n-r)!, where n is the size of the set, r is the size of the permutation. Set = "abc", r = 2 ==> {ab, ac, ba, ca, bc, cb}.
120Combinations: All possible combinations of all sizes [0, n] = powerset = 2^n. Combinations of size r = n!/[(n-r)!r!], where r is combination size. Set = "abc", r = 2 ==> {ab, bc, ac}.
121
122---------------------------
123Tips:
1241. Whenever you are asked about uniqueness, consider hash tables, or sets
1252. Whenever you are asked about maximum or minimum or "optimal", consider Dynamic Programming and Greedy Algorithms.
1263. Consider augmenting the data structure. Some problems will require that, and others will have performance benefits.
1274. When writing dynamic programming algorithms, remember to include the memorization part, not only the recursion. Recursion-only solution can still be exponential in time.
1285. Whenever you see something like k-smallest or k-largest, consider using a heap.
1296. Most important interview tips:
130 A. Think loud
131 B. Corner and base cases
132 C. Verify and test using many inputs before you show your work
133 - For strings and chars: test null, empty string, capital, small, numeric, etc.
134 - For numbers: test positive, negative, zero.
135 - For boundaries: check empty array, array start, array end, etc.
136 D. If stuck, try another approach.
137 E. Most Important: TAKE YOUR TIME. CORRECTNESS IS VITAL
1387. Algorithms tips:
139 A. Make sure you fully understand the problem (inputs, outputs, desired behavior or transformation).
140 B. WRITE down and draw some examples that you will use later for testing.
141 C. Try to come up with a brute-force or a simple solution. Make sure it is right
142 D. Think about how to optimize by thinking in **datastructures and algorithms**:
143 1. What data structures would make your task easier or more efficient
144 2. What techiques can result in an improved algorithm? Divide and conquer, greedy algorithm, dynamic programming, sorting, recursion, graph algorithms?
145 E. Make sure that your optimized solution works by trying it on multiple input. Modify as necessary
146 F. Identify base cases and corner cases.
147 G. Code it up.
148 H. Test it with inputs that would cover all program paths. When testing, follow the code line by line, not what you think the code is doing!
149 I. what is the asymptotic complexity of your algorithm?
150 J. Paste your code into a compiler and see if it works. Learn from your mistakes.
1518. Coding Tips:
152 A. Write clean and correct code, with very clear handwriting.
153 B. Use meaningful function and variable names.
154 C. Explain your code as you write it.
155 D. Be modular, try to decompose your code into functions.
156 E. Delay the implementation of your helper functions, but define the helper functions signatures. Implement the main algorithm first.
157 F. Use libraries when appropriate. For example, call sort() STL function instead of writing your own sort() function.
158 G. Use whiteboard space wisely, use multiple columns.
159 H. Testing:
160 - Test your code that is on the whiteboard, not your algorithm.
161 - Use multiple small test examples, all edge cases, and one big example.
1629. Other tips:
163 A. If asked how to evolve a certain product and you don't know much about that product or you feel stuck, tell the interviewer that you are not familiar with that product.
164 B. When asked to provide a solution of a certain complexity requirements such as O(n), remember that you can always make more than one (but still constant) pass over the data structure and still have O(n) complexity.
165
166---------------------------
167Problems to revise:
168EPI: 6.23, 7.12, 8.13, 8.14, 9.3, 11.8, 12.14, 13.1, 13.3, (13.12, 13.13), 13.15, 14.14 (k-d trees), 14.7, 14.8, 14.15, 15.3, 15.15
169
170---------------------------
171Sets, Permutations and Combinations:
1721. Write a program to print the powerset for a string of characters of any length (not limited to the size of a word like 32 or 64)
173Solution: Use a recursion, for each character, either take it and recursively print the next power set or don't take it and recursively print the next power set
174template<class T> void PowerSet(vector<T> pre, vector<T> v) {
175 if(v.size() == 0) {
176 for(int j = 0; j < pre.size(); j++)
177 cout << pre[j];
178 cout << "\n";
179 return;
180 }
181 PowerSet(pre, vector<T>(v.begin() + 1, v.end()));
182 vector<T> pre2(pre.begin(), pre.end());
183 pre2.push_back(v[0]);
184 PowerSet(pre2, vector<T>(v.begin() + 1, v.end()));
185}
1862. Write a function that prints all permutations of a vector.
187Solution: the idea is to use recursion as follows: Perm(v) = for all char c in v: select c as first char + Perm(all other chars).
188template<class T>
189vector<vector<T> > permutations(vector<T> v) {
190 vector<vector<T> > result;
191 if(v.size() == 0) {
192 result.push_back(vector<T>());
193 return result;
194 }
195
196 vector<vector<T> > partial = permutations(vector<T>(v.begin() + 1, v.end()));
197 for(int i = 0; i < v.size(); i++) {
198 for(int j = 0; j < partial.size(); ++j) {
199 vector<T> tmp(partial[j]);
200 tmp.insert(tmp.begin() + i, v[0]);
201 result.push_back(tmp);
202 }
203 }
204
205 return result;
206}
207
2083. Combinations (n, k)
209void combinations_helper(vector<T> &v, int i, int r, set<T> data, vector<set<T> > &result) {
210 if(data.size() == r) {
211 result.push_back(data);
212 return;
213 }
214
215 if(i >= v.size())
216 return;
217
218 combinations_helper(v, i+1, r, data, result);
219
220 data.insert(v[i]);
221 combinations_helper(v, i+1, r, data, result);
222}
223
224template <class T>
225void combinations(vector<T> &v, int r, vector<set<T> > &result) {
226 set<T> data;
227 combinations_helper(v, 0, r, data, result);
228}
2294. Print all combinations of balanced parantheses of size n: The number of those is nth catalan number (assuming n is even, 0 otherwise).
230
231void printParenthesis(int n)
232{
233 if(n > 0)
234 _printParenthesis(0, n, 0, 0);
235 return;
236}
237void _printParenthesis(int pos, int n, int open, int close)
238{
239 static char str[MAX_SIZE];
240 if(close == n)
241 {
242 printf("%s \n", str);
243 return;
244 }
245 else
246 {
247 if(open > close) {
248 str[pos] = '}';
249 _printParenthesis(pos+1, n, open, close+1);
250 }
251 if(open < n) {
252 str[pos] = '{';
253 _printParenthesis(pos+1, n, open+1, close);
254 }
255 }
256}
257
2585. How to find the permutation that has the next lexicographical order? For example given the permutation (2, 3, 1, 4) the next permutation is (2, 3, 4, 1).
259Solution: O(n)
260vector<int> next_permutation(vector<int> v) {
261 int k = v.size() - 2;
262 while(k >= 0 && v[k] > v[k+1]) { // find the greatest k such that v[k] < v[k+1]
263 --k;
264 }
265 if(k < 0)
266 return vector<int>(); //this was the greatest permutation, so next one is empty
267 int l;
268 for(int i = k+1; i < v.size(); ++i) { //find the greatest l such that v[l] > v[k]
269 if(v[i] > v[k])
270 l = i;
271 else
272 break;
273 }
274 swap(v[l], v[k]);
275 reverse(v.begin() + k + 1, v.end());
276 return v;
277}
278
2796. How to rotate an array by k elements, using only O(1) additional storage:
280Solution: O(n)
281void rotate(const vector<T> &v, int k) {
282 k = k % v.size();
283 reverse(v.begin(), v.end());
284 reverse(v.begin(), v.begin() + k);
285 reverse(v.begin() + k, v.end());
286}
287
2887. How to move a subarray inplace within an array (like MS excel). For example we have cells: A B C D E F G, move BCD to index between F and G.
289Solution:
2901. Reverse BCD: A D C B E F G
2912. Reverse EF: A D C B F E G
2923. Reverse BCDEF A E F B C D G
293
294---------------------------
295Bit manipulation:
296- Logical shift: shifts all bits including the MSB of signed numbers. You can achieve this effect by casting to (unsigned).
297- Arithmetic shift: shifts all bits except the MSB of signed numbers. The sign bit is shifted to next bit.
2981. Swap two numbers x & y without a temporary
299Solution 1: x = x ^ y, y = x ^ y, x = x ^ y. The swap with a temp is generally faster because these operations are dependent on each other and the compiler can't paralellize.
300Solution 2: x = y - x, y = y - x, x = x + y.
3012. Given a number x (not 0 nor MAX_INT), how to compute a number y with same number of 1s in its binary representation where |y-x| is minimum:
302Solution: find the first two consecutive bits that differ and swap them.
3033. How to check if an integer x is a power of 2?
304Solution: v && !(v & (v - 1))
3054. Write a function to determine whether a machine is big-endian or little endian:
306#define BIG_ENDIAN 0
307#define LITTLE_ENDIAN 1
308int TestByteOrder() {
309 short int word = 0x0001;
310 char *byte = (char *) &word;
311 return (byte[0] ? LITTLE_ENDIAN : BIG_ENDIAN);
312}
3135. Given two numbers a, b. Write a max and min functions without comparison operators:
314max:
315 c = a - b;
316 k = (c >> 31) & 0x1; //k=1 iff b>a
317 return a - k*c;
318min:
319 return y ^ ((x ^ y) & - (x < y));
320
3216. Write a function to add two numbers without using +.
322Solution: verified to work on signed numbers in 2's complement notation. Try examples on 4-bit numbers that can represent numbers from -8 to +7
323int add_no_arithm(int a, int b) {
324 if (b == 0) return a;
325 int sum = a ^ b; // add without carrying
326 int carry = (a & b) << 1; // carry, but don’t add
327 return add_no_arithm(sum, carry); // recurse
328}
3297. How to round up to the next power of 2?
330Solution: Assuming 32-bit integer n:
331--n;
332n |= n >> 1;
333n |= n >> 2;
334n |= n >> 4;
335n |= n >> 8;
336n |= n >> 16;
337++n;
3388. How to find the least significant bit that is set to 1 in a given integer x:
339Solution: x & (-x)
3409. How to count the number of 1s in an integer x?
341Solution 1:
342 for(r = 0; x != 0; ++r)
343 x &= (x - 1);
344Solution 2: Create a lookup table of 256 elements, each element represents the number of 1s in the index. table = {0, 1, 1, 2, 1, 2, 2, 3, ...}. Lookup one byte at a time.
345Solution 3: There is also a faster divide and conquer method O(lgn)
3468. How to find out if two integers have opposite signs?
347Solution: (x ^ y) < 0
3489. How to compute absolute value of an integer without conditionals?
349int const mask = v >> sizeof(int) * 8 - 1; //This statement extends the sign bit to all bits: if sign = 0 then mask = 0 else mask = 0xffff
350r = (v + mask) ^ mask;
35110. How to swap ith and jth bit in an integer?
352int swap(int num, int i, int j)
353{
354 int xor = ((num>>i) ^ (num>>j)) & 1; //xor=1 iff the two bits are different. Otherwise xor = 0.
355 return num ^ (xor<<i) ^ (xor<<j); //if xor==1 then flip ith and jth bits, otherwise do nothing.
356}
35711. How to reverse bits in an integer:
358Solution: O(lgn)
359unsigned int v; // 32-bit word to reverse bit order
360// swap odd and even bits
361v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
362// swap consecutive pairs
363v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
364// swap nibbles ...
365v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
366// swap bytes
367v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
368// swap 2-byte long pairs
369v = ( v >> 16 ) | ( v << 16);
370
37112. How to compute x % y, where y is a power of 2?
372result = x & (y-1)
37313. How to clear the least significant bit that is 1? This is useful when counting # of 1s.
374Solution:
375if(x)
376 x &= (x-1);
37714. How to multiply n by 7:
378Solution: (n << 3) - n. Or n + (n >> 1) + (n >> 2)
37915. How to rotate bits left or right
380Solution:
381int rotate_left(int n, int shift) {
382 int bits = sizeof(int) * 8;
383 shift %= bits;
384 return (n << shift) | (n >> (bits - shift));
385}
386int rotate_right(int n, int shift) {
387 int bits = sizeof(int) * 8;
388 shift %= bits;
389 return (n >> shift) | (n << (bits - shift));
390}
39116. An array A contains n+2 elements and all elements are in the range(1,n). All elements occur exactly once except two elements (x, y) which appear twice in the array. find x and y. Example A = 1 2 3 4 4 5 5
392Solution O(n):
393 1. XOR all elements in A with all elements in range(1,n). The result z = x ^ y. (In the example z= = 001).
394 2. Find a bit k in z where kth bit = 1. This bit means that x and y differ in the kth element. (In the example, k = 0th bit)
395 3. XOR all elements in A that have kth bit = 1. The result u = XOR of all elements in A that have kth bit = 1, except those that are repeated. (In the example z = 1 ^ 3 ^ 5 ^ 5 = 1 ^ 3).
396 4. XOR u with all elements in the range(1,n) that have kth bit = 1. The result v = x. (In the example, v = u ^ (1 ^ 3 ^ 5) = (1 ^ 3) ^ (1 ^ 3 ^ 5) = 5.
397 5. To find y, y = z ^ x. (In the example y = 001 ^ 101 = 100 = 4).
39817. An array of integers has all elements appearing 3 times except for one element, which appears only once. Find that element.
399Solution: http://www.programcreek.com/2014/03/leetcode-single-number-ii-java/
40018. Find out if an integer is a multiple of 3: let x = number of odd bits set to 1, y = number of even bits set to 1. The number is a multiple of 3 iff x-y is also a multiple of 3 (recurse of same function).
40119. Given a number n, find the number of set bits in all numbers from 1 to n: http://www.geeksforgeeks.org/count-total-set-bits-in-all-numbers-from-1-to-n/
402Solution1 O(nLgn) - naiive: loop through all numbers i from 1 to n, then return sum(numOfSetBits(i)).
403Solution2 O(Lgn): recursively do the following:
404func CountBits(n)
405 m = LeftMostSetBitPos(n)
406 //For example if n==11 (m=1), then for the 2 bits (0,1): all_bits = (m+1) 2 bits x (1<<(m+1)) 4 numbers = 8 bits, half of which will be 1s = 4.
407 if n is in the form 2^b-1 (i.e. all consecutive 1s), then return (m+1)*(1<<m).
408 else: n = n - (1<<m); //set MSB off, to prepare for recursion
409 return m*(1<<(m-1)) // number of set bits in all numbers of bit-length m-1.
410 + (n+1) // when the number is not 2^b-1 (i.e. has some ones and zeros) then this is the number of numbers between [1..n] with MSB = 1.
411 + CountBits(n) //recursively run for one less bit.
41220. Given an array of N integers (N is large), compute the number of set bits in all numbers a[i].
413- Create a look up table for the number of bits for numbers of size one byte [0..255]
414sum = 0;
415for each number k in array
416 for each byte b in k: sum += lookupTable[b]
417
418---------------------------
419Back Tracking: Just remember how backtracking algorithms work, such as the maze problem.
420
4211. Knight tour
4222. Maze
4233. N queen problem
4244. Subset sum.
4255. m-coloring problem.
4266. Finding hamiltonian cycle.
4277. Sudoku: Given a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.
428
429---------------------------
430Linked Lists, Queues and Stacks
431
4321. How to find out if a linked list has a cycle?
433Solution: Use a fast and a slow pointer. The list has a cycle iff they meet before finding the tail of the array.
4342. If a linked list does have a cycle, how to find the length of the cycle?
435Starting from the solution of the previous question, because the two pointers p_fast and p_slow point to the same node within the cycle, freeze one pointer and advance the other until they meet again.
4363. How to find the length of a linked list that has a cycle?
437Having computed the cycle length = C as in (2). Place both pointers at the head, advance p_fast by C nodes, then start advancing both pointers by one (same speed). The start of the cycle is where they meet.
438Next, place p_slow at head and keep p_fast at the beginning of the cycle. Move p_slow k times until it meets p_fast at the beginning of the cycle. Length of linked list = k + C -1.
4394. How to reverse a linked list:
440Solution O(n): loop through each node and make it point to the prev node, return the last node.
4415. How to print a linked list in reverse?
442void print_reverse(Node *n) {
443 if(n == NULL) return;
444 print_reverse(n->next);
445 cout << n->data << " ";
446}
4476. How to check if a linked list is a palindrome?
448Solution 1: Split the list in two halfs, reverse one half and compare the two halfs.
449Solution 2: Use a stack.
4507. Design a stack with min() function. All operations are O(1)
451Solution 1: always push a pair <element, cur_min>
452Solution 2: (More space-efficient). Use an auxiliary stack that stores only the minimums. Push and pop only when necessary.
4538. Design a space-efficient doubly linked list
454Solution: Let the pointer of each node = next_addr ^ prev_addr
455For example: A <--> B <--> C <--> D
456struct list {
457 T data;
458 struct list *ptr;
459}
460A->ptr = B ^ 0 = B
461B->ptr = A ^ C
462
463Traversal: To traverse left to right, you need a node and its left node, to traverse right-to-left you need a node and its right:
464next(n, left_of_n) = n->ptr ^ left_of_n. For example: next(B, A) = B->ptr ^ A = A ^ C ^ A = C
4659. Implement a stack using queues: You can use two queues to implement a stack, to push an element, push to the empty queue (q2), then push all elements from q1 to q2.
46610. How to select a random node in a linked list?
467Solution 1: Find length of the list, generate a number i from 0..n-1, traverse list again to node #i and return the node.
468Solution 2 (one pass): We use reservoir sampling (see Misc problems below for a better description) as for selecting a random element from a stream:
469- set result as node #0
470- init n = 2
471- For each next node, generate a number j from 0..n-1. if j==0, replace set result = cur_node.
47211. Implement quick sort for doubly linked lists: (Tip: what makes things easier is to swap values rather than pointers): http://www.geeksforgeeks.org/quicksort-for-linked-list/
473- Note: implementing quick sort for singly linked lists is more difficult, and we need to change pointers rather than swapping values: http://www.geeksforgeeks.org/quicksort-on-singly-linked-list/
47412. Implement merge sort for linked lists: http://www.geeksforgeeks.org/merge-sort-for-doubly-linked-list/
47513. Given a string in infix notiation (e.g. a - b + c), convert that string into postfix notation: http://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/
476- Scan the infix expression from left to right.
477- If the scanned character is an operand, output it.
478- Else,
479 - 3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it.
480 - 3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.
481- If the scanned character is an ‘(‘, push it to the stack.
482- If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
483- Repeat steps 2-6 until infix expression is scanned.
484- Pop and output from the stack until it is not empty.
48514. Evaluate an expression in postfix notation:
4861) Create a stack to store operands (or values).
4872) Scan the given expression and do following for every scanned element.
488 .a) If the element is a number, push it into the stack
489 .b) If the element is a operator, pop operands for the operator from stack. Evaluate the operator and push the result back to the stack
4903) When the expression is ended, the number in the stack is the final answer
49115. Given an array A[], for each element, print the next greater element: http://www.geeksforgeeks.org/?p=8405
4921) Push the first element to stack.
4932) Pick rest of the elements one by one and follow following steps in loop.
494 .a) Mark the current element as next.
495 .b) If stack is not empty, then pop an element from stack and compare it with next.
496 .c) If next is greater than the popped element, then next is the next greater element for the popped element.
497 .d) Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
498 .e) If next is smaller than the popped element, then push the popped element back.
499 .f) push next into the stack.
5003) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.
50115. Reverse a stack using recursion: http://www.geeksforgeeks.org/?p=6921
502- Notice that using a single recursive function to pop, reverse() and push() will result in the same ordering. To reverse, you will need an extra recursive function
503void insertAtBottom(struct sNode** top_ref, int item)
504{
505 if (isEmpty(*top_ref))
506 push(top_ref, item);
507 else
508 {
509 /* Hold all items in Function Call Stack until we reach end of the stack. When the stack becomes empty, the isEmpty(*top_ref)becomes true, the above if part is executed and the item is inserted at the bottom */
510 int temp = pop(top_ref);
511 insertAtBottom(top_ref, item);
512 /* Once the item is inserted at the bottom, push all the items held in Function Call Stack */
513 push(top_ref, temp);
514 }
515}
516void reverse(struct sNode** top_ref)
517{
518 if (!isEmpty(*top_ref))
519 {
520 /* Hold all items in Function Call Stack until we reach end of the stack */
521 int temp = pop(top_ref);
522 reverse(top_ref);
523 /* Insert all the items (held in Function Call Stack) one by one from the bottom to top. Every item is inserted at the bottom */
524 insertAtBottom(top_ref, temp);
525 }
526}
52716. Stock Span problem (similar to max rectangular area under histogram): http://www.geeksforgeeks.org/the-stock-span-problem/
52817. Design a stack with findMiddle() and deleteMiddle() operations:
529Idea is to implement a stack using a doubly linked list and keep a pointer to the middle element.
53018. How to clone a linked list with a random pointer?
531Solution 1:
532- Copy the linked list into a new list and ignore the random pointer. Each time you copy a node, add a mapping in a hash table old_node --> new node
533- Iterate over both linked lists and for each random pointer in the new list, set it to hashtable[old_list_cur_node->random]
534Solution 2: See figure in EPI page 230.
53519. Design a queue with max operation such that enqueue, dequeue and max have an amortized time complexity of O(1). EPI 8.13
536Solution 1: Indirect: Use two stacks that support the max operation to implement the queue.
537Solution 2:
538We maintain an auxiliary dequeue D that contains the list of elements that can be max at some point.
539- An element e can never be max if there is another element f that appears after e and is larger than e, since e will be dequeued before f.
540- Notice that the max will always be at the head of dequeue D.
541- Dequeue operation: If the element at the head of the queue Q is equal to the element at the head of queue D, then we dequeue both, otherwise D remains unchanged.
542- Enqueue operation: When an element K is enqueued, we remove elements from the tail of D until the element at the tail is >= K, then we insert K at the tail.
54320. Given a stream of numbers and a window size w, how to maintain max element in a sliding window of the stream.
544Solution 1 O(nw): brute-force every window.
545Solution 2 O(nlogw): use a BST to maintain max.
546Solution 3 O(n): use a queue with max just like in the previous question.
54721. Find next greater element: Given an array arr, return an array (result) such that result[i] = the next greater element of arr[i], i.e the first element arr[j] where j > i and arr[j] > arr [i]
548Solution: create a stack then traverse the array right to left and for each element arr[i], keep popping elements in stack until you get an element greater than arr[i], and add arr[i] to the top of the stack.
549Note: to do this for a circular array, just loop twice on the array, the first iteration may produce wrong results but the second iteration will overwrite them.
550---------------------------
551Numbers:
5521. How to approximate PI?
553Solution: PI = 4/1 - 4/3 + 4/5 - 4/7 ...
5542. How to factor a natural number x to its prime components?
555Solution:
556 - Get a list of prime numbers from 1 to sqrt(x) + 1
557 - for each number p in the primes list: while(x % p == 0): add p to the factors, x = x / p.
558Note: many faster algorithms exist such as wheel factorization and Euler's method.
559
560---------------------------
561Heap: A complete binary tree that satisfies the heap property
562
563Tip: When asked about finding k-largest elements, maintain a min-heap of first k elements, then for each new element e, compare it with r, the root of the heap (minimum of largest k), if e > r then remove r and insert e, otherwise just ignore e.
564
565Heap applications:
566Note: we can use priority_queue<T> in STL as a heap.
5671. Sort n sorted large files (or sequences) into a single file.
5682. Stack can be implemented using max_heap, queue using min heap.
5693. Sort k-increasing array.
5704. find k-smallest/largest elements in a large file. This can be also solved using a selection algorithm.
5715. Find kth largest element in a streaming input. (Use k-min heap).
5726. Sorting an approximately sorted array.
5737. Online (stream) median can be implemented using two heaps: max heap that stores the smaller half, and a min heap that stores the larger half.
574Note: Another solution is to use a self-balancing BST. The median will always be in the root (more or less).
5758. Tournament trees: http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
576---------------------------
577Searching:
578
5791. Find the first element in array A that is larger than k: k might not be in A.
580Solution: do a binary search as follows: initialize res = -1. divide array in 2 parts, if A[mid] > k: res = mid and continue searching. Return last value in res. Worst case is O(lgn).
5812. (11.4) In an absolutely sorted array (eg: -50, 100, 150, -200). Find a pair of elements that sum up to x:
582Solution 1: Consider 3 separate cases, write a separate function for each case.
583 A. both are negative (have one pointer at each end of the array).
584 B. both are positive (have one pointer at each end of the array).
585 C. One is negative and the other is positive: (have both pointers at the end of the array), if the number is too large, search for the next |largest| negative, if it is too small, look for the next largest positive.
586Solution 2: use a hash table, store all elements in A in the hash table. Then loop over the array: for each element k, lookup the hash table for x-k.
5873. (11.5) search for smallest element in cyclicly sorted array.
588Idea: k is smallest if elements at both sides are larger. Perform bsearch on the right-half array if a[k] < a[end], otherwise perform bsearch on left-half. (recursive or iterative bsearch).
5894. Searching an array of unknown length: search for k in elements 0, 1, 2, 4,8,16,...
5905. Search for kth largest element in array of known length: Use kth-order statistics and partition(). Make sure you use randomized version to achieve O(n) expected complexity.
5916. Search for kth largest element in array of unknown length: keep track of largest k elements in 2k - 1 array O(n). Or use a heap O(nlogk).
5927. Find missing element in array containing permutation [1 .. n]. n(n+1)/2 - sum(A) = missing element. Same logic for duplicate element.
593Solution 2: to find missing element, XOR all numbers [1..n] and XOR the result with all elements of A. The final result = missing element.
594O(lgn) solution: Use binary search if the array is sorted.
5958. Given a 2D array in which all rows and column are sorted in non-decreasing order, how would you find an element x in the array?
596Solution: start with row = 0, col = cols - 1, then loop: if A[row][col] == x then return A[row][col] else if A[row][col] > x then --col else ++row
5979. Given an array A of N elements. Find all array pairs that sum to Z. Generalize to find k elements that sum to Z.
598Solution:
599A. For k = 2.
600 1. Create a hash table with key=array element, value = # times element appears in A.
601 2. For each element e in A:
602 Compute e2 = Z - e
603 Look in the hash table and find out if e2 is there
604 if(e2 found)
605 if e != e2 or (e == e2 and count(e2) > 1) //Assume Z = 10, e = 5 then e2 = 10-5=5. We don't want to pair e with itself so we require that another element e2 = 5 to be in the array.
606 add element to list of pairs.
607 end if
608 end if
609B. For k >= 2:
610 if k is odd: O(n^((k+1)/2))
611 create a hash map of (k-1)/2 tuple sums.
612 For every (k+1)/2 tuple t of A
613 s = sum of tuple
614 D = Z - C
615 if(D is in hash table)
616 output elements of D union tuple t.
617 end if
618
619 if k is even: O(n^(k/2))
620 create a hash map of k/2 tuple sums.
621 For every k/2 tuple t of A
622 s = sum of tuple
623 D = Z - C
624 if(D is in hash table)
625 output elements of D union tuple t.
626 end if
62710. Given an unsorted array A, find the length of the longest consecutive subsequence. For example: [2,5,1,3,6] would return 3 because the result is (1, 2, 3)
628Solution: O(N).
629 Build a hashmap of all the array elements <element, bool(visited=false)>.
630 longest = 1, count = 1
631 For each element e in A:
632 if e is visited then continue
633 i = e
634 while(true)
635 if element --i is in hashmap then count++ else break; (mark hashmap[i] = true)
636 i = e
637 while(true)
638 if element ++i is in hashmap then count++ else break; (mark hashmap[i] = true)
639 longest = max(longest, count);
640 count = 1;
64111. Find the minimum and the maximum of an array using no more than 3n/2-2 comparisons.
642Solution: Compare each adjacent pair in the array (for example compare (A[0], A[1]), (A[2], A[3])). Details is in question 11.12 in EPI.
64312. Given an array A of n elements in the range [0, n-1]. Exactly one element t appears twice in the array, which means that exactly one element in [0, n-1] is missing. Find the duplicate and missing elements.
644Solution: O(n)
645 A. XOR all elements in A with all elements in the range [0, n-1]. The result is m XOR t.
646 B. Because m and t are not equal, they must differ in some bit.
647 C. XOR all elements in A with the different bit is set to 1. The result of this operation is either m or t (we don't know exactly).
648 D. To find out, we simply scan through the array again. If the element is found then it must be the duplicate element t, otherwise it is the missing element m.
64913. Given a string s and a pattern p. How can we improve the naiive search algorithm if we know that all characters in p are different:
650Solution: Suppose that we compare s with p and s matches p in the first k characters, then we can safely shift p with k characters instead of naiively shifting it by 1.
65114. Given a book of words. How would you efficiently find the most frequent k words:
652Solution 1 O(nlogk) time, O(n) space: Use a hashtable to insert all word and their counts, and simultanously keep track of the k most common words in a min-heap
65315. Given two strings s1 and s2, find if s2 is a shifted version of s1.
654Solution: str3 = str1 + str1.
655if(str2 is substring of str1) then return true, otherwise return false.
65616. In an array of all positive intergers, find the smallest subarray with sum >= s
657Solution: A sliding window starting from the first two elements then: if(sum) >= 7 smallest_subarray = min(smallest_subarray, i2 - i1 + 1); i1++. Else: i2++.
65817. Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right, write a function that computes maximum in this sliding window as it slides:
659O(n) solution: keep the max at the head of a double-ended queue: http://www.programcreek.com/2014/05/leetcode-sliding-window-maximum-java/
66018. Given a string s, find the length of the longest palindrome substring.
661Solution 1 O(n^2):
662For each index i in s
663 start from i, and then consider left and right characters, if they match then length+=2 else break. Keep track of longest. Pay attention to odd and even string lengths
664Solution 2 O(n): Manacher's algorithm: http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4/
66519. Given an array of positive integers, find the maximum sum subsequence such that no two elements are adjacent: http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/
666Solution O(n): maintain two sums: sum_inc and sum_exc, for each element sum_inc = sum_exc + cur, sum_exc = max(sum_inc, sum_exc). return max(sum_exc, sum_inc)
66720. Given an n by m matrix, transpose the array in-place (i.e. the matrix should become m by n matrix with first column becoming first row, etc): http://www.geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/
668Solution O(m x n): Look at an example like the following
669a b c a d g j
670d e f ==> b e h k
671g h i c f i l
672j k l
673
674And notice that by transforming 2D indeces into a 1D index by the equation: ol = or x C + oc, where ol: old location, C:# of columns, oc:old column
675Transpose is cycles of permutations:
6761->4->5->9->3->1 – Total 5 elements form the cycle
6772->8->10->7->6->2 – Another 5 elements form the cycle
6780 – Self cycle
67911 – Self cycle.
680
681ol = or x C + oc
682nl = ol x R - or x (N-1)
683
684For each element, that is not rotated yet (you can keep that in a bit map):
685 compute cycle indices
686 for each cycle index
687 do exchanges to complete cycle rotation.
68821. For an n by n matrix where every row and every column is sorted, print all elements in sorted order: http://www.geeksforgeeks.org/print-elements-sorted-order-row-column-wise-sorted-matrix/
689Solution O(N^2logn):
690These are n sorted arrays, each of size n. Use a min heap of size n to merge them.
69122. Given an array of n+1 integers where integers are in the range [1,n]. An element can appear 0 to n+1 times. Find the duplicate element.
692Solution 1: Mark seen index by flipping the sign of the integer to '-'.
693for(int i = 0; i < nums.Length; i++)
694 {
695 if(nums[Math.Abs(nums[i])] < 0)
696 return Math.Abs(nums[i]);
697 nums[Math.Abs(nums[i])] *= -1;
698 }
699Solution 2: cycle detection.
70023. For any question that is like: given an array where every element appears X number of times, but one element A appears only once, find that element:
701Solution: We simply count how many times each of the 32 bits is set. The bits that belong to the element that appears only once (A) will be set (nX + 1) times, but the bits that don't belong to A will be set nX times.
702public int singleNumber(int[] nums) {
703 int ans = 0;
704 for(int i = 0; i < 32; i++) {
705 int sum = 0;
706 for(int j = 0; j < nums.length; j++) {
707 if(((nums[j] >> i) & 1) == 1) {
708 sum++;
709 sum %= 3; //In this question X == 3, you can generalize this solution to whatever X is.
710 }
711 }
712 if(sum != 0) {
713 ans |= sum << i;
714 }
715 }
716 return ans;
717}
718---------------------------
719Strings and Pattern Matching:
720
7211. KMP algorithm: The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of next window. We take advantage of this information to avoid matching the characters that we know will anyway match.
722- lps(longest proper prefix that is also a suffix) array is constructed from pattern p such that lps[i] = longest *proper* prefix of p[0..i] that is also a suffix of p. proper means that whole string isn't considered (aa isn't pp of aa)
723
724To match string s[0..n-1] and pattern p[0..m-1]:
725Build lps for p.
726while i < n
727 if s[i] == p[j]:
728 i++, j++
729 if j==m-1 print "Found match", j = lps[j-1]
730 else if i < n && s[i] != p[j]
731 if j > 0 j = lps[j-1] else i++;
732
733Function buildlps(p)
734 lps[0] = 0;
735 i = 1; len = 0;
736 while(i < m)
737 if p[i] == len
738 len++
739 lps[i] = len
740 i++
741 else
742 if len != 0 len = lps[len-1] else lps[i]=0, i++
743
7442. Given a string s and a pattern p, find all occurrences of all anagrams of p within s in O(n) time.
745Solution: Because all p1..pn are anagrams of p, this means that the count of each character in the alphabet is equal in all pi. So count(p1, 'a') = count(pi, 'a') for all i.
746
747- Build a count array of alphabet size and store countPattern[c] for each char c in p.
748- Build a second count array countString and for first m chars in s, store countString[c].
749- Search string s in a sliding window fashion, with a window size of m. Each time window slides, you decrement the count for the char that became outside the window, and increment the count for char that is inside the window.
750 - Then you compare countPattern with countString, if they are equal then you found an anagram. This comparison is O(1) because alphabet size is constant.
751---------------------------
752Suffix trees and suffix arrays:
753
7541. Suffix trees:If you have a text of length n and a pattern of length m, then when pre-processing the text using suffix trees you can search for any pattern in O(m).
755- A Suffix Tree for a given text is a compressed trie for all suffixes of the given text.
756- Compressed Trie is obtained from standard trie by joining chains of single nodes.
757Building a suffix tree: http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/
758 1. Generate all suffixes of given text.
759 2. Consider all suffixes as individual words and build a compressed trie.
760Applications of suffix trees:
761 1. Longest repeated substring.
762 2. Longest common substring.
763 3. Longest Palindrome in a string.
764 4. Pattern matching.
765
766Important: Review this which explains how to build and search in suffix trees: http://www.geeksforgeeks.org/pattern-searching-using-trie-suffixes/
767
7682. Suffix Arrays: Suffix arrays are a simpler representation of suffix trees. Everything that can be done with one can also be done with the other.
769Advantages over suffix trees: Space-efficient, simpler, cache-locality, linear time construction.
770Example: "banana" suffixes are {banana, anana, nana, ana, na, a}. Sorted suffixes are: {a, ana, anana, banana, na, nana}. --> Suffix array = [5, 3, 1, 0, 4, 2].
771
772Building suffix arrays:
773 1. Naive method O(n*nlogn):
774 A. Generate all suffixes.
775 B. Sort them
776 2. Radix Sort O(n*n)
777
778Searching using suffix arrays: can be done by simple binary search:
779void search(char *pat, char *txt, int *suffArr, int n) {
780 int m = strlen(pat); // get length of pattern, needed for strncmp()
781 int l = 0, r = n-1; // Initilize left and right indexes
782 while (l <= r) {
783 int mid = l + (r - l)/2;
784 int res = strncmp(pat, txt+suffArr[mid], m);
785 if (res == 0) {
786 cout << "Pattern found at index " << suffArr[mid];
787 return;
788 }
789 if (res < 0) r = mid - 1;
790 else l = mid + 1;
791 }
792 cout << "Pattern not found";
793}
794
7951. Word Boggle: Given a board of MxN characters and a dictionary. Find all words that can be formed by adjacent characters.
796Solution 1: For each character, do a DFS from that character and lookup the word in the dictionary.
797Solution 2 (More optimized): http://www.geeksforgeeks.org/boggle-set-2-using-trie/
798- Create an empty trie and insert all dictionary words into the trie.
799- For each character in the boggle that is a child of the trie root: recurisvely search for the word in the trie that matches adjacent chars of the current cell.
8002. Longest prefix matching: Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary.
801Solution: We build a Trie of all dictionary words. Once the Trie is built, traverse through it using characters of input string. If prefix matches a dictionary word, store current length and look for a longer match. Finally, return the longest match.
8023. Print unique rows in a given boolean matrix
803Solution: Since the matrix is boolean, a variant of Trie data structure can be used where each node will be having two children one for 0 and other for 1. Insert each row in the Trie. If the row is already there, don’t print the row. If row is not there in Trie, insert it in Trie and print it.
8044. Implement Reverse DNS Look Up Cache.
805One solution is to use hashing, but trie-based solution is better as it offers O(1) worst case lookup, it can also provide prefix search ability.
806Alphabet size is 11 (10 numbers and the dot). The idea is to store IP addresses in Trie nodes and in the last node we store the corresponding domain name.
807A similar solution can be provided for forward DNS cache. Alphabet size would be (26 letters + 1 dot + 10 numbers = 37).
808
809---------------------------
810Hashing:
811
812- A good hash function is function that:
813 1. Distributes elements over the array as evenly as possible.
814 2. Avoids collisions
815 3. Fast
816 4. Rolling: if a small portion of the object is changed (eg. one character of a string), then it can be computed in O(1) time.
817
818Handling collisions in hash tables:
8191. Chaining: Each hashtable cell can become a linked list of values. A chaining hash table has an average time complexity of O(1 + n/m)
8202. Open addressing: No linked lists, the elements are stored in the hashtable itself. Methods:
821 A. Linear probing: if hash(e) is occupied then try hash(e) + 1, etc until you find an empty slot in the table. This results in clustering and poor performance.
822 B. Quad probing: if hash(e) is occupied then try hash(e) + 1*1, hash(e) + 2*2, etc.
823 3. Double hashing: Uses two hash functions. if hash(e) is occupied then try hash2(e).
8243. Like chaining, open addressing insert and lookup operations have O(1 + n/m) time complexity.
825
826**Study the design of hash functions**
827hash(unsigned char *str)
828{
829 unsigned long hash = 5381;
830 int c;
831 while (c = *str++)
832 hash = hash * 33 + c;
833 return hash;
834}
835
8361. Find word with nearest repetition (12.3).
8372. Finding all anagrams in a large dictionary of words.
838Solution 1: create a hash function that computes the hash based on all characters of the string regardless of the character position. An elegant solution is to sort characters in words, such that myhash(word) = hash(sort(word)). All anagrams will hash to the same hash. You can create a map<int, <vector<string> > to emulate that.
839Solution 2: Create an empty trie and then for each word sort the word by characters and insert the sorted word into the trie with a pointer to the original word.
840Then, for each leaf node in the trie, print all words that are pointed to by that leaf node. All words in a particular leaf are anagrams.
8413. Given a set of points(xi, yi), find the line that passes through most of the points.
842Solution: See solution 12.10. It addresses a lot of issues that need attention in this question.
8434. Given a string s, find out if it can be permuted to form a palindrome.
844Solution: If s.length() is even, then all characters in s must appear even number of times, otherwise all characters (except 1) must appear even number of times. These two cases can be covered by checking that at most one character appears an odd number of times.
8455. Given a very large sequence of n words (not distinct). Design an algorithm to find (at most) k words that occur at least n/k times.
846Solution: create a hash table, keep inserting <word, count> until you have k elements in the hash table. For the next word w, if is in hash table, increase its count, if not, decrement the counts of all other words and drop w. Don't forget to remove the words whose count reaches 0.
8476. Given an array A of n numbers, find if there is a subarray whose sum = 0.
848Solution:
849 1. Create a hash table H, sum = 0
850 2. For i = 0 to n-1:
851 sum += A[i]
852 if(H[sum] != NULL) return (H[sum]+1, i) //The subarray whose sum = 0 starts at H[sum]+1 and ends at i.
853 H[sum] = i
854Note: This algorithm can be extended to find a subarray whose sum = k by looking up H[sum - k] in the hash table. There is also a special case when the subarray starts at index 0, try it.
855
856---------------------------
857Sorting:
858
8591. Sorting an array of variable size objects, so that swapping is not trivial.
860Solution: Use indirect sort (sorting pointers to objects)
8612. Sort an array in O(n) algorithm where the number of distinct elements k is much less than the array size.
862Solution: Use a hash table to record each element's frequency, then iterate through the hashtable and rewrite the array. The hash function should keep the hashtable sorted.
8633. Print the number of occurences of each character in a string, sorted by character.
864Solution: sort the string.
8654. Remove all duplicates from an array
866Solution 1: Sort the array and keep only one instance of each element value.
867Solution 2: Use a hashtable to store the elements
8685. Given a list of events in terms of start and end times [si, ei], find the maximum number of events that are occurring in parallel (intersect in time).
869Solution: sort all si and ei, if si=ei then si comes first. then loop through the array from the beginning and each time you find si you (count++) and each time you find ei you (count--). Find the max count.
8706. Given a set of intervals [si, ei], find the minimum set of intervals that represent the union of intervals.
871Solution: sort all intervals according to start time of each interval.
8727. Given two teams heights in two arrays T1 and T2, write a function that returns true iff one team can be placed behind the other in a photograph such that each team must be in a row and each player in the back is taller than the one in front of him in the front.
873Solution O(nlgn): sort T1 and T2 and return true iff sort(T1) < sort(T2) || sort(T2) < sort(T1).
8748. External sort: How to sort n numbers stored in disk, with a memory size of m, where n >> m.
875 1. Load first m numbers into memory. Sort them using any sort algorithm like quicksort and write them back to disk
876 2. Load next m numbers into memory, do the same and repeat until you have k = n/m sorted chunks on disk.
877 3. divide memory into k+1 buffers, k for input and 1 for output.
878 4. Perform a k-way merging of the sorted arrays as follows:
879 a. Load each of the k input buffer with a chunk of the corresponding sorted data.
880 b. store the result of merging into the output buffer. when the output buffer is full, write it to disk and re-use it for another merging pass.
881 c. When one of the k input buffers becomes empty, load the next chunk of data for that buffer.
882 d. Continue untill all data has been sorted, merged into output buffer and written to disk.
8839. How would you sort n uniformly distributed numbers?
884Solution: Use bucket sort O(n) as follows:
885 A. Create n empty buckets (Or lists).
886 B. Do following for every array element arr[i].
887 B1. Insert arr[i] into bucket[n*array[i]]
888 C. Sort individual buckets using insertion sort.
889 D. Concatenate all sorted buckets.
890 Note: For uniformly distributed numbers, interpolation search can be faster than binary search.
89110. Which sorting algorithm makes the least number of memory writes?
892Answer: Selection sort O(n) writes (see wikipedia for code.). There is also another algorithm (Cycle sort) which does even less writes.
89311. Find the minimum-length unsorted subarray within array A.
894Solution: O(n)
895 A. Starting from 0, find the minimum index s such that A[s] > A[s+1]
896 B. Starting from n-1, find the maximum index e such that A[e] < A[e-1]
897 C. Find min and max within [s, e].
898 D. Find the first index i such that A[i] > min. Assign s = i.
899 E. Find the last index such that A[j] > max. Assign e = j.
900 F. The result is A[s..e].
90111. How to shuffle an array A of length n making sure that any permutation of the array has equal probability to be produced:
902Solution O(n): exchange the last element with a random element from the array, decrease the size of the array by 1, repeat until size = 0.
90312. Inversion Count: Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
904Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
905Solution O(n^2): Naiively compare every two elements in the array.
906Solution O(nlgn): Use a modified version of merge sort: http://www.geeksforgeeks.org/counting-inversions/
90713. Given two sorted arrays, find the median of their merged array.
908Solution1 O(n): Merge the two arrays into one sorted array and return the median of the sorted array.
909Solution2 O(lgn): Works only for arrays of same size
9101) Calculate the medians m1 and m2 of the input arrays ar1[] and ar2[] respectively.
9112) If m1 and m2 both are equal then we are done. return m1 (or m2)
9123) If m1 is greater than m2, then median is present in one of the below two subarrays.
913 a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
914 b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
9154) If m2 is greater than m1, then median is present in one of the below two subarrays.
916 a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
917 b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
9185) Repeat the above process until size of both the subarrays becomes 2.
9196) If size of the two arrays is 2 then use below formula to get the median.
920 Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
921Solution 3: A more general solution that works for arrays of different sizes: http://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/
92214. Pancake sorting: Given an array A and a function reverse(A, k) which reverses elements from k to n-1. Write a function that sorts the array.
923Solution:
924Note that you can move any element to any position by at most two reverse operations. For example, the array 1, 0, 3, 5, 2, 4.
925To move 0 to the start position call reverse(A, 1) --> 1, 4, 2, 5, 3, 0 --> reverse(A, 0) --> 0, 3, 5, 2, 4, 1
926Then to move one to the second position call reverse(A, 1) --> 0, 1, 4, 2, 5, 3
927Keep doing the same until the array is sorted.
928
929Notes:
930- The best sorting algorithm for linked lists is mergesort.
931- The sorting algorithm that makes the least number of writes is Cycle Sort. Also selection sort makes close to minimum # of writes.
932- Cycle sort views an unsorted array as cycles which can be rotated in order to achive sorting: http://www.geeksforgeeks.org/cycle-sort/
933
934---------------------------
935Trees and Binary Search Trees:
936
937Tree: a tree is an undirected graph in which any two vertices are connected by exactly one simple path
938Full binary tree: every node other than leaves has two children
939Perfect binary tree: full binary tree with all leaves at the same depth and all parents have two children
940Complete binary tree: a binary tree in which every level, except possibly the last is completely filled and all nodes are as far left as possible
941Balanced binary tree: a binary tree in which the depth of the left and right subtrees of **every node** differ by 1 or less.
942
943Tips:
944 - BST search is better implemented iteratively for O(1) space and faster execution. No need for recursion. Morris Traversal.
945 - When giving algorithm complexity, make sure to use O(h) and O(lgn) accurately, O(h) is usually the right bound.
946
9471. Write a function that returns true iff a binary tree satisfies the BST propperty.
948Solution 1 - O(n^2): check that each node n has n.key >= max(n.left) and n.key <= min(n.right). That is, each node's key must be greater than or equal to the minimum key in the left sub-tree, etc.
949Solution 2: Same as solution 1 above but cache the max and min at each subtree. Needs O(n) more space. Time reduces to O(n)
950Solution 3 - O(n) time, O(h) space: let v = root->key. l=lower, u=upper. All nodes in left (right) subtree must be within the interval [l,v] ([v,u]). Check recursively.
951Solution 4 O(n) time, O(h) space: In-order traversal of the BST should result in a sorted array. If at any point a visited node is < the previous node then BST property is violated.
9522. Design a O(h) function to delete a node n from a BST. Revise 14.2
953Solution: We have to consider three cases:
954 A. n is a leaf: simply update the pointers of the parent of n to null.
955 B. n has either a left child or a right child, but not both: Replace n by its own child.
956 C. n has both a left child and a right child: find n's successor (m) and consider two sub-cases:
957 C1. m is n's right child: replace n by m.
958 C2. m is not n's right child: replace m by its own right child, then replace n by m.
9593. Find kth largest/smallest element in BST.
960Solution 1 O(n): (Reverse) in-order traversal.
961Solution 2 O(h): Augment the tree datastrcuture so that each element contains the count of elements that are in the right/left subtrees. Do BST search on counts
9624. Find lowest common ancestor of n1 and n2 in a BST. Assume n1.k < n2.k
963Solution: Iterative O(h) time, O(1) space:
964Set x=root, if x.k > n1.k and x.k > n2.k then x = x.left, continue search. if x.k < n1.k and x.k < n2.k then x = x.right, continue search. If x.k > n1.k && x.k < n2.k return x.
9655. Find lowest common ancestor of n1 and n2 in a binary tree
966Solution:
967search for n1 and n2 in left and right subtrees
968 if both are on the left then recursively search for both on the left side.
969 if both are on the right then recursively search for both on the right side.
970 if one is on the left (or == cur_node) and the other is on the right (or == cur_node) then return the cur_node as lowest common ancestor.
9716. Given a sorted linked list of nodes, construct a balanced BST in O(n) time. (EPI 14.8)
972Solution: Idea is to recursively construct the tree, instead of iterating to move pointer to the mid-point of the LL, pass a pointer by reference and let it visit each tree node only once.
9737. Merge two BSTs
974Solution 1: Traverse the smaller BST and insert its elements into the larger BST. O(nlgn).
975Solution 2: Convert each BST into a sorted array, merge the two sorted arrays, create a new BST from the merged array. O(n).
9768. If we have a sequence of node keys in the order of pre-order traversal, then we can uniquely re-generate the BST (not applicable to general binary trees) that corresponds to the key sequence, as follows:
977For sequence list k1, k2, ..., kn. The root is k1, all the keys after k1 until ki that are < k1 correspond to k1's left subtree. All the othe keys are in k1's right subtree. Build trees recursively.
9789. How would you perform a range search [L,R] on a BST?
979Solution: I think that finding the smalles element >=L and then doing an inorder traversal works well. See 14.14 solution for the other method.
98010. Implement a function that determines if a binary tree is balanced in O(n): http://www.geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced/
981Solution: The difference between min_depth and max_depth of any non-leaf nodes must be <= 1. Calculate height in the same function call as isBalanced
982The key to achieving O(n) is getting the height and isBalanced in the same recursive call, and then setting cur_height = max_height(left, right) + 1
98311. How to do an in-order of a binary tree traversal with O(1) space?
984Solution: There is an algorithm (Morris Traversal) that can do this in O(n) time. It modifies the tree but also restores the tree to its original form after the traversal.
985Morris Traversal: https://www.youtube.com/watch?v=wGXB9OWhPTg
986See this image for the visualization of the tree: http://www.geeksforgeeks.org/threaded-binary-tree/
987cur = root
988while cur != null
989 if cur->left == null
990 print cur->data
991 cur = cur->data
992 else
993 //find the predecessor p of cur and set cur as the right child of p (The idea is that we need cur to be printed after its predecessor, as in-order traversal)
994 p = cur->left
995 while (p->right == null & p->right = cur)
996 p = p->right;
997 if(p->right == null) //This case is when the predeccesor has not been visited yet, so we modify the tree
998 p->right = cur //make cur node as the right child of its predecessor
999 cur = cur->left //visit the left subtree, as in normal in-order traversal, later we will revisit cur as it is now in this left subtree
1000 else // This case is when the predecessor has been visited, so we restore the tree to its original shape
1001 p->right = null //remove the right to restore the shape of the tree.
1002 print cur->data //print this data as we already visited our predecessor
1003 cur = cur->right //finished left and self, so visit right!
100413. How to check if a Binary Tree is complete
1005Solution O(n): Use BFS, as you traverse each level all nodes must either have left and right children, if a node has only right child then return false, if a node has only a left child, all next nodes must have no children.
100614. How to find two nodes n1, n2 in a BST whose sum = k.
1007Solution: O(n): We do two traversals simultaneously (in order and reverse in-order). This needs to be done iteratively using stacks to emulate recursion.
100815. Modify a binary tree to be a mirror image of itself:
1009Solution: Recursive: Reverse(left), Reverse(right), swap(left, right).
101016. Construct a BST from a sorted linked list in O(n)
1011Solution: The idea is to construct the BST while head is moving left to right:
1012curHead = head;
1013TreeNode SortedListToBST(length)
1014{
1015 if(n <= 0) return null;
1016 TreeNode left = SortedListToBST(curHead, n/2);
1017 TreeNode root = new TreeNode(curHead.Value);
1018 curHead = curHead.next;
1019 TreeNode right = SortedListToBST(n - length/2 - 1);
1020 root.left = left;
1021 root.right = right;
1022 return root;
1023}
102417. Binary tree maximum path sum: http://www.programcreek.com/2013/02/leetcode-binary-tree-maximum-path-sum-java/
102518. Find if a binary tree is symmetric: Can be solved with recursion, basically you need to implement isMirror() which checks if a BST is a mirror of itself: http://www.geeksforgeeks.org/symmetric-tree-tree-which-is-mirror-image-of-itself/
102619. Clone a binary tree with left, right and random pointers: http://www.geeksforgeeks.org/clone-binary-tree-random-pointers/
1027Two methods: Use a hash table or modify the original tree.
102820. Construct a binary tree from pre-order and inorder traversal: http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
1029Idea is that we can know the root from pre-order traversal, then we look for the root in the inorder traversal, all elements to the left are in the left sub-tree, elements on the right are in the right sub-tree. Solve recursively.
103021. Find the max width of a binary tree: http://www.geeksforgeeks.org/maximum-width-of-a-binary-tree/
1031Solution 1 O(n): Use BFS (level-order traversal). Because tree nodes do not have a "level" or "distance" member variable, you need to keep track of the current level by knowing how many items you pushed into the queue since last level.
1032Solution 2 O(n): create a width array of size h (height of tree) then traverse all tree nodes and at each node of level k: width[k++]. Then return max of the width array.
103322. Check if a tree S is a sub-tree of a tree T:
1034bool isSubtree(struct node *T, struct node *S)
1035{
1036 /* base cases */
1037 if (S == NULL)
1038 return true;
1039
1040 if (T == NULL)
1041 return false;
1042
1043 /* Check the tree with root as current node */
1044 if (areIdentical(T, S))
1045 return true;
1046
1047 /* If the tree with root as current node doesn't match then try left and right subtrees one by one */
1048 return isSubtree(T->left, S) || isSubtree(T->right, S);
1049}
1050
1051bool areIdentical(struct node * root1, struct node *root2)
1052{
1053 /* base cases */
1054 if (root1 == NULL && root2 == NULL)
1055 return true;
1056
1057 if (root1 == NULL || root2 == NULL)
1058 return false;
1059
1060 /* Check if the data of both roots is same and data of left and right subtrees are also same */
1061 return (root1->data == root2->data &&
1062 areIdentical(root1->left, root2->left) &&
1063 areIdentical(root1->right, root2->right) );
1064}
106523. How to insert a new element into a BST: (Does that keep the tree balanced? No, for that we have self-balanced BSTs)
1066Solution O(lgn): A new key is always inserted as a leaf. Search for the key and once you hit a leaf make the new element as left/right child of the leaf node depending on whether it is smaller or greater.
106724. Correct a BST that has two of its elements swapped: http://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/
1068Tip: consider two cases, when the swapped elements are adjacent, and when they are not. First case has one inversion and second case has two.
106925. Convert a binary tree into a BST while keeping the structure of the original tree.
1070Solution:
1071- Do inorder traversal of the tree and store elements into an array arr.
1072- Sort the array
1073- Do a second inorder traversal of the tree, and for each element, replace its value with the value from the array.
107426. Given a binary tree, print elements in vertical order: http://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/
1075Solution 1 O(n^2):
1076 - Assume that root is at vertical point = 0. Each time we go to left sub-tree we subtract 1, each time we go to the right sub tree we add 1.
1077 - Find min and max vertical positions in the tree.
1078 - For vertical_order in min..max, printElements(root, vertical_order).
1079Solution 2 O(n):
1080Use a hash table<vertical_order, list_of_nodes> to store elements at each vertical order.
1081
1082---------------------------
1083Self-balancing binary search trees
1084- For a classic implementation of a BST, tree inserts can make the tree very unbalanced resulting in poor performance, henve the concept of self-blanacing BSTs.
1085Multiple variants of SB-BST:
10861. Treap: The idea is to use Randomization and Binary Heap property to maintain balance with high probability. The expected time complexity of search, insert and delete is O(Log n).
1087- Every node of Treap maintains two values: Key (same as BST's key), and priority.
1088- Priority is a random number in some range e.g. [1..100]
1089- Priority is used to maintain the heap property. Whenever a new element is added, rotation happen in order to maintain the heap property.
1090
1091Insert Operation:
1092A. Create new node with key equals to x and value equals to a random value.
1093B. Perform standard BST insert.
1094C. A newly inserted node gets a random priority, so Max-Heap property may be violated.. Use rotations to make sure that inserted node’s priority follows max heap property.
1095
1096Other details: http://www.geeksforgeeks.org/treap-set-2-implementation-of-search-insert-and-delete/
1097
10982. Red-Black trees.
10993. AVL trees.
1100---------------------------
1101Divide and conquer:
11021. In a list of points pi=(xi,yi), find the two closest points.
1103Solution 1: Brute force compute the distance between every two points. O(n^2).
1104Solution 2: Use divide and conquer as follows: O(nlgn).
1105 A. Partition the points around the median x-coordinate O(n)
1106 B. recursively find the two closest points in L and R partitions
1107 C. Let the two closest points in L and R have d1 and d2 distance respectively. Let d = min(d1, d2).
1108 D. The next time we need only to consider points [median - d, median + d]
1109
11102. Compute the diameter of a tree. Each edge has a cost, the diameter is the maximum cost from a tree node to another node.
1111Solution 1 O(n^2): BFS from each node to all other nodes and recording the shortest path distances and maintaining a maximum.
1112Solution 2 O(n):
1113int diameterOpt(struct node *root, int* height)
1114{
1115 /* lh --> Height of left subtree. rh --> Height of right subtree */
1116 int lh = 0, rh = 0;
1117 /* ldiameter --> diameter of left subtree. rdiameter --> Diameter of right subtree */
1118 int ldiameter = 0, rdiameter = 0;
1119 if(root == NULL)
1120 {
1121 *height = 0;
1122 return 0; /* diameter is also 0 */
1123 }
1124
1125 /* Get the heights of left and right subtrees in lh and rh And store the returned values in ldiameter and ldiameter */
1126 ldiameter = diameterOpt(root->left, &lh);
1127 rdiameter = diameterOpt(root->right, &rh);
1128
1129 /* Height of current node is max of heights of left and right subtrees plus 1*/
1130 *height = max(lh, rh) + 1;
1131
1132 return max(lh + rh + 1, max(ldiameter, rdiameter));
1133}
1134
11353. Compute x to the power y in O(logn)
1136int power(int x, unsigned int y) {
1137 int temp;
1138 if( y == 0)
1139 return 1;
1140 temp = power(x, y/2);
1141 if (y%2 == 0)
1142 return temp*temp;
1143 else
1144 return x*temp*temp;
1145}
1146---------------------------
1147Dynamic Programming:
1148- Overlapping sub-problem and Memoization vs tabulation: http://www.geeksforgeeks.org/dynamic-programming-set-1/
1149- Optimal sub-structure property: http://www.geeksforgeeks.org/dynamic-programming-set-2-optimal-substructure-property/
1150
1151Examples of Dynamic Programming Problems:
1152 1. Rod cutting
1153 2. Optimal BST construction
1154 3. Matrix-chain multiplication
1155 4. Longest simple path in a DAG
1156
11571. Find the maximum subarray sum.
1158Solution O(n): Create array S such that S[i] = sum of all elements from 0 to i. During the iterations, maintain the maximum (S[i] - S[j]) by keeping track of the minimum S[j], j<=i. value = S[i] - S[j], range = [j, i]
11592. Find the maximum subarray sum in a circular array.
1160Solution 1: Find the minimum (non-circular) subarray sum that is less than zero. The remaining elements are the maximum circular subarray.
1161Solution 2: See EPI page 353.
11623. Important: Longest non-decreasing subsequence in array A[0..n-1]: EPI 15.6
1163Solution: Create array M such that M[0] = 1.
1164 For i = 1 to n-1
1165 M[i] = 1
1166 for j = 0 to i - 1
1167 if(A[i] > A[j])
1168 M[i] = max(M[i], M[j] + 1);
1169
1170for all M[i], i > 0 = max(for all j<i: A[j]<=A[i] ? M[j]+1 : 1). O(n^2)
1171Solution 2 DP O(nlgn):
1172 Create M as a dynamic size vector
1173 for each a in A do
1174 find first element M[i] in M > a. If found, set M[i] = a, else append a to M //binary search O(logn).
1175 end for
1176 return M //contains the longest non-decreasing subsequence
11774. Weighted interval scheduling: Given a set of intervals [Si, Ei] with each interval having a weight Wi, find the non-overlapping schedule which results in the largest total W.
1178Solution: O(n)
1179//Assumes intervals are sorted by nondecreasing finish times
1180M-Compute-Opt (j)
1181 If j = 0 then
1182 Return 0
1183 Else if M[j] is not empty then //not empty means it was computed before so no need to re-compute (memorization)
1184 Return M[j]
1185 Else
1186 //p(j), for an interval j, is the largest index i < j such that intervals i and j are disjoint
1187 Define M[j] = max(vj+M-Compute-Opt(p(j)), M-Compute-Opt(j-1)) //vj is interval weight
1188 Return M[j]
11895. Given array A (which can contain negative numbers), find the longest subarray whose sum <= k
1190My own solution O(n) (Not verified): Create an array M (M[-1]=0) with cumulative sum such that M[i] = sum(A[0]...A[i]). Then pointer s points to M[-1], e points to M[n-1].
1191Compute the sum of A[i]..A[j] by (M[j]-M[i]), if sum<=k, return range(i,j). Otherwise, if (A[e] - A[e-1]) > (A[s+1] - A[s]) then e-- else s++.
1192Book Solution: EPI page 356
11936. Maximum 2D subarray (EPI page 15.9 Page 120): Given a m x n 2D array, find the maximum submatrix sum.
1194Solution: 2D Kadane algorithm: https://www.youtube.com/watch?v=yCQN096CwWM&t=286s
1195
1196//The first two nested loops check all possible right and left positions (col numbers) in a bruteforce method.
1197for fromCol 0..cols-1
1198 create dp[0..rows-1] array with all zero
1199 for col fromCol..cols-1
1200 //Now we fill dp with elements
1201 for row 0..rows-1
1202 dp[row] += arr[row,col]
1203 //run 1D kadane
1204 sum = 0, max1D = 0
1205 for i 0..dp.Length-1
1206 sum += dp[i]
1207 if(sum < 0)
1208 sum = 0;
1209 top = i+1;
1210 if(sum > maxSum)
1211 maxSum = sum
1212 maxL = fromCol, maxR = col, maxTop = top, maxBottom = i;
1213Complexity: O(col^2*row)
1214Note: There is a better O(row*col) that uses max area under histogram algorithm in EPI page 361
1215
12167. Extracting words from a URL: devise efficient algorithm to extract words from a URL. bedbathandbeyond.com = {bed bath and beyond} or {bed bat hand beyond}.
1217Solution DP: 1. extract all words that begin at 0 (be, bed) and put them into a table. Then extract next words (start from 2 after "be" or from 3 after "bed"), and so on.
12188. Given two arrays A and B, find the longest common subsequence.
1219Solution: we will write this as a recurrence:
1220 1 + LCS(i-1, j-1) A[i] = B[j]
1221LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1)) A[i] != B[j]
1222 0 if i == 0 or j == 0
12239. Coin change problem: Given a value n, and infinite supply of coins of values [v1, v2, v3, ..., vm], return how many ways we can represent n.
1224To count total number solutions, we can divide all set solutions in two sets.
12251) Solutions that do not contain mth coin (or Sm).
12262) Solutions that contain at least one Sm.
1227Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).
1228Solution: O(nm).
1229int count( int S[], int m, int n ) {
1230 int table[n+1] = {0};
1231 table[0] = 1;
1232 for(int i=0; i<m; i++)
1233 for(int j=S[i]; j<=n; j++)
1234 table[j] += table[j-S[i]];
1235 return table[n];
1236}
1237
1238What if you want to count the number of permutations? i.e. 1, 1, 2 is different from 1, 2, 1?
1239Suppose we know for all u < n the number of permutations in which u can be achieved, for each coin vi we can do n - S[i] and then followed by coin S[i].
1240Solution O(nm):
1241int count(int S[], int m, int n)
1242{
1243 int table[n+1] = 0;
1244 table[0] = 1;
1245 for(int i=0; i <= n; i++)
1246 for(int j = 0; j < m; j++)
1247 if(i >= S[i])
1248 table[i] += table[i - S[i]];
1249
1250 return table[n];
1251}
1252
125310. Matrix chain multiplication: See matrix_chain.cpp
125411. Binomial Coefficient: C(n, k) is the number of ways you can choose k objects from n objects, disregarding order. C(n, k) = C(n-1, k-1) + C(n-1, k).
125512. Egg dropping puzzle: You have n eggs and k floors. Determine minimum number of eggs required to find out the highest floor from which you can drop an egg without the egg breaking.
1256Solution: The idea is that if you try to drop an egg from floor i then you have two cases:
1257 A. The egg breaks: So you have n-1 eggs and you need to try i-1 floors. Recursion is f(n-1, i-1).
1258 B. The egg doesn't break: So you have n eggs, and k-i floors to try. Recursion is f(n, k-i)
1259 - You need to try this for all floors, and minimize the maximum of the above two cases:
1260int eggDrop(int n, int k) {
1261 if (k == 1 || k == 0) // If there are no floors, then no trials needed. OR if there is one floor, one trial needed.
1262 return k;
1263 if (n == 1) // We need k trials for one egg and k floors
1264 return k;
1265 int min = INT_MAX, x, res;
1266
1267 // Consider all droppings from 1st floor to kth floor and return the minimum of these values plus 1.
1268 for (x = 1; x <= k; x++) {
1269 res = max(eggDrop(n-1, x-1)/*when the egg breaks*/,
1270 eggDrop(n, k-x)/*when the egg doesn't break*/);
1271 if (res < min)
1272 min = res;
1273 }
1274 return min + 1;
1275}
127613. Longest Palindrome subsequence: Given a string s of length n, find the longest palindrome subsequence:
1277Solution: f(0, n) = if s[0] == s[n-1] then result = 2 + f(1, n-2) else result = max(f(0, n-2), f(1, n-1)).
1278int lps(char *seq, int i, int j) {
1279 if (i == j) // Base Case 1: If there is only 1 character
1280 return 1;
1281 if (seq[i] == seq[j] && i + 1 == j) // Base Case 2: If there are only 2 characters and both are same
1282 return 2;
1283 if (seq[i] == seq[j]) // If the first and last characters match
1284 return lps (seq, i+1, j-1) + 2;
1285 return max( lps(seq, i, j-1), lps(seq, i+1, j) ); // If the first and last characters do not match
1286}
128714. Longest Bitonic subsequence: Given an array A of n integers, find the longest subsequence that is increasing then decreasing.
1288Solution:
1289 A. Construct the array A1 such that A1[i] = the LIS ending at index i (as in problem 3).
1290 B. Construct the array A2 such that A2[i] = the LDS starting at index i.
1291 C. Return LIS(i) + LDS (i) - 1, that is maximum for all i.
129215. Word wrap problem
129316. Set partition problem: You have a set S of n numbers, find out if you can partition the numbers in two sets with equal sum.
1294Solution: if sum(S) is odd, then return false. Otherwise, find out if you can find a subset S1 of S with sum(S1) = sum(S) / 2. So this problem reduces to subset sum.
1295part[i][j] = true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum equal to i, otherwise false
1296bool findPartiion (int arr[], int n) {
1297 int sum = 0, i, j;
1298 for (i = 0; i < n; i++) //sum of all elements
1299 sum += arr[i];
1300 if (sum%2 != 0)
1301 return false;
1302 bool part[sum/2+1][n+1]; // initialize top row as true
1303 for (i = 0; i <= n; i++)
1304 part[0][i] = true;
1305 for (i = 1; i <= sum/2; i++) // initialize leftmost column, except part[0][0], as 0
1306 part[i][0] = false;
1307
1308 // Fill the partition table in bottom up manner
1309 for (i = 1; i <= sum/2; i++) {
1310 for (j = 1; j <= n; j++) {
1311 part[i][j] = part[i][j-1]; //if there is a subset of arr[0..j-1] whose sum = i, then there is definitely a subset of arr[0..j] whose sum = i.
1312 if (i >= arr[j-1])
1313 part[i][j] = part[i][j] || part[i - arr[j-1]][j-1]; //if there is a subset of arr[0..j-1] whose sum = i - arr[j-1], part[i][j] is true, since we can just add arr[j-1] to make the subset sum=i.
1314 }
1315 }
1316 return part[sum/2][n];
1317}
131817. You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs.
1319Solution:
1320 A. Sort pairs in increasing order.
1321 B. Run longest increasing subsequence algorithm.
132218. Building bridges: http://www.geeksforgeeks.org/dynamic-programming-set-14-variations-of-lis/
132319. Maximum-size square submatrix with all 1s: Given a binary array M, find the largest square submatrix with all 1s.
1324Solution: Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.
1325
13261) Construct a sum matrix S[R][C] for the given M[R][C].
1327 a) Copy first row and first columns as it is from M[][] to S[][]
1328 b) For other entries, use following expressions to construct S[][]
1329 If M[i][j] is 1 then
1330 S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
1331 Else /*If M[i][j] is 0*/
1332 S[i][j] = 0
13332) Find the maximum entry in S[R][C]
13343) Using the value and coordinates of maximum entry in S[i], print
1335 sub-matrix of M[][]
1336
133720. Maximum size rectangular submatrix with all 1s: http://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/
1338Solution:
1339Step 1: Find maximum area for row[0]
1340Step 2: Create auxiliary array a[rows][cols] and copy first row to this array
1341Step 2:
1342For all rows 1..n-1
1343 For each element e=a[row][col] in row: if(e==1) a[row][col] = arr[row][col - 1] + 1 else a[row][col] = 0
1344 FindMaxArea(a[row])
1345
1346Note: To find max area for this row you can either use max area under histogram algorithm (O(n)) or just use a naiive algorithm O(n^2). For a row 2 3 3 2 max area = (3 + 3) = 6, as 3 + 3 forms the largest rectange.
1347
134821. largest rectangular area under a histogram: http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
1349The idea behind this question is that we keep pushing elements to a stack as long as histogram bars are not decreasing in value, once we see a bar that is a decrease we start our computation. See this:
1350For each index i in hist array (0..n-1)
1351 if stack is empty or this bar is higher than the bar at the top of the stack, then push i into the stack.
1352 else: Compute the area in the window with elemt e = hist[s.pop()] as the min element. right = i-1, left = stack.empty() ? 0 : i - s.top - 1, area = (right - left + 1) * e
1353
135422. Largest independent set: http://www.geeksforgeeks.org/largest-independent-set-problem/
135522. Word wrap problem: Given n words and a line width of k characters, Find an optimal division of words such that the lines contain as few extra spaces as possible. Formally, the goal is minimize the sum of the cost function: cost(line_i) = extra_spaces ^ 3.
1356Solution:
1357 A. A well-known solution is a greedy method where you pack as many words as you can on single line, and then you move on to the next line. This method is not optimal but still good. O(n)
1358 B. An optimal solution is possible using dynamic programming. The solution is O(n^2) but works better in practice because lines can't be too long.
1359 Let c[j] be the cost of arranging the words from 0 to j on multiple lines.
1360 Let lc[i, j] be the cost of arranging the words i to j on a single line = extra_space ^ 3.
1361 We have the following recursion:
1362 c[j] = min (c[i-1] + lc[i, j]), for all i (1 <= i <= j). And note that c[0] = 0.
136323. Given an array of Xs and Os (or 0s and 1s), find the dimension of the biggest square that is surrounded by Xs (or 1s).
1364 X O X X X X
1365 X O X X O X
1366M = X X X O O X
1367 O X X X X X
1368 X X X O X O
1369 O O X O O O
1370Solution 1 (Naiive O(n^4)): Consider every square and check if it is surrounded by Xs, return the largest.
1371Solution 2 (DP - ON(n^3)):
1372- Create two aux arrays hor and ver, hor contains the number of consecutive Xs up-to each cell in the row, ver contains the number of consecutive Xs up-to each cell in a col:
1373hor[6][6] = 1 0 1 2 3 4
1374 1 0 1 2 0 1
1375 1 2 3 0 0 1
1376 0 1 2 3 4 5
1377 1 2 3 0 1 0
1378 0 0 1 0 0 0
1379
1380ver[6][6] = 1 0 1 1 1 1
1381 2 0 2 2 0 2
1382 3 1 3 0 0 3
1383 0 2 4 1 1 4
1384 1 3 5 0 2 0
1385 0 0 6 0 0 0
1386max = 0
1387for (i = n-1; i >= 0, --i)
1388 for(j = m-1; j >= 0; --j)
1389 small = min(hor[i,j], ver[i,j]) //We take the smallest as we want a square, not a rectangle.
1390 //The above confirms that we have two sides of the square, but what about the two other sides that complete this square? We need to search for them before we can set max=k for k=[small down to max].
1391 while (small > max)
1392 {
1393 if (ver[i][j-small+1] >= small && hor[i-small+1][j] >= small)
1394 max = small;
1395 small--;
1396 }
1397
1398---------------------------
1399Greedy Algorithms:
1400
1401Definition: A greedy algorithm is an algorithm that makes a locally optimal choice and never changes it, in the hope of reaching of a globally optimal solution.
1402- Any problem that can be solved by a greedy method can be also solved by dynamic programming. This means that dynamic programming is a more general method.
1403 - However, for some problems using dynamic programming is an overkill as there exist greedy algorithms that can find the optimal solution in less asymptotic time.
1404 - In dynamic programming, the local choice that we make is dependent on the solutions of the sub-problems, the greedy choice does not depend on any sub-problem, it only depends on the local problem.
1405 - we must prove that a greedy choice at each step yields a globally optimal solution.
1406
14071. Given n simultaneous database requests with each request Ri having service time Ti. Process the requests in some order that minimizes waiting time.
1408Solution: Sort by non-decreasing Ti and process in that order.
14092. Interval scheduling: We have a set of n requests R1..Rn with Ri having start time Si and finish time Fi. Find the largest non-overlapping subset of intervals.
1410Solution O(nlgn): Sort by increasing finish time, accept the request with smallest Fi that is non-overlapping with previously accepted requests.
14113. Interval scheduling 2: Schedule all n intervals on M machines
1412Solution:
1413Sort all intervals by nondecreasing start time
1414for j=1 to n
1415 for each interval i that precedes and overlaps j
1416 exclude i.label from consideration for labeling j
1417 end for
1418 if there is an unused machine, use it otherwise allocate a new machine.
1419end for
14204. Schedluing to minimize latency: sort by nondecreasing deadline.
14215. The fractional knapsack problem: You have n items and each item has a value of x/unit and you can take a total of y units.
1422Solution: sort in decreasing x/unit.
14236. Huffman codes
14247. Graph coloring: Given a graph G, use a minimum number of colors (k) to color its vertices such that no adjacent vertices have the same color.
1425- This problem is NP-complete, but there is a greedy algorithm that guarantees that no more d+1 colors are used, where d is the maximum degree (number of edges) of a vertex v in G.
1426- To achieve minimum k, a back-tracking algorithm is used.
1427Solution:
1428 A. assign color 0 to first vertex
1429 B. Do following for each vertex v of the remaining V-1 vertices.
1430 B1. Color v with the lowest color that has not been used for an adjacent vertex
14318. Given a value v and an infinite number of coins of values (v1, v2, ..., vm). Find the minimum number of coins to represent v
1432Solution: There is a greedy algorithm but it doesn't work for all inputs O(m). A dynamic programming algorithm works for all inputs.
1433- Start from the highest value coin that has vi <= v, subtract vi from v, k++. Repeat until v == 0.
14349. Connect n ropes with minimum cost, given that the cost to connect two ropes is the sum of their lengths.
14351. Insert all ropes into a min-heap.
14362. While min_heap.count > 1
1437 Take the two smalles ropes
1438 cost += connect(r1, r2)
1439 return the connected rope into the heap
1440
1441---------------------------
1442Graphs:
1443
1444Clique: undirected graph in which there is an edge between each two vertices.
1445BFS: can be used to get information about distances (# of edges). Works for directed and undirected graphs.
1446DFS: can be used to detect cycles and compute discovery and finish times.
1447MST: Applicable to undirected connected graphs. Two main algorithms: Kruskal and Prim. O(ElgV). Easier to implement Kruskal algorithm in an interview.
1448Bi-connected graph: a connected and "nonseparable" graph, meaning that if any vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.
1449Strongly connected: There is a path from each vertex to each other vertex. For undirected graphs, you can start from any vertex and see if all other veritces are reachable. For directed graphs use Strongly Connected Components algorithm
1450Semi-connected: a graph that for each pair of vertices u,v, there is either a path from u to v or a path from v to u.
1451Bipartite Graph: a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
1452Articulation point: A vertex whose removal disconnects the graph.
1453Bridge: An edge whose removal disconnects the graph.
1454Biconnected component of G: A maximal set of edges such that any two edges in the set lie on a common simple cycle.
1455Simple cycle: Simple path with no repeated vertices other than the starting and ending vertices.
1456
1457Representing a graph: This might be problem-dependent. Each problem may have a distinct representation of a graph, you need to think about your requirements. A typical representation might be:
1458
1459 public class Graph
1460 {
1461 public List<Vertex> Vertices = new List<Vertex>();
1462 public List<Edge> Edges = new List<Edge>();
1463 }
1464
1465 public class Vertex
1466 {
1467 public string Name;
1468 public List<Vertex> Adj = new List<Vertex>();
1469 public bool Visited;
1470 public Vertex Predecessor;
1471
1472 //For DFS
1473 public int DiscoveryTime;
1474 public int FinishTime;
1475
1476 //For BFS
1477 public int Distance;
1478
1479 //For union-find
1480 public Vertex Parent;
1481 public int Rank;
1482 }
1483
1484 public class Edge
1485 {
1486 public Vertex Src, Dest;
1487 public int Weight = 1;
1488 }
1489
14901. Design an algorithm that checks if a graph is a bi-partite graph:
1491Solution: We assume that the graph is connected. Run BFS starting from an arbitrary node s, assign s to "left partition", now all elements in queue will either have edge to vertices at d+1 or at d distance. If there is an edge from a vertex at d distance to a vertex at d distance then the graph is not bi-partite, otherwise, continue BFS in same way. If the graph is not connected, we can get its SCC and analyze them separately. G is bi-partite if and only if all SCCs are bi-partite.
14922. Given a connected graph G, design an algorthim that returns true iff there exists an edge such that if removed from the graph, the graph remains connected.
1493Solution O(V): The above can be true iff there exists a cycle in the graph. Use DFS to look for a cycle. If a cycle exits return true, otherwise return false.
14943. Given a connected graph G, design an algorthim that returns true iff if any edge is removed from the graph, the graph remains connected.
1495Solution O(V): The above can be true iff every edge in the graph lies on a cycle. Use DFS to find out.
14964. See the implementation of solution 16.7 page 396. It says a lot about how to analyze graphs using STL.
14975. Find shortest path with minimum number of edges.
1498Solution: Instead of using integers to represent path length, use a pair<int, int> representing path cost and path length. Implement operators < and + and use Dijkstra's algorithm with a BST rather than a heap.
14996. Given a table of currency exchange rates. Find if there is an arbitrage (A situation where you can take one unit of currency C, make a series of transactions and end up in more than one unit of C).
1500Solution: Model currencies as vertices, -log(exchange rate) as edge costs. Return true iff there is a negative cycle in the graph, this can be found using Bellman-Ford algorithm.
15017. Given a DAG find the longest path from a source vertex s to all other vertices.
1502Solution: Longest path for a general graph is NP hard. But it is linear for a DAG:
1503 A. Create a topological sorting of vertices
1504 B. Initialize dist(v) = -INF for all v
1505 C. For each vertex v in topological order:
1506 for every vertex u in adj(v): if dist(u) < dist(v) + w(v,u) then dist(u) + dist(v) + w(v,u)
15078. How to find all articulation points in a graph?
1508Solution:
1509 A. For each vertex v:
1510 remove v from graph (along with its edges)
1511 Check if this disconnects the graph (via SCC algorithm)
1512 if so, print v.
1513 re-insert v in the graph.
1514Solution 2: There is a more efficient solution that uses one pass of DFS: http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
15159. How to find if a directed graph has a cycle
1516Note: simply finding an edge to an already visited vertex is NOT the right solution, as the visited vertex could be in another tree in the DFS forest.
1517Solution: We need to find a back edge, an edge from a descendent to an ancestor. We do this by keeping a stack of visited vertices in the current recursion tree. If we discover a vertix that is already in the stack then cycle is found.
1518Tip: Rather than maintaining an explicit stack (searching in stack is O(n)), keep a bitset, where bitset[vertix]==1 iff the vertix was visited in the current recursive call.
1519Link to solution: http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
152010. How to find if an undirected graph has a cycle
1521Solution: A union-find algorithm can be used.
1522- Create a set for each vertex
1523- For each edge(u,v) if(v.set == u.set) return true, else u.set = v.set = Math.Min(u.set, u.set)
1524Solution 2: During DFS: For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If on such vertex, return false.
152511. Find out if a Graph G is strongly connected:
15261) Initialize all vertices as not visited.
15272) Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS traversal doesn’t visit all vertices, then return false.
15283) Reverse all arcs (or find transpose or reverse of graph)
15294) Mark all vertices as not-visited in reversed graph.
15305) Do a DFS traversal of reversed graph starting from same vertex v (Same as step 2). If DFS traversal doesn’t visit all vertices, then return false. Otherwise return true.
153112. Graph Coloring:
1532Applications:
1533- Register Assignment in CPU
1534- Frequency assignment in radio towers
1535- Soduko
1536- Making schedule or time table: Example is college exams, exams are vertices, students are edges between exams if they have a common exam. Goal is to schedule exams with no overlapping exams for a student.
1537- Bi-partite graphs: Graph is bi-partite iff it can be colored with only 2 colors.
1538- Map coloring: No two adjacent countries are painted with the same color.
1539- Rolling out updates to servers that can't be taken down simultanously.
1540Solution: NP-Complete problem but there is a greedy approximation algorithm that is guaranteed to use no more than m+1 colors, where m is the minimum number of colors that is produced by the optimal backtracking algorithm
15411. Color first vertex with first color.
15422. Do following for remaining V-1 vertices.
1543 a) Consider the currently picked vertex and color it with the lowest numbered color that has not been used on any previously colored vertices adjacent to it. If all previously used colors appear on vertices adjacent to v, assign a new color to it.
154413. Traveling salesman: Given a complete undirected graph G of cities and distances (there is an edge between every two vertices). Find a simple cycle that covers all vertices and has the minimum cost.
1545- This is an NP complete problem.
1546Solution 1 (Naiive), O(n!):
1547 A. Choose any city c0 as the starting point.
1548 B. Generate (n-1)! permutations for the other cities.
1549 C. compute the cost for all paths that start from c0 and visit each permutation in order, maintain and return the minimum.
1550Solution 2 (Dynamic Programming): O(n^2 * 2^n): http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
1551Solution 3 (Approximate): The approximate algorithms work only if the problem instance satisfies Triangle-Inequality.
1552 A. Select any city c0 as the starting point
1553 B. Use Prim's algorithm to compute the MST with c0 as root.
1554 C. Walk through the tree printing each vertex you find, if the vertex has been visited before then you can skip visiting it and visit the next city without increasing the cost (because of triangle inequality)
1555This solution guarantees that the cost is no more than twice the optimal cost. The reason is that every edge in the MST is visited at most twice, so max cost = 2 * cost (MST) <= 2 * optimal cost of the tour.
155614. Vertex Cover: A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph.
1557Problem: Given an undirected graph, the vertex cover problem is to find minimum size vertex cover.
1558Note: This is known to be NP-Complete problem.
1559Solution (Approximate):
15601) Initialize the result as {}
15612) Consider a set of all edges in given graph. Let the set be E.
15623) Do following while E is not empty
1563...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result
1564...b) Remove all edges from E which are either incident on u or v.
15654) Return result
156615. Given a list of contacts (username, phone, email), two contacts are considered to be the same person if they have the same username, phone or email. Given the list of contacts, return entries that belong to each person.
1567Solution: Model as a graph, each entry is a vertex, an edge connects two vertices if they share common info (username, phone, email). Return SCC.
156816. 0-1 BFS: Given a graph G where all edges have weight of 0 or 1. Compute single-source shortest paths from a given vertex v.
1569- Notice that if all edges were 1 then BFS O(V+E) can be used.
1570- Also notice that Dijkstra's algorithm solves the general problem of single-source shortes paths in O(ElgV).
1571We use a method that is similar to Dijkstra's but because edge values are limited to 0, 1 we can avoid the need for a priority queue by using a double ended queue, insert vertices that are 0 units away from current in front, and vertices that are 1 unit from current source at the back.
1572-Note: Revise Network flow algorithms
157317. Cloning a graph?
157418. Given a graph with both directed and undirected edges. It is given that the directed edges don’t form cycle. How to assign directions to undirected edges so that the graph (with all directed edges) remains acyclic even after the assignment?
1575Solution: First do topological sorting with the directed edges (ignore the undirected edges). Then for each undirected edge between (u, v), make it a directed edge from u to v if u comes before v in the directed graph, or v to u otherwise.
1576
1577---------------------------
1578Intractability:
15791. The partition problem: This is a special case of the subset sum problem: Given a set of n integers, is there a subset of n that sums to sum(n)/2?
1580Solution: The problem is known to be NPC. However there is a pseudo-polynomial algorithm using DP which runs in O(nN), where N is the sum of all elements. See EPI solutio 17.1 p403
15812. The 0-1 Knapsack problem: Given a list of n items, each item has a size si and a value vi, you have a knapsack of total size S. How would you choose a subset of items such that their total size <= S and have a maximum total value.
1582Solution: Using dynamic programming we can get a pseudo-polynomial complexity O(nS).
1583Guess: For each item, we either include it in the subset of items or we don't
1584KS(i, x) = max(KS(i+1, x), KS(i+1, x - si) + vi), where x is the remaining size in the knapsack. We execute the recursion as long as x < S.
1585
1586int knapsack(vector<int> &v, int remaining, int i) {
1587 if(i >= v.size())
1588 return 0;
1589 if(v[i] > remaining)
1590 return knapsack(v, remaining, i + 1);
1591 return max(knapsack(v, remaining, i+1), knapsack(v, remaining - v[i], i + 1) + v[i]);
1592}
15933. Traveling salesman: See Graph Algorithms
1594---------------------------
1595Other problems:
1596
15971. Given a sentence, check it for a set of rules: Use state diagram: http://www.geeksforgeeks.org/check-given-sentence-given-set-simple-grammer-rules/
15982. Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array: Keep track of prev_zero and prev_prev_zero indices: http://www.geeksforgeeks.org/find-index-0-replaced-1-get-longest-continuous-sequence-1s-binary-array/
15993. Given pair-sum array (pair[]) of an array A. Construct A from pair.
1600Example: A = {6, 8, 3, 4} --> pair = {14, 9, 10, 11, 12 ,7}
1601Working a few examples:
1602pair[0] = A[0] + A[1] = 14
1603pair[1] = A[0] + A[2] = 9
1604pair[2] = A[0] + A[3] = 10
1605pair[3] = A[1] + A[2] = 11
1606pair[4] = A[1] + A[3] = 12
1607pair[5] = A[2] + A[3] = 7
1608
1609Notice that A[0] = (pair[0] + pair[1] - pair[n-1]) / 2 = (A[0] + A[1] + A[0] + A[2] - A[1] - A[2]) / 2 = (14 + 9 - 11) / 2 = 12 / 2 = 6.
1610You can compute all other values in the array like this:
1611for (int i=1; i<n; i++)
1612 arr[i] = pair[i-1]-arr[0];
1613
1614- Find the smallest positive number missing from an unsorted array: Use index i to mark if element i was found or not, then reiterate over the array and find the first unmarked element.
1615- Find top k frequent elements. Can use bucket sort to solve in O(n) time and O(n) space.
1616---------------------------
1617Design Problems:
1618
16191. Design LRU cache with a limited capacity.
1620Solution: Use a hash table<pageNumber, CacheEntry*> and a linked list<CacheEntry>. A CacheEntry is a node in a Linked List with {next, prev, pageNumber, data}. See my own implementation LRU.cpp.
16212. Design LFU cache with a limited capacity
1622Solution: Instead of using a linked list, use a min-heap for sorting CacheEntry elements. Operations are O(lg(Capacity)).
16233. Design a FIFO queue that allows only unique elements and has O(1) operations.
1624Solution: Try a normal queue with a hashtable.
16254. Design a short URL system:
1626Solution: You need a bijective function. Assume that your short URL will constitute of characters [a-zA-Z0-9] (64 distinct chars)
1627 1. Store the long URL in the DB and get x = its auto-generated ID.
1628 2. Y = Convert x to its 64-base equivalent number + (int)'a'
1629 3. Your short URL is www.shorturl/Y
1630When doing a lookup you do the following:
1631 1. X = (Y - (int)'a') converted to base 10 number
1632 2. Lookup the URL in the DB with ID = X.
1633 3. Redirect.
16345. How would you design a spell checker?
1635Solution:
1636 1. Have a dictionary of all words
1637 2. let d(x,y) is the edit distance between two words x and y. You can add transposition to edit distance (i.e. the distance between cat and act = 1).
1638 3. Given a word x, generate all words that have distance <= k from x. Look up all these words in a dictionary, those found in the dictionary are candidates to replace x.
1639 Note: Other more complex algortihms exist.
16406. How would you design an auto-complete system?
1641Use a Trie data structure. Assuming that the use types "ca" in the text box, we traverse the path in the trie that starts from c --> then to a --> Then we do a DFS to find all words that start with "ca".
1642---------------------------
1643OOP:
1644
1645Encapsulation: Encapsulation is the packing of data and functions into a single component. The features of encapsulation are supported using classes.
1646Polymorephism: polymorphism is the provision of a single interface to entities of different types. A polymorphic type is a type whose operations can also be applied to values of some other type, or types
1647Data Abstraction: ADTs are defined by their meanings (semantics), while hiding away the details of how they work. In other words, separating interface from implementation.
1648
1649---------------------------
1650Math & Geometry:
1651Cross product of two directed line segments [(0,0),(x1,y1)] and [(0,0),(x2,y2)] = p1 x p2 = det(p1, p2) = x1y2 - x2y1.
1652
16531. How to determine whether a line directed line segment (p0,p1) is closer to another directed line segment (p0,p2) in clockwise or counterclockwise direction?
1654Solution O(1):
1655 A. Transolate p0 as the origin so that p1' = p1 - p0 and p2' = p2 - p0.
1656 B. Compute the cross product z = p1' x p2' = (x1 - x0)(y2 - y0) - (x2 - x0)(y1 - y0)
1657 C. We have three cases: If z > 0 then (p0,p1) is clockwise from (p0,p2), else if z < 0 then (p0,p1) is counterclockwise from (p0,p2), else if z==0, then both segments are colinear.
16582. Determine if two consecutive line segments (p0,p1) and (p1,p2) turn left (counterclockwise) or right (clockwise).
1659Solution: We use the technique as in the previous question:
1660 A. Compute z = (p2 - p0) x (p1 - p0)
1661 B. If z > 0 then clockwise, else counterclockwise.
16623. Find out if two lines intersect:
1663Solution: If the two lines have different slopes (not parallel) then they will intersect somewhere.
16644. Find out if two line segments intersect:
1665Solution 1: This solution is very sensitive to the precision of the division operation and is therefore not very accurate.
1666Find the point of intersection of the two lines:
1667 A. find the equations of the two lines in the form y1 = f1(x), y2 = f2(x)
1668 B. If slope1 = slope2 then: generally return false (but to be more accurate these line segments might be the same, or might be partially the same).
1669 C. To find y intersection, plug the x we found in step B in any of the two equations.
1670 D. Return true if and only if both x and y are in the ranges of the two lines.
1671Solution 2: Look at page 1018 of Introduction to Algorithms.
16725. Determine if **any** of n given line segments intersect:
1673Solution 1: O(n^2): Run the algorithm above for n*(n-1) segments and return the first intersecting line segments pair.
1674Solution 2 O(nlgn): Assumes no vertical segments. See Page 1025.
1675Note: You need to run Solution 1 if you need to determine **all** intersecting pairs. Solution 2 gives only a pair of intersecting line segments, if they exist.
16766. Given n points in a plane, find the two closest points
1677Solution 1: Compute distances between all n(n-1) point pairs, return the closest. O(n^2)
1678Solution 2 O(nlgn): see page 349 of EPI.
16797. Given a function foo() that generate a uniform random number from 1 to 5, write a function that generates a random number from 1 to 7 with equal probability:
1680Solution:
1681int my_rand() {// returns 1 to 7 with equal probability
1682 int i;
1683 i = 5*foo() + foo() - 5; //random number between [1,25] with uniform probability
1684 if (i < 22)
1685 return i%7 + 1;
1686 return my_rand(); //just try again.
1687}
16887. Devise a space-and-time efficient algorithm to compute the binomial coefficient C(n, k).
1689Solution O(k) time and O(1) space:
1690C(n, k) = n!/((n-k)!k!) = [n * (n-1) *... * (n-k-1)]/k!
1691Also note that C(n, k) = C(n, n-k)
1692unsigned binomial(n, k) {
1693 int res = 1;
1694 if(n - k < k)
1695 k = n - k;
1696 for(int i = 0; i < k; ++i) {
1697 res *= n-i;
1698 res /= i + 1;
1699 }
1700 return res;
1701}
17028. Write a program to print all prime factors of a given number n
1703Solution: Note that all the printed numbers are prime despite that we did not explicitly get a list of prime numbers < sqrt(n), this is because prime factors are always smaller and therefore visited by the loop before.
1704void primeFactors(int n) {
1705 for (int i = 2; i <= sqrt(n); i = i++)
1706 {
1707 // While i divides n, print i and divide n
1708 while (n%i == 0)
1709 {
1710 cout << i << " ";
1711 n = n/i;
1712 }
1713 }
1714 if (n > 2) // This condition is to handle the case whien n is a prime number greater than 2
1715 cout << n;
1716}
17179. Generate magic square matrix of size n by n:
1718Solution: 1 goes into (i,j)= (n/2,n-1). Now the next numbers (2, 3, 4, ...) go into column ((i+1)%n, (j-1)%n).
171910. Given a number n of k digits, find the next palindrom number:
1720Solution: 3 cases:
1721a. n is all 9s, return a number with k+1 digits with first and last digits as 1, and all other digits as 0. Eg: 999 --> 1001.
1722b. otherwise: mirror first half into second. while(n2 < n) {increment middle digits, and move the carry} Eg. 12923 --> 12921 --> 12(10)21 --> 13031.
172311. Given a number n, return true iff it is a Fibonacci number: A number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 – 4) is a perfect square
172412. Multiply two numbers without using the * operator:
1725 int res = 0; // initialize result
1726 while (b > 0)
1727 {
1728 if (b & 1)
1729 res = res + a;
1730 a = a << 1;
1731 b = b >> 1;
1732 }
1733 return res;
173413. Given a polynomial cnx^n + ... + c1x + c0, represented by an array c[n+1], and a value a for x. Evaluate the polynomial for x=a.
1735Solution O(n): Horner's method. Notice that the polynomial can be rewritten as (((cnx + cn-1)x + cn-2)x + ...)
1736int result = c[0]; //c[0] = cn
1737for(int i = 1; i < n+1; i++)
1738 result = result * x + c[i];
173914. Given a number n, count the number of trailing zeros in n!
1740Solution:
1741Idea 1: All trailing zeros come from the prime factors 2 and 5, so we need to find the number of primes 2s and 5s for all numbers in the range (2..n) that are multiplied together to result in a trailing zeros
1742Idea 2: Number of 5s is always <= number of 2s, so we only need to count the number of 5s.
1743 int count = 0;
1744 for (int i=5; n/i>=1; i *= 5)
1745 count += n/i;
174615. Catalan numbers have many applications such as:
1747- Count the number of expressions containing n pairs of parentheses which are correctly matched.
1748- Count the number of possible Binary Search Trees with n keys.
1749- Count the number of full binary trees with n + 1 keys.
1750Computing Catalan numbers:
1751C[0] = 1
1752C[n+1] = for all k [0..n]: sum(C[k]*C[n-k])
1753C[n] = (2n)! / (n+1)!n!
175416. Finding GCD using Euler's method is very easy:
1755Suppose we wish to compute
1756gcd(27,33). First, we divide the bigger one by the smaller one:
175733=1×27+6, Thus gcd(33,27)=gcd(27,6). Repeating this trick: 27=4×6+3 and we see gcd(27,6)= gcd(6,3). Lastly ,6=2×3+0, So since 6 is a perfect multiple of 3, gcd(6,3)=3, and we have found that gcd(33,27)=3.
1758---------------------------
1759Misc:
1760
17611. Longest non-decreasing subarray (differet from subsequence): Given an array A, find the longest subarray A[i..j] whose elements are non-decreasing
1762Solution: The idea is trivial. Start from i=0 and count how many elements are non-decreasing, stop when v[i+1] < v[i]. Start again at v[i+1] and count again, get the max length as you go.
17632. Keep track of a random sample of k elements of a very long stream of numbers. The stream is of infinite length.
1764Solution: Reservoir sampling, as follows:
1765 A. Base case: store the 1st k [0..k-1] elements in the random array A.
1766 B. For the ith element in the stream, we need to select that element with a probability of k/i, so generate a random number r = [0,i] (inclusive of both ends).
1767 C. if r < k, replace A[r] with A[i].
1768 D. Repeat steps B-D.
17693. Given a team of N players. How many minimum games are required to find second best player?
1770Solution: N + lg2(n) - 2. How??
1771
1772---------------------------
1773Concurrency:
1774
17751. Dining philosophers:
1776Solution: The naiive solution leads to a deadlock. To avoid deadlock, make an ordering on resources such that a philosopher must acquire R1 before R2. This can lead to starvation of some philosophers.
1777
1778---------------------------
1779Operating Systems:
1780
1781More concepts:
1782- A semaphore S is an integer variable that can be accessed only through two standard operations : wait() and signal().
1783- There are two types of semaphores: counting semaphores and binary semaphores.
1784
17851. Explain Belady's anomaly.
1786Answer: increasing the # of allocated frames to a process increases the # of page faults.
17872. What is thrashing?
1788When the processor spends most of its time swapping pages rather than doing real processing.
17893. What are the 4 conditions for a deadlock?
1790Mutual exclusion, hold and wait, circular wait, non-preemption
17914. What are the 4 elements of a process image?
1792User code, user data, stack(s), PCB.
17935. What is the TLB?
1794Contains the most recently used page table entries
17956. When is a system in a safe state?
1796When there is at least one way of execution that does not lead to a dead lock.
17977. What is cycle stealing?
1798When a DMA controller forces the CPU to suspend an operation in order to be able to use the data bus.
17998. What is load sharing?
1800When processes are not assigned to particular processors so there is a global process queue that all processes share.
18019. For disks, what is rotational delay, seek time, and transfer time?
180210. What is a monitor:
1803An object that implements mutual exclusion by itself (like a thread-safe object). So it allows safe multi-threaded access to its clients.
180411. What are the disadvantages of thread locks?
1805Blocking, more overhead, priority inversion, if a thread holding the lock dies other threads get stuck, difficult to debug.
180612. What is a spinlock and when is it used?
1807A spinlock is a lock that requires the thread trying to acquire it to wait in a loop (busy waiting).
1808Can be used when locks are held for a very short time, as they avoid context switches.
180913. What synchronization primitives are used in multi-processor / multi-core systems?
1810Spinlocks are the simplest. Others are Queued locks and Ticket spin locks
181114. What is the difference between a binary semaphore and a mutex?
1812A mutex supports ownership, which means only the process that has the lock can unlock it. This is not true for binary semaphores.
1813A mutex is used to protect shared resources (mutual exclusion). A semaphore is used to make a process wait for something to happen.
1814A mutex is valid within a process (can't use inter-process mutex), whereas a semaphore can be used by different processes
181515. Describe Peterson's algorithm of mutual exclusion
1816bool flag[0] = false;
1817bool flag[1] = false;
1818int turn;
1819 Process 0 Process 1
1820------------------------------ ------------------------------
1821P0: flag[0] = true; P1: flag[1] = true;
1822P0_gate: turn = 1; P1_gate: turn = 0;
1823while (flag[1] && turn == 1) while (flag[0] && turn == 0)
1824{ {
1825 // busy wait //busy wait
1826} }
1827// critical section //critical section
1828... ...
1829// end of critical section // end of critical section
1830flag[0] = false; flag[1] = false
1831
1832---------------------------
1833Testing:
1834
1835When testing something we need to consider the following:
18361. What are the specific use cases of the object to test? Try to explicitly make a list and then ask the interviewer if there are any other functionalities/uses to consider.
18372. Test the object for each functionality/use case. If it fails, does it fail gracefully?
18383. What are the expectations of this object if it was used outside the use cases it was meant for? Does it give wrong behavior, throw exceptions, have minimum usefulness, etc?
18394. What stress conditions this object can be used in? low memory, low bandwidth, etc.
1840
1841---------------------------
1842Database & SQL:
1843
18441. Write SQL query to print department names and their employee count
1845Solution: use left join so that departments with 0 employees will be printed as well.
1846Select DName, count(*) as 'num_emps' FROM Dept left join Emp ON Dept.did = Emp.did Group by Dept_Name
18472. Explain what database de-normalization is.
1848Solution: Cracking the Coding Interview page 234.
18493. Find the employee with the nth largest salary:
1850SELECT *
1851FROM Employee Emp1
1852WHERE (N-1) = (
1853SELECT COUNT(DISTINCT(Emp2.Salary))
1854FROM Employee Emp2
1855WHERE Emp2.Salary > Emp1.Salary)
1856
1857The above query looks for the employee whose salary is less than n-1 other employees, that is, the nth largest.
18584. What are join types?
1859 1. Inner Join
1860 2. Outer Join: 3 types
1861 A. Left outer join
1862 B. Right outer join
1863 C. Full outer join
1864
1865---------------------------
1866General and Behavioral Questions:
18671. Tell Me About Your Experience
18682. Why do you want this job?
18693. Why did you choose this company?
18704. What is your favorite programmming language?
18715. What are your career goals?
18726. Give examples of difficult problems you faced.
1873Qualcomm's compilation. Buffered Reader performance.
1874- Tell me about a time when you overcame a challenge in the workplace
1875- How have you improved a certain process at work?
1876- Why Google?
1877- Tell me about a time when you spoke with a dissatisfied client and what did you do to appease them?
1878- Name 3 advantages of AdWords
1879- Have you ever improved the efficiency of a process/task at work?
1880
1881----------------------------
1882Misc Data Structure:
1883
18841. Trie
1885struct trie_node {
1886 bool isLeaf; /* Used to mark leaf nodes */
1887 struct trie_node *children[ALPHABET_SIZE];
1888};
1889
1890struct trie {
1891 struct trie_node *root;
1892 int count; //count of all keys in the trie
1893};
1894
1895- Insert key in trie:
1896void insert(struct TrieNode *root, const char *key)
1897{
1898 int level;
1899 int length = strlen(key);
1900 int index;
1901
1902 struct TrieNode *pCrawl = root;
1903
1904 for (level = 0; level < length; level++)
1905 {
1906 index = CHAR_TO_INDEX(key[level]);
1907 if (!pCrawl->children[index])
1908 pCrawl->children[index] = getNode();
1909
1910 pCrawl = pCrawl->children[index];
1911 }
1912
1913 // mark last node as leaf
1914 pCrawl->isLeaf = true;
1915}
1916
1917- Search a trie:
1918bool search(struct TrieNode *root, const char *key)
1919{
1920 int level;
1921 int length = strlen(key);
1922 int index;
1923 struct TrieNode *pCrawl = root;
1924
1925 for (level = 0; level < length; level++)
1926 {
1927 index = CHAR_TO_INDEX(key[level]);
1928
1929 if (!pCrawl->children[index])
1930 return false;
1931
1932 pCrawl = pCrawl->children[index];
1933 }
1934
1935 return (pCrawl != NULL && pCrawl->isLeaf);
1936}
1937
1938- Delete a key from a trie:
1939During delete operation we delete the key in bottom up manner using recursion. The following are possible conditions when deleting key from trie,
1940A. Key may not be there in trie. Delete operation should not modify trie.
1941B. Key present as unique key (no part of key contains another key (prefix), nor the key itself is prefix of another key in trie). Delete all the nodes.
1942C. Key is prefix key of another long key in trie. Unmark the leaf node.
1943D. Key present in trie, having atleast one other key as prefix key. Delete nodes from end of key until first leaf node of longest prefix key.
1944
1945Questions:
1946 1. Find the k most frequent words from a file: Use a trie and a min heap. Or you can use hashing.
1947
19482. Skip Lists: Skip lists are composed of multiple (typically, two) layers of linked lists. The upper linked list contains fewer elements and is called the express line.
19491 <-------------------------------->10<---------------------------->34
1950| | |
19511 <--> 2 <--> 4 <--> 7 <--> 9 <--> 10 <--> 18 <--> 23 <--> 30 <--> 34
1952- The optimal number of nodes in the express line is O(sqrt(n)), and the number of nodes between each two consecutive upper list nodes is also sqrt(n), where n is the number of nodes in the bottom linked list.
1953- Time complexity of search is: number of nodes in express list + number of nodes between each two consecutive nodes in express list = sqrt(n) + sqrt(n) = O(sqrt(n)).
1954
1955
19565. Given a 2D array of boolean values, print rows such that repeated rows are printed only once
1957Solution:
1958 1. Print first row, create a trie structure from that row
1959 2. For each of the remaining rows, check to see if the row is in the trie, if it doesn't exist then print it and add it to the trie, else ignore it.
1960
19616. Interval tree: Is a tree that is augmented to hold intervals. This tree can do search, insert interval, remove interval in O(logn): http://www.geeksforgeeks.org/interval-tree/
1962
1963----------------------------
1964Linux Commands:
1965
19661. How to replace a pattern in files:
1967grep "mypattern" | xargs sed -i "s/string1/string2/g"
1968-----------------------------------------------------------------
1969Multi-threaded programming in C#:
1970
1971- Creating a new thread: You can create a thread in two ways:
1972 - an anonymous function:
1973 Thread t3 = new Thread(p =>
1974 {Console.WriteLine(p));
1975 t3.Start(20);
1976 - A method:
1977 public static void DoWork(object data) {...}
1978 newThread = new Thread(w.DoWork);
1979 newThread.Start("The answer.");
1980
1981- Terminating a thread: thread.Abort();
1982- Waiting for a tread to finish: thread.Join();
1983
1984Thread synchronization:
19851. Locks (or ciritical sections): we use the lock keyword on any object:
1986Object lockObj = new Object();
1987lock(lockObj)
1988{
1989//critical section
1990}
19912. Synchronization Events and Wait Handles
1992- There are two kinds of synchronization events: AutoResetEvent, and ManualResetEvent. They differ only in that AutoResetEvent changes from signaled to unsignaled automatically any time it activates a thread. Conversely, a ManualResetEvent allows any number of threads to be activated by its signaled state, and will only revert to an unsignaled state when its Reset method is called.
1993- Threads can be made to wait on events by calling one of the wait methods, such as WaitOne, WaitAny, or WaitAll. WaitAny(WaitHandle[]) and WaitAll(WaitHandle[]) are static methods of WaitHandle class, which is the base class of AutoResetEvent and ManualResetEvent.
1994
1995Example:
1996autoEvent = new AutoResetEvent(false);
1997static void Main()
1998{
1999 Console.WriteLine("main thread starting worker thread...");
2000 Thread t = new Thread(DoWork);
2001 t.Start();
2002 autoEvent.Set();
2003}
2004
2005static void DoWork()
2006{
2007 Console.WriteLine(" worker thread started, now waiting on event...");
2008 autoEvent.WaitOne();
2009 Console.WriteLine(" worker thread reactivated, now exiting...");
2010}
2011
2012Mutex object:
2013- A mutex is similar to a monitor; it prevents the simultaneous execution of a block of code by more than one thread at a time. Unlike monitors, however, a mutex can be used to synchronize threads across processes.
2014- It is a wrapper of Win32 constructs.
2015- Computationally more intensive, because of the need to InterOp with System calls. Monitors (lock calls) are better for intra process synchronization becaues they were designed for .NET with lower overhead.
2016Mutex mut = new Mutex();
2017mut.WaitOne();
2018//some work
2019mut.ReleaseMutex();
2020
2021Interlocked class: You can use the methods of the Interlocked class to prevent problems that can occur when multiple threads attempt to simultaneously update or compare the same value. The methods of this class let you safely increment, decrement, exchange, and compare values from any thread.
2022- Add(Int32, Int32): Adds two 32-bit integers and replaces the first integer with the sum, as an atomic operation.
2023- CompareExchange(Int32, Int32, Int32): Compares two 32-bit signed integers for equality and, if they are equal, replaces the first value.
2024- Decrement(Int32): Decrements a specified variable and stores the result, as an atomic operation.
2025- Exchange(Int32, Int32): Sets a 32-bit signed integer to a specified value and returns the original value, as an atomic operation.
2026- Increment(Int32): Increments a specified variable and stores the result, as an atomic operation.
2027
2028Concurrency problems:
2029- Priority Inversion: L is running in Critical Section CS; H also needs to run in CS; H waits for L to come out of CS ; M interrupts L and starts running ; M runs till completion and relinquishes control ; L resumes and starts running till the end of CS ; H enters CS and starts running. Note that neither L nor H share CS with M. Here, we can see that running of M has delayed the running of both L and H. Precisely speaking, H is of higher priority and doesn’t share CS with M; but H had to wait for M.
2030
2031- Sleeping barber problem: here is a barber shop which has one barber, one barber chair, and n chairs for waiting for customers if there are any to sit on the chair.
2032 - If there is no customer, then the barber sleeps in his own chair.
2033 - When a customer arrives, he has to wake up the barber.
2034 - If there are many customers and the barber is cutting a customer’s hair, then the remaining customers either wait if there are empty chairs in the waiting room or they leave if no chairs are empty.
2035Semaphore Customers = 0;
2036Semaphore Barber = 0;
2037Mutex Seats = 1;
2038int FreeSeats = N;
2039
2040Barber {
2041 while(true) {
2042 down(Customers); /* waits for a customer (sleeps). */
2043 down(Seats); /* mutex to protect the number of available seats.*/
2044 FreeSeats++; /* a chair gets free.*/
2045 up(Barber); /* bring customer for haircut.*/
2046 up(Seats); /* release the mutex on the chair.*/
2047 CutHair(); /* barber is cutting hair.*/
2048 }
2049}
2050
2051Customer {
2052 while(true) {
2053 down(Seats); /* protects seats so only 1 customer tries to sit in a chair if that's the case.*/
2054 if(FreeSeats > 0) {
2055 FreeSeats--; /* sitting down.*/
2056 up(Customers); /* notify the barber. */
2057 up(Seats); /* release the lock */
2058 down(Barber); /* wait in the waiting room if barber is busy. */
2059 // customer is having hair cut
2060 } else {
2061 up(Seats); /* release the lock */
2062 // customer leaves
2063 }
2064 }
2065}
2066
2067- Readers-writer problem:
2068Writer:
2069do {
2070 wait(wrt); // writer requests for critical section
2071 // performs the write
2072 signal(wrt); // leaves the critical section
2073} while(true);
2074
2075Readers:
2076do {
2077 wait(mutex); // Reader wants to enter the critical section
2078 readcnt++; // The number of readers has now increased by 1
2079 // there is atleast one reader in the critical section, this ensure no writer can enter if there is even one reader, thus we give preference to readers here
2080 if (readcnt==1)
2081 wait(wrt);
2082 // other readers can enter while this current reader is inside the critical section
2083 signal(mutex);
2084 // current reader performs reading here
2085 wait(mutex); // a reader wants to leave
2086 readcnt--;
2087 // that is, no reader is left in the critical section,
2088 if (readcnt == 0)
2089 signal(wrt); // writers can enter
2090 signal(mutex); // reader leaves
2091
2092} while(true);
2093
2094- Producer-Consumer problem: We have a buffer of fixed size. A producer can produce an item and can place in the buffer. A consumer can pick items and can consume them. We need to ensure that when a producer is placing an item in the buffer, then at the same time consumer should not consume any item. In this problem, buffer is the critical section.
2095
2096Producer:
2097do{
2098//produce an item
2099wait(empty);
2100wait(mutex);
2101//place in buffer
2102signal(mutex);
2103signal(full);
2104}while(true);
2105
2106Consumer:
2107
2108do{
2109wait(full);
2110wait(mutex);
2111// remove item from buffer
2112signal(mutex);
2113signal(empty);
2114// consumes item
2115}while(true)
2116
2117Sempaphores:
2118Semaphore threadPool = new Semaphore(3, 5);