DSA Cheat Sheet

Intermediate · 12 min read · Interview Playbook, Interview Playbook

Every pattern, template and complexity on one page for revision.

This page is for revision, not for learning: use it the night before an interview or as a warm-up before a mock. Each pattern gets its signal, its template and its cost on one screen. Every template is copied from its lesson, and the code is verified in this site's Java test suite.

Complexity budget

Java collections

Pattern → signal → cost

Arrays and strings

Two pointers (opposite ends / read–write):

Binary search

One template covers both kinds. Use it to search positions in sorted data, or to search a range of possible answers with a yes/no check:

Linked lists

Use a dummy node (ListNode dummy = new ListNode(0, head)) whenever the head might change.

Stacks and heaps

Monotonic stack (next greater element; store indexes):

Trees

DFS (trust the recursion and combine):

Graphs

Grid BFS (fewest steps). Mark cells visited when you enqueue them, and for multi-source BFS enqueue every source first:

Backtracking

The loop shape depends on what you're generating:

Dynamic programming

Define the state in words, write the recurrence, choose the base cases and the order of evaluation, then compress the space if you can.

Greedy, tries, bits

Design, matrices and advanced topics

LRU cache = HashMap<key, Node> plus a doubly linked list with sentinel head and tail. On get or put, unlink the node and add it at the front; when full, evict tail.prev. The node stores its key so eviction can delete it from the map.

Edge cases to test every time

Key takeaways

Constraints give the target complexity, and the target narrows the pattern.
Every pattern has a short template; know each one well enough to write it from memory.
Complexity always comes with a reason: count what each element does.
Test the edge-case table on every problem before saying "done".

Previous: Mock Interviews, Annotated · Next: Problem Tracker