-
Notifications
You must be signed in to change notification settings - Fork 19
/
Copy path🔰important_revision.txt
199 lines (158 loc) · 10.5 KB
/
🔰important_revision.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
NOTE: '>' is path shown in the repo!
📌️ Algorithms:
1. Sorting Techniques | algorithms > sorting
2. KMP- Knuth Morris Pratt String Matching algorithm (How Pi Table works) | algorithm > string > pattern_matching
📌️️ Sorting:
1. Merge sort (divide and conquer) | single items are always sorted | 2 pointer to merge array
Questions:
- Count inversions
- Smallest string
2. Quick Sort (divide and conquer) | pivot (always want to do quickly!) | left to placed pivot are all less | right items are all >
Questions:
- kth largest in array
📌️️ Questions:
1. Burglar Thief/Pick max adjacent number
2. Next Permutation problem (repeated many times)
3. One Edit distance/ Levenshtein problem
4. Minimum window substring (many similar questions)
5. Inversion of array (Similar to Merge sort)
NOTE: Minimum swaps to sort & count inversions are different question.
- Count inversions is completely different thing(it asks to check num[i]>num[j] where i<j)
- Whereas, Minimum swaps just asks to count minimum swaps required.
6. kth largest in array (Similar to Quick Sort)
7. Angry Birds problem - many problems, similar solution - monotonic Binary Search
8. Maximize the minimum - Game of Greed, monotonic Binary Search
- (Maximize the minimum something) problem, check if taking values from (1....x) is possible - if yes it's monotonic Binary Search
9. Minimize the Maximum - Reading Books 🌟
10. Min Pairs problem - 2 array find smallest absoulte difference picking one from each
11. Create all possible subsequences of string, array
12. Generate valid parenthesis
13. ** Backtracking(Must do) - longest_possible_route, NQueens, rat_maze, sudoku_solver
14. game_of_coins! (understanding how we are calculating all possible solutions and then deciding)
15. Reverse LinkedList in group of k! (k-reverse) - scratch/practice specific!
16. ** Next greater element, online stock span - important for stack! and when to use it!
17. Sliding window max - important to understand how queue helped to keep max present in window!
18. K smallest/greatest Questions indicate -> use Priority Q as it's better than sorting!
19. Finding running median - nice example of heap, priority_queue
20. **Merge k sorted list - intuition of min Heap is important, Also using comparator!
21. Swap sort - useful when 1 to N numbers given! - O(N)
22. Converting integer to binary quickly using bitset
23. Most frequent number in interval - imp to understand how we are keeping the range in map
24. Understanding Trie Data Structure - 'find string exists in array'
25. Do n-k-ladders dynamic programming all 3) types - imp to understand what we do in top-down(easy) & bottom-up approach
26. Longest common subsequence -> important to understand how we do 2D (diagonal movement if char matches)
- Also important to understand how we are priting the characters! (just backtracking :) )
27. Selling wines -> bottom up is important
- How we are relating recursion to iteration and grid understand is main logic
28. Longest alternative subsequence - O(n) approach (DP Problem)
------- ⭐️REVISE⭐️ + TUF_imp_revision.txt + TUF_graph_revision --------
1. Longest Increasing Subsequence (optimizing from o(N^2) to O(NlogN))
- Intuition- {1, 3, 6} -> 4 comes so {1, 3, 4} -> 4 replaces 6 by binary search! (Intuition)
- The fact we have a vector sorted(ans) is reason we could use binary search here
- ** If we want LIS array printed, we can't use it, as it will only check length!
- (Logic of replacement) Replacing 4 to 6 won't make any harm as until last of {} is not replaced we won't add more/ last one must be smallest possible
- By DP we can print array as well -> O(N^2)
2. Longest Alternative Subsequence
- Just make a graph going up and down
- You just need to keep a check on up/down peaks that's all
- Can be done in O(N), but looks like & can be done by DP as well
3. Inversion Count/ Reverse Pair ( both similar question )
- Basically we need to reduce complexity from O(N^2) to O(NlogN)
- And things could be little better we have have 2 sorted array where we can check the requirement
- And merge sort we have these arrays and hence we can easlily check it there
- In Reverse Pair, the method where we check is important as that logic is little tricky yet easy!
4. (Easy Level) Product of 3 numbers
- 2 cases, 1st is easy - prod of last 3 (works for both all pos and all neg)
- 2nd case - if some negative - prod of first 2 (that will give max pos) and third num is last one (last one will be max of positive)
5. 🌟 Permutation Sequence (MUST DO)
- Although we can do next_permutation k times but that won't be efficient solution
- Hence we make use of math trick i.e if we have 123 then 1 {2, 3} -> this will be total 2 sequence (0-1) and hence if we have k=1 we know it will be 132
- Hence we pick 1 and recursively take 2 {3} or 3 {2} based on remaining number
6. Postfix Notation
- We can use stack to cover all conditions in postfix evaluation!
- Pop two numbers when operators occur and do operation and store result back in
7. Hash Table
- Creation of hash table. Use array to store keys as index but of limited size
- Hence collision will occur, so make linkedin list at each index of above array
- Keep hash function (%1000) optimized -> try/error
8. Subsequence Sum (BS problem - important to check question)
- Can be done using DP - gives TLE
- Greedy approach is difficult to reach!
- Constraint A[i] - A[j] = i - j, hence we conclude A[i] - i = A[j] - j, hence all same difference must be conslidated together
9. Perfect Squares (BS Problem, Math, DP)
- Important to understand how to solve a math problem using DP
- We can just send num and check if it can be further reduced using a sqauare and recurse!
- We can do memoization as it's an overlapping subproblems!
10. The Accountant
- Problem asks to convert 27 to AA
- But the issue is it's given in 1 based indexing
- In the while loop just do n-- or consider num as (n-1) during each iteration (Crux of problem)
11. Interval Overlaps
- Important Question, makes use of just pointers and if else statments
12. Direct Clousure (BS Problem) - if path exists from each vertices to every other vertices
- 2 different solutions are possible
- Either do with DFS or with UnionFind
- View question/ans to understand
13. Maximum Non adjacent tree sum (BS Problem) - Good Question * LOGIC: Forgot even 2nd time -_-
- Don't send data from top to bottom
- return it from last
- This way at each node we can check if we are taking current root then .second of both
- Or else we can merge the max from left and right
14. Movie Theatre (BS Problem) - Good Interval problem
- Was confused about a basic logic of how to proceed
- here minHeap came to the advantage - didn't thought of this
- Q must be tried once in order to understand
15. Jump Game and Jump Game II Problem
- Jump game can be implemented using Dynamic Programming as multiple ways of solving is possible
- In Jump Game 2 we can also do DP but can be further optimised using Greedy approach by choosing intervals and jumping as far as possible and counting the jumps
15. Course Schedule - graph question
- Important to realize that it's a graph question, just after creating in scratch it should have been clear!
16. 🌟 (must do) Implement Trie
- LOGIC: Must understand these things!
- 1) We need a class to implement the node
- 2) TrieNode* val[123] -> array pointing to complete different array (important)
- 3) TrieNode* val[123] = {}; use {} else error is thrown
- 4) node pointed as the end is the next node basically (why? - because it's the exact character which is last)
⭐️ > previously I had marked the complete node with array[123] as the last and not the character inside it as the last due to which some test cases failed
17. 🌟 Maximal Square (Tricky!!)
- LOGIC: Intial intuition for DP part is tricky
- Instead of reading the '1' on top and left, we can make use of cache array itself top reach top and left index
- Why we are reading top and left '1's or using cache is important
18. 🌟 Path sum 3
- Prefix sum knowledge is required
- It's simple, just keep doing sum and rememer the sum seen so far
- If currSum - targetNeeded is seen somewhere that means soln exists
19. 🌟 Palindromic Substrings
- LOGIC: Need 2 things here
- 1) First start from the ind and keep moving outwards
- 2) Second start from the ind and ind+1 as this case won't be covered in 1)
20. 🌟 (Must check) Partition Labels (aaabdcakioppelll)
- LOGIC: Intuition was litte tedious but easy
- We just need to precalculate when the char is last occuring
- and now till that ind, we need to check if any in btw char is having even further occurance
- If yes update last occurance(end)
- If you reach last occurance(end) - just store the count and start over the counter.
21. 🌟 Decode String
- LOGIC: 1) thing is Intuition- is to use stack
- 2) thing is to push back the resultant after finding
- 2) point I couldn't understand
22. Binary Tree Zig-Zag Order Traversal/ Spiral Traversal of Tree ( Use 2 Stack! )
- LOGIC: intuition comes from scratch
- Make tree and use arrows to denote how to pick numbers
- Also, using more than 1 array, stack, queue should also be checked
23. (MUST CHECK) Gas Station (Optimization part is interesting)
- LOGIC: Brute force is easy, thinking about optimization is tedious part
- Yet, it's easy to think about the optimization part.
- As on reaching each station, we can refill the gas, and the amount of gas required to travel will be substracted
- Let's say the man travelled from index 3 to 7 and on 7 he had no more gas.
- So, even if you start from 4-6, still the man won't go beyond 7, let alone the complete cycle...
- But why? - because at each station we WILL HAVE 0 or more in surplus and if that couldn't help him go over 7 how will individual gas will help
24. 🌟 Sieve of eratosthenes (DO Check once as applied maths)
- LOGIC: Check solution directly, try once!
25. 🌟 Pair of songs divisible by 60 (MUST DO!!!)
- LOGIC: O(N^2) solution is clearly the first approach
- Optimized approach is in O(N) where we can pick the remainders! How?
- First understand that if we have 40, then we need to check 60 - ('40'%60) = 20 so find how many 20's are there
- As in if we have 80 -> that's a 20! because 40+80 will be 120 which is divisible by 60 and hence a valid pair!
- We can keep incrementing the remainders we find so that if we have 2 remainders then we can simply add them to result
- Why add them to result? because that's the number of new pairs we generate when a new number is added to it