Pattern Wise goes topic by topic. Last Minute 100 is the short version for when the interview is close.
Building mastery one problem at a time — keep the momentum going!
Service Based Company sheet — the DSA problems most frequently asked by service-based / IT-consulting firms (TCS, Infosys, Wipro, Cognizant, Accenture, Capgemini, HCL), organized by pattern.
Contiguous, index-addressable collections — the substrate for most DSA patterns.
Use two indices that move towards or away from each other to reduce redundant comparisons.
Maintain a window of fixed size or expand/shrink it to satisfy a condition.
Precompute cumulative sums so any subarray or range sum can be answered in O(1).
Track the best subarray sum ending at each index and update the global maximum.
Work out the traversal order or recurrence by hand first, then translate it into index arithmetic with explicit boundary checks.
Sequence problems on characters — two-pointer, windowing and parsing.
Compare characters from both ends and move inward until the condition fails.
Maintain a moving window and adjust its size to satisfy character constraints.
Scan the string once and handle signs, overflow, and malformed input explicitly — these are graded on edge cases, not on complexity.
Halving the search space over sorted data or a monotonic answer range.
Divide-and-conquer → narrow search space in sorted array.
Find first/last occurrence or smallest/largest index satisfying a condition.
Treat answer space as sorted → binary search to find minimum/maximum feasible value.
Apply binary search row-wise / column-wise or flattened array.
Pointer manipulation on singly linked nodes.
Directly manipulate pointers to insert, delete, traverse, and get length.
Use two pointers at different speeds to detect cycles, middle node, or duplicates.
Reverse entire list, partial list, or groups to reorder nodes.
Merge sorted lists, sort list using merge sort, or reorder using middle + reverse + merge.
Use a stack to handle backward traversal, carry logic, or next greater node.
Nodes with prev+next pointers — O(1) insert/remove at both ends.
Maintain prev and next pointers carefully for insert, delete, traversal; use DLL + HashMap for O(1) cache operations.
O(1) average lookups — frequency counting, prefix maps and design.
Count elements to find majority, top-k frequent, or sort by frequency.
Track cumulative sums; map stores first occurrence → solve subarray sum problems.
Back the structure with a bucket array plus chaining, then implement hash, put, get, and remove on top of it.
LIFO structure — monotonic stacks, expression evaluation and design.
Maintain a monotonic increasing/decreasing stack to find next/prev greater/smaller, histogram ranges, or collisions.
Use two stacks or postfix evaluation to handle numbers and operators efficiently.
Simulate operations using a stack → pop on undo, remove adjacent duplicates, collapse characters.
Push opening symbols and validate closing ones; sometimes track count or score.
Use two stacks to implement another data structure or maintain extra info.
Solving a problem in terms of smaller instances of itself.
Solve problems by reducing them to a simpler instance of the same problem.
Binary tree traversals and structural queries.
Standard DFS → used for max depth, path sums, subtree calculations.
Use queue → traverse level by level → calculate sums, averages, or side views.
DFS recursion or parent-pointer mapping → find common ancestor efficiently.
Ordered binary trees — search, insert, delete and validation.
Leverage BST property (left < root < right) for search, insertion, deletion, and range queries.
BFS/DFS, topological ordering and union-find over vertices & edges.
Standard BFS → track distance/levels → queue-based traversal → multi-source if needed.
DFS recursion or stack → track visited → identify connected components or detect cycles.
DFS postorder or BFS (Kahn’s algorithm) → order nodes respecting dependencies.
Use Kruskal’s / Prim’s algorithm or Union-Find → find MST, minimum cost connections, or detect cycles.
Priority queues — top-K, k-way merge and running medians.
Use min-heap for top-k largest, max-heap for top-k smallest → maintain heap of size k.
Use min-heap to merge multiple sorted arrays/lists efficiently.
Build the heap yourself with sift-up/sift-down over an array, or hold two heaps — max-heap for the lower half, min-heap for the upper — and rebalance after every insert.
Systematic search with pruning over the decision tree.
At each level pick an unused candidate, recurse, then undo the pick; prune as soon as the partial answer overshoots the target.
Recurse on the index with two branches — include the element or exclude it — and record the path at each leaf.
Move in grid recursively → explore all valid paths → backtrack after each move.
Generate sequences or strings recursively by making a choice at each step.
Locally optimal choices — intervals, reachability and sorting.
Sort intervals or extend reach as far as possible from current position → maximize tasks done / minimize steps.
Sort array or select elements → make locally optimal choice → achieve global optimum.
Overlapping subproblems solved once and reused.
Track optimal solution using a 1D array → sequences, sums, or counts.
Use 2D array → track states for row/column → movement or path constraints.
Use 2D DP → index i,j represent substrings/subsequences → solve LCS, palindrome, or edit distance.
Track states based on weight/value → classic 0-1 / bounded / unbounded variants.
State machine DP to track whether you are holding a stock or not.
Prefix trees for string retrieval and segmentation.
Build Trie → insert words → search full word or prefix efficiently → collect suggestions in lexicographic order.
Use Trie for fast lookup → combine with DP or backtracking for word segmentation and concatenation.
Bitwise tricks for counting and set arithmetic.
Use XOR / AND / OR / shift operations → detect single/missing numbers or count bits efficiently.
Pure math with low pattern-reuse — kept outside the pattern tree.
Work digit by digit with / and %, and guard against overflow, zero, and negative inputs.