Link to the SDE Sheet: view
Collection of the solutions in C++
| S.No. | Question Name | Logic Used | Topic | Date |
|---|---|---|---|---|
| 1 | Missing and Repeating | repeated xor | Bit Manipulation | 02 June 21 |
| 2 | Duplicate Number | Linked List Cycle Detection | Arrays and Linked List | 02 June 21 |
| 3 | Merge Sorted Space in O(1) Space | Gap Method: Shear Sort | Sorting | 02 June 21 |
| 4 | Set Matrix Zeros | in place, bottom to top, right to left | Matrix | 03 June 21 |
| 5 | Reverse Pairs Count | count inversions using merge sort | Arrays | 04 June 21 |
| 6 | Reverse in Groups of K | addFirst, original and temp pointers | Linked List | 06 June 21 |
| 7 | Clone list with random pointers | adjacent copy nodes | Linked List | 07 June 21 |
| 8 | Trapping Rainwater | 2 pointers, min(max_left, max_right) - arr[i] | Two Pointers | 07 June 21 |
| 9 | Job Sequencing | n-slots, job index in sorted array | Greedy | 08 June 21 |
| 10 | Minimum Railways Platforms | sorted: arrival vs dep times | Greedy | 08 June 21 |
| 11 | Combination Sum without repetition | recursion with 2 options; avoid duplicates | Bactracking | 12 June 21 |
| 12 | Permutations of an Array | fixing first position, all swaps | Backtracking | 13 June 21 |
| 13 | Rat in a Maze | backtracking, dfs calls in 4 directions | Backtracking | 14 June 21 |
| 14 | M Coloring Graph | backtracking, trying every color | Bactracking | 17 June 21 |
| 15 | Median of 2 Sorted Arrays | Contribution size partitioning of smaller array | Binary Search | 17 June 21 |
| 16 | Allocate min pages | monotonic search space of min possible max upper bound | Binary Search | 25 June 21 |
| 17 | Median in Row sorted matrix | count of left part of sorted array; upper_bound | Binary Search | 26 June 21 |
| 18 | Count Total Set Bits | f(n)=x*2^(x-1)+(n-2^x+1)+f(n-2^x) | Recursion | 26 June 21 |
| 19 | Find nearest power of 2 <= n | one by one set all the bits | Bit Manipulation | 26 June 21 |
| 20 | Square of a number | Left shift + recursion | Bit Manipulation | 27 June 21 |
| 21 | LRU Cache Design | Hashing + DLL {latest used on left near head} | Linked List | 30 June 21 |
| 22 | Sliding Window Maximum | Deque + store max at dq front | Deque + Sliding Window | 01 July 21 |
| 23 | Largest rectangle in Histogram | 3 vars: i-->nse, top = height, below top = pse | Stacks | 01 July 21 |
| 24 | Longest Palindromic Substring | Two pointer consecutive + 1 gap apart expansion | Strings | 01 July 21 |
| 25 | Integer to Roman | Store the exception symbols like 1, 4, 5, 9, etc | Maths | 01 July 21 |