InternshipDSA quick reference
Which structure to reach for, and its cost.
| If the question says | Try |
|---|---|
Sorted array | Binary search or two pointers |
Longest or best stretch | Sliding window |
Have I seen this before? | Hash set or map |
Matching brackets, undo | Stack |
Shortest path, fewest steps | BFS |
Top k items | Heap |
Count the ways, best total | Dynamic programming |
All combinations | Backtracking |
| Structure | Typical cost |
|---|---|
Array | Index O(1), search O(n) |
Hash map | Insert and lookup O(1) on average |
Balanced tree | Insert and lookup O(log n) |
Heap | Insert O(log n), peek O(1) |
Linked list | Add at front O(1), search O(n) |