---
title: Data Structures Interview Questions & Answers (2026)
description: The data structures interview questions that actually get asked in 2026 — arrays, linked lists, stacks, trees, graphs, hashing and heaps — with real code, time complexity, and the judgment call each one tests.
url: https://usegreenroom.app/blog/data-structures-interview-questions
last_updated: 2026-06-21
---
← Back to blog
Technical
# Data structures interview questions and answers
June 21, 2026 · 35 min read
You've solved 312 problems on LeetCode. You can write a balanced binary search tree insert in your sleep. You know, in your bones, that a hash map gives you O(1) average lookup. So when the interviewer asks you to design a system that logs the last million events and lets you fetch the most recent N at any time, you say "hash map" — fast, confident, done.
The interviewer doesn't write anything down. "Okay," they say. "Why not just use an array?"
And here's the thing nobody warns you about: you don't actually know. You know hash maps are O(1). You don't know *why a hash map is wrong here*, because nobody ever made you say it out loud before. You start explaining hashing — collisions, load factor, the whole textbook page — while the actual question, "why not the simpler structure," just sits there unanswered. Thirty seconds in, you've technically said true things about hash maps and zero true things about why you picked one. The interviewer asks, gently, "but you don't need fast lookup by key here, you need order — so why not an array, or a deque?" And you freeze, because somewhere between problem 1 and problem 312, you trained yourself to *produce* a correct structure, never to *defend* one against a more obvious alternative.
This is the actual shape of a **data structures interview questions** session in 2026, and it's a different test than the one most candidates prepare for. The conceptual half of a coding interview rarely asks "implement a linked list" cold — it asks "why this, and not that," usually right after you've already committed to an answer out loud. This guide covers the full conceptual landscape — arrays, linked lists, stacks, queues, trees, heaps, tries, hash tables, and graphs — with working code, real time complexity, and, for every structure, the specific judgment call an interviewer is actually listening for. For the problem-solving half (turning a prompt into working code under time pressure), pair this with our [DSA prep guide for India](/blog/dsa-coding-interview-preparation-india), [coding interview communication tips](/blog/coding-interview-communication-tips), and our breakdown of [common coding interview mistakes](/blog/common-coding-interview-mistakes).
## Why "I know the structure" and "I can defend the structure" are different skills
Quick gut check before we go topic by topic: can you explain, out loud, in under sixty seconds, why you'd use a deque instead of two separate stacks for a sliding-window maximum problem — without writing a single line of code? If that's hard, you're not missing knowledge. You're missing the specific muscle this guide and Greenroom's mock interviews both train: narrating a choice, under a small amount of social pressure, to someone who's allowed to ask "why not the other thing" the second you finish your sentence.
That muscle is exactly what gets tested when the interviewer changes one constraint mid-problem. "Cool, now do it with O(1) extra space." "Now the input is a stream you can't store fully." "Now there can be duplicates." A candidate who memorized one canonical answer per topic stalls on the follow-up; a candidate who understands the trade-off space adapts. Almost every example below ends with a note on the specific judgment call being tested — read those as closely as the code, because in the actual interview, that's the part that's graded.
## Linear structures
### Array vs linked list — access, insertion, memory trade-offs
An **array** stores elements in contiguous memory, so any index can be read in O(1) by computing `base_address + index * element_size`. A **linked list** stores elements as nodes scattered across memory, each holding a value and a pointer to the next node, so reaching the *k*th element means walking k pointers — O(n).
```python
# Array: O(1) random access
arr = [10, 20, 30, 40]
print(arr[2]) # 30, instant — direct address computation
# Linked list: O(n) random access
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def get_kth(head, k):
node = head
for _ in range(k):
node = node.next # have to walk every pointer in between
return node.val
```
The trade-off flips for insertion. Inserting into the middle of an array means shifting every element after it — O(n). Inserting into a linked list is O(1) once you already hold a reference to the right node, since you just rewire two pointers. Arrays also win on memory locality — contiguous memory plays nicely with CPU cache prefetching, while a linked list's scattered nodes cause cache misses on every hop, something the canonical CS reference *Introduction to Algorithms* (CLRS) discusses under pointer-based versus array-based data structure design. **The judgment call being tested:** can you say, unprompted, "I'd default to an array unless I specifically need frequent insertion/deletion at arbitrary positions and don't need random access" — rather than picking a structure because it's the one you remember best.
### Singly vs doubly vs circular linked list
A **singly linked list** node points only to the next node, so you can only traverse forward — deleting a node requires a reference to its predecessor, which you often don't have without an extra pointer or a full traversal.
```python
class SinglyNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def delete_after(prev_node):
if prev_node and prev_node.next:
prev_node.next = prev_node.next.next
```
A **doubly linked list** adds a `prev` pointer on every node, so you can traverse both directions and delete a node in O(1) given just a reference to it — at the cost of extra memory per node and more pointer bookkeeping on every insert/delete.
```python
class DoublyNode:
def __init__(self, val, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
def delete_node(node):
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
# no need to walk from head to find the predecessor
```
A **circular linked list** has its tail point back to the head instead of to `null`, which is useful for round-robin scheduling, buffering (a circular queue), or any structure that needs to cycle indefinitely without a defined "end." Browser history (back/forward navigation) and LRU cache implementations commonly use doubly linked lists for exactly this O(1)-removal property — when an LRU cache evicts its least-recently-used entry, it needs to remove an arbitrary node from the middle of the list instantly, which a singly linked list can't do without an extra predecessor pointer or a full scan. **The judgment call:** name the LRU cache example unprompted — it signals you've connected the structure to a real system, not just a textbook diagram.
### Stack vs queue — LIFO vs FIFO, and real use cases
A **stack** is LIFO (last in, first out) — push and pop both happen at the same end, in O(1).
```python
stack = []
stack.append(1) # push
stack.append(2)
stack.append(3)
stack.pop() # 3 — last one in, first one out
```
Real uses: the call stack for function execution and recursion, undo/redo in editors, and parsing balanced brackets or expressions (the classic "valid parentheses" problem is a stack with one line of logic: push opening brackets, and on a closing bracket, check the top of the stack matches).
A **queue** is FIFO (first in, first out) — items are enqueued at the back and dequeued from the front, both O(1) with a proper implementation. A naive array-based queue using `list.pop(0)` in Python is O(n) per dequeue, because every remaining element has to shift left — `collections.deque` exists specifically to fix that with O(1) append and popleft on both ends.
```python
from collections import deque
queue = deque()
queue.append(1) # enqueue
queue.append(2)
queue.popleft() # 1 — first one in, first one out, O(1)
```
Real uses: task scheduling, BFS traversal, and request buffering in any producer-consumer system. **The interview tell:** can you name a use case, not just recite LIFO/FIFO. An interviewer asking "why is undo/redo a stack and not a queue" wants to hear "because the most recent action is the one you want to reverse first" — the LIFO property mapped to the actual product behavior, not the definition repeated back.
### How is a stack used in function calls and recursion?
Every function call pushes a new "stack frame" onto the call stack, holding local variables, parameters, and the return address — when the function returns, its frame pops off and control resumes where it left off. Recursion is just functions calling themselves, so each recursive call adds a frame; if the recursion is too deep (or infinite, from a missing base case), you exhaust the stack and crash with a **stack overflow**.
```python
def factorial(n):
if n <= 1: # base case — without this, infinite recursion
return 1
return n * factorial(n - 1) # each call adds a new stack frame
```
This is exactly why interviewers ask "what's the base case?" for any recursive solution — without one, the stack just keeps growing until it crashes, and Python in particular will throw `RecursionError` well before you hit a true OS-level stack overflow, because CPython caps recursion depth (default 1000) defensively. Tail-call optimization — reusing the current frame instead of pushing a new one when a recursive call is the very last operation — is not guaranteed in most mainstream languages including JavaScript and Python, which is the practical reason "convert this recursive solution to iterative" is a common Adobe/Google/Amazon follow-up: it's testing whether you can manually manage the stack with an explicit list, rather than relying on language-level optimization that may not exist.
### What is a deque and a priority queue?
A **deque** (double-ended queue) allows O(1) insertion and removal from *both* ends, making it a strict superset of stack and queue behavior — useful for sliding-window problems where you need to drop from the front and add to the back as the window moves.
```python
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # stores indices, kept in decreasing value order
result = []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] < n:
dq.pop() # remove smaller values — they can never be the max again
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # index fell outside the window
if i >= k - 1:
result.append(nums[dq[0]])
return result
```
A **priority queue** doesn't dequeue in arrival order; it always dequeues the highest (or lowest) priority element, typically backed by a heap so insert and extract-min/max are both O(log n).
```python
import heapq
pq = []
heapq.heappush(pq, (2, "medium"))
heapq.heappush(pq, (1, "urgent"))
heapq.heappush(pq, (3, "low"))
heapq.heappop(pq) # (1, "urgent") — lowest number = highest priority by convention
```
Priority queues power Dijkstra's shortest path, task schedulers that respect priority levels, and any "process the most urgent item next" system. **The judgment call:** the sliding-window-maximum example above is a favorite precisely because the naive solution (a nested loop recomputing the max for every window) is O(n·k), and the deque trick that gets it to O(n) only works because you discard values from the deque that can *never* be the answer again — stating that invariant out loud is the actual signal, not just producing working code.
## Trees
### Binary tree vs binary search tree (BST)
A **binary tree** is just a tree where each node has at most two children — no ordering constraint. A **binary search tree** (BST) adds a rule: for every node, all values in its left subtree are smaller and all values in its right subtree are larger.
```python
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bst_insert(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = bst_insert(root.left, val)
else:
root.right = bst_insert(root.right, val)
return root
def bst_search(root, val):
if root is None or root.val == val:
return root
return bst_search(root.left, val) if val < root.val else bst_search(root.right, val)
```
That ordering is what makes search, insertion, and deletion O(log n) on average in a BST — you discard half the remaining tree at each step, the same intuition as binary search on a sorted array. The catch, and the part interviewers love to push on: a BST built by inserting already-sorted input degenerates into a straight line (every node has only a right child), pushing those operations to O(n) — which is exactly why self-balancing variants exist. **The judgment call:** if you propose a plain BST for a problem, expect "what if the input arrives sorted?" as an immediate follow-up — having an answer ready ("it degenerates to a linked list, so I'd use a self-balancing tree if insertion order isn't guaranteed random") is what separates a complete answer from a half one.
### Tree traversals — inorder, preorder, postorder, level-order
**Inorder** (left, node, right) visits a BST's nodes in ascending sorted order — useful whenever you need sorted output from a BST.
```python
def inorder(node, result=None):
if result is None:
result = []
if node:
inorder(node.left, result)
result.append(node.val)
inorder(node.right, result)
return result
```
**Preorder** (node, left, right) visits the root before its subtrees, which is how you'd serialize a tree to later reconstruct it — you need the root's value first to know where to start rebuilding.
```python
def preorder(node, result=None):
if result is None:
result = []
if node:
result.append(node.val)
preorder(node.left, result)
preorder(node.right, result)
return result
```
**Postorder** (left, right, node) visits children before their parent, which is necessary when deleting a tree bottom-up (you must free children before the parent) or evaluating an expression tree (you need both operands resolved before applying the operator at the root).
```python
def postorder(node, result=None):
if result is None:
result = []
if node:
postorder(node.left, result)
postorder(node.right, result)
result.append(node.val)
return result
```
**Level-order** (breadth-first, using a queue) visits all nodes at depth 0, then depth 1, and so on — the right choice whenever the question involves "the shortest path" or "level by level" in a tree, like finding the minimum depth or a zigzag traversal.
```python
from collections import deque
def level_order(root):
if not root:
return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
```
**The judgment call:** an interviewer who asks "print this tree's values in sorted order" without saying "inorder" is testing whether you can map the requirement to the traversal yourself — saying "inorder, because it walks a BST in ascending order by construction" beats reciting the four traversal names and guessing.
### Why do we balance trees (AVL, red-black)?
An unbalanced BST can degrade to O(n) operations if data arrives in sorted (or near-sorted) order, because the tree grows tall and thin instead of short and wide. **AVL trees** enforce that the heights of a node's two subtrees never differ by more than 1, rebalancing via rotations on every insert/delete to guarantee O(log n) height — strict balancing, more rotation overhead, but consistently fast lookups.
```python
# Right rotation — the core AVL/red-black primitive, used to fix a left-heavy imbalance
def rotate_right(y):
x = y.left
y.left = x.right
x.right = y
return x # x is now the new subtree root
```
**Red-black trees** use a looser balancing rule (a set of coloring invariants — every path from root to leaf has the same number of black nodes) that guarantees height stays within roughly a 2x factor of optimal, trading a slightly taller tree for fewer rotations on writes. That's why most language standard libraries — Java's `TreeMap`, C++'s `std::map` — use red-black trees under the hood: they're tuned for a healthy mix of reads and writes, not read-only workloads where AVL's stricter balance would pay off more. **The judgment call:** "why not just use AVL everywhere since it's more balanced" is a real follow-up, and the honest answer is a trade-off, not a winner — AVL for read-heavy workloads where lookup speed matters most, red-black where writes are frequent and rotation cost adds up.
### What is a heap, and min-heap vs max-heap?
A heap is a tree (usually implemented as an array) satisfying the **heap property**: in a min-heap, every parent is smaller than or equal to its children, so the minimum is always at the root; a max-heap flips that, keeping the maximum at the root.
```python
import heapq
min_heap = [5, 3, 8, 1]
heapq.heapify(min_heap)
heapq.heappush(min_heap, 0)
print(min_heap[0]) # 0 — the minimum, always at the root, O(1) peek
heapq.heappop(min_heap) # removes and returns the min, O(log n)
# Python's heapq is min-heap only — simulate max-heap by negating values
max_heap = [-x for x in [5, 3, 8, 1]]
heapq.heapify(max_heap)
print(-max_heap[0]) # 8 — the max
```
Both support O(log n) insert and O(log n) extract-root, with O(1) peek at the root — but unlike a BST, a heap gives you no ordering guarantee beyond parent-child, so you can't do an efficient inorder traversal or range query on it. Heaps are the backbone of priority queues, heap sort, and the classic "find the k largest/smallest elements" interview problem, where you maintain a heap of size k instead of sorting the whole input — giving O(n log k) instead of O(n log n), which matters when k is small relative to n. **The judgment call:** explaining *why* a heap of size k beats full sorting (you only ever pay log k per operation, not log n) is the part candidates skip when they just say "use a heap" without the complexity comparison that justifies it.
### What is a trie and where is it used?
A trie (prefix tree) stores strings character by character along paths from the root, so that all strings sharing a prefix share the same path through the tree — looking up or inserting a string of length L takes O(L) time, independent of how many other strings are stored.
```python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True # O(L) regardless of how many words are stored
```
This makes tries the natural fit for autocomplete (walk to the prefix's node, then collect everything below it), spell-checkers, and IP routing tables, where the longest-matching-prefix lookup is exactly a trie traversal. The trade-off is memory: a naive trie allocates a node per character per branch, which can be heavier than a hash set for a small number of strings — it pays off specifically when you need prefix queries, which a hash set can't do efficiently at all (you'd have to check every stored string individually). **The judgment call:** "why not a hash set of all words" is the standard follow-up, and the answer is that a hash set gives O(1) exact-match lookup but offers nothing for "give me everything starting with 'gre'" without scanning the whole set — a trie turns that into an O(L) walk plus a subtree collection.
The diagram on the whiteboard is rarely the test — defending why you drew it that way, under a changed constraint, is.
## Hashing and graphs
### How does a hash table work? Collision handling (chaining vs open addressing)
A **hash table** runs each key through a hash function to get an index into a backing array, giving O(1) average insert/lookup/delete — the entire trick is turning "search for a key" into "compute an address."
```python
# A hash table from scratch, simplified, to show the mechanics chaining relies on
class SimpleHashMap:
def __init__(self, size=16):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
bucket = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # update existing key
return
bucket.append((key, value)) # chaining: append on collision
def get(self, key):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
raise KeyError(key)
```
Collisions (two keys hashing to the same index) are inevitable once the table fills up, and there are two standard fixes. **Chaining** stores a small list (or, in Java's `HashMap` since JDK 8, a balanced tree once a bucket grows past a threshold) at each bucket, so colliding keys just append to that bucket's list. **Open addressing** instead probes for the next free slot in the array itself (linear, quadratic, or double hashing), keeping everything in one contiguous array but making deletion trickier — you need tombstones marking "deleted, but keep probing past me," not just clearing the slot, or lookups for other keys that probed past this one will incorrectly stop early. MDN's documentation on JavaScript's `Map` and `Object` covers a related practical wrinkle: plain object keys get coerced to strings, which is its own source of hash-table-adjacent interview bugs ("why did my number key turn into a string key"). **The judgment call:** chaining degrades more gracefully under high load factor (worst case becomes "a slightly long list to scan," not corrupted probing), while open addressing has better cache locality when load factor is kept low — naming both sides, not just one technique, is what the question is fishing for.
### Time complexity of hash table operations
Average case, insert/lookup/delete are all O(1) — that's the entire value proposition of a hash table. But worst case, if the hash function clusters many keys into the same bucket — or an adversary crafts inputs to do so deliberately, a real attack called **hash flooding** — every operation degrades to O(n) since you're effectively scanning a linked list one bucket at a time.
```python
# Why a bad hash function matters: this "hash" sends every key to bucket 0
def bad_hash(key):
return 0 # collides every single time — degrades to O(n) for every op
# A good hash function distributes keys roughly uniformly across buckets,
# which is exactly what makes the O(1) average case hold in practice
```
A good hash function spreads keys uniformly, and most production hash maps periodically *resize* (rehash into a larger backing array, typically doubling) once the load factor crosses a threshold — commonly 0.75 — keeping the average case close to O(1) over the table's lifetime even as it grows. **The judgment call:** hash flooding is the follow-up most candidates haven't prepared for — "what if someone deliberately sends keys that all hash to the same bucket" — and it's a real production concern, which is why several languages (including Python and PHP) randomize their string hash seed per process specifically to make this attack harder to pull off against a public-facing service.
### Graph representations — adjacency matrix vs list
An **adjacency matrix** is a V×V grid where `matrix[i][j]` is 1 (or a weight) if an edge exists between nodes i and j.
```python
# Adjacency matrix — O(1) edge check, O(V^2) space regardless of sparsity
V = 4
matrix = [[0] * V for _ in range(V)]
matrix[0][1] = matrix[1][0] = 1 # undirected edge between node 0 and 1
```
Checking whether an edge exists is O(1), but the matrix takes O(V²) space regardless of how sparse the graph is, and iterating a node's neighbors is O(V) even if it only has 2 neighbors — you scan the whole row to find them.
An **adjacency list** stores, for each node, a list of just its neighbors.
```python
# Adjacency list — O(V+E) space, the right default for sparse graphs
graph = {0: [1, 2], 1: [0], 2: [0, 3], 3: [2]}
for neighbor in graph[0]: # iterating cost is proportional to actual degree
print(neighbor)
```
This is O(V+E) space, far better for sparse graphs — and most real-world graphs are sparse: a social network has millions of users but each user follows only a few hundred, so a V×V matrix would waste an enormous amount of memory on the millions of non-edges. Iterating neighbors with a list is proportional to the actual degree of the node, not the total node count. **The judgment call:** the rule of thumb interviewers want is adjacency list by default; reach for a matrix only when the graph is dense or you need O(1) edge-existence checks constantly — saying "it depends on density" without naming a concrete threshold or example reads as half an answer, so have the social-network-versus-fully-connected-cluster contrast ready.
### BFS vs DFS — and when to use each
**BFS** (breadth-first search) explores level by level using a queue — visit a node, enqueue all its unvisited neighbors, repeat.
```python
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
```
Because it expands outward in rings, the first time BFS reaches a node is guaranteed to be via the shortest path (in an unweighted graph) — which is why BFS is the standard tool for "shortest path" and "minimum number of steps" questions.
**DFS** (depth-first search) explores as deep as possible down one branch before backtracking, using a stack or recursion.
```python
def dfs(graph, start, visited=None, order=None):
if visited is None:
visited, order = set(), []
visited.add(start)
order.append(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited, order)
return order
```
DFS suits problems like detecting cycles, topological sorting, finding connected components, and exploring all possible paths (since it naturally backtracks to try alternatives). Both visit every node and edge once, so both are O(V+E) — the choice is about what *guarantee* you need, not raw speed. **The judgment call:** "I'd use BFS because it's faster" is a wrong answer that interviewers hear constantly — they're the same complexity. The correct framing is "BFS because I need the shortest path guarantee," or "DFS because I need to explore exhaustively/detect a cycle/get a topological order" — naming the *property*, not a speed claim that isn't true.
### Detecting a cycle; shortest path basics
To detect a cycle in an **undirected** graph, run DFS and watch for an edge to an already-visited node that isn't the immediate parent — that's a back edge, meaning a cycle.
```python
def has_cycle_undirected(graph, n):
visited = [False] * n
def dfs(node, parent):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True # back edge to a non-parent = cycle
return False
return any(not visited[i] and dfs(i, -1) for i in range(n))
```
In a **directed** graph, you need three states per node (unvisited, visiting, visited) because a back edge to a node currently "in progress" on the same DFS path indicates a cycle, while an edge to an already-fully-visited node from an earlier, unrelated branch does not.
```python
def has_cycle_directed(graph, n):
WHITE, GRAY, BLACK = 0, 1, 2
state = [WHITE] * n
def dfs(node):
state[node] = GRAY
for neighbor in graph[node]:
if state[neighbor] == GRAY:
return True # edge into the current path = cycle
if state[neighbor] == WHITE and dfs(neighbor):
return True
state[node] = BLACK
return False
return any(state[i] == WHITE and dfs(i) for i in range(n))
```
For shortest path: BFS handles unweighted graphs. **Dijkstra's algorithm** (a priority queue plus greedy relaxation) handles weighted graphs with non-negative weights in O((V+E) log V).
```python
import heapq
def dijkstra(graph, start):
# graph[node] = list of (neighbor, weight)
dist = {start: 0}
pq = [(0, start)]
while pq:
d, node = heapq.heappop(pq)
if d > dist.get(node, float('inf')):
continue
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist.get(neighbor, float('inf')):
dist[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return dist
```
**Bellman-Ford** handles graphs with negative weights (and can detect negative cycles) in O(VE), trading speed for that extra capability — it relaxes every edge V-1 times, which is provably enough to propagate the shortest path information across any graph without a negative cycle, and a V-th pass that still finds an improvement proves one exists. **The judgment call:** "why not just always use Dijkstra" is a real follow-up, and the answer is that Dijkstra's greedy choice (always expand the currently-closest node) breaks in the presence of negative edges — a later negative edge could make a path cheaper than the one Dijkstra already finalized and will never revisit. That single sentence is usually worth more than being able to recite Bellman-Ford's pseudocode from memory.
## Complexity
### Big-O of common operations for each structure
**Arrays:** O(1) access, O(n) insert/delete (middle), O(n) search (unsorted), O(log n) search (sorted, via binary search).
**Linked lists:** O(n) access, O(1) insert/delete (given a node reference), O(n) search.
**Stacks and queues:** O(1) push/pop/enqueue/dequeue with a proper backing structure (linked list or deque); O(n) for a naive array-based queue using front-removal.
**Hash tables:** O(1) average insert/lookup/delete, O(n) worst case under heavy collision.
**Balanced BSTs (AVL/red-black):** O(log n) for insert/lookup/delete, guaranteed, not just average.
**Heaps:** O(log n) insert/extract-root, O(1) peek.
**Tries:** O(L) for a string of length L, independent of how many strings are stored.
**Graphs (BFS/DFS):** O(V+E) to traverse, regardless of representation; O(1) edge check with an adjacency matrix vs O(degree) with an adjacency list.
Knowing these cold — and being able to justify *why* each one holds, not just recite it — is the actual interview signal. A table of numbers memorized without the reasoning behind each one falls apart the moment someone asks "why is BST insert log n on average but not worst case," which is a one-sentence answer (height can degrade to n on adversarial input) that a surprising number of candidates can't produce despite having the row of the table memorized.
### How do you choose the right data structure for a problem?
Start from the operations the problem needs most often, not the data itself:
- Need fast membership checks or counting? Reach for a **hash set/map**.
- Need sorted order maintained as you insert? Reach for a **balanced BST** or a sorted structure.
- Need "the next most urgent item"? Reach for a **heap**.
- Need prefix matching on strings? Reach for a **trie**.
- Need to model relationships or connectivity? Reach for a **graph** with BFS/DFS.
- Need LIFO undo behavior, or to track nested structure (brackets, call frames)? Reach for a **stack**.
- Need FIFO processing order, or to expand a search level by level? Reach for a **queue**.
The skill interviewers are testing isn't memorization — it's mapping a problem's *access pattern* to the structure whose Big-O matches it, and being able to say which pattern you're matching against, out loud, before you write code. "I'll use a hash map here because the problem needs O(1) membership checks, not a sorted array, because I don't actually need order" is a complete answer. "I'll use a hash map" alone, with no "because," is half of one — and it's the half that gets the "why not X instead" follow-up, every time.
The core truth: Interviews don't reward memorizing every operation — they reward knowing when to reach for each structure, and being able to defend that choice the moment someone proposes a plausible alternative. "I'd use a hash map here for O(1) lookup, not an array, because I need membership checks, not order" said at the right moment is the signal that separates a hire from a near-miss.
## How candidates actually prepare — and where each method falls short
Almost everyone preparing for a data-structures-heavy interview ends up combining a few of the same four approaches. None of them are wrong, exactly — but each trains a different half of the real interview, and most people over-invest in the half that's easiest to do alone, at night, with no one watching.
**LeetCode, grinding alone in silence.** This builds real pattern recognition and keeps your syntax fluent — genuinely necessary, not optional. The gap is the one from the opening story: solving 300 problems silently trains you to *produce* a correct structure, not to *narrate* one under a live follow-up. A LeetCode submission screen never asks "why not an array instead" the second after you get the green checkmark. You can be a 300-problem veteran and still freeze the first time a real interviewer interrupts your explanation mid-sentence to ask exactly that — because narrating a trade-off live is a different skill than typing a correct answer with no one watching your face.
**GeeksforGeeks-style question dumps.** Genuinely useful for knowing *what topics* come up, and several of the questions in this guide will look familiar if you've browsed one. The risk is treating a question list as an answer key rather than a syllabus. These dumps give you the prompt and often a model answer, but they don't simulate the part where an interviewer changes the constraint mid-problem — "now do it with O(1) extra space," "now the input is a stream you can't fully store" — specifically to test whether you understood the underlying technique or just memorized one fixed solution shape. That's exactly where memorized-from-a-dump answers stall: the candidate has the right opening line, and nothing for the next beat.
**A friend's WhatsApp PDF or Notion DSA sheet.** These crowd-curated sheets (the "450 DSA questions" genre that circulates every placement season) are genuinely useful for triage — knowing which 50 topics show up constantly versus the long tail that rarely does. The honest limitation: a static PDF can't ask you a follow-up. It's a checklist of what to study, not a rehearsal of how to explain it, and a candidate who's "completed the sheet" by reading every solution silently has done the equivalent of reading 450 chess openings without ever playing a game against an opponent who responds differently than the book expects.
**Generic ChatGPT mock-interview prompting.** Typing "ask me data structures interview questions" into a chat window and typing your answers back is meaningfully better than nothing — it's good for drilling factual recall (complexity classes, definitions, when-to-use-what). But it's still a text-based, turn-taking exercise with no real-time pressure and no spoken delivery practice, and critically, the follow-ups are only as sharp as the prompt you wrote — it's easy to accidentally prompt yourself into an easy interview that never pushes back the way a real interviewer would. It doesn't replicate the specific discomfort of explaining a recursive invariant or a hash-collision trade-off out loud, live, to someone who can interrupt you mid-thought, which is the actual skill being graded in the room.
The honest throughline across all four: real interviews grade **reasoning out loud and defending a structure choice under a changed constraint** — not whether you can eventually produce a correct written answer with unlimited time and no one watching. That's the specific gap [Greenroom](/)'s spoken mock-interview format is built to close: you talk through a data-structures problem out loud, the AI interviewer asks real follow-ups the way a human interviewer does — a constraint change, a "why not X instead" challenge, a request to extend your design to handle duplicates or a stream — and you get feedback on the clarity of your reasoning, not just whether the final code compiled. It's not a replacement for the actual studying — you still need the LeetCode reps and the fundamentals cold — but it's the only one of these methods that rehearses the verbal, interrupted, defend-your-choice format the real interview actually is.
## Worked example: the hash-map-vs-array moment, properly answered
Back to the opening scene — the "log the last million events, fetch the most recent N" problem. Here's what a complete answer sounds like, narrated the way an interviewer wants to hear it:
"My first instinct is a hash map keyed by event ID for O(1) lookup by ID. But the actual requirement is 'fetch the most recent N' — that's an *order*-based query, not a key-based one, and a hash map doesn't preserve insertion order reliably as a guarantee across implementations. What I actually need is a structure that's cheap to append to and cheap to read the tail of — a deque gives me O(1) append and O(1) access to the most recent N from the right end, and if I also need to look up a specific event by ID, I'd keep a hash map *alongside* the deque, not instead of it, trading some memory for both access patterns." That's roughly ninety seconds, it names the wrong-first-instinct honestly, and it ends with a structure that actually matches the requirement — which is the entire content of what these interviews are grading.
## Practise explaining, not just memorizing
You can recognize every answer in this guide on a flashcard and still freeze the moment an interviewer asks you to defend a structure choice live, with someone watching you think and free to interrupt. The interview is verbal, so the practice has to be verbal too — reading an answer is a fundamentally different skill from producing one under mild pressure with real follow-up questions. [Greenroom](/) runs spoken technical interviews where you talk through your approach as you solve, and the AI interviewer asks the same kind of "why not the other structure" follow-ups a real one would — then gives feedback on how clearly you justified your choice, not just whether the final code worked. Pair it with our [DSA coding interview prep for India](/blog/dsa-coding-interview-preparation-india), [coding interview communication tips](/blog/coding-interview-communication-tips), [common coding interview mistakes](/blog/common-coding-interview-mistakes), and [system design interview prep](/blog/system-design-interviews-what-they-test) once you're ready to combine structure choices into a full design answer.
## Frequently asked questions
### What are the most common data structures interview questions?
Common questions cover array vs linked list trade-offs, stack vs queue and their use cases, linked list variants (singly, doubly, circular), tree topics (binary tree vs BST, traversals, balancing with AVL/red-black, heaps, tries), hashing (how hash tables work and collision handling via chaining vs open addressing), graph representations and BFS vs DFS, cycle detection, Dijkstra and Bellman-Ford basics, and the Big-O complexity of common operations plus how to choose the right structure for a problem.
### When should I use a hash table vs an array?
Use an array when you need indexed access by position, ordered data, or cache-friendly iteration. Use a hash table (hash map) when you need fast lookups, insertions and deletions by key in average O(1) time, such as counting frequencies, deduplicating, or checking membership. The trade-off is that hash tables don't maintain order and have worst-case O(n) operations under heavy collisions, while arrays guarantee O(1) access by index regardless of load.
### What is the difference between BFS and DFS?
BFS (breadth-first search) explores a graph level by level using a queue, making it ideal for finding the shortest path in an unweighted graph because the first time it reaches a node is guaranteed to be via the shortest route. DFS (depth-first search) explores as far as possible along each branch before backtracking, using a stack or recursion, and suits problems like cycle detection, topological sorting and exploring all paths. Both visit every node in O(V+E).
### Why do we need self-balancing trees like AVL or red-black trees?
A plain binary search tree can degrade into a linked-list shape if data arrives in sorted order, pushing operations from O(log n) to O(n). Self-balancing trees rebalance automatically on insert and delete — AVL trees enforce a strict height-balance rule with more rotations, while red-black trees use a looser rule with fewer rotations — to guarantee O(log n) height no matter the insertion order, which is why most standard library map implementations use a red-black tree under the hood.
### How should I prepare for data structures interview questions?
Learn not just how each structure works but when to reach for it and its Big-O trade-offs, since interviews reward choosing and justifying the right structure under a changed constraint, not reciting a definition. Practise narrating your choice — "I'll use a hash map here for O(1) lookup, instead of an array, because I need membership checks, not order" — out loud while solving, ideally with a voice-based mock interview that gives feedback on how clearly you reason and pushes back the way a real interviewer would.
### Do I need to memorize how to implement every data structure from scratch?
Mostly no — most interviews care more about when and why to use a structure than your ability to hand-roll a red-black tree's rotation logic from memory. The exceptions worth practicing cold are the simple, frequently-asked-to-implement ones: a basic hash map, a linked list with insert/delete, a binary search tree's traversal, a heap's sift-up/sift-down, and BFS/DFS on a graph — these come up often enough as standalone questions that fumbling the implementation reads as a real gap, not a minor slip.
### Is LeetCode enough preparation for data structures interview questions, or do I need something else?
LeetCode is necessary but not sufficient. It builds the pattern recognition and syntax fluency you need to actually write correct code under time pressure, but it's a silent, untimed-conversation exercise — it never asks you to defend a structure choice out loud the way a real interviewer does mid-explanation. Most strong candidates combine LeetCode (or a topic-sorted DSA sheet) for the underlying knowledge with some form of spoken mock practice for the verbal, interrupted, "why not X instead" delivery skill the actual interview grades.
Interviews reward choosing the right structure out loud, under a follow-up you didn't see coming. Greenroom runs spoken technical interviews where you talk through your approach and get feedback on how clearly you reasoned. Free to start.
