TL;DR
- The point of an interview cheat sheet is not to read during the round but to pre-load common facts so working memory is free for reasoning.
- Memorize the big-O table, data-structure operation costs, sorting tradeoffs, graph algorithms, concurrency primitives, HTTP status codes, SQL versus NoSQL choices, system design building blocks, and capacity-estimation latencies.
- Read each table, cover it, reproduce it, then explain it out loud as if to a junior.
- You own a cheat sheet only when you can recreate it from scratch in under two minutes.
Introduction
You cannot open Google during an interview. The point of a cheat sheet is not to give you something to read during the round, it is to pre-load the facts you will need so your working memory is free for reasoning. The best interview candidates are not the ones who know more, they are the ones whose most common questions take up zero thinking cost.
This guide is a compact set of cheat sheets you should be able to recite. Read them. Then cover them and reproduce each table from memory. You will know you own them when you can draw the whole big-O table on a whiteboard in under two minutes.
Table of Contents
- How to use these cheat sheets
- Big-O complexity table
- Data structure tradeoffs
- Sorting algorithms comparison
- Graph algorithms cheat sheet
- Concurrency primitives
- HTTP status code map
- SQL versus NoSQL choices
- System design building blocks
- Capacity estimation numbers
- Common pitfalls and edge cases
- FAQ
- Conclusion
1. How to Use These Cheat Sheets
Do not print them and stare at them during the interview. Interviewers can tell. Instead, use this cycle:
| Day | Action |
|---|---|
| 1 | Read each table slowly |
| 2 | Cover the table, reproduce it |
| 3 | Explain each row out loud as if to a junior engineer |
| 4 | Write all tables from scratch |
| 5 | Recall during a warm-up set before a mock interview |
Knowledge becomes useful only after you can retrieve it under load. That is the bar.
2. Big-O Complexity Table
Common complexities, from fastest to slowest
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Hash lookup |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Single pass over array |
| O(n log n) | Linearithmic | Merge sort, quick sort average |
| O(n^2) | Quadratic | Nested loops over same array |
| O(n^3) | Cubic | Triple nested loops |
| O(2^n) | Exponential | Subset enumeration |
| O(n!) | Factorial | Permutation enumeration |
Core operations by data structure
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Dynamic array | O(1) | O(n) | O(1) amortized | O(n) | O(n) |
| Linked list | O(n) | O(n) | O(1) at known node | O(1) at known node | O(n) |
| Hash table | - | O(1) avg | O(1) avg | O(1) avg | O(n) |
| Binary search tree, balanced | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(1) top | O(n) | O(log n) | O(log n) top | O(n) |
| Trie | O(k) | O(k) | O(k) | O(k) | O(n*k) |
n is number of elements, k is length of key.
3. Data Structure Tradeoffs
When to pick what
| Need | Pick |
|---|---|
| Fast random access by index | Array |
| Fast key to value lookup | Hash table |
| Ordered keys with range queries | Balanced BST or sorted map |
| Top-K by priority | Heap |
| Frequent prefix lookup | Trie |
| Membership test with small memory | Bloom filter |
| LRU cache semantics | Doubly linked list plus hash |
| Disjoint sets / connectivity | Union-Find |
| Undo history, matching parens | Stack |
| BFS, rate limiting queue | Queue |
| Range sum, range update | Fenwick tree or segment tree |
Hash table pitfalls
| Pitfall | Fix |
|---|---|
| Mutable keys | Use immutable types or tuples |
| Poor hash function on user-defined keys | Combine fields with a prime multiplier |
| Worst-case O(n) on collisions | Balanced bucket or rehashing |
| Iteration order assumptions | Use an explicitly ordered map |
4. Sorting Algorithms Comparison
| Algorithm | Best | Average | Worst | Space | Stable | In-place |
|---|---|---|---|---|---|---|
| Quick sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Yes |
| Tim sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Counting sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | No |
| Radix sort | O(d*(n+b)) | O(d*(n+b)) | O(d*(n+b)) | O(n+b) | Yes | No |
Quick choices under pressure
| Situation | Use |
|---|---|
| Small n, partially sorted | Insertion sort |
| Large n, general | Tim sort (default in Python, Java) |
| Limited memory, worst case critical | Heap sort |
| Stable sort required | Merge sort |
| Integers in known bounded range | Counting or radix sort |
5. Graph Algorithms Cheat Sheet
Traversal and shortest path
| Algorithm | Use | Complexity | Notes |
|---|---|---|---|
| BFS | Shortest path in unweighted graph | O(V+E) | Queue based |
| DFS | Components, cycles, topological sort | O(V+E) | Stack or recursion |
| Dijkstra | Shortest path, non-negative weights | O((V+E) log V) | Min-heap |
| Bellman-Ford | Shortest path with negative weights | O(V*E) | Detects negative cycles |
| Floyd-Warshall | All-pairs shortest path | O(V^3) | Dense graphs only |
| A* | Shortest path with heuristic | Depends on heuristic | Needs admissible heuristic |
Spanning tree and connectivity
| Algorithm | Use | Complexity |
|---|---|---|
| Prim | MST, dense graphs | O(E log V) |
| Kruskal | MST, sparse graphs | O(E log E) |
| Union-Find | Connectivity queries | Nearly O(1) amortized |
| Tarjan | Strongly connected components | O(V+E) |
| Kosaraju | Strongly connected components | O(V+E) |
6. Concurrency Primitives
Common primitives
| Primitive | Purpose | Typical API |
|---|---|---|
| Mutex | Exclusive access to a resource | lock, unlock |
| Read-write lock | Many readers or one writer | rlock, wlock |
| Semaphore | Bounded number of concurrent users | acquire, release |
| Condition variable | Wait for a predicate | wait, signal, broadcast |
| Barrier | Synchronize N threads at a point | await |
| Channel | Message passing between workers | send, receive |
| Atomic | Lock-free single-variable ops | load, store, CAS |
| Future or Promise | Eventual value | await, then |
Concurrency bugs map
| Bug | Cause | Detection |
|---|---|---|
| Race condition | Unsynchronized shared state | Stress tests, TSan |
| Deadlock | Cycle of locks | Lock order graph |
| Livelock | Threads yield to each other indefinitely | Backoff with randomization |
| Starvation | Unfair scheduling | Use fair locks, queues |
| Priority inversion | Low-priority holds lock high-priority needs | Priority inheritance |
| Double-checked locking errors | Unsafe publication | Use language-appropriate patterns |
Memory ordering basics
| Model | Guarantees |
|---|---|
| Sequential consistency | Strict, global order |
| Acquire-release | Orders synchronization between threads |
| Relaxed | Only atomicity, no ordering |
| Happens-before | Partial order via release-acquire pairs |
7. HTTP Status Code Map
Classes
| Range | Meaning |
|---|---|
| 1xx | Informational |
| 2xx | Success |
| 3xx | Redirection |
| 4xx | Client error |
| 5xx | Server error |
Codes you should know cold
| Code | Name | When |
|---|---|---|
| 200 | OK | Success |
| 201 | Created | New resource created |
| 202 | Accepted | Queued for async processing |
| 204 | No Content | Success with empty body |
| 301 | Moved Permanently | Long-term redirect |
| 302 | Found | Temporary redirect |
| 304 | Not Modified | Cached resource valid |
| 400 | Bad Request | Client-side validation failure |
| 401 | Unauthorized | Missing or invalid auth |
| 403 | Forbidden | Auth valid but no permission |
| 404 | Not Found | Resource does not exist |
| 409 | Conflict | Version conflict or duplicate |
| 422 | Unprocessable Entity | Semantic validation failure |
| 429 | Too Many Requests | Rate limit exceeded |
| 500 | Internal Server Error | Generic server failure |
| 502 | Bad Gateway | Upstream failure |
| 503 | Service Unavailable | Overloaded or down |
| 504 | Gateway Timeout | Upstream did not respond |
Common HTTP method behaviors
| Method | Idempotent | Safe | Cacheable |
|---|---|---|---|
| GET | Yes | Yes | Yes |
| HEAD | Yes | Yes | Yes |
| POST | No | No | Rarely |
| PUT | Yes | No | No |
| PATCH | No | No | No |
| DELETE | Yes | No | No |
| OPTIONS | Yes | Yes | No |
8. SQL Versus NoSQL Choices
When to pick which
| Need | Pick | Reason |
|---|---|---|
| Strong transactions, joins | Relational | ACID, referential integrity |
| Flexible schema, write volume | Document | JSON-native, horizontal scale |
| Time-series telemetry | Time-series DB | Optimized compression, retention |
| Massive key-value lookups | Key-value | O(1) lookup, partitioned |
| Graph traversals | Graph DB | Native relationship indexing |
| Full-text search | Search engine | Inverted index, ranking |
| Analytics over TB | Columnar warehouse | Scan compression, MPP |
Consistency options you must explain
| Term | Meaning |
|---|---|
| Strong consistency | A read reflects the latest successful write |
| Eventual consistency | Reads converge after some delay |
| Read-your-writes | A client sees its own writes immediately |
| Monotonic reads | A client never sees older data after newer |
| Causal consistency | Operations with cause-effect order are preserved |
9. System Design Building Blocks
Core components to recognize
| Block | Purpose | Typical choice |
|---|---|---|
| Load balancer | Spread traffic | L7 reverse proxy |
| API gateway | Auth, routing, rate limit | Managed gateway |
| Stateless services | Horizontal scale | Containerized fleet |
| Relational database | Source of truth | Managed Postgres |
| Cache | Reduce read latency | In-memory distributed cache |
| Message queue | Decoupling, buffering | Broker with durable queues |
| Object store | Blobs and large files | Cloud object storage |
| Search index | Full-text and filtering | Inverted index service |
| Stream processor | Real-time aggregation | Stream platform |
| Batch processor | Nightly jobs | Distributed batch engine |
| CDN | Static and cacheable content | Edge delivery network |
| Monitoring | Metrics, logs, traces | Observability stack |
Common design patterns
| Pattern | Use |
|---|---|
| Read replicas | Scale reads |
| Sharding by user id | Scale writes and storage |
| CQRS | Separate read and write models |
| Event sourcing | Replay and audit |
| Saga | Distributed transactions |
| Leader-follower | Writes to leader, reads from followers |
| Consistent hashing | Sharding that survives node changes |
| Write-through cache | Cache always consistent with DB |
| Write-back cache | Higher write throughput, risk on crash |
| Rate limiter | Protect services from abuse |
| Circuit breaker | Stop cascading failure |
| Bulkhead | Isolate failure domains |
10. Capacity Estimation Numbers
Latencies you should know cold
| Operation | Latency |
|---|---|
| L1 cache | ~1 ns |
| Branch mispredict | ~5 ns |
| L2 cache | ~4 ns |
| Mutex lock/unlock | ~25 ns |
| Main memory | ~100 ns |
| Compress 1 KB | ~2,000 ns |
| Send 2 KB over 1 Gbps | ~20,000 ns |
| SSD random read | ~150,000 ns |
| Round trip same datacenter | ~500,000 ns |
| Read 1 MB sequentially from memory | ~250,000 ns |
| Read 1 MB sequentially from SSD | ~1 ms |
| Disk seek | ~10 ms |
| Cross-continent round trip | ~150 ms |
Sizing shortcuts
| Figure | Approximation |
|---|---|
| Seconds in a day | ~10^5 |
| Seconds in a month | ~2.5 x 10^6 |
| Bytes in a TB | 10^12 |
| Chars in a tweet | ~280 |
| DAU:QPS rule of thumb | DAU / 86400 x peak factor |
| Peak to average ratio | 2x to 10x |
| Read:write on social feed | 100:1 |
| Write amplification on SSD | 2x to 10x |
11. Common Pitfalls and Edge Cases
Coding pitfalls
| Category | Classic edge case |
|---|---|
| Arrays | Empty, single element, all duplicates |
| Strings | Empty string, unicode, whitespace |
| Trees | Empty tree, single node, skewed |
| Graphs | Disconnected components, self-loops |
| Recursion | Max recursion depth |
| Integer math | Overflow, negative zero, division by zero |
| Floating point | Precision, NaN, infinity |
| Concurrency | Empty queue on consumer start |
| IO | Partial reads, EOF in the middle of a record |
Design pitfalls
| Category | Classic pitfall |
|---|---|
| Cache | Cold start, thundering herd |
| Queue | Poison messages |
| DB | Hot partitions |
| Auth | Token replay |
| Rate limit | Clock skew across nodes |
| Retry | No jitter, cascading load |
| Rollout | No canary, no rollback plan |
12. FAQ
Q: Should I memorize all of these tables? Yes for big-O, HTTP status, concurrency primitives, and capacity numbers. The rest should be at the level where you can reproduce them on a whiteboard given five minutes.
Q: Do I need to know all sorting algorithms? You should know quick sort, merge sort, heap sort, and insertion sort cold. Counting and radix are bonus knowledge for interviews about ranges of integers.
Q: How do I practice retrieval? Cover the table and reproduce it. Explain each row out loud. Do it once a day for a week before the interview.
Q: What about new databases and tools? Learn the categories first: relational, document, key-value, columnar, graph, search, time-series. Specific product names are less important than mapping the shape of the need.
Q: Are cheat sheets allowed during remote interviews? Written notes are usually fine, but reading from them visibly is a negative signal. Treat the cheat sheet as prep, not as an aid during the round.
Q: What if I forget a big-O mid-interview? Derive it. Count operations out loud. Interviewers prefer a candidate who reasons from first principles over one who recites the wrong memorized answer.
13. Conclusion
A cheat sheet is only as useful as your ability to recite it under pressure. The goal is not to keep the reference nearby, it is to internalize the reference. The tables above represent the minimum vocabulary required to perform at a top engineering interview: big-O, data structure operations, concurrency primitives, HTTP, SQL and NoSQL choices, system design building blocks, and capacity numbers.
Copy them, cover them, reproduce them, and explain them. When you can do that without looking, your working memory is free for the parts of the interview that actually require thinking: decomposing the problem, making tradeoffs, and communicating clearly. That is the real value of a cheat sheet, and that is why every senior engineer keeps one quietly in their head.
Frequently asked questions
What should be on a software engineer interview cheat sheet?The minimum: big-O complexity for common operations, data-structure tradeoffs (array, hash table, BST, heap, trie), sorting algorithms, graph algorithms (BFS, DFS, Dijkstra, Union-Find), concurrency primitives, HTTP status codes, SQL versus NoSQL choices, system design building blocks, and capacity-estimation numbers like cache, memory, SSD, and cross-continent latencies.
What latency numbers should I memorize for system design interviews?Know these cold: L1 cache around 1 ns, main memory around 100 ns, SSD random read around 150 microseconds, round trip same datacenter around 500 microseconds, disk seek around 10 ms, and cross-continent round trip around 150 ms. These power back-of-the-envelope calculations on whether to cache, replicate, or shard.
Are cheat sheets allowed to look at during a remote tech interview?Written notes are usually fine, but visibly reading from a cheat sheet during the round is a negative signal. Treat the cheat sheet as preparation, not as an in-round aid. The goal is to internalize the tables so you can recall them without breaking eye contact or pausing your narration.
What is the difference between SQL and NoSQL choices in interviews?Pick relational for strong transactions and joins (ACID, referential integrity). Pick document for flexible schema and write volume (JSON-native, horizontal scale). Pick key-value for massive O(1) lookups, columnar for analytics over terabytes, time-series for telemetry, graph for relationship traversals, and search engines for full-text.
What concurrency primitives do tech interviewers expect me to know?Mutex (exclusive lock), read-write lock (many readers or one writer), semaphore (bounded concurrency), condition variable (wait for a predicate), barrier (synchronize N threads), channel (message passing), atomic operations (lock-free CAS), and futures or promises. Also know the common bugs: race conditions, deadlock, livelock, starvation, and priority inversion.