Dsa | MNgo Interview PrepQUESTIONS (20 / 28)
Topic | Difficulty to Learn | Return on Investment |
Two Pointers | Easy | High |
Sliding Window | Easy | High |
Breadth-First Search | Easy | High |
Depth-First Search | Medium | High |
Backtracking | High | High |
Heap | Medium | Medium |
Binary Search | Easy | Medium |
Dynamic Programming | High | Medium |
Divide and Conquer | Medium | Low |
Trie | Medium | Low |
Union Find | Medium | Low |
Greedy | High | Low |
- Sliding Window - used to analyze specific sub-section of a Array / String
- window
- sub-array / substring / sub-sequence (meet some condition like max, min, target)
- METHODS:
- Expands or contracts the window to meet specific conditions
- Two Pointers - used to efficiently analyze specific segments of a Array / String
- Palindrome / Pair / Reverse
- METHODS:
- Same direction: used for scanning data in a single pass (e.g., fast and slow pointers to detect cycles or find middle elements).
- Opposite directions: used for finding pairs (e.g., sum of two numbers in a sorted array).
- Binary Search
- sorted stuffs (meet some condition like find, divide)
- BFS/DFS
- almost all graph (including tree) can be solved using them
- DFS: Dives deep into one path before exploring others
- BFS: Explores nodes level by level
- Priority Queue (Heap)
- kth largest / smallest / frequent / closest element
- top n largest / smallest / frequent / closest elements
- select something based on some priority
- Backtracking - extension of DFS - used to explore all possible paths
- go into depth looking for best optimized solution if the current is not optimized then go back and check at that point
- Builds the solution dynamically by making decisions and backtracking on invalid paths
- Dynamic Programming
- where ever recursion is used -> it can be optimized using DP
- Optimizes solutions by breaking problems into overlapping subproblems - solution of overlapping problems can be saved/memoized by pre-computing
- METHODS
- Top-down: recursive with memoization to store results.
- Bottom-up: solves smaller subproblems iteratively using a table.
- Greedy Algo
- pick best option at the point and move to next sub-problem
- min cost
- shortest path
- Divide & Conquer
- Divide problem in to non-overlapping sub-problems
