Scribd
Upload
92 views3 pages

DSA CheatSheet

This cheat sheet provides quick strategies for various coding problems, including techniques like Binary Search for sorted arrays and Backtracking for permutations. It outlines specific methods for data structures such as trees, graphs, and linked lists, as well as approaches for in-place modifications and dynamic programming. Additionally, it suggests using maps and sorting for general problem-solving efficiency.

Uploaded by

rajanravi006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
92 views3 pages

DSA CheatSheet

This cheat sheet provides quick strategies for various coding problems, including techniques like Binary Search for sorted arrays and Backtracking for permutations. It outlines specific methods for data structures such as trees, graphs, and linked lists, as well as approaches for in-place modifications and dynamic programming. Additionally, it suggests using maps and sorting for general problem-solving efficiency.

Uploaded by

rajanravi006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Coding Interview Cheat Sheet – Read This

in a Hurry!
1️⃣ If Input Array is Sorted
Use Binary Search → If looking for a position or searching for an element.
Time Complexity: O(log n) (Faster than a linear scan).

Use Two Pointers → If finding pairs (e.g., sum = target).


Time Complexity: O(n) (Efficient for sorted arrays).

2️⃣ If Asked for All Permutations/Subsets


Use Backtracking → When exploring all possibilities.
Key Idea: Build solutions incrementally, remove invalid paths (pruning).

3️⃣ If Given a Tree


Use DFS (Depth-First Search) → If exploring deep paths, max depths, or finding paths.
Use BFS (Breadth-First Search) → If doing level-order traversal or shortest path.

DFS = Recursive (Stack) | BFS = Queue

4️⃣ If Given a Graph


Use DFS → When exploring paths, cycles, or topological sorting.
Use BFS → When finding shortest paths or connected components.

DFS = Deep search | BFS = Level-wise search

5️⃣ If Given a Linked List


Use Two Pointers → If detecting cycles, finding the middle, or reversing a list.
Fast Pointer = 2 Steps | Slow Pointer = 1 Step
6️⃣ If Recursion is Banned
Use a Stack → If recursion leads to stack overflow.
Key Idea: Simulate recursion manually with a stack.

7️⃣ If You Must Solve In-Place (No Extra Memory Allowed)


Swap Corresponding Values → If reversing an array or swapping elements.
Store Multiple Values in the Same Pointer → If modifying arrays efficiently.

Goal: Keep O(1) space complexity.

8️⃣ If Asked for Maximum/Minimum Subarray/Subset


Use Dynamic Programming (DP) → If problem involves overlapping subproblems.
Key Idea: Store intermediate results to avoid redundant calculations.

9️⃣ If Asked for Top/Least K Items


Use a Heap → If dynamically finding the k-th largest/smallest element.
Heap Operations: O(log n)

Use QuickSelect → If finding k-th element without sorting.


Time Complexity: O(n) on average (Faster than sorting).

If Asked for Common Strings


Use a Map (Hash Table) → If tracking string occurrences (O(1) lookup).
Use a Trie → If searching prefixes or matching strings dynamically.
1️⃣1️⃣ General Strategy for Any Problem
Use Maps/Sets → If checking for uniqueness or fast lookups (O(1)).
Sort First, Then Apply Logic → If binary search or k-th element problems.

Summary – What to Use & When?


Problem Type Best Technique
Sorted Array Binary Search, Two Pointers
Permutations/Subsets Backtracking
Trees DFS, BFS
Graphs DFS, BFS
Linked Lists Two Pointers
No Recursion Allowed Use a Stack
In-Place Modifications Swap, Store in Pointer
Max/Min Subarray Dynamic Programming
Top K Elements Heap, QuickSelect
Common Strings Map, Trie
General Problems Maps/Sets, Sorting

You might also like