9622105
| Frage | Antworten |
| Find Longest Common Substring | Longest Common Suffix of all the Substrings ToDo: Tabulation and if same char, increment diagonal and place in current position |
| Longest Increasing Subsequence | O(n^2) 1) Iterate i and bring j from beginning 2) Get Maximum length & a[j] < a[i] 3) MaxLen + 1 OR 1 4) Max of final array is answer |
| LIS O(nlogn) | 1) S - Active Array, R - for Path, Len 2) Each index of S- Smallest element of that Size. A[0] = smallest 1 digit element 3) First check last index, if greater, new element in S 4) If less than first element, replace first element 5) Do CeilIndex search over middle elements. |
| Fibonacci | 1) Memoization 2) Power of Matrix "M" |F(n+1) F(n) | | F(n) F(n-1) | Power(M, n-1) => M[0,0] = F(n) Use Pow(M, n) Optimization for O(log n) |
| 0-1 Knapsack | 1) Do tabulation for different weights and [0, 1... TotalWeight] 2) If current weight <= j (linear dist of TotWeight) add profit 3) If not, copy value from previous weight iteration O(nW) |
| Longest Common SubSequence | 1) Retain the maximum length so far. 2) Take an example and check tabulation. http://ide.geeksforgeeks.org/nGQR66 |
Möchten Sie mit GoConqr kostenlos Ihre eigenen Karteikarten erstellen? Mehr erfahren.