Top 25 DSA Interview Questions
Curated questions covering arrays, linked lists, trees, graphs, sorting, searching, dynamic programming, and Big O notation.
What is Big O notation?
Big O notation describes the time or space complexity of an algorithm in terms of input size n. It represents the worst-case growth rate. Common complexities: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, O(2n) exponential.
What is the difference between an array and a linked list?
- Array — contiguous memory; O(1) random access; O(n) insertion/deletion in middle; fixed size (static arrays).
- Linked List — non-contiguous nodes with pointers; O(n) access; O(1) insertion/deletion at head; dynamic size.
- Use arrays for frequent reads; linked lists for frequent insertions/deletions.
What is a stack and what are its operations?
A stack is a LIFO (Last In First Out) data structure. Operations: push (add to top), pop (remove from top), peek (view top), isEmpty. Used for function call stacks, undo operations, and expression evaluation.
// Stack using array
class Stack {
constructor() { this.items = []; }
push(x) { this.items.push(x); }
pop() { return this.items.pop(); }
peek() { return this.items[this.items.length - 1]; }
}What is a queue and what are its operations?
A queue is a FIFO (First In First Out) data structure. Operations: enqueue (add to rear), dequeue (remove from front), peek, isEmpty. Used for BFS, task scheduling, and print queues.
What is the difference between BFS and DFS?
- BFS (Breadth-First Search) — explores level by level using a queue; finds shortest path in unweighted graphs; O(V+E).
- DFS (Depth-First Search) — explores as deep as possible using a stack/recursion; used for cycle detection, topological sort; O(V+E).
// BFS
function bfs(graph, start) {
const queue = [start], visited = new Set([start]);
while (queue.length) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); }
}
}
}What is a binary search tree (BST)?
A BST is a binary tree where each node's left subtree contains only nodes with smaller values, and the right subtree contains only nodes with larger values. Operations: search, insert, delete — O(log n) average, O(n) worst case.
What is the difference between a tree and a graph?
- Tree — connected, acyclic graph with a root; n nodes, n-1 edges; hierarchical structure.
- Graph — can have cycles, multiple components, and directed/undirected edges; more general structure.
- A tree is a special case of a graph.
What is binary search?
Binary search finds a target in a sorted array by repeatedly halving the search space. Time complexity: O(log n). Requires the array to be sorted.
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}What is the difference between merge sort and quick sort?
- Merge Sort — divide and conquer; always O(n log n); stable; requires O(n) extra space.
- Quick Sort — divide and conquer; O(n log n) average, O(n²) worst case; in-place; not stable; faster in practice.
- Use merge sort for stability; quick sort for in-place sorting.
What is dynamic programming?
Dynamic programming solves problems by breaking them into overlapping subproblems and storing results (memoisation or tabulation) to avoid redundant computation. Used for: Fibonacci, knapsack, longest common subsequence, shortest path.
// Fibonacci with memoisation
function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}What is a hash table?
A hash table maps keys to values using a hash function. Average O(1) for insert, delete, and lookup. Collisions are handled by chaining (linked lists) or open addressing (probing).
What is a heap?
A heap is a complete binary tree satisfying the heap property. Min-heap: parent = children (root is minimum). Max-heap: parent = children (root is maximum). Used for priority queues and heap sort. Insert/delete: O(log n).
What is a trie?
A trie (prefix tree) is a tree where each node represents a character. Used for efficient string search, autocomplete, and spell checking. Search/insert: O(m) where m is string length.
What is the difference between a singly and doubly linked list?
- Singly linked list — each node has a next pointer; can only traverse forward; less memory.
- Doubly linked list — each node has next and prev pointers; can traverse both directions; easier deletion; more memory.
What is topological sorting?
Topological sort orders vertices of a directed acyclic graph (DAG) such that for every edge u?v, u comes before v. Used for task scheduling, build systems, and dependency resolution. Implemented with DFS or Kahn's algorithm (BFS).
What is Dijkstra's algorithm?
Dijkstra's algorithm finds the shortest path from a source to all vertices in a weighted graph with non-negative edges. Uses a min-heap (priority queue). Time complexity: O((V+E) log V).
What is the difference between memoisation and tabulation?
- Memoisation (top-down) — recursive approach; stores results of subproblems in a cache; only computes needed subproblems.
- Tabulation (bottom-up) — iterative approach; fills a table from base cases up; computes all subproblems.
What is a balanced binary tree?
A balanced binary tree has a height of O(log n). Examples: AVL tree (height difference = 1 for every node), Red-Black tree (used in Java TreeMap, C++ map). Ensures O(log n) operations.
What is the two-pointer technique?
Two pointers use two indices to traverse an array or linked list, often from both ends or at different speeds. Used for: finding pairs with a sum, removing duplicates, detecting cycles (Floyd's algorithm).
// Find pair with target sum in sorted array
function twoSum(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo < hi) {
const sum = arr[lo] + arr[hi];
if (sum === target) return [lo, hi];
else if (sum < target) lo++;
else hi--;
}
return null;
}What is a sliding window?
The sliding window technique maintains a window of elements and slides it across the array to solve subarray/substring problems efficiently. Reduces O(n²) brute force to O(n).
// Maximum sum subarray of size k
function maxSumSubarray(arr, k) {
let sum = arr.slice(0, k).reduce((a, b) => a + b, 0), max = sum;
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
max = Math.max(max, sum);
}
return max;
}What is Floyd's cycle detection algorithm?
Floyd's algorithm (tortoise and hare) detects cycles in a linked list using two pointers — slow (moves 1 step) and fast (moves 2 steps). If they meet, a cycle exists. Time: O(n), Space: O(1).
What is the difference between linear and binary search?
- Linear search — checks each element sequentially; O(n); works on unsorted arrays.
- Binary search — halves the search space each step; O(log n); requires sorted array.
What are the common sorting algorithms and their complexities?
- Bubble Sort — O(n²) average; simple but inefficient.
- Selection Sort — O(n²); in-place.
- Insertion Sort — O(n²) average, O(n) best; good for small/nearly sorted arrays.
- Merge Sort — O(n log n); stable; O(n) space.
- Quick Sort — O(n log n) average; in-place.
- Heap Sort — O(n log n); in-place; not stable.
- Counting/Radix Sort — O(n+k); for integers.
What is a graph and what are its representations?
- Adjacency Matrix — 2D array; O(1) edge lookup; O(V²) space; good for dense graphs.
- Adjacency List — array of lists; O(V+E) space; good for sparse graphs.
- Edge List — list of edges; simple; used in some algorithms like Kruskal's.
What is the knapsack problem?
The 0/1 knapsack problem: given items with weights and values, find the maximum value that fits in a knapsack of capacity W. Each item can be taken (1) or not (0). Solved with dynamic programming in O(nW) time and space.
function knapsack(weights, values, W) {
const n = weights.length;
const dp = Array(n+1).fill(null).map(() => Array(W+1).fill(0));
for (let i = 1; i <= n; i++)
for (let w = 0; w <= W; w++) {
dp[i][w] = dp[i-1][w];
if (weights[i-1] <= w)
dp[i][w] = Math.max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
}
return dp[n][W];
}