· 6 years ago · Dec 18, 2019, 05:10 PM
1SYSTEM DESIGN STUFF:
2https://github.com/donnemartin/system-design-primer#index-of-system-design-topics
3https://github.com/checkcheckzz/system-design-interview
4
5NOTES FOR COMPETITIVE PROGRAMMING:
6
7@ Inorder traversal iterative
8void traversal(TreeNode* root){
9 stack<TreeNode*> st;
10 while(!st.empty() || root){
11 while(root){
12 st.push(root);
13 root = root->left;
14 }
15 root = st.top();
16 st.pop();
17 cout<<root->data<<" ";
18 root = root->right;
19 }
20}
21
22@ Iterative verify BST
23void checkBST(TreeNode *root){
24 stack<TreeNode*> st;
25 TreeNode *cur = NULL;
26 while(root || !st.empty()){
27 while(root){
28 st.push(root);
29 root = root->left;
30 }
31 root = st.top();
32 st.pop();
33 if(cur != NULL && cur->data >= root->data)
34 return false;
35 cur = root;
36 root = root->right;
37 }
38 return true;
39}
40
41@ Root to node path recursive
42bool findPath(TreeNode* root,TreeNode *p,vector<TreeNode*>&v){
43 if(root==NULL)
44 return false;
45 v.push_back(root);
46 if(root==p)
47 return true;
48 if(findPath(root->left,p,v) || findPath(root->right,p,v))
49 return true;
50 v.pop_back();
51 return false;
52}
53
54@ Iterative root to leaf path sum equals target
55def hasPathSum2(self, root, sum):
56 if not root:
57 return False
58 stack = [(root, root.val)]
59 while stack:
60 curr, val = stack.pop()
61 if not curr.left and not curr.right:
62 if val == sum:
63 return True
64 if curr.right:
65 stack.append((curr.right, val+curr.right.val))
66 if curr.left:
67 stack.append((curr.left, val+curr.left.val))
68 return False
69
70@ Count nodes in a complete binary tree
71* calculate height of left and right subtree, if both heights are same, then total nodes=2^(height of tree) -1
72* else recursively visit the left and right subtrees and calculate both heights.
73TreeNode *l = root,*r = root;
74int hl=0,hr=0;
75while(l){
76 hl++;
77 l = l->left;
78}
79while(r){
80 hr++;
81 r = r->right;
82}
83if(hl == hr)
84 return pow(2,hl) - 1;
85return 1 + countNodes(root->left) + countNodes(root->right);
86
87@ For zig zag traversal of a binary tree use two stacks.
88
89@ For iterative postorder traversal, use two stacks. Push the parent node`s left and right in stack 1 and push the parent
90 to the second stack.
91
92@ Maximum area of rectangle in histogram.
93* If stack is empty or bars[st.top] <= bars[i], push bar into the stack.
94* else, pop a bar from stack till bar at st.top() is lesser than the current bar.
95* for each popped bar, left index is st.top(if stack is not empty) and right index is i,
96* hence area of popped bar is (height of this bar)*(i-st.top-1);
97
98@ To check if a number is a power of 3 or not, check if that number divides 3^19 leaving remainder 0.
99
100@ In an array, each number appears thrice except one. Find that number
101* For every bit position for every number calculate sum % 3
102* The bits for which sum is not multiple of 3, are the bits of number with single occurrence.
103
104@ To add two numbers without using any arithmetic operator, apply half adder`s logic.
105add(a,b){
106 while(b != 0){
107 carry = a & b;
108 a = a ^ b;
109 b = carry << 1;
110 }
111 return a;
112}
113
114@ keep adding digits of a number till you get a 1 digit number.
115return 1+(num-1)%9;
116
117@ Set matrix row and column to 0 when a 0 is encountered, this process is to be done inplace and O(1) extra space.
1181. Check first row, if any 0 encountered, set (bool rowCheck) to true.
119 Check first column, if any 0 encountered, set (bool colCheck) to true.
1202. Start from 2nd row and 2nd column till last row and column, if any 0 encountered, set corresponding value at index in the first row and column to 0.
1213. Start from 1 st row and 1st column, if value at the start of any row is 0, set the whole row to 0.
122 Start from 1 st row and 1st column, if value at the start of any column is 0, set the whole column to 0.
1234. If rowCheck is true, set the whole first row to 0.
124 If colCheck is true, set the whole first column to 0.
125
126@ Inplace checking for a repeated element in an array, without modifying the array, O(1) space, O(n) runtime solution.
127 ##Floyd`s Algorithm- Hare and Tortoise.
1281. initialize tortoise=nums[0],hare=nums[0];
1292. find their intersection point,
130 tortoise=nums[tortoise],hare=nums[nums[hare]]
131
1323. find the entry in the cycle, by taking two pointers,
133 ptr1=nums[0], ptr2=tortoise
134 while(ptr1!=ptr2){
135 ptr1=nums[ptr1]
136 ptr2=nums[ptr2]
137 }
1384. return ptr1
139
140@ 4sum, 3sum and 2sum problem :-(In case of duplicate elements)
141* https://www.sigmainfy.com/blog/summary-of-ksum-problems.html
142
143@ Fast modulo exponentiation: x^n
144* While n>0...
145* If n is odd, multiply result with x.
146* Divide n by 2 and square x.
147
148@ Classic Sieve of Eratosthenes :- O(N log(log N))
149* To find all the prime numbers less than or equal to n.
150* Create a boolean array (all true) of size n.
151* Run a loop (iter) from 2 to sqrt(n).
152* For every loop mark all multiples of iter as false.
153* Scan the array, true indices are required values.
154
155@ All prime factors of a number :- O(n^(1/2))
156* If the number is divisible by 2, keep on dividing it by 2 till its not. (Gives the power of 2)
157* Start loop from 3 till sqrt(n), incrementing iterator(i) by 2...
158* If i divides n, keep on dividing the number by i till its not. (Gives the power of i)
159* If the number survives the above steps, check if it is greater then 2, if yes then the number is itself a prime.
160
161@ Convert integer to Hex :-
162* pick last 4 bits of the num (num & 15)
163* get corresponding value from the array (0,1,2....,e,f), append to the result string.
164* right shift num by 4 bits.
165
166@ Find intersection of two Linked Lists (Two Pointers)
167* initialize t1=head1 and t2=head2
168* traverse the pointers in their respective lists till either of them reaches end,
169* if in the midway, they converge to the same address, return that node.
170* if either of them reaches NULL, redirect them to the head of the other list and continue traversing.
171
172@ Remove kth node from the end of a linked list.
173* create a dummy node and attach it to the head. Make head point the dummy node.
174* take aux pointer to nth pos in the list. create another dummy node pointing to head.
175* move both pointers till the first aux pointer`s next is NULL.
176* the second aux's pointer's next is the node to be deleted.
177
178@ Infix to Prefix:
179* reverse the string, replace ')' with '(' and ')' with `(`
180* find corresponding postfix expression.
181* reverse the postfix expression to get the prefix expression.
182
183@ To find the minimum number of swaps to make an array sorted (if only adjacent swapping is allowed)
184* Find the inversion count in the array
185
186@ Search for an element in a matrix in which elements are ascending in top to bottom and left to right. O(m+n)
187* start from left-bottom element.
188* if(matrix[row][col]==target) return true
189* if(matrix[row][col]>target) row--
190* else if(matrix[row][col]<target) col++
191
192@ Next Permutation (lexicographic)
193* If the sequence is in decreasing order, return its reverse.
194* Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
195* Find the highest index j > i such that s[i] < s[j]. Such a j must exist, since i+1 is such an index.
196* Swap s[i] with s[j].
197* Reverse the order of all of the elements after index j till the last element.
198
199
200@ Word Ladder
201* bfs algorithm will be used to create a graph. Words with a single letter differing will have an edge between them.
202* unordered set will be used to search for words by altering a letter of a word at a position.
203* if the word is found, remove it from the given dictionary and add it to the queue.
204* when the target word is found, return the count.
205
206@ Anagrams of a substring in a string
207* Use sliding window mechanism.
208* Count the occurence of characters in the pattern and the first p letters in the string beforehand.
209* Slide the window, decrease the previous letter`s count, increase the current letter`s count and compare the vectors.
210* If both vectors same, add the index to the resultant array.
211
212@ Converting a word into a 32 bit integer
213* for i=0 to word.size()
214* val= val | 1<<(word[i]-'a')
215
216@ To get the minimum absolute difference in a binary tree, get pairwise minimum difference through inorder traversal.
217
218@ http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
219
220@ To find the position or the count of the occurence of a pattern in a string, Z-ALGORITHM is used.
221
222@ While generating PERMUTATIONS using BACKTRACKING, condition for unique entries :
223 if( i != index && nums[i] == nums[index]) continue;
224
225@ While generating distinct SUBSETS using BACKTRACKING, condition when ignoring the element at index i :
226 if(temp.empty() || temp.back()!=nums[i]) subsets(nums,temp,i+1)
227
228@ To Merge Overlapping intervals, use a stack.
229 -- sort the intervals based on their start time. Insert the first interval in stack.
230 -- compare the incoming interval with the stack`s top interval, if they are overlapping, merge them.
231 -- else push this interval to the stack
232
233@ Top frequent k elements
234 -- make count map (number,count)
235 -- copy to map to a vector of pairs
236 -- sort vector on second element of pairs
237 -- return the first elements of top k pairs
238
239@ Longest Consecutive Sequence
240* Insert all elements into an unordered set.
241* For every element x,
242 * Check if x-1 is present in the set.
243 * If not, then count number of elements in the consecutive starting with this element.
244 * If count is more than current res, then update res.
245
246@ To validate a SUDOKU config,
247* For every (i,j), use a set in its corresponding row, col and block.
248
249@ Minimum number of appends to make the string palindrome
250* Keep on deleting characters from front till you get a palindrome.
251* Return the count of the deleted characters.
252
253@ Minimum number of insertions at beginning to make the string palindrome
254* Keep on deleting characters from end till you get a palindrome.
255* Return the count of the deleted characters.
256
257@ nth fibonacci number
258* find (n-1)th power of [[1,1],[1,0]] using fast exponentiation
259* return F[0,0]
260
261@ To find kth smallest number in an unsorted array
262* Use max heap(priority queue).
263* Insert first k elements in the heap.
264* For every (k+1)th to (n-1)th element, if arr[i] < pq.top(), pq.pop() and insert vec[i] (heapify)
265
266@ Swap even and odd position bits of a number
267* a = n & 0xAAAAAAAA, b = n & 0x55555555 (even and odd bits respectively)
268* a = a >> 1, b = b << 1
269* return (a | b)
270
271@ Check if a set of strings form a chain of circle
272* Create graph taking first and last characters of the string
273* Chain of circle exists if :
274 - if indegree and outdegree of each character is same
275 - A single dfs visits all the characters
276
277@ To implement LRU cache, use list(as queue) and unordered_map<int,list<int>::iterator> to find the page in the cache
278
279
280
281--------------------------------------------------------DYNAMIC PROGRAMMING-------------------------------------------------------
282
283@ Longest common subsequence
284* first row and first column all 0`s
285* if(str1[i-1] != str2[j-1]) matrix[i][j] = max(matrix[i-1][j-1],matrix[i-1][j])
286* if(str1[i-1] == str2[j-1]) matrix[i][j] = matrix[i-1][j-1]+1;
287
288@ Longest common substring
289* first row and first column all 0`s
290* if(str1[i-1] != str2[j-1]) matrix[i][j] = 0
291* if(str1[i-1] == str2[j-1]) matrix[i][j] = matrix[i-1][j-1] + 1;
292
293@ Longest increasing subsequence
294* Initialize auxilliary array temp of size n with 1.
295* Run i from 1 to n-1, run j from 0 to i,
296* if nums[i] > nums[j] , check if temp[j] + 1 > temp[i], if yes then temp[i] = temp[j] + 1
297* return max element in temp.
298
299@ minimum cost path to reach from (0,0) to (m-1,n-1)
300* matrix[i][j] = min(cost[i-1][j-1] , cost[i][j-1],cost[i-1][j]) + cost[i][j]
301* return matrix[m-1][n-1]
302
303@ Coin change problem
304* vec[j] = vec[j-coins[i]]
305* return vec[amount]
306
307@ Box stacking
308* Generate all rotations of a box dimension
309* sort the base of all rotations in descending order
310* Apply LIS on height
311
312@ Divide in two subsets such that subsets` sum difference is minimum
313* Build the table bottom up using subset sum(true/false).
314* Check if in last row from sum/2 down to 0, if an entry is true
315 - return sum - 2*j
316
317@ Longest palindromic substring :-
318APPROACH 1 ----> O(N^2) time and space
319 * since all single letter strings are palindrome, matrix[i][i]=true.
320 * initialize start=0 (starting index of longest length palidomic substring), max_len=1 (maximum length of the susbtring)
321 * check all two letter strings, if s[i] == s[i+1], matrix[i][i+1]=true.
322 * check all substrings of length greater than 2, for each sustring of size k>2, check from i=0 to i=L-k,
323 j = i+k-1
324 if s[i]==s[j] and matrix[i+1][j-1]==true,
325 matrix[i][j]=true, max_len=max(max_len,k), start=i
326 * extract the substring from index start till start+max_len-1, return the substring.
327
328APPROACH 2 ----> O(N^2) time and constant space (Expand around center)
329 * For every char in string, expand around center and find the max length.
330 * expand(i-1,i+1)(odd length palindromes), expand(i-1,i)(even length palindrome)
331 * update start and maxLen for each palindrome iteration.
332 * return substring [start , start+maxLen-1]
333
334//Manacher's algorithm to be added here...
335
336@ Edit distance(minimum edits to convert one string to another)
337* if i == 0, matrix[i][j] = j
338* if j == 0, matrix[i][j] = i
339* if str1[i-1] == str2[j-1], matrix[i][j] = matrix[i-1][j-1]
340* else matrix[i][j]= 1 + min(matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1])
341
342@ Largest product subarray
343* three variables, max_ending_here=0, min_ending_here=0, max_so_far=INT_MIN
344* if(nums[i]>0),
345 max_ending_here = max(max_ending_here*nums[i],nums[i])
346 min_ending_here = min_ending_here*nums[i]
347* if(nums[i]==0),
348 max_ending_here = 0
349 min_ending_here = 0
350* if(nums[i]<0),
351 max_ending_here = min_ending_here*nums[i]
352 min_ending_here = min(max_ending_here(previous)*nums[i],nums[i])
353 * max_so_far=max(max_ending_here,max_so_far)
354
355@ Largest rectangular area in matrix containing 1s and 0s
356* Declare temp vector.
357* Scan the matrix row wise, if row element is 0 temp[i]=0 else temp[i]+=matrix_element
358* After every row is scanned, calculate the max area of the rectangle (histogram method) formed by the temp vector. Return that area.
359* Compare this area after scanning every row. Return the max_area finally.
360
361@ Maximum sum rectangle in 2d matrix using kadane`s algorithm O(n^3)
362* Apply kadane`s algorithm on every column cumulatively and obtain the sum everytime.
363* max_sum thus obtained will be the required solution.
364
365@ Longest Arithmetic Progression subsequence
366* initialize tab[][] with 2 //smallest size of AP sequence
367* for every middle element in the array(n-2:1), initialize a left = mid - 1 and right = mid + 1 elements and traverse such that
368 * if(nums[left] + nums[right] > 2 * nums[mid]) l--;
369 * if(nums[left] + nums[right] < 2 * nums[mid]) r++;
370 * else {tab[l][m] = tab[m][r] + 1; max_len = max(max_len,tab[l][m])}; l--; r++;
371* return max_len
372
373@ Word Break
374* declare a boolean array of size len+1,vec[0]=true
375* for i=1 to len and j=0 to i-1
376* extract substring from j of (i-j) characters.
377* check if substring exists in dict, if yes then vec[i]=true and break out of j loop.
378
379@ Decode Ways
380* for i =2 to len check if substring(i-1,1) and substring(i-2,2) come in [1,9] and [10,26] range,
381* vec[i]+=vec[i-1] (for 1st condition)
382* vec[i]+=vec[i-2] (for 2nd condition)
383* return vec[len]
384
385@ Longest chain when a set of pairs eg (a,b),(c,d) such that b<c
386* Sort the given pairs in ascending order on the basis of first element.
387* Apply longest increasing subsequence on the resultant sequence.
388
389@ Count numbers with unique digits
390* count = 9, res = 10
391* for i = 2 to n
392 count = count * (10 - i + 1); res += count;
393
394@ To find the minimum number of insertions to make string Palindrome
395* Calculate LCS of string vs reverse(string)
396* return n - LCS
397
398@ To find the minimum number of deletions to make the string Palindrome
399* Calculate Longest Palindromic Subsequence of string say LPS
400* return n - LPS