· 7 years ago · Feb 06, 2019, 07:42 AM
1Common design patterns: Observer, Monitor, Visitor, Singleton, Adapter, Decorator
2
31. Kadane's algorithm for the maximum subarray: DONE
42. Maximum submatrix: Revise https://www.youtube.com/watch?v=yCQN096CwWM
53. longest non-decreasing subsequence.
64. Compute the power set. Use a counter and then check for individual bits if they are set or not.
75. Implement a hash table: DONE
86. How to implement a hash function: Revise
97. Why do you want to work at Google?: Revise
108. What are hard problems that you faced?: Revise
119. Rotating an array: DONE
1210. Finding median, kth smalles/largest number in O(n) time: DONE
1311. String search algorithms
14 A. Rabin Karp (See my own implementation in cpp)
15 B. KMP
16 C. Boyer Moore
1712. Longest common subsequence: DONE
1813. In-order traversal with O(1) space. See EPI 9.5: DONE
1914. Longest non-decreasing subarray (differet from subsequence): DONE
2015. Sequence alignment in algorithms design book section 6.6
2116. Segmented least square in algorithms design book section 6.3
2217. Search for "most common greedy", "most common DP algorithms", etc.
2318. MRU, LRU cache: DONE
2419. Write functions that print all permutations of chars in a string. Do another algorithm for combinations: DONE
2520. Rubikee Cube algorithm
2621. External sort: DONE
2722. SQL interview Questions
2823. Java Interview Questions
2924. Python Interview Questions
3025. Algorithms Design Book.
3126. LFU cache: DONE
3227. Queue with unique elements: DONE
3328. Distributed systems interview questions.
3429. Skip lists: DONE
3530. Bit manipulation tricks: DONE
3631. Geometric algorithms: DONE
3732. Given System X of Google/Microsoft/etc, how would you evolve it.
3833. Regular expressions
3934. String operations interview questions.
4035. Update/Delete from BST, rotations Revise
4136. Red-Black Trees.
4237. Suffix trees: http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/ : Revise
4338. C++ Standard Library vs STL Revise
4439. Online hiring problem: Introduction to algorithms p139
4540. Backtracking solutions in Dynamic programming algorithms.
4641. Towers of Hanoi DONE
4742. Distributed Hash Table
4843. Min-Max Heap and its applications on wikipedia
4944. Solve maze using recursion. Get optimal path. DONE
5045. String matching homework questions.
5146. Clock synchronization in a distributed system
5247. 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.
5348. Trie data structure.
5449. Multi-dimensional BSTs (such as Quad-trees, k-d trees).
5550. Write a program to make a deep copy of a graph.
5651. Super recursion
5752. Bloom filter
5853. Agile/Scrum
5954. Screws and bolts
6055. Combinations of size k out of n.
6156. Rotate mxn array.
62
63Definitions:
64Anagrams: 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.
65Palindrome: A word that reads the same forwards or backwords like mom, dad, deed.
66Powerset: all possible subsets, # of sets in a powerset = 2^n
67Permutations: 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}.
68Combinations: 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}.
69
70---------------------------
71Tips:
721. Whenever you are asked about uniqueness, consider hash tables, or sets
732. Whenever you are asked about maximum or minimum or "optimal", consider Dynamic Programming and Greedy Algorithms.
743. Consider augmenting the data structure. Some problems will require that, and others will have performance benefits.
754. When writing dynamic programming algorithms, remember to include the memorization part, not only the recursion. Recursion-only solution can still be exponential in time.
765. Whenever you see something like k-smallest or k-largest, consider using a heap.
776. Most important interview tips:
78 A. Think loud
79 B. Corner and base cases
80 C. Verify and test using many inputs before you show your work
81 - For strings and chars: test null, empty string, capital, small, numeric, etc.
82 - For numbers: test positive, negative, zero.
83 - For boundaries: check empty array, array start, array end, etc.
84 D. If stuck, try another approach.
85 E. Most Important: TAKE YOUR TIME. CORRECTNESS IS VITAL
867. Algorithms tips:
87 A. Make sure you fully understand the problem (inputs, outputs, desired behavior or transformation).
88 B. WRITE down and draw some examples that you will use later for testing.
89 C. Try to come up with a brute-force or a simple solution. Make sure it is right
90 D. Think about how to optimize by thinking in **datastructures and algorithms**:
91 1. What data structures would make your task easier or more efficient
92 2. What techiques can result in an improved algorithm? Divide and conquer, greedy algorithm, dynamic programming, sorting, recursion, graph algorithms?
93 E. Make sure that your optimized solution works by trying it on multiple input. Modify as necessary
94 F. Identify base cases and corner cases.
95 G. Code it up.
96 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!
97 I. what is the asymptotic complexity of your algorithm?
98 J. Paste your code into a compiler and see if it works. Learn from your mistakes.
998. Coding Tips:
100 A. Write clean and correct code, with very clear handwriting.
101 B. Use meaningful function and variable names.
102 C. Explain your code as you write it.
103 D. Be modular, try to decompose your code into functions.
104 E. Delay the implementation of your helper functions, but define the helper functions signatures. Implement the main algorithm first.
105 F. Use libraries when appropriate. For example, call sort() STL function instead of writing your own sort() function.
106 G. Use whiteboard space wisely, use multiple columns.
107 H. Testing:
108 - Test your code that is on the whiteboard, not your algorithm.
109 - Use multiple small test examples, all edge cases, and one big example.
1109. Other tips:
111 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.
112 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.
113
114---------------------------
115Problems to revise:
116EPI: 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
117
118---------------------------
119Sets, Permutations and Combinations:
1201. 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)
121Solution: 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
122template<class T> void PowerSet(vector<T> pre, vector<T> v) {
123 if(v.size() == 0) {
124 for(int j = 0; j < pre.size(); j++)
125 cout << pre[j];
126 cout << "\n";
127 return;
128 }
129 PowerSet(pre, vector<T>(v.begin() + 1, v.end()));
130 vector<T> pre2(pre.begin(), pre.end());
131 pre2.push_back(v[0]);
132 PowerSet(pre2, vector<T>(v.begin() + 1, v.end()));
133}
1342. Write a function that prints all permutations of a vector.
135Solution: 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).
136template<class T>
137vector<vector<T> > permutations(vector<T> v) {
138 vector<vector<T> > result;
139 if(v.size() == 0) {
140 result.push_back(vector<T>());
141 return result;
142 }
143
144 vector<vector<T> > partial = permutations(vector<T>(v.begin() + 1, v.end()));
145 for(int i = 0; i < v.size(); i++) {
146 for(int j = 0; j < partial.size(); ++j) {
147 vector<T> tmp(partial[j]);
148 tmp.insert(tmp.begin() + i, v[0]);
149 result.push_back(tmp);
150 }
151 }
152
153 return result;
154}
155
1563. Combinations (n, k)
157void combinations_helper(vector<T> &v, int i, int r, set<T> data, vector<set<T> > &result) {
158 if(data.size() == r) {
159 result.push_back(data);
160 return;
161 }
162
163 if(i >= v.size())
164 return;
165
166 combinations_helper(v, i+1, r, data, result);
167
168 data.insert(v[i]);
169 combinations_helper(v, i+1, r, data, result);
170}
171
172template <class T>
173void combinations(vector<T> &v, int r, vector<set<T> > &result) {
174 set<T> data;
175 combinations_helper(v, 0, r, data, result);
176}
1774. Print all combinations of balanced parantheses of size n: The number of those is nth catalan number (assuming n is even, 0 otherwise).
178
179void printParenthesis(int n)
180{
181 if(n > 0)
182 _printParenthesis(0, n, 0, 0);
183 return;
184}
185void _printParenthesis(int pos, int n, int open, int close)
186{
187 static char str[MAX_SIZE];
188 if(close == n)
189 {
190 printf("%s \n", str);
191 return;
192 }
193 else
194 {
195 if(open > close) {
196 str[pos] = '}';
197 _printParenthesis(pos+1, n, open, close+1);
198 }
199 if(open < n) {
200 str[pos] = '{';
201 _printParenthesis(pos+1, n, open+1, close);
202 }
203 }
204}
205
2065. 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).
207Solution: O(n)
208vector<int> next_permutation(vector<int> v) {
209 int k = v.size() - 2;
210 while(k >= 0 && v[k] > v[k+1]) { // find the greatest k such that v[k] < v[k+1]
211 --k;
212 }
213 if(k < 0)
214 return vector<int>(); //this was the greatest permutation, so next one is empty
215 int l;
216 for(int i = k+1; i < v.size(); ++i) { //find the greatest l such that v[l] > v[k]
217 if(v[i] > v[k])
218 l = i;
219 else
220 break;
221 }
222 swap(v[l], v[k]);
223 reverse(v.begin() + k + 1, v.end());
224 return v;
225}
226
2276. How to rotate an array by k elements, using only O(1) additional storage:
228Solution: O(n)
229void rotate(const vector<T> &v, int k) {
230 k = k % v.size();
231 reverse(v.begin(), v.end());
232 reverse(v.begin(), v.begin() + k);
233 reverse(v.begin() + k, v.end());
234}
235
2367. 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.
237Solution:
2381. Reverse BCD: A D C B E F G
2392. Reverse EF: A D C B F E G
2403. Reverse BCDEF A E F B C D G
241
242---------------------------
243Bit manipulation:
244- Logical shift: shifts all bits including the MSB of signed numbers. You can achieve this effect by casting to (unsigned).
245- Arithmetic shift: shifts all bits except the MSB of signed numbers. The sign bit is shifted to next bit.
2461. Swap two numbers x & y without a temporary
247Solution 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.
248Solution 2: x = y - x, y = y - x, x = x + y.
2492. 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:
250Solution: find the first two consecutive bits that differ and swap them.
2513. How to check if an integer x is a power of 2?
252Solution: v && !(v & (v - 1))
2534. Write a function to determine whether a machine is big-endian or little endian:
254#define BIG_ENDIAN 0
255#define LITTLE_ENDIAN 1
256int TestByteOrder() {
257 short int word = 0x0001;
258 char *byte = (char *) &word;
259 return (byte[0] ? LITTLE_ENDIAN : BIG_ENDIAN);
260}
2615. Given two numbers a, b. Write a max and min functions without comparison operators:
262max:
263 c = a - b;
264 k = (c >> 31) & 0x1; //k=1 iff b>a
265 return a - k*c;
266min:
267 return y ^ ((x ^ y) & - (x < y));
268
2696. Write a function to add two numbers without using +.
270Solution: 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
271int add_no_arithm(int a, int b) {
272 if (b == 0) return a;
273 int sum = a ^ b; // add without carrying
274 int carry = (a & b) << 1; // carry, but don’t add
275 return add_no_arithm(sum, carry); // recurse
276}
2777. How to round up to the next power of 2?
278Solution: Assuming 32-bit integer n:
279--n;
280n |= n >> 1;
281n |= n >> 2;
282n |= n >> 4;
283n |= n >> 8;
284n |= n >> 16;
285++n;
2868. How to find the least significant bit that is set to 1 in a given integer x:
287Solution: x & (-x)
2889. How to count the number of 1s in an integer x?
289Solution 1:
290 for(r = 0; x != 0; ++r)
291 x &= (x - 1);
292Solution 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.
293Solution 3: There is also a faster divide and conquer method O(lgn)
2948. How to find out if two integers have opposite signs?
295Solution: (x ^ y) < 0
2969. How to compute absolute value of an integer without conditionals?
297int 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
298r = (v + mask) ^ mask;
29910. How to swap ith and jth bit in an integer?
300int swap(int num, int i, int j)
301{
302 int xor = ((num>>i) ^ (num>>j)) & 1; //xor=1 iff the two bits are different. Otherwise xor = 0.
303 return num ^ (xor<<i) ^ (xor<<j); //if xor==1 then flip ith and jth bits, otherwise do nothing.
304}
30511. How to reverse bits in an integer:
306Solution: O(lgn)
307unsigned int v; // 32-bit word to reverse bit order
308// swap odd and even bits
309v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
310// swap consecutive pairs
311v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
312// swap nibbles ...
313v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
314// swap bytes
315v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
316// swap 2-byte long pairs
317v = ( v >> 16 ) | ( v << 16);
318
31912. How to compute x % y, where y is a power of 2?
320result = x & (y-1)
32113. How to clear the least significant bit that is 1? This is useful when counting # of 1s.
322Solution:
323if(x)
324 x &= (x-1);
32514. How to multiply n by 7:
326Solution: (n << 3) - n. Or n + (n >> 1) + (n >> 2)
32715. How to rotate bits left or right
328Solution:
329int rotate_left(int n, int shift) {
330 int bits = sizeof(int) * 8;
331 shift %= bits;
332 return (n << shift) | (n >> (bits - shift));
333}
334int rotate_right(int n, int shift) {
335 int bits = sizeof(int) * 8;
336 shift %= bits;
337 return (n >> shift) | (n << (bits - shift));
338}
33916. 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
340Solution O(n):
341 1. XOR all elements in A with all elements in range(1,n). The result z = x ^ y. (In the example z= = 001).
342 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)
343 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).
344 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.
345 5. To find y, y = z ^ x. (In the example y = 001 ^ 101 = 100 = 4).
34617. An array of integers has all elements appearing 3 times except for one element, which appears only once. Find that element.
347Solution: http://www.programcreek.com/2014/03/leetcode-single-number-ii-java/
34818. 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).
34919. 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/
350Solution1 O(nLgn) - naiive: loop through all numbers i from 1 to n, then return sum(numOfSetBits(i)).
351Solution2 O(Lgn): recursively do the following:
352func CountBits(n)
353 m = LeftMostSetBitPos(n)
354 //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.
355 if n is in the form 2^b-1 (i.e. all consecutive 1s), then return (m+1)*(1<<m).
356 else: n = n - (1<<m); //set MSB off, to prepare for recursion
357 return m*(1<<(m-1)) // number of set bits in all numbers of bit-length m-1.
358 + (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.
359 + CountBits(n) //recursively run for one less bit.
36020. Given an array of N integers (N is large), compute the number of set bits in all numbers a[i].
361- Create a look up table for the number of bits for numbers of size one byte [0..255]
362sum = 0;
363for each number k in array
364 for each byte b in k: sum += lookupTable[b]
365
366---------------------------
367Back Tracking: Just remember how backtracking algorithms work, such as the maze problem.
368
3691. Knight tour
3702. Maze
3713. N queen problem
3724. Subset sum.
3735. m-coloring problem.
3746. Finding hamiltonian cycle.
3757. 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.
376
377---------------------------
378Linked Lists, Queues and Stacks
379
3801. How to find out if a linked list has a cycle?
381Solution: Use a fast and a slow pointer. The list has a cycle iff they meet before finding the tail of the array.
3822. If a linked list does have a cycle, how to find the length of the cycle?
383Starting 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.
3843. How to find the length of a linked list that has a cycle?
385Having 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.
386Next, 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.
3874. How to reverse a linked list:
388Solution O(n): loop through each node and make it point to the prev node, return the last node.
3895. How to print a linked list in reverse?
390void print_reverse(Node *n) {
391 if(n == NULL) return;
392 print_reverse(n->next);
393 cout << n->data << " ";
394}
3956. How to check if a linked list is a palindrome?
396Solution 1: Split the list in two halfs, reverse one half and compare the two halfs.
397Solution 2: Use a stack.
3987. Design a stack with min() function. All operations are O(1)
399Solution 1: always push a pair <element, cur_min>
400Solution 2: (More space-efficient). Use an auxiliary stack that stores only the minimums. Push and pop only when necessary.
4018. Design a space-efficient doubly linked list
402Solution: Let the pointer of each node = next_addr ^ prev_addr
403For example: A <--> B <--> C <--> D
404struct list {
405 T data;
406 struct list *ptr;
407}
408A->ptr = B ^ 0 = B
409B->ptr = A ^ C
410
411Traversal: 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:
412next(n, left_of_n) = n->ptr ^ left_of_n. For example: next(B, A) = B->ptr ^ A = A ^ C ^ A = C
4139. 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.
41410. How to select a random node in a linked list?
415Solution 1: Find length of the list, generate a number i from 0..n-1, traverse list again to node #i and return the node.
416Solution 2 (one pass): We use reservoir sampling (see Misc problems below for a better description) as for selecting a random element from a stream:
417- set result as node #0
418- init n = 2
419- For each next node, generate a number j from 0..n-1. if j==0, replace set result = cur_node.
42011. 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/
421- 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/
42212. Implement merge sort for linked lists: http://www.geeksforgeeks.org/merge-sort-for-doubly-linked-list/
423---------------------------
424Numbers:
4251. How to approximate PI?
426Solution: PI = 4/1 - 4/3 + 4/5 - 4/7 ...
4272. How to factor a natural number x to its prime components?
428Solution:
429 - Get a list of prime numbers from 1 to sqrt(x) + 1
430 - for each number p in the primes list: while(x % p == 0): add p to the factors, x = x / p.
431Note: many faster algorithms exist such as wheel factorization and Euler's method.
432
433---------------------------
434Heap: A complete binary tree that satisfies the heap property
435
436Tip: 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.
437
438Heap applications:
439Note: we can use priority_queue<T> in STL as a heap.
4401. Sort n sorted large files (or sequences) into a single file.
4412. Stack can be implemented using max_heap, queue using min heap.
4423. Sort k-increasing array.
4434. find k-smallest/largest elements in a large file. This can be also solved using a selection algorithm.
4445. Find kth largest element in a streaming input. (Use k-min heap).
4456. Sorting an approximately sorted array.
4467. 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.
447Note: Another solution is to use a self-balancing BST. The median will always be in the root (more or less).
4488. Tournament trees: http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
449---------------------------
450Searching:
451
4521. Find the first element in array A that is larger than k: k might not be in A.
453Solution: 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).
4542. (11.4) In an absolutely sorted array (eg: -50, 100, 150, -200). Find a pair of elements that sum up to x:
455Solution 1: Consider 3 separate cases, write a separate function for each case.
456 A. both are negative (have one pointer at each end of the array).
457 B. both are positive (have one pointer at each end of the array).
458 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.
459Solution 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.
4603. (11.5) search for smallest element in cyclicly sorted array.
461Idea: 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).
4624. Searching an array of unknown length: search for k in elements 0, 1, 2, 4,8,16,...
4635. 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.
4646. 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).
4657. Find missing element in array containing permutation [1 .. n]. n(n+1)/2 - sum(A) = missing element. Same logic for duplicate element.
466Solution 2: to find missing element, XOR all numbers [1..n] and XOR the result with all elements of A. The final result = missing element.
467O(lgn) solution: Use binary search if the array is sorted.
4688. 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?
469Solution: 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
4709. Given an array A of N elements. Find all array pairs that sum to Z. Generalize to find k elements that sum to Z.
471Solution:
472A. For k = 2.
473 1. Create a hash table with key=array element, value = # times element appears in A.
474 2. For each element e in A:
475 Compute e2 = Z - e
476 Look in the hash table and find out if e2 is there
477 if(e2 found)
478 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.
479 add element to list of pairs.
480 end if
481 end if
482B. For k >= 2:
483 if k is odd: O(n^((k+1)/2))
484 create a hash map of (k-1)/2 tuple sums.
485 For every (k+1)/2 tuple t of A
486 s = sum of tuple
487 D = Z - C
488 if(D is in hash table)
489 output elements of D union tuple t.
490 end if
491
492 if k is even: O(n^(k/2))
493 create a hash map of k/2 tuple sums.
494 For every k/2 tuple t of A
495 s = sum of tuple
496 D = Z - C
497 if(D is in hash table)
498 output elements of D union tuple t.
499 end if
50010. 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)
501Solution: O(N).
502 Build a hashmap of all the array elements <element, bool(visited=false)>.
503 longest = 1, count = 1
504 For each element e in A:
505 if e is visited then continue
506 i = e
507 while(true)
508 if element --i is in hashmap then count++ else break; (mark hashmap[i] = true)
509 i = e
510 while(true)
511 if element ++i is in hashmap then count++ else break; (mark hashmap[i] = true)
512 longest = max(longest, count);
513 count = 1;
514
515---------------------------
516Strings and Pattern Matching:
517
5181. 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.
519- 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)
520
521To match string s[0..n-1] and pattern p[0..m-1]:
522Build lps for p.
523while i < n
524 if s[i] == p[j]:
525 i++, j++
526 if j==m-1 print "Found match", j = lps[j-1]
527 else if i < n && s[i] != p[j]
528 if j > 0 j = lps[j-1] else i++;
529
530Function buildlps(p)
531 lps[0] = 0;
532 i = 1; len = 0;
533 while(i < m)
534 if p[i] == len
535 len++
536 lps[i] = len
537 i++
538 else
539 if len != 0 len = lps[len-1] else lps[i]=0, i++
540
5412. Given a string s and a pattern p, find all occurrences of all anagrams of p within s in O(n) time.
542Solution: 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.
543
544- Build a count array of alphabet size and store countPattern[c] for each char c in p.
545- Build a second count array countString and for first m chars in s, store countString[c].
546- 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.
547 - 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.
548---------------------------
549Suffix trees and suffix arrays:
550
5511. 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).
552- A Suffix Tree for a given text is a compressed trie for all suffixes of the given text.
553- Compressed Trie is obtained from standard trie by joining chains of single nodes.
554Building a suffix tree: http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/
555 1. Generate all suffixes of given text.
556 2. Consider all suffixes as individual words and build a compressed trie.
557Applications of suffix trees:
558 1. Longest repeated substring.
559 2. Longest common substring.
560 3. Longest Palindrome in a string.
561 4. Pattern matching.
562
563Important: Review this which explains how to build and search in suffix trees: http://www.geeksforgeeks.org/pattern-searching-using-trie-suffixes/
564
5652. 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.
566Advantages over suffix trees: Space-efficient, simpler, cache-locality, linear time construction.
567Example: "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].
568
569Building suffix arrays:
570 1. Naive method O(n*nlogn):
571 A. Generate all suffixes.
572 B. Sort them
573 2. Radix Sort O(n*n)
574
575Searching using suffix arrays: can be done by simple binary search:
576void search(char *pat, char *txt, int *suffArr, int n) {
577 int m = strlen(pat); // get length of pattern, needed for strncmp()
578 int l = 0, r = n-1; // Initilize left and right indexes
579 while (l <= r) {
580 int mid = l + (r - l)/2;
581 int res = strncmp(pat, txt+suffArr[mid], m);
582 if (res == 0) {
583 cout << "Pattern found at index " << suffArr[mid];
584 return;
585 }
586 if (res < 0) r = mid - 1;
587 else l = mid + 1;
588 }
589 cout << "Pattern not found";
590}
591
5921. Word Boggle: Given a board of MxN characters and a dictionary. Find all words that can be formed by adjacent characters.
593Solution 1: For each character, do a DFS from that character and lookup the word in the dictionary.
594Solution 2 (More optimized): http://www.geeksforgeeks.org/boggle-set-2-using-trie/
595- Create an empty trie and insert all dictionary words into the trie.
596- 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.
5972. 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.
598Solution: 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.
5993. Print unique rows in a given boolean matrix
600Solution: 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.
6014. Implement Reverse DNS Look Up Cache.
602One 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.
603Alphabet 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.
604A similar solution can be provided for forward DNS cache. Alphabet size would be (26 letters + 1 dot + 10 numbers = 37).
605
606---------------------------
607Hashing:
608
609- A good hash function is function that:
610 1. Distributes elements over the array as evenly as possible.
611 2. Avoids collisions
612 3. Fast
613 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.
614
615Handling collisions in hash tables:
6161. 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)
6172. Open addressing: No linked lists, the elements are stored in the hashtable itself. Methods:
618 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.
619 B. Quad probing: if hash(e) is occupied then try hash(e) + 1*1, hash(e) + 2*2, etc.
620 3. Double hashing: Uses two hash functions. if hash(e) is occupied then try hash2(e).
6213. Like chaining, open addressing insert and lookup operations have O(1 + n/m) time complexity.
622
623**Study the design of hash functions**
624hash(unsigned char *str)
625{
626 unsigned long hash = 5381;
627 int c;
628 while (c = *str++)
629 hash = hash * 33 + c;
630 return hash;
631}
632
6331. Find word with nearest repetition (12.3).
6342. Finding all anagrams in a large dictionary of words.
635Solution 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.
636Solution 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.
637Then, 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.
6383. Given a set of points(xi, yi), find the line that passes through most of the points.
639Solution: See solution 12.10. It addresses a lot of issues that need attention in this question.
6404. Given a string s, find out if it can be permuted to form a palindrome.
641Solution: 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.
6425. 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.
643Solution: 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.
6446. Given an array A of n numbers, find if there is a subarray whose sum = 0.
645Solution:
646 1. Create a hash table H, sum = 0
647 2. For i = 0 to n-1:
648 sum += A[i]
649 if(H[sum] != NULL) return (H[sum]+1, i) //The subarray whose sum = 0 starts at H[sum]+1 and ends at i.
650 H[sum] = i
651Note: 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.
652
653---------------------------
654Sorting:
655
6561. Sorting an array of variable size objects, so that swapping is not trivial.
657Solution: Use indirect sort (sorting pointers to objects)
6582. Sort an array in O(n) algorithm where the number of distinct elements k is much less than the array size.
659Solution: 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.
6603. Print the number of occurences of each character in a string, sorted by character.
661Solution: sort the string.
6624. Remove all duplicates from an array
663Solution 1: Sort the array and keep only one instance of each element value.
664Solution 2: Use a hashtable to store the elements
6655. 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).
666Solution: 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.
6676. Given a set of intervals [si, ei], find the minimum set of intervals that represent the union of intervals.
668Solution: sort all intervals according to start time of each interval.
6697. 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.
670Solution O(nlgn): sort T1 and T2 and return true iff sort(T1) < sort(T2) || sort(T2) < sort(T1).
6718. External sort: How to sort n numbers stored in disk, with a memory size of m, where n >> m.
672 1. Load first m numbers into memory. Sort them using any sort algorithm like quicksort and write them back to disk
673 2. Load next m numbers into memory, do the same and repeat until you have k = n/m sorted chunks on disk.
674 3. divide memory into k+1 buffers, k for input and 1 for output.
675 4. Perform a k-way merging of the sorted arrays as follows:
676 a. Load each of the k input buffer with a chunk of the corresponding sorted data.
677 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.
678 c. When one of the k input buffers becomes empty, load the next chunk of data for that buffer.
679 d. Continue untill all data has been sorted, merged into output buffer and written to disk.
6809. How would you sort n uniformly distributed numbers?
681Solution: Use bucket sort O(n) as follows:
682 A. Create n empty buckets (Or lists).
683 B. Do following for every array element arr[i].
684 B1. Insert arr[i] into bucket[n*array[i]]
685 C. Sort individual buckets using insertion sort.
686 D. Concatenate all sorted buckets.
687 Note: For uniformly distributed numbers, interpolation search can be faster than binary search.
68810. Which sorting algorithm makes the least number of memory writes?
689Answer: Selection sort O(n) writes (see wikipedia for code.). There is also another algorithm (Cycle sort) which does even less writes.
69011. Find the minimum-length unsorted subarray within array A.
691Solution: O(n)
692 A. Starting from 0, find the minimum index s such that A[s] > A[s+1]
693 B. Starting from n-1, find the maximum index e such that A[e] < A[e-1]
694 C. Find min and max within [s, e].
695 D. Find the first index i such that A[i] > min. Assign s = i.
696 E. Find the last index such that A[j] > max. Assign e = j.
697 F. The result is A[s..e].
69811. How to shuffle an array A of length n making sure that any permutation of the array has equal probability to be produced:
699Solution 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.
70012. 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.
701Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
702Solution O(n^2): Naiively compare every two elements in the array.
703Solution O(nlgn): Use a modified version of merge sort: http://www.geeksforgeeks.org/counting-inversions/
70413. Given two sorted arrays, find the median of their merged array.
705Solution1 O(n): Merge the two arrays into one sorted array and return the median of the sorted array.
706Solution2 O(lgn): Works only for arrays of same size
7071) Calculate the medians m1 and m2 of the input arrays ar1[] and ar2[] respectively.
7082) If m1 and m2 both are equal then we are done. return m1 (or m2)
7093) If m1 is greater than m2, then median is present in one of the below two subarrays.
710 a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
711 b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
7124) If m2 is greater than m1, then median is present in one of the below two subarrays.
713 a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
714 b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
7155) Repeat the above process until size of both the subarrays becomes 2.
7166) If size of the two arrays is 2 then use below formula to get the median.
717 Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
718Solution 3: A more general solution that works for arrays of different sizes: http://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/
71914. 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.
720Solution:
721Note 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.
722To 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
723Then to move one to the second position call reverse(A, 1) --> 0, 1, 4, 2, 5, 3
724Keep doing the same until the array is sorted.
725
726Notes:
727- The best sorting algorithm for linked lists is mergesort.
728- The sorting algorithm that makes the least number of writes is Cycle Sort. Also selection sort makes close to minimum # of writes.
729- Cycle sort views an unsorted array as cycles which can be rotated in order to achive sorting: http://www.geeksforgeeks.org/cycle-sort/
730
731---------------------------
732Trees and Binary Search Trees:
733
734Tree: a tree is an undirected graph in which any two vertices are connected by exactly one simple path
735Full binary tree: every node other than leaves has two children
736Perfect binary tree: full binary tree with all leaves at the same depth and all parents have two children
737Complete 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
738Balanced binary tree: a binary tree in which the depth of the left and right subtrees of **every node** differ by 1 or less.
739
740Tips:
741 - BST search is better implemented iteratively for O(1) space and faster execution. No need for recursion. Morris Traversal.
742 - When giving algorithm complexity, make sure to use O(h) and O(lgn) accurately, O(h) is usually the right bound.
743
7441. Write a function that returns true iff a binary tree satisfies the BST propperty.
745Solution 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.
746Solution 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)
747Solution 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.
748Solution 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.
7492. Design a O(h) function to delete a node n from a BST. Revise 14.2
750Solution: We have to consider three cases:
751 A. n is a leaf: simply update the pointers of the parent of n to null.
752 B. n has either a left child or a right child, but not both: Replace n by its own child.
753 C. n has both a left child and a right child: find n's successor (m) and consider two sub-cases:
754 C1. m is n's right child: replace n by m.
755 C2. m is not n's right child: replace m by its own right child, then replace n by m.
7563. Find kth largest/smallest element in BST.
757Solution 1 O(n): (Reverse) in-order traversal.
758Solution 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
7594. Find lowest common ancestor of n1 and n2 in a BST. Assume n1.k < n2.k
760Solution: Iterative O(h) time, O(1) space:
761Set 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.
7625. Find lowest common ancestor of n1 and n2 in a binary tree
763Solution:
764search for n1 and n2 in left and right subtrees
765 if both are on the left then recursively search for both on the left side.
766 if both are on the right then recursively search for both on the right side.
767 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.
7686. Given a sorted linked list of nodes, construct a balanced BST in O(n) time. (EPI 14.8)
769Solution: 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.
7707. Merge two BSTs
771Solution 1: Traverse the smaller BST and insert its elements into the larger BST. O(nlgn).
772Solution 2: Convert each BST into a sorted array, merge the two sorted arrays, create a new BST from the merged array. O(n).
773
774---------------------------
775Self-balancing binary search trees
776- 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.
777Multiple variants of SB-BST:
7781. 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).
779- Every node of Treap maintains two values: Key (same as BST's key), and priority.
780- Priority is a random number in some range e.g. [1..100]
781- Priority is used to maintain the heap property. Whenever a new element is added, rotation happen in order to maintain the heap property.
782
783Insert Operation:
784A. Create new node with key equals to x and value equals to a random value.
785B. Perform standard BST insert.
786C. 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.
787
788Other details: http://www.geeksforgeeks.org/treap-set-2-implementation-of-search-insert-and-delete/
789
7902. Red-Black trees.
7913. AVL trees.
792---------------------------
793Divide and conquer:
7941. In a list of points pi=(xi,yi), find the two closest points.
795Solution 1: Brute force compute the distance between every two points. O(n^2).
796Solution 2: Use divide and conquer as follows: O(nlgn).
797 A. Partition the points around the median x-coordinate O(n)
798 B. recursively find the two closest points in L and R partitions
799 C. Let the two closest points in L and R have d1 and d2 distance respectively. Let d = min(d1, d2).
800 D. The next time we need only to consider points [median - d, median + d]
801
8022. Compute the diameter of a tree. Each edge has a cost, the diameter is the maximum cost from a tree node to another node.
803Solution 1 O(n^2): BFS from each node to all other nodes and recording the shortest path distances and maintaining a maximum.
804Solution 2 O(n):
805int diameterOpt(struct node *root, int* height)
806{
807 /* lh --> Height of left subtree. rh --> Height of right subtree */
808 int lh = 0, rh = 0;
809 /* ldiameter --> diameter of left subtree. rdiameter --> Diameter of right subtree */
810 int ldiameter = 0, rdiameter = 0;
811 if(root == NULL)
812 {
813 *height = 0;
814 return 0; /* diameter is also 0 */
815 }
816
817 /* Get the heights of left and right subtrees in lh and rh And store the returned values in ldiameter and ldiameter */
818 ldiameter = diameterOpt(root->left, &lh);
819 rdiameter = diameterOpt(root->right, &rh);
820
821 /* Height of current node is max of heights of left and right subtrees plus 1*/
822 *height = max(lh, rh) + 1;
823
824 return max(lh + rh + 1, max(ldiameter, rdiameter));
825}
826
8273. Compute x to the power y in O(logn)
828int power(int x, unsigned int y) {
829 int temp;
830 if( y == 0)
831 return 1;
832 temp = power(x, y/2);
833 if (y%2 == 0)
834 return temp*temp;
835 else
836 return x*temp*temp;
837}
838---------------------------
839Dynamic Programming:
840- Overlapping sub-problem and Memoization vs tabulation: http://www.geeksforgeeks.org/dynamic-programming-set-1/
841- Optimal sub-structure property: http://www.geeksforgeeks.org/dynamic-programming-set-2-optimal-substructure-property/
842
843Examples of Dynamic Programming Problems:
844 1. Rod cutting
845 2. Optimal BST construction
846 3. Matrix-chain multiplication
847 4. Longest simple path in a DAG
848
8491. Find the maximum subarray sum.
850Solution 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]
8512. Find the maximum subarray sum in a circular array.
852Solution 1: Find the minimum (non-circular) subarray sum that is less than zero. The remaining elements are the maximum circular subarray.
853Solution 2: See EPI page 353.
8543. Important: Longest non-decreasing subsequence in array A[0..n-1]: EPI 15.6
855Solution: Create array M such that M[0] = 1.
856 For i = 1 to n-1
857 M[i] = 1
858 for j = 0 to i - 1
859 if(A[i] > A[j])
860 M[i] = max(M[i], M[j] + 1);
861
862for all M[i], i > 0 = max(for all j<i: A[j]<=A[i] ? M[j]+1 : 1). O(n^2)
863Solution 2 DP O(nlgn):
864 Create M as a dynamic size vector
865 for each a in A do
866 find first element M[i] in M > a. If found, set M[i] = a, else append a to M //binary search O(logn).
867 end for
868 return M //contains the longest non-decreasing subsequence
8694. 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.
870Solution: O(n)
871//Assumes intervals are sorted by nondecreasing finish times
872M-Compute-Opt (j)
873 If j = 0 then
874 Return 0
875 Else if M[j] is not empty then //not empty means it was computed before so no need to re-compute (memorization)
876 Return M[j]
877 Else
878 //p(j), for an interval j, is the largest index i < j such that intervals i and j are disjoint
879 Define M[j] = max(vj+M-Compute-Opt(p(j)), M-Compute-Opt(j-1)) //vj is interval weight
880 Return M[j]
8815. Given array A (which can contain negative numbers), find the longest subarray whose sum <= k
882My 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].
883Compute 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++.
884Book Solution: EPI page 356
8856. Maximum 2D subarray (EPI page 15.9 Page 120): Given a m x n 2D array, find the maximum submatrix sum.
886Solution: 2D Kadane algorithm: https://www.youtube.com/watch?v=yCQN096CwWM&t=286s
887
888//The first two nested loops check all possible right and left positions (col numbers) in a bruteforce method.
889for fromCol 0..cols-1
890 create dp[0..rows-1] array with all zero
891 for col fromCol..cols-1
892 //Now we fill dp with elements
893 for row 0..rows-1
894 dp[row] += arr[row,col]
895 //run 1D kadane
896 sum = 0, max1D = 0
897 for i 0..dp.Length-1
898 sum += dp[i]
899 if(sum < 0)
900 sum = 0;
901 top = i+1;
902 if(sum > maxSum)
903 maxSum = sum
904 maxL = fromCol, maxR = col, maxTop = top, maxBottom = i;
905Complexity: O(col^2*row)
906Note: There is a better O(row*col) that uses max area under histogram algorithm in EPI page 361
907
9087. 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}.
909Solution 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.
9108. Given two arrays A and B, find the longest common subsequence.
911Solution: we will write this as a recurrence:
912 1 + LCS(i-1, j-1) A[i] = B[j]
913LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1)) A[i] != B[j]
914 0 if i == 0 or j == 0
9159. 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.
916To count total number solutions, we can divide all set solutions in two sets.
9171) Solutions that do not contain mth coin (or Sm).
9182) Solutions that contain at least one Sm.
919Let 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).
920Solution: O(nm).
921int count( int S[], int m, int n ) {
922 int table[n+1] = {0};
923 table[0] = 1;
924 for(int i=0; i<m; i++)
925 for(int j=S[i]; j<=n; j++)
926 table[j] += table[j-S[i]];
927 return table[n];
928}
929
930What if you want to count the number of permutations? i.e. 1, 1, 2 is different from 1, 2, 1?
931Suppose 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].
932Solution O(nm):
933int count(int S[], int m, int n)
934{
935 int table[n+1] = 0;
936 table[0] = 1;
937 for(int i=0; i <= n; i++)
938 for(int j = 0; j < m; j++)
939 if(i >= S[i])
940 table[i] += table[i - S[i]];
941
942 return table[n];
943}
944
94510. Matrix chain multiplication: See matrix_chain.cpp
94611. 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).
947
948---------------------------
949Greedy Algorithms:
950
951Definition: 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.
952- 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.
953 - 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.
954 - 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.
955 - we must prove that a greedy choice at each step yields a globally optimal solution.
956
9571. Given n simultaneous database requests with each request Ri having service time Ti. Process the requests in some order that minimizes waiting time.
958Solution: Sort by non-decreasing Ti and process in that order.
9592. 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.
960Solution O(nlgn): Sort by increasing finish time, accept the request with smallest Fi that is non-overlapping with previously accepted requests.
9613. Interval scheduling 2: Schedule all n intervals on M machines
962Solution:
963Sort all intervals by nondecreasing start time
964for j=1 to n
965 for each interval i that precedes and overlaps j
966 exclude i.label from consideration for labeling j
967 end for
968 if there is an unused machine, use it otherwise allocate a new machine.
969end for
9704. Schedluing to minimize latency: sort by nondecreasing deadline.
9715. 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.
972Solution: sort in decreasing x/unit.
9736. Huffman codes
9747. 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.
975- 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.
976- To achieve minimum k, a back-tracking algorithm is used.
977Solution:
978 A. assign color 0 to first vertex
979 B. Do following for each vertex v of the remaining V-1 vertices.
980 B1. Color v with the lowest color that has not been used for an adjacent vertex
9818. Given a value v and an infinite number of coins of values (v1, v2, ..., vm). Find the minimum number of coins to represent v
982Solution: There is a greedy algorithm but it doesn't work for all inputs O(m). A dynamic programming algorithm works for all inputs.
983- Start from the highest value coin that has vi <= v, subtract vi from v, k++. Repeat until v == 0.
9849. Connect n ropes with minimum cost, given that the cost to connect two ropes is the sum of their lengths.
9851. Insert all ropes into a min-heap.
9862. While min_heap.count > 1
987 Take the two smalles ropes
988 cost += connect(r1, r2)
989 return the connected rope into the heap
990
991---------------------------
992Graphs:
993
994Clique: undirected graph in which there is an edge between each two vertices.
995BFS: can be used to get information about distances (# of edges). Works for directed and undirected graphs.
996DFS: can be used to detect cycles and compute discovery and finish times.
997MST: Applicable to undirected connected graphs. Two main algorithms: Kruskal and Prim. O(ElgV). Easier to implement Kruskal algorithm in an interview.
998Bi-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.
999Strongly 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
1000Semi-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.
1001Bipartite 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.
1002Articulation point: A vertex whose removal disconnects the graph.
1003Bridge: An edge whose removal disconnects the graph.
1004Biconnected component of G: A maximal set of edges such that any two edges in the set lie on a common simple cycle.
1005Simple cycle: Simple path with no repeated vertices other than the starting and ending vertices.
1006
1007Representing 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:
1008
1009 public class Graph
1010 {
1011 public List<Vertex> Vertices = new List<Vertex>();
1012 public List<Edge> Edges = new List<Edge>();
1013 }
1014
1015 public class Vertex
1016 {
1017 public string Name;
1018 public List<Vertex> Adj = new List<Vertex>();
1019 public bool Visited;
1020 public Vertex Predecessor;
1021
1022 //For DFS
1023 public int DiscoveryTime;
1024 public int FinishTime;
1025
1026 //For BFS
1027 public int Distance;
1028
1029 //For union-find
1030 public Vertex Parent;
1031 public int Rank;
1032 }
1033
1034 public class Edge
1035 {
1036 public Vertex Src, Dest;
1037 public int Weight = 1;
1038 }
1039
10401. Design an algorithm that checks if a graph is a bi-partite graph:
1041Solution: 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.
10422. 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.
1043Solution 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.
10443. Given a connected graph G, design an algorthim that returns true iff if any edge is removed from the graph, the graph remains connected.
1045Solution O(V): The above can be true iff every edge in the graph lies on a cycle. Use DFS to find out.
10464. See the implementation of solution 16.7 page 396. It says a lot about how to analyze graphs using STL.
10475. Find shortest path with minimum number of edges.
1048Solution: 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.
10496. 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).
1050Solution: 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.
10517. Given a DAG find the longest path from a source vertex s to all other vertices.
1052Solution: Longest path for a general graph is NP hard. But it is linear for a DAG:
1053 A. Create a topological sorting of vertices
1054 B. Initialize dist(v) = -INF for all v
1055 C. For each vertex v in topological order:
1056 for every vertex u in adj(v): if dist(u) < dist(v) + w(v,u) then dist(u) + dist(v) + w(v,u)
10578. How to find all articulation points in a graph?
1058Solution:
1059 A. For each vertex v:
1060 remove v from graph (along with its edges)
1061 Check if this disconnects the graph (via SCC algorithm)
1062 if so, print v.
1063 re-insert v in the graph.
1064Solution 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/
10659. How to find if a directed graph has a cycle
1066Note: 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.
1067Solution: 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.
1068Tip: 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.
1069Link to solution: http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
107010. How to find if an undirected graph has a cycle
1071Solution: A union-find algorithm can be used.
1072- Create a set for each vertex
1073- For each edge(u,v) if(v.set == u.set) return true, else u.set = v.set = Math.Min(u.set, u.set)
1074Solution 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.
107511. Find out if a Graph G is strongly connected:
10761) Initialize all vertices as not visited.
10772) Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS traversal doesn’t visit all vertices, then return false.
10783) Reverse all arcs (or find transpose or reverse of graph)
10794) Mark all vertices as not-visited in reversed graph.
10805) 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.
108112. Graph Coloring:
1082Applications:
1083- Register Assignment in CPU
1084- Frequency assignment in radio towers
1085- Soduko
1086- 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.
1087- Bi-partite graphs: Graph is bi-partite iff it can be colored with only 2 colors.
1088- Map coloring: No two adjacent countries are painted with the same color.
1089- Rolling out updates to servers that can't be taken down simultanously.
1090Solution: 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
10911. Color first vertex with first color.
10922. Do following for remaining V-1 vertices.
1093 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.
109413. 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.
1095- This is an NP complete problem.
1096Solution 1 (Naiive), O(n!):
1097 A. Choose any city c0 as the starting point.
1098 B. Generate (n-1)! permutations for the other cities.
1099 C. compute the cost for all paths that start from c0 and visit each permutation in order, maintain and return the minimum.
1100Solution 2 (Dynamic Programming): O(n^2 * 2^n): http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
1101Solution 3 (Approximate): The approximate algorithms work only if the problem instance satisfies Triangle-Inequality.
1102 A. Select any city c0 as the starting point
1103 B. Use Prim's algorithm to compute the MST with c0 as root.
1104 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)
1105This 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.
110614. 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.
1107Problem: Given an undirected graph, the vertex cover problem is to find minimum size vertex cover.
1108Note: This is known to be NP-Complete problem.
1109Solution (Approximate):
11101) Initialize the result as {}
11112) Consider a set of all edges in given graph. Let the set be E.
11123) Do following while E is not empty
1113...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result
1114...b) Remove all edges from E which are either incident on u or v.
11154) Return result
111615. 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.
1117Solution: Model as a graph, each entry is a vertex, an edge connects two vertices if they share common info (username, phone, email). Return SCC.
111816. 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.
1119- Notice that if all edges were 1 then BFS O(V+E) can be used.
1120- Also notice that Dijkstra's algorithm solves the general problem of single-source shortes paths in O(ElgV).
1121We 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.
1122-Note: Revise Network flow algorithms
112317. Cloning a graph?
112418. 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?
1125Solution: 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.
1126
1127---------------------------
1128Intractability:
11291. 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?
1130Solution: 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
11312. 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.
1132Solution: Using dynamic programming we can get a pseudo-polynomial complexity O(nS).
1133Guess: For each item, we either include it in the subset of items or we don't
1134KS(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.
1135
1136int knapsack(vector<int> &v, int remaining, int i) {
1137 if(i >= v.size())
1138 return 0;
1139 if(v[i] > remaining)
1140 return knapsack(v, remaining, i + 1);
1141 return max(knapsack(v, remaining, i+1), knapsack(v, remaining - v[i], i + 1) + v[i]);
1142}
11433. Traveling salesman: See Graph Algorithms
1144---------------------------
1145Other problems:
1146
11471. 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/
11482. 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/
11493. Given pair-sum array (pair[]) of an array A. Construct A from pair.
1150Example: A = {6, 8, 3, 4} --> pair = {14, 9, 10, 11, 12 ,7}
1151Working a few examples:
1152pair[0] = A[0] + A[1] = 14
1153pair[1] = A[0] + A[2] = 9
1154pair[2] = A[0] + A[3] = 10
1155pair[3] = A[1] + A[2] = 11
1156pair[4] = A[1] + A[3] = 12
1157pair[5] = A[2] + A[3] = 7
1158
1159Notice 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.
1160You can compute all other values in the array like this:
1161for (int i=1; i<n; i++)
1162 arr[i] = pair[i-1]-arr[0];
1163
1164- 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.
1165- Find top k frequent elements. Can use bucket sort to solve in O(n) time and O(n) space.
1166---------------------------
1167Design Problems:
1168
11691. Design LRU cache with a limited capacity.
1170Solution: 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.
11712. Design LFU cache with a limited capacity
1172Solution: Instead of using a linked list, use a min-heap for sorting CacheEntry elements. Operations are O(lg(Capacity)).
11733. Design a FIFO queue that allows only unique elements and has O(1) operations.
1174Solution: Try a normal queue with a hashtable.
11754. Design a short URL system:
1176Solution: You need a bijective function. Assume that your short URL will constitute of characters [a-zA-Z0-9] (64 distinct chars)
1177 1. Store the long URL in the DB and get x = its auto-generated ID.
1178 2. Y = Convert x to its 64-base equivalent number + (int)'a'
1179 3. Your short URL is www.shorturl/Y
1180When doing a lookup you do the following:
1181 1. X = (Y - (int)'a') converted to base 10 number
1182 2. Lookup the URL in the DB with ID = X.
1183 3. Redirect.
11845. How would you design a spell checker?
1185Solution:
1186 1. Have a dictionary of all words
1187 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).
1188 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.
1189 Note: Other more complex algortihms exist.
11906. How would you design an auto-complete system?
1191Use 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".
1192---------------------------
1193OOP:
1194
1195Encapsulation: Encapsulation is the packing of data and functions into a single component. The features of encapsulation are supported using classes.
1196Polymorephism: 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
1197Data Abstraction: ADTs are defined by their meanings (semantics), while hiding away the details of how they work. In other words, separating interface from implementation.
1198
1199---------------------------
1200Math & Geometry:
1201Cross product of two directed line segments [(0,0),(x1,y1)] and [(0,0),(x2,y2)] = p1 x p2 = det(p1, p2) = x1y2 - x2y1.
1202
12031. 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?
1204Solution O(1):
1205 A. Transolate p0 as the origin so that p1' = p1 - p0 and p2' = p2 - p0.
1206 B. Compute the cross product z = p1' x p2' = (x1 - x0)(y2 - y0) - (x2 - x0)(y1 - y0)
1207 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.
12082. Determine if two consecutive line segments (p0,p1) and (p1,p2) turn left (counterclockwise) or right (clockwise).
1209Solution: We use the technique as in the previous question:
1210 A. Compute z = (p2 - p0) x (p1 - p0)
1211 B. If z > 0 then clockwise, else counterclockwise.
12123. Find out if two lines intersect:
1213Solution: If the two lines have different slopes (not parallel) then they will intersect somewhere.
12144. Find out if two line segments intersect:
1215Solution 1: This solution is very sensitive to the precision of the division operation and is therefore not very accurate.
1216Find the point of intersection of the two lines:
1217 A. find the equations of the two lines in the form y1 = f1(x), y2 = f2(x)
1218 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).
1219 C. To find y intersection, plug the x we found in step B in any of the two equations.
1220 D. Return true if and only if both x and y are in the ranges of the two lines.
1221Solution 2: Look at page 1018 of Introduction to Algorithms.
12225. Determine if **any** of n given line segments intersect:
1223Solution 1: O(n^2): Run the algorithm above for n*(n-1) segments and return the first intersecting line segments pair.
1224Solution 2 O(nlgn): Assumes no vertical segments. See Page 1025.
1225Note: 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.
12266. Given n points in a plane, find the two closest points
1227Solution 1: Compute distances between all n(n-1) point pairs, return the closest. O(n^2)
1228Solution 2 O(nlgn): see page 349 of EPI.
12297. 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:
1230Solution:
1231int my_rand() {// returns 1 to 7 with equal probability
1232 int i;
1233 i = 5*foo() + foo() - 5; //random number between [1,25] with uniform probability
1234 if (i < 22)
1235 return i%7 + 1;
1236 return my_rand(); //just try again.
1237}
12387. Devise a space-and-time efficient algorithm to compute the binomial coefficient C(n, k).
1239Solution O(k) time and O(1) space:
1240C(n, k) = n!/((n-k)!k!) = [n * (n-1) *... * (n-k-1)]/k!
1241Also note that C(n, k) = C(n, n-k)
1242unsigned binomial(n, k) {
1243 int res = 1;
1244 if(n - k < k)
1245 k = n - k;
1246 for(int i = 0; i < k; ++i) {
1247 res *= n-i;
1248 res /= i + 1;
1249 }
1250 return res;
1251}
12528. Write a program to print all prime factors of a given number n
1253Solution: 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.
1254void primeFactors(int n) {
1255 for (int i = 2; i <= sqrt(n); i = i++)
1256 {
1257 // While i divides n, print i and divide n
1258 while (n%i == 0)
1259 {
1260 cout << i << " ";
1261 n = n/i;
1262 }
1263 }
1264 if (n > 2) // This condition is to handle the case whien n is a prime number greater than 2
1265 cout << n;
1266}
12679. Generate magic square matrix of size n by n:
1268Solution: 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).
126910. Given a number n of k digits, find the next palindrom number:
1270Solution: 3 cases:
1271a. 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.
1272b. otherwise: mirror first half into second. while(n2 < n) {increment middle digits, and move the carry} Eg. 12923 --> 12921 --> 12(10)21 --> 13031.
127311. 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
127412. Multiply two numbers without using the * operator:
1275 int res = 0; // initialize result
1276 while (b > 0)
1277 {
1278 if (b & 1)
1279 res = res + a;
1280 a = a << 1;
1281 b = b >> 1;
1282 }
1283 return res;
1284---------------------------
1285Misc:
1286
12871. Longest non-decreasing subarray (differet from subsequence): Given an array A, find the longest subarray A[i..j] whose elements are non-decreasing
1288Solution: 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.
12892. Keep track of a random sample of k elements of a very long stream of numbers. The stream is of infinite length.
1290Solution: Reservoir sampling, as follows:
1291 A. Base case: store the 1st k [0..k-1] elements in the random array A.
1292 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).
1293 C. if r < k, replace A[r] with A[i].
1294 D. Repeat steps B-D.
12953. Given a team of N players. How many minimum games are required to find second best player?
1296Solution: N + lg2(n) - 2. How??
1297
1298---------------------------
1299Concurrency:
1300
13011. Dining philosophers:
1302Solution: 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.
1303
1304---------------------------
1305Operating Systems:
1306
1307More concepts:
1308- A semaphore S is an integer variable that can be accessed only through two standard operations : wait() and signal().
1309- There are two types of semaphores: counting semaphores and binary semaphores.
1310
13111. Explain Belady's anomaly.
1312Answer: increasing the # of allocated frames to a process increases the # of page faults.
13132. What is thrashing?
1314When the processor spends most of its time swapping pages rather than doing real processing.
13153. What are the 4 conditions for a deadlock?
1316Mutual exclusion, hold and wait, circular wait, non-preemption
13174. What are the 4 elements of a process image?
1318User code, user data, stack(s), PCB.
13195. What is the TLB?
1320Contains the most recently used page table entries
13216. When is a system in a safe state?
1322When there is at least one way of execution that does not lead to a dead lock.
13237. What is cycle stealing?
1324When a DMA controller forces the CPU to suspend an operation in order to be able to use the data bus.
13258. What is load sharing?
1326When processes are not assigned to particular processors so there is a global process queue that all processes share.
13279. For disks, what is rotational delay, seek time, and transfer time?
132810. What is a monitor:
1329An object that implements mutual exclusion by itself (like a thread-safe object). So it allows safe multi-threaded access to its clients.
133011. What are the disadvantages of thread locks?
1331Blocking, more overhead, priority inversion, if a thread holding the lock dies other threads get stuck, difficult to debug.
133212. What is a spinlock and when is it used?
1333A spinlock is a lock that requires the thread trying to acquire it to wait in a loop (busy waiting).
1334Can be used when locks are held for a very short time, as they avoid context switches.
133513. What synchronization primitives are used in multi-processor / multi-core systems?
1336Spinlocks are the simplest. Others are Queued locks and Ticket spin locks
133714. What is the difference between a binary semaphore and a mutex?
1338A mutex supports ownership, which means only the process that has the lock can unlock it. This is not true for binary semaphores.
1339A mutex is used to protect shared resources (mutual exclusion). A semaphore is used to make a process wait for something to happen.
1340A mutex is valid within a process (can't use inter-process mutex), whereas a semaphore can be used by different processes
134115. Describe Peterson's algorithm of mutual exclusion
1342bool flag[0] = false;
1343bool flag[1] = false;
1344int turn;
1345 Process 0 Process 1
1346------------------------------ ------------------------------
1347P0: flag[0] = true; P1: flag[1] = true;
1348P0_gate: turn = 1; P1_gate: turn = 0;
1349while (flag[1] && turn == 1) while (flag[0] && turn == 0)
1350{ {
1351 // busy wait //busy wait
1352} }
1353// critical section //critical section
1354... ...
1355// end of critical section // end of critical section
1356flag[0] = false; flag[1] = false
1357
1358---------------------------
1359Testing:
1360
1361When testing something we need to consider the following:
13621. 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.
13632. Test the object for each functionality/use case. If it fails, does it fail gracefully?
13643. 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?
13654. What stress conditions this object can be used in? low memory, low bandwidth, etc.
1366
1367---------------------------
1368Database & SQL:
1369
13701. Write SQL query to print department names and their employee count
1371Solution: use left join so that departments with 0 employees will be printed as well.
1372Select DName, count(*) as 'num_emps' FROM Dept left join Emp ON Dept.did = Emp.did Group by Dept_Name
13732. Explain what database de-normalization is.
1374Solution: Cracking the Coding Interview page 234.
13753. Find the employee with the nth largest salary:
1376SELECT *
1377FROM Employee Emp1
1378WHERE (N-1) = (
1379SELECT COUNT(DISTINCT(Emp2.Salary))
1380FROM Employee Emp2
1381WHERE Emp2.Salary > Emp1.Salary)
1382
1383The above query looks for the employee whose salary is less than n-1 other employees, that is, the nth largest.
13844. What are join types?
1385 1. Inner Join
1386 2. Outer Join: 3 types
1387 A. Left outer join
1388 B. Right outer join
1389 C. Full outer join
1390
1391---------------------------
1392General and Behavioral Questions:
13931. Tell Me About Your Experience
13942. Why do you want this job?
13953. Why did you choose this company?
13964. What is your favorite programmming language?
13975. What are your career goals?
13986. Give examples of difficult problems you faced.
1399- Tell me about a time when you overcame a challenge in the workplace
1400- How have you improved a certain process at work?
1401- Why Google?
1402- Tell me about a time when you spoke with a dissatisfied client and what did you do to appease them?
1403- Name 3 advantages of AdWords
1404- Have you ever improved the efficiency of a process/task at work?
1405
1406----------------------------
1407Misc Data Structure:
1408
14091. Trie
1410struct trie_node {
1411 bool isLeaf; /* Used to mark leaf nodes */
1412 struct trie_node *children[ALPHABET_SIZE];
1413};
1414
1415struct trie {
1416 struct trie_node *root;
1417 int count; //count of all keys in the trie
1418};
1419
1420- Insert key in trie:
1421void insert(struct TrieNode *root, const char *key)
1422{
1423 int level;
1424 int length = strlen(key);
1425 int index;
1426
1427 struct TrieNode *pCrawl = root;
1428
1429 for (level = 0; level < length; level++)
1430 {
1431 index = CHAR_TO_INDEX(key[level]);
1432 if (!pCrawl->children[index])
1433 pCrawl->children[index] = getNode();
1434
1435 pCrawl = pCrawl->children[index];
1436 }
1437
1438 // mark last node as leaf
1439 pCrawl->isLeaf = true;
1440}
1441
1442- Search a trie:
1443bool search(struct TrieNode *root, const char *key)
1444{
1445 int level;
1446 int length = strlen(key);
1447 int index;
1448 struct TrieNode *pCrawl = root;
1449
1450 for (level = 0; level < length; level++)
1451 {
1452 index = CHAR_TO_INDEX(key[level]);
1453
1454 if (!pCrawl->children[index])
1455 return false;
1456
1457 pCrawl = pCrawl->children[index];
1458 }
1459
1460 return (pCrawl != NULL && pCrawl->isLeaf);
1461}
1462
1463- Delete a key from a trie:
1464During delete operation we delete the key in bottom up manner using recursion. The following are possible conditions when deleting key from trie,
1465A. Key may not be there in trie. Delete operation should not modify trie.
1466B. 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.
1467C. Key is prefix key of another long key in trie. Unmark the leaf node.
1468D. 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.
1469
1470Questions:
1471 1. Find the k most frequent words from a file: Use a trie and a min heap. Or you can use hashing.
1472
14732. 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.
14741 <-------------------------------->10<---------------------------->34
1475| | |
14761 <--> 2 <--> 4 <--> 7 <--> 9 <--> 10 <--> 18 <--> 23 <--> 30 <--> 34
1477- 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.
1478- 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)).
1479
1480
14815. Given a 2D array of boolean values, print rows such that repeated rows are printed only once
1482Solution:
1483 1. Print first row, create a trie structure from that row
1484 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.
1485
14866. 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/
1487
1488----------------------------
1489Linux Commands:
1490
14911. How to replace a pattern in files:
1492grep "mypattern" | xargs sed -i "s/string1/string2/g"
1493-----------------------------------------------------------------
1494Multi-threaded programming in C#:
1495
1496- Creating a new thread: You can create a thread in two ways:
1497 - an anonymous function:
1498 Thread t3 = new Thread(p =>
1499 {Console.WriteLine(p));
1500 t3.Start(20);
1501 - A method:
1502 public static void DoWork(object data) {...}
1503 newThread = new Thread(w.DoWork);
1504 newThread.Start("The answer.");
1505
1506- Terminating a thread: thread.Abort();
1507- Waiting for a tread to finish: thread.Join();
1508
1509Thread synchronization:
15101. Locks (or ciritical sections): we use the lock keyword on any object:
1511Object lockObj = new Object();
1512lock(lockObj)
1513{
1514//critical section
1515}
15162. Synchronization Events and Wait Handles
1517- 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.
1518- 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.
1519
1520Example:
1521autoEvent = new AutoResetEvent(false);
1522static void Main()
1523{
1524 Console.WriteLine("main thread starting worker thread...");
1525 Thread t = new Thread(DoWork);
1526 t.Start();
1527 autoEvent.Set();
1528}
1529
1530static void DoWork()
1531{
1532 Console.WriteLine(" worker thread started, now waiting on event...");
1533 autoEvent.WaitOne();
1534 Console.WriteLine(" worker thread reactivated, now exiting...");
1535}
1536
1537Mutex object:
1538- 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.
1539- It is a wrapper of Win32 constructs.
1540- 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.
1541Mutex mut = new Mutex();
1542mut.WaitOne();
1543//some work
1544mut.ReleaseMutex();
1545
1546Interlocked 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.
1547- Add(Int32, Int32): Adds two 32-bit integers and replaces the first integer with the sum, as an atomic operation.
1548- CompareExchange(Int32, Int32, Int32): Compares two 32-bit signed integers for equality and, if they are equal, replaces the first value.
1549- Decrement(Int32): Decrements a specified variable and stores the result, as an atomic operation.
1550- Exchange(Int32, Int32): Sets a 32-bit signed integer to a specified value and returns the original value, as an atomic operation.
1551- Increment(Int32): Increments a specified variable and stores the result, as an atomic operation.
1552
1553Concurrency problems:
1554- 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.
1555
1556- 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.
1557 - If there is no customer, then the barber sleeps in his own chair.
1558 - When a customer arrives, he has to wake up the barber.
1559 - 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.
1560Semaphore Customers = 0;
1561Semaphore Barber = 0;
1562Mutex Seats = 1;
1563int FreeSeats = N;
1564
1565Barber {
1566 while(true) {
1567 down(Customers); /* waits for a customer (sleeps). */
1568 down(Seats); /* mutex to protect the number of available seats.*/
1569 FreeSeats++; /* a chair gets free.*/
1570 up(Barber); /* bring customer for haircut.*/
1571 up(Seats); /* release the mutex on the chair.*/
1572 CutHair(); /* barber is cutting hair.*/
1573 }
1574}
1575
1576Customer {
1577 while(true) {
1578 down(Seats); /* protects seats so only 1 customer tries to sit in a chair if that's the case.*/
1579 if(FreeSeats > 0) {
1580 FreeSeats--; /* sitting down.*/
1581 up(Customers); /* notify the barber. */
1582 up(Seats); /* release the lock */
1583 down(Barber); /* wait in the waiting room if barber is busy. */
1584 // customer is having hair cut
1585 } else {
1586 up(Seats); /* release the lock */
1587 // customer leaves
1588 }
1589 }
1590}
1591
1592- Readers-writer problem:
1593Writer:
1594do {
1595 wait(wrt); // writer requests for critical section
1596 // performs the write
1597 signal(wrt); // leaves the critical section
1598} while(true);
1599
1600Readers:
1601do {
1602 wait(mutex); // Reader wants to enter the critical section
1603 readcnt++; // The number of readers has now increased by 1
1604 // 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
1605 if (readcnt==1)
1606 wait(wrt);
1607 // other readers can enter while this current reader is inside the critical section
1608 signal(mutex);
1609 // current reader performs reading here
1610 wait(mutex); // a reader wants to leave
1611 readcnt--;
1612 // that is, no reader is left in the critical section,
1613 if (readcnt == 0)
1614 signal(wrt); // writers can enter
1615 signal(mutex); // reader leaves
1616
1617} while(true);
1618
1619- 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.
1620
1621Producer:
1622do{
1623//produce an item
1624wait(empty);
1625wait(mutex);
1626//place in buffer
1627signal(mutex);
1628signal(full);
1629}while(true);
1630
1631Consumer:
1632
1633do{
1634wait(full);
1635wait(mutex);
1636// remove item from buffer
1637signal(mutex);
1638signal(empty);
1639// consumes item
1640}while(true)
1641
1642Sempaphores:
1643Semaphore threadPool = new Semaphore(3, 5);