Lead: six theory prompts beside the coding task
Preparing for a technical interview? This guide covers the six most common theoretical questions about algorithms and data structures—the exact ones that come up in coding interviews at top tech companies. Whether you're just starting your interview prep or brushing up on fundamentals, these answers will give you the confidence to tackle any algorithm question thrown your way.
Do not grind this page in silence. Close a hole on express quizzes, then say the trade-off out loud on a pair mock. The gym matches a partner. You host the call.
Disclaimer. These six questions sit beside a whiteboard task. Complexity and the “right” algorithm depend on size, memory, and how sorted the input already is. This is not a substitute for solving a specific problem, and the gym does not promise an offer.
1. Sorting algorithms: which ones should you know?
Sorting is the foundation of algorithmic thinking. Interviewers expect you to know how each algorithm works and when to pick which one.
Simple (O(n²)) — great for learning, rarely used in production
| Algorithm | How it works | Best use case |
|---|---|---|
| Bubble Sort | Repeatedly compares adjacent elements and swaps them if they are in the wrong order | Educational purposes; nearly sorted data (with optimization) |
| Selection Sort | Finds the minimum element and places it at the current position on each pass | When memory writes are expensive |
| Insertion Sort | Builds the sorted array one element at a time, inserting each new element into its correct position | Small datasets; nearly sorted data; online sorting |
Efficient (O(n log n)) — the interview favorites
| Algorithm | How it works | Key advantage | Key limitation |
|---|---|---|---|
| Quick Sort | Picks a pivot, partitions the array into smaller and larger elements, recursively sorts each partition | Fastest in practice; excellent cache performance; in-place | Worst case O(n²) when pivot selection is poor |
| Merge Sort | Recursively divides the array in half until single elements, then merges sorted subarrays | Guaranteed O(n log n) always; stable sort | Requires O(n) extra memory |
| Heap Sort | Builds a binary heap from the data, then repeatedly extracts the max/min element | In-place; guaranteed O(n log n) | Slower constant factors than Quick Sort; not stable |
Non-comparison sorts — when you know your data
| Algorithm | How it works | Time complexity | When to use |
|---|---|---|---|
| Counting Sort | Counts occurrences of each value, then reconstructs the sorted array | O(n + k) where k is the range | Integer data with a limited range |
| Radix Sort | Sorts digit by digit (least significant to most significant) | O(n × k) where k is the number of digits | Integers or strings with fixed-length keys |
Interview tip. When asked “which sorting algorithm is best?” — there is no single answer. The right choice depends on size, whether the data is nearly sorted, memory, and whether stability matters. Quick Sort dominates in practice for general-purpose sorting, which is why most standard libraries use it (or a hybrid like Timsort). Say that choice on a pair mock; close a hole in stable vs in-place on an express quiz.
2. Graph pathfinding algorithms: navigating the network
Graph traversal questions are a staple of technical interviews, especially at companies that work with maps, networks, or recommendation systems.
For weighted graphs (non-negative weights)
| Algorithm | What it does | Time complexity | Best for |
|---|---|---|---|
| Dijkstra’s Algorithm | Finds the shortest path from one starting node to all other nodes | O((V + E) log V) with a priority queue | GPS navigation, network routing |
| A* (A-Star) | Dijkstra’s algorithm plus a heuristic function estimating distance to the goal | Depends on heuristic quality | Pathfinding in games, maps (when you know the direction) |
For graphs with negative weights
| Algorithm | What it does | Time complexity | Best for |
|---|---|---|---|
| Bellman-Ford | Finds shortest paths from one source; handles negative edges; detects negative cycles | O(V × E) | Currency arbitrage detection, graphs with negative weights |
For unweighted graphs
| Algorithm | What it does | Time complexity | Best for |
|---|---|---|---|
| BFS (Breadth-First Search) | Explores level by level; finds shortest path by number of edges | O(V + E) | Shortest path in unweighted graphs, social network connections |
For all-pairs shortest paths
| Algorithm | What it does | Time complexity | Best for |
|---|---|---|---|
| Floyd-Warshall | Finds shortest paths between every pair of vertices | O(V³) | Dense graphs; when you need all-pairs distances |
Interview tip. The most common follow-up is “What if the graph has negative weights?” — that is your cue for Bellman-Ford. If the graph is unweighted, BFS is simpler to implement. Sketch BFS or Dijkstra on a deep quiz, then take it to a human on Find a partner.
3. Dynamic array vs linked list: the eternal trade-off
This is a fundamental comparison that tests your understanding of memory layout and performance characteristics.
| Criterion | Dynamic array (ArrayList, vector) | Linked list |
|---|---|---|
| Memory layout | Elements stored in contiguous memory | Nodes scattered in memory; each stores data + pointer(s) |
| Index access | O(1) — instant access via address calculation | O(n) — must traverse from head to the target node |
| Insert/delete at beginning | O(n) — must shift all subsequent elements | O(1) — just update the head pointer |
| Insert/delete at end | O(1) amortized (O(n) when resizing) | O(1) for doubly-linked with tail; O(n) for singly-linked |
| Insert/delete in middle | O(n) — shifting required | O(1) for the operation itself; O(n) to find the position |
| CPU cache efficiency | Excellent (data locality) | Poor (nodes scattered across memory) |
| Extra memory | Only for capacity buffer | Stores pointers/references |
The verdict. Use a dynamic array when you need fast random access and frequent iteration. Use a linked list when you have frequent insertions/deletions at the beginning or middle, and you rarely need index-based access. An LRU write-up belongs in a pet-project README — hash map plus a doubly-linked list, not “just a list”.
Trade-offs die if you only highlight them
Quick vs Merge, Dijkstra vs Bellman-Ford, array vs list — say the constraint first. A partner hears the pause. A quiz only marks the hole.
4. Balanced vs unbalanced binary search trees: why balance matters
A Binary Search Tree (BST) is only efficient when it is balanced. Here is what that means in practice.
| Characteristic | Balanced BST (AVL, Red-Black, Splay) | Unbalanced BST (naive BST) |
|---|---|---|
| Height | O(log n) | O(n) worst case (degenerates into a linked list) |
| Search / insert / delete | Guaranteed O(log n) | Average O(log n); worst case O(n) |
| Structure | Maintained via rotations, recoloring, or restructuring rules | Depends entirely on insertion order |
| Real-world use | Databases, file systems, standard libraries (std::map in C++, TreeMap in Java) | Educational purposes only; dangerous in production |
Why this matters. Imagine inserting sorted data (1, 2, 3, 4, 5, …) into a naive BST. You get a straight line — a linked list with O(n) search time. Balanced trees prevent this degeneration, guaranteeing logarithmic performance regardless of input order.
The takeaway. Never use a naive BST in production. Always choose a self-balancing variant.
5. What is a complete binary tree?
A complete binary tree is a binary tree where every level, except possibly the last, is completely filled, and all nodes on the last level are packed as far left as possible.
-
Level 0
A — the root. One node. The level is full.
-
Level 1
B and C. Two children. The level is full.
-
Level 2
D, E, F packed left. F has no right sibling. The last level is not full, but nothing sits to the right of a hole.
Why complete binary trees matter
| Property | Explanation |
|---|---|
| Array storage | A complete binary tree can be stored in a flat array without pointers |
| Index formulas | For a node at index i (0-based): left child = 2i + 1; right child = 2i + 2; parent = ⌊(i − 1) / 2⌋ |
| Heap implementation | Binary heaps (used in Heap Sort and priority queues) are complete binary trees |
| Height guarantee | Always ⌊log₂ n⌋ |
Interview connection. The heap — central to Heap Sort and priority queues — is a complete binary tree. That is why heap operations run in array form without explicit pointers. If graphs or heaps still stall, open a deep quiz.
6. Hash table collision resolution: two main strategies
Collisions are inevitable in hash tables. How you handle them determines performance. There are two fundamentally different approaches.
Strategy 1: separate chaining
| Aspect | Description |
|---|---|
| How it works | Each bucket holds a reference to a linked list (or another container) of all elements that hash to the same index |
| On collision | New element is appended to the list in that bucket |
| Advantages | Simple; performs well even at high load factors; deletion is straightforward |
| Disadvantages | Extra memory for pointers; poor cache locality |
Strategy 2: open addressing
| Aspect | Description |
|---|---|
| How it works | All elements stored directly in the table array; on collision, probe for the next free slot |
| Linear probing | h(k, i) = (h′(k) + i) mod m — simple, but causes primary clustering |
| Quadratic probing | h(k, i) = (h′(k) + c₁i + c₂i²) mod m — reduces clustering, but may fail to find a free slot |
| Double hashing | h(k, i) = (h₁(k) + i × h₂(k)) mod m — uses a second hash function; most effective |
| Advantages | Better cache performance; no extra memory for pointers |
| Disadvantages | Deletion requires tombstone markers; degrades sharply at high load factors |
Side-by-side comparison
| Criterion | Separate chaining | Open addressing |
|---|---|---|
| Memory overhead | Pointers for lists | None (array only) |
| Cache efficiency | Poor | Excellent |
| Deletion complexity | Easy | Requires tombstones |
| Load factor tolerance | Can exceed 1.0 | Must stay below 1.0 (typically < 0.7) |
| Clustering risk | None | Primary (linear), secondary (quadratic), reduced (double hashing) |
| Best for | High-load scenarios; unknown element count | Memory-constrained environments; cache-sensitive applications |
Interview tip. The most common follow-up is “How do you handle deletion in open addressing?” — tombstone markers. You cannot simply mark a slot as empty, because that would break probe sequences. Rehearse that sentence on Find a partner.
Quick reference: complexity cheat sheet
| Data structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Dynamic array | O(1) | O(n) | O(1)* | O(n) |
| Linked list | O(n) | O(n) | O(1) | O(1) |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash table | — | O(1)** | O(1)** | O(1)** |
| Binary heap | O(1) (min/max) | O(n) | O(log n) | O(log n) |
*Amortized. **Average case; worst case O(n).
Final thoughts: how to use this in your interview prep
These six questions form the theoretical backbone of almost every technical interview. Knowing the answers is not enough — you need to explain the trade-offs, connect complete binary trees to heaps to Heap Sort, and handle follow-ups: negative weights, collisions, nearly sorted data.
Ready to test it? Create an account, run an express quiz, then a human mock on Find a partner. Already have an account? Log in.
Questions people actually ask
Only one row stays open. These are follow-ups after a sorting or graph prompt, not a glossary.
-
Which sorting algorithm should I name first on a whiteboard?
There is no single best sort. Ask about size, nearly-sorted input, memory, and stability. Quick Sort is the usual general-purpose answer, or a hybrid like Timsort in standard libraries. Name Insertion Sort for small or nearly sorted data.
Link to this answer -
What if the graph has negative weights?
Dijkstra assumes non-negative weights. Switch to Bellman-Ford: O(V × E), and it detects negative cycles. If the graph is unweighted, BFS is the shortest path by number of edges.
Link to this answer -
Array or linked list for an LRU cache?
The cache map is a hash table. The recency order is a doubly-linked list so you can move a node to the front in O(1) once you have the pointer. A dynamic array would force O(n) shifts. Say both structures, not just “a list”.
Link to this answer -
Why not ship a naive BST?
Sorted inserts (1, 2, 3, 4, 5) turn it into a linked list with O(n) search. Production maps use AVL, Red-Black, or another self-balancing tree so height stays O(log n).
Link to this answer -
How do you delete in open addressing?
Tombstone markers. Clearing a slot to empty breaks later probe sequences. Load factor should stay below 1.0, typically under 0.7.
Link to this answer -
Does Gym run the coding round for me?
No. Bring tasks from the express quiz, then match a human on Find a partner. You host the call. The gym does not book a FAANG interviewer and does not promise an offer.
Link to this answer -
Is this a substitute for grinding 150 LeetCode problems?
No. These six questions sit beside the coding task. You still need to implement. Use the cheat sheet to explain trade-offs, then practice out loud.
Link to this answer
Say it, then code it
Open a search, pick one trade-off, and keep the quizzes for the holes. Already have an account? Log in and start matching.
Related: System Design theory · Last week before the interview · Pair mock interview · Avito hiring loop · Amazon system design · Stripe system design