The 50 questions interviewers ask most about Data Structures, with short, clear answers and code where it helps. The first 25 are the most common; the rest go deeper. Free, no sign-up.
A data structure is a way of organizing and storing data in memory so it can be accessed and modified efficiently. Different structures make different trade-offs between the speed of operations such as insertion, deletion, search and traversal, and the memory they use. Common examples are arrays, linked lists, stacks, queues, hash tables, trees and graphs. Choosing the right one is often the key to an efficient algorithm.
An array stores elements in contiguous memory and gives O(1) access by index, while a linked list stores nodes scattered in memory, each pointing to the next, so access by position is O(n). Linked lists can insert or delete in O(1) once you hold a reference to the node, whereas arrays must shift elements, which is O(n). Arrays are more cache-friendly and use less memory per element because they store no pointers.
Big-O notation describes an upper bound on how an algorithm's running time or memory use grows as the input size n grows. It ignores constants and lower-order terms, so 3n + 10 is simply O(n). It matters because it lets you compare algorithms independently of hardware and predict whether a solution will still work when the input becomes very large.
Arrays give O(1) index access, O(n) search and O(n) insert or delete in the middle. Singly linked lists give O(n) access and search, and O(1) insert or delete at the head. Hash tables give O(1) average insert, delete and lookup, but O(n) in the worst case. A balanced binary search tree gives O(log n) for search, insert and delete, while an unbalanced one can degrade to O(n).
A stack is a linear data structure that follows Last In, First Out (LIFO) order, where the most recently added element is removed first. Its main operations, push, pop and peek, all run in O(1). Stacks are used for function call management, undo features, expression evaluation, balanced-parentheses checking and depth-first search.
const stack = [];
stack.push(1);
stack.push(2);
stack.pop(); // 2A queue is a linear data structure that follows First In, First Out (FIFO) order, so the oldest element is removed first, whereas a stack removes the newest. You add at the back with enqueue and remove from the front with dequeue, both O(1) in a proper implementation. Queues are used for task scheduling, buffering and breadth-first search.
Use one stack for incoming elements and another for outgoing ones. On enqueue, push onto the input stack. On dequeue, if the output stack is empty, pop everything from the input stack and push it onto the output stack, which reverses the order, then pop from the output stack. Each element moves at most once, so dequeue is amortized O(1).
class Queue {
constructor() { this.in = []; this.out = []; }
enqueue(x) { this.in.push(x); }
dequeue() {
if (!this.out.length) while (this.in.length) this.out.push(this.in.pop());
return this.out.pop();
}
}A hash table stores key-value pairs and uses a hash function to convert each key into an array index, giving O(1) average-time insert, lookup and delete. The hash function should distribute keys evenly. When two keys map to the same index, a collision occurs and must be resolved. In JavaScript, Map and plain objects are the common hash-table-based structures.
A hash collision happens when two different keys produce the same hash index. The two main solutions are chaining, where each bucket holds a linked list or similar collection of entries, and open addressing, where the table probes for another free slot using linear probing, quadratic probing or double hashing. Resizing the table when the load factor gets high keeps collisions rare and operations close to O(1).
A good hash function is deterministic, fast to compute and spreads keys uniformly across the table so that few collisions occur. The load factor is the number of stored entries divided by the number of buckets. When it exceeds a threshold, commonly around 0.75, the table is resized and entries are rehashed, which keeps average operations at O(1).
A binary tree is a hierarchical structure where each node has at most two children, called left and right. A binary search tree (BST) adds an ordering rule: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. That ordering allows search, insert and delete in O(log n) when the tree is balanced.
In a BST, search, insert and delete take O(h), where h is the tree height. For a balanced tree, h is about log n, so each operation is O(log n). If you insert already sorted data into a plain BST, it degenerates into a linked list with height n, and operations become O(n). Self-balancing trees such as AVL and red-black trees prevent this.
The depth-first traversals are in-order (left, node, right), pre-order (node, left, right) and post-order (left, right, node), and the breadth-first traversal is level-order, which visits nodes level by level using a queue. In-order traversal of a BST returns the values in sorted order. All traversals take O(n) time.
function inorder(node, visit) {
if (!node) return;
inorder(node.left, visit);
visit(node.value);
inorder(node.right, visit);
}A balanced tree keeps its height close to log n so that operations stay O(log n). AVL trees enforce a strict rule that the heights of a node's two subtrees differ by at most one, using rotations to restore balance, which makes lookups fast. Red-black trees use looser color-based rules, which means fewer rotations on insert and delete. Many standard library ordered maps use red-black trees.
A heap is a complete binary tree that satisfies the heap property: in a min-heap every parent is less than or equal to its children, and in a max-heap every parent is greater than or equal to its children. Unlike a BST, a heap does not order siblings, so it only gives fast access to the minimum or maximum, in O(1), with insert and removal in O(log n). Heaps are usually stored in an array.
A priority queue is an abstract data type where each element has a priority and the element with the highest priority is removed first, regardless of insertion order. It is most commonly implemented with a binary heap, giving O(log n) insert and extract and O(1) peek. It is used in Dijkstra's algorithm, task scheduling and finding the top k elements.
Maintain a min-heap of size k while scanning the array. For each element, push it, and if the heap grows beyond k, remove the smallest. At the end the heap holds the k largest elements. This runs in O(n log k) time and O(k) space, which beats fully sorting in O(n log n) when k is small. Quickselect offers O(n) average time.
A graph is a set of vertices connected by edges, and it can be directed or undirected, weighted or unweighted. The two common representations are an adjacency list, which maps each vertex to its neighbors and uses O(V + E) space, and an adjacency matrix, a V by V grid that uses O(V^2) space but checks whether an edge exists in O(1). Adjacency lists suit sparse graphs.
Breadth-first search (BFS) explores a graph level by level using a queue, while depth-first search (DFS) goes as deep as possible along a path before backtracking, using a stack or recursion. Both run in O(V + E) time. BFS finds the shortest path in an unweighted graph, and DFS suits cycle detection, topological sorting and exploring all paths.
function bfs(graph, start) {
const seen = new Set([start]), queue = [start];
while (queue.length) {
const node = queue.shift();
for (const next of graph[node]) {
if (!seen.has(next)) { seen.add(next); queue.push(next); }
}
}
return seen;
}Use Floyd's tortoise and hare algorithm: move one pointer one step at a time and another two steps at a time. If the list has a cycle, the fast pointer eventually meets the slow pointer; if it reaches null, there is no cycle. This takes O(n) time and O(1) space, unlike a hash set of visited nodes, which needs O(n) space.
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}A trie, or prefix tree, is a tree where each node represents a character and the path from the root spells a string. Insert and search take O(m) time, where m is the length of the word, independent of how many words are stored. Tries are ideal for autocomplete, prefix search, spell checking and dictionary lookups, at the cost of higher memory use than a hash set.
Recursion solves a problem by having a function call itself on smaller inputs until it reaches a base case, while iteration repeats a block using a loop. Recursion often gives cleaner code for trees and divide-and-conquer problems but uses call stack space, risking a stack overflow on deep inputs. Iteration usually uses constant extra space. Any recursion can be converted to iteration with an explicit stack.
Bubble, insertion and selection sort are O(n^2) in the average and worst case, though insertion sort is O(n) on nearly sorted data. Merge sort is O(n log n) in all cases but needs O(n) extra space. Quick sort is O(n log n) on average but O(n^2) in the worst case, and it sorts in place. Heap sort is O(n log n) with O(1) extra space. Comparison sorts cannot beat O(n log n).
Binary search finds a target in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain it. It runs in O(log n) time and O(1) space when written iteratively. The data must be sorted and support random access, which is why it does not work efficiently on linked lists.
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1; else hi = mid - 1;
}
return -1;
}Start from the operations you need most and pick the structure that makes them cheap. Use an array for fast indexed access, a hash table for fast lookup by key, a stack for LIFO behavior, a queue for FIFO processing, a heap when you repeatedly need the minimum or maximum, a BST or balanced tree for sorted data with range queries, a trie for prefix searches, and a graph for relationships. Also weigh memory use and how often the data changes.
Walk the list once while reversing each node's next pointer, keeping track of the previous node. Save the next node, point the current node back at the previous one, then advance both pointers. When the loop ends, prev is the new head. This takes O(n) time and O(1) extra space.
function reverse(head) {
let prev = null, cur = head;
while (cur) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}Use the slow and fast pointer technique: move slow one step and fast two steps per iteration. When fast reaches the end, slow is at the middle. This needs only one pass, O(n) time and O(1) space, instead of counting the length first and then walking half of it. For an even length it returns the second middle node with the usual loop condition.
function middle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}Use a hash map that stores each value you have seen with its index. For every number, check whether target - num is already in the map; if so, you have the pair. This runs in O(n) time and O(n) space, compared with O(n^2) for checking every pair. If the array is sorted, two pointers solve it in O(n) time and O(1) space.
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
return [];
}Use a stack. Push each opening bracket, and for each closing bracket pop the stack and check that it is the matching opener. The string is balanced only if no mismatch occurs and the stack is empty at the end. This runs in O(n) time and O(n) space, and it handles mixed types like (), [] and {} correctly.
function isBalanced(s) {
const pairs = { ')': '(', ']': '[', '}': '{' };
const stack = [];
for (const ch of s) {
if ('([{'.includes(ch)) stack.push(ch);
else if (stack.pop() !== pairs[ch]) return false;
}
return stack.length === 0;
}Combine a hash map with a doubly linked list so that both get and put run in O(1). The map gives direct access to nodes by key, and the list keeps entries ordered from most to least recently used. On every access, move the node to the front; when capacity is exceeded, evict the node at the tail. In JavaScript, a Map preserves insertion order and can do this compactly.
class LRU {
constructor(cap) { this.cap = cap; this.m = new Map(); }
get(k) {
if (!this.m.has(k)) return -1;
const v = this.m.get(k);
this.m.delete(k); this.m.set(k, v);
return v;
}
put(k, v) {
this.m.delete(k); this.m.set(k, v);
if (this.m.size > this.cap) this.m.delete(this.m.keys().next().value);
}
}Sort the intervals by start time, then scan once and merge each interval into the last result if its start is less than or equal to the last end. Otherwise, append it as a new interval. Sorting dominates, so the time is O(n log n), with O(n) space for the output.
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const out = [];
for (const [s, e] of intervals) {
const last = out[out.length - 1];
if (last && s <= last[1]) last[1] = Math.max(last[1], e);
else out.push([s, e]);
}
return out;
}Start at the root and compare both values with the current node. If both are smaller, go left; if both are larger, go right; otherwise the current node is the lowest common ancestor, because the values split here or one equals the node. This takes O(h) time and O(1) space when done iteratively. For a general binary tree, use recursion over both subtrees in O(n).
Pass down an allowed range for each node and verify that its value lies strictly inside it. Going left, the upper bound becomes the node's value; going right, the lower bound does. Comparing only a node with its direct children is a common mistake, since a deeper node can violate an ancestor's bound. This runs in O(n) time.
function isValidBST(node, lo = -Infinity, hi = Infinity) {
if (!node) return true;
if (node.value <= lo || node.value >= hi) return false;
return isValidBST(node.left, lo, node.value) &&
isValidBST(node.right, node.value, hi);
}The height of a tree is one plus the larger height of its two subtrees, with an empty tree having height 0. A recursive post-order function computes this in O(n) time, using O(h) call stack space. An iterative alternative uses level-order traversal and counts the levels.
function maxDepth(node) {
if (!node) return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}Use a queue. Start with the root, and in each round process exactly as many nodes as the queue currently holds, which is one level, while enqueuing their children. Grouping by level size lets you return the values level by level. It runs in O(n) time and O(w) space, where w is the maximum width of the tree.
function levelOrder(root) {
if (!root) return [];
const res = [], queue = [root];
while (queue.length) {
const level = [];
for (let n = queue.length; n > 0; n--) {
const node = queue.shift();
level.push(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
}
return res;
}Run DFS while tracking three states for each node: unvisited, currently in the recursion stack, and fully processed. If you reach a node that is currently in the stack, there is a back edge and therefore a cycle. Alternatively, Kahn's algorithm for topological sorting detects a cycle if it cannot process all nodes. Both run in O(V + E).
Topological sorting orders the vertices of a directed acyclic graph (DAG) so that every edge points from an earlier vertex to a later one. It is used for task scheduling, build systems and resolving course prerequisites or package dependencies. It can be done with DFS by reversing the finish order, or with Kahn's algorithm using in-degrees and a queue, both in O(V + E). It is impossible if the graph has a cycle.
Dijkstra's algorithm finds the shortest paths from a source to all other vertices in a graph with non-negative edge weights. It repeatedly picks the unvisited vertex with the smallest known distance, using a priority queue, and relaxes the edges going out of it. With a binary heap it runs in O((V + E) log V). It fails with negative weights, where Bellman-Ford should be used instead.
Union-find tracks a collection of non-overlapping sets and supports find, which returns a set's representative, and union, which merges two sets. With path compression and union by rank, each operation takes nearly constant amortized time, O(alpha(n)). It is used to detect cycles in undirected graphs, count connected components and implement Kruskal's minimum spanning tree algorithm.
const parent = [];
function find(x) {
if (parent[x] === undefined) parent[x] = x;
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(a, b) { parent[find(a)] = find(b); }A minimum spanning tree (MST) is a subset of edges in a connected, weighted, undirected graph that connects all vertices with the smallest possible total weight and no cycles. Kruskal's algorithm sorts all edges and adds the cheapest one that does not form a cycle, using union-find. Prim's algorithm grows a single tree outward from a start vertex using a priority queue. Kruskal's suits sparse graphs, while Prim's often works better on dense ones.
The sliding window technique maintains a contiguous range of an array or string and moves it across the input, updating the result incrementally instead of recomputing it. It turns many O(n^2) subarray or substring problems into O(n), such as the maximum sum of k consecutive elements or the longest substring without repeating characters.
function maxSumK(nums, k) {
let sum = 0, best = -Infinity;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= k) sum -= nums[i - k];
if (i >= k - 1) best = Math.max(best, sum);
}
return best;
}The two-pointer technique uses two indices that move through a data structure, often from opposite ends or at different speeds, to solve problems in a single pass. It works well on sorted arrays and linked lists, for example finding a pair with a given sum, removing duplicates, checking a palindrome or finding a cycle. It typically reduces O(n^2) brute force to O(n) with O(1) extra space.
Dynamic programming solves a problem by breaking it into overlapping subproblems and storing each result so it is computed only once. Memoization is the top-down version, caching the results of a recursive function, while tabulation fills a table bottom-up. It applies when a problem has optimal substructure and overlapping subproblems, and turns exponential recursion into polynomial time.
function fib(n, memo = new Map()) {
if (n < 2) return n;
if (memo.has(n)) return memo.get(n);
const v = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, v);
return v;
}Choose a linked list when you frequently insert or delete at known positions, especially at the front, and do not need random access. It also avoids the occasional costly resize of a dynamic array. In practice, arrays often win even for insertions because contiguous memory is cache-friendly, so linked lists are mainly used for queues, LRU caches and structures where nodes must be spliced in O(1).
Amortized complexity is the average cost per operation over a long sequence, even if a single operation is occasionally expensive. A dynamic array doubles its capacity when full, so a resize copies n elements but happens rarely. Spread across all appends, the total cost is O(n) for n appends, which makes each append amortized O(1) even though one append can take O(n).
A Bloom filter is a space-efficient probabilistic data structure that tests whether an element is in a set. It uses a bit array and several hash functions: adding an element sets several bits, and a query checks those same bits. It can return false positives but never false negatives, and it cannot delete elements. It is used to avoid expensive lookups in caches, databases and web crawlers.
A B-tree is a self-balancing search tree where each node holds many keys and has many children, rather than at most two. This keeps the tree very shallow, so a lookup needs only a few disk reads, which matters because disk and page access is far slower than memory. All leaves are at the same depth, and operations take O(log n). Databases and file systems use B-trees and B+ trees for indexes.
Do an in-order traversal, which visits BST values in ascending order, and stop when you have visited k nodes. This takes O(h + k) time, which is much better than collecting and sorting all values. An iterative version with an explicit stack lets you stop early without finishing the recursion.
function kthSmallest(root, k) {
const stack = [];
let cur = root;
while (cur || stack.length) {
while (cur) { stack.push(cur); cur = cur.left; }
cur = stack.pop();
if (--k === 0) return cur.value;
cur = cur.right;
}
}A set stores unique values and offers O(1) average membership checks, while an array allows duplicates, keeps position-based access and needs O(n) to check membership. To remove duplicates, put the values into a Set, which runs in O(n) time. Sets built on hash tables do not guarantee sorted order, though a JavaScript Set preserves insertion order.
const unique = [...new Set([3, 1, 3, 2, 1])];
// [3, 1, 2]The most common pitfalls are skipping edge cases such as empty input, a single element, duplicates and negative numbers, and jumping into code before clarifying constraints. Others include off-by-one errors in loops and binary search, forgetting to mark visited nodes in graph traversal, mutating input unexpectedly, and ignoring space complexity. State your approach and its Big-O cost aloud, and test with a small example before finishing.
Read the Data Structures revision notes, then come back and test yourself with these questions.
OOP · Microservices · Project Architecture · System Design · All interview questions