Data Structures & Algorithms Interview Questions & Answers (2026) – RankWeb3

Algorithm	Best	Worst
Binary Search	O(1)	O(log n)
Merge Sort	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n²)
BFS / DFS	O(V+E)	O(V+E)
Dijkstra	O((V+E) log V)	O((V+E) log V)
Hash Lookup	O(1)	O(n)

🧩 DSA All Levels 40 Questions Updated 2026

Data Structures & Algorithms
Interview Questions & Answers

📅 Updated: March 2026

⏱️ Read time: ~32 min

🎯 40 questions — Beginner to Advanced

✍️ By RankWeb3 Team

Total Questions

Beginner

Intermediate

Advanced

🌱Beginner QuestionsQ1–Q14

What is Big O notation and why does it matter?

BeginnerVery Common

Big O notation describes how an algorithm's runtime or memory usage grows as the input size n grows. It expresses the worst-case upper bound, ignoring constants and lower-order terms.

Best O(1) O(log n) O(n) O(n log n) O(n²) Worst O(2ⁿ)

Big O Examples
// O(1) — constant: array index access
arr[5];

// O(log n) — logarithmic: binary search
// Halves search space each step

// O(n) — linear: single loop
for (let i = 0; i < n; i++) { ... }

// O(n log n) — linearithmic: merge sort, heapsort

// O(n²) — quadratic: nested loops
for (let i = 0; i < n; i++)
  for (let j = 0; j < n; j++) { ... }

// O(2ⁿ) — exponential: naive Fibonacci recursion
function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2); // ← very slow!
}

💡Drop constants: O(2n) → O(n). O(n² + n) → O(n²). Big O describes growth rate, not exact speed. Also consider space complexity — extra memory used by your algorithm.

What are arrays and what are their time complexities?

BeginnerVery Common

An array is a contiguous block of memory storing elements of the same type, accessed by index in O(1) time. It is the most fundamental data structure.

Operation	Array	Dynamic Array (ArrayList)
Access by index	O(1)	O(1)
Search (unsorted)	O(n)	O(n)
Search (sorted)	O(log n)	O(log n)
Insert at end	O(1)*	O(1) amortized
Insert at middle	O(n)	O(n)
Delete at middle	O(n)	O(n)

JavaScript — Array Operations
// Two Pointers — classic array pattern:
function twoSum(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

// Sliding Window — O(n) vs O(n²) brute force:
function maxSumSubarray(nums, k) {
  let sum = nums.slice(0, k).reduce((a, b) => a + b, 0);
  let max = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k]; // slide window
    max = Math.max(max, sum);
  }
  return max;
}

What is a linked list and how does it differ from an array?

BeginnerVery Common

Singly Linked List

[Head] → [1|next] → [2|next] → [3|next] → [null] Each node holds: data + pointer to next node No random access — must traverse from head

Operation	Array	Linked List
Access by index	O(1) ✅	O(n) ❌
Insert at head	O(n)	O(1) ✅
Insert at tail	O(1)*	O(1) with tail ptr ✅
Insert at middle	O(n)	O(n) (search) + O(1) (insert)
Memory	Contiguous, cache-friendly	Scattered, pointer overhead

JavaScript — Linked List
class ListNode {
  constructor(val, next = null) {
    this.val = val; this.next = next;
  }
}

// Detect cycle — Floyd's fast/slow pointers:
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;
}

// Reverse linked list — O(n) time, O(1) space:
function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr; curr = next;
  }
  return prev;
}

What are stacks and queues? What are their use cases?

BeginnerVery Common

Stack (LIFO) vs Queue (FIFO)

STACK: push → [3][2][1] ← pop (top of stack) QUEUE: enqueue → [1][2][3] → dequeue (front of queue)

Feature	Stack	Queue
Order	LIFO (Last In, First Out)	FIFO (First In, First Out)
Operations	push, pop, peek	enqueue, dequeue, front
All ops time	O(1)	O(1)
Use cases	Undo/redo, call stack, DFS, balanced brackets	BFS, task scheduling, print queue, rate limiting
Variants	Min-stack, monotonic stack	Deque, priority queue, circular queue

JavaScript
// Valid parentheses — classic stack problem:
function isValid(s) {
  const stack = [], map = { ')':'(', '}':'{', ']':'[' };
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch);
    else if (stack.pop() !== map[ch]) return false;
  }
  return stack.length === 0;
}

// Min Stack — O(1) getMin():
class MinStack {
  constructor() { this.stack = []; this.mins = []; }
  push(val) {
    this.stack.push(val);
    const min = Math.min(val, this.mins.at(-1) ?? val);
    this.mins.push(min);
  }
  pop() { this.stack.pop(); this.mins.pop(); }
  getMin() { return this.mins.at(-1); }
}

What is a hash map and how does it achieve O(1) lookup?

BeginnerVery Common

A hash map (hash table, dictionary) stores key-value pairs. A hash function converts the key into an array index, enabling O(1) average-case access. Collisions (two keys map to same index) are resolved by chaining or open addressing.

Hash Map Internal

key "name" → hash("name") → 3 → bucket[3] → "Meraj" key "age" → hash("age") → 7 → bucket[7] → 25 key "city" → hash("city") → 3 → bucket[3].next → "Delhi" (chaining)

JavaScript — Hash Map Patterns
// Two Sum — hash map solution O(n):
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
}

// Frequency counter pattern:
function mostFrequent(arr) {
  const freq = new Map();
  for (const x of arr) freq.set(x, (freq.get(x) || 0) + 1);
  return [...freq.entries()].reduce((a, b) => b[1] > a[1] ? b : a)[0];
}

Collision handling: Chaining — each bucket is a linked list of entries. Open addressing — on collision, probe next empty slot (linear, quadratic, double hashing). Load factor (entries/capacity) determines when to resize (rehash) — typically at 0.75.

What is a binary search and when can you use it?

BeginnerVery Common

Binary search finds a target in a sorted array in O(log n) by repeatedly halving the search space. Each step eliminates half the remaining candidates.

Binary Search — find 7 in [1,3,5,7,9,11,13]

Step 1: mid = 5 (index 3) → 5 < 7 → search right half Step 2: mid = 9 (index 5) → 9 > 7 → search left half Step 3: mid = 7 (index 4) → found! ✓ Only 3 steps for 7 elements (log₂7 ≈ 2.8)

JavaScript — Binary Search Templates
// Classic binary search:
function binarySearch(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1; // avoid overflow
    if      (nums[mid] === target) return mid;
    else if (nums[mid] < target)  lo = mid + 1;
    else                           hi = mid - 1;
  }
  return -1;
}

// Left-most insertion point (lower bound):
function lowerBound(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo; // first index where nums[i] >= target
}

// Search on answer space (not array):
// "Find min days to ship packages" → binary search on days

What is a binary tree and what are common traversal methods?

BeginnerVery Common

Binary Tree

[1] / \ [2] [3] / \ [4] [5] Inorder (L→Root→R): 4, 2, 5, 1, 3 Preorder (Root→L→R): 1, 2, 4, 5, 3 Postorder (L→R→Root): 4, 5, 2, 3, 1 Level-order (BFS): 1, 2, 3, 4, 5

JavaScript — Tree Traversals
class TreeNode {
  constructor(val, left=null, right=null) {
    this.val=val; this.left=left; this.right=right;
  }
}

// DFS — Inorder (recursive):
function inorder(root, result=[]) {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

// BFS — Level order:
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [], size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

What is a Binary Search Tree (BST)?

BeginnerVery Common

A BST is a binary tree with the property: for every node, all values in the left subtree are less and all values in the right subtree are greater. This enables O(log n) search, insert, and delete on a balanced BST.

BST Example

[8] / \ [3] [10] / \ \ [1] [6] [14] Inorder traversal gives sorted: 1, 3, 6, 8, 10, 14

JavaScript — BST Operations
// BST search — O(h) where h = tree height:
function search(root, target) {
  if (!root || root.val === target) return root;
  return target < root.val
    ? search(root.left, target)
    : search(root.right, target);
}

// Validate BST — track min/max bounds:
function isValidBST(root, min=-Infinity, max=Infinity) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val)
      && isValidBST(root.right, root.val, max);
}

Worst case: A degenerate BST (sorted insert) becomes a linked list — O(n) operations. Self-balancing BSTs (AVL, Red-Black Tree) guarantee O(log n) height.

What is recursion and what is the base case?

BeginnerVery Common

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive function needs a base case (stopping condition) to prevent infinite recursion.

JavaScript — Recursion Patterns
// Pattern: base case + recursive case

// Factorial — O(n) time, O(n) space (call stack):
function factorial(n) {
  if (n <= 1) return 1;         // base case
  return n * factorial(n - 1); // recursive case
}

// Tree height — elegant with recursion:
function maxDepth(root) {
  if (!root) return 0;           // base case
  return 1 + Math.max(
    maxDepth(root.left),
    maxDepth(root.right)
  );
}

// Memoized Fibonacci — O(n) vs O(2ⁿ):
function fib(n, memo={}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

⚠️Stack overflow: Deep recursion (large n) can exhaust the call stack. Convert to iterative using an explicit stack, or use tail-call optimisation (TCO) if the language supports it.

What are basic sorting algorithms and their complexities?

BeginnerVery Common

Algorithm	Best	Average	Worst	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	❌
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(k)	✅

JavaScript — Merge Sort
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left  = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length)
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  return result.concat(left.slice(i), right.slice(j));
}

💡In practice: QuickSort is often fastest in practice due to cache locality despite O(n²) worst case. Most language built-in sorts use TimSort (hybrid merge + insertion sort) — O(n log n) worst, O(n) best.

What is a heap (priority queue) and what are its operations?

BeginnerVery Common

A heap is a complete binary tree stored as an array where the parent is always greater than (max-heap) or less than (min-heap) its children. It supports fast access to the max/min element.

Min-Heap (parent ≤ children)

[1] ← always minimum at root / \ [3] [2] / \ [5] [4] Array: [1, 3, 2, 5, 4] parent(i) = floor((i-1)/2)

Operation	Time
Get min/max (peek)	O(1)
Insert (push)	O(log n) — bubble up
Remove min/max (pop)	O(log n) — bubble down
Build heap from array	O(n)
Heap sort	O(n log n)

JavaScript — Heap Use Cases
// K Largest Elements — min-heap of size k:
// Keep a min-heap of k elements.
// If new element > heap minimum → push, then pop min.
// Result: k largest elements remain in heap.

// Merge K sorted lists → use min-heap:
// Push first element of each list.
// Pop min → add to result → push next from same list.
// O(n log k) vs O(nk) naive

// Top K frequent elements:
// 1. Count frequency with hash map.
// 2. Use min-heap of size k on (freq, element).
// 3. Return elements in heap. O(n log k)

What is a graph? What are adjacency lists vs adjacency matrices?

BeginnerVery Common

A graph is a set of vertices (nodes) connected by edges. Graphs can be directed or undirected, weighted or unweighted, cyclic or acyclic.

Graph Representations

Graph: A — B — D | | C —————— Adjacency List: A: [B, C] B: [A, D] C: [A, D] D: [B, C] Adjacency Matrix: A B C D A [0, 1, 1, 0] B [1, 0, 0, 1] C [1, 0, 0, 1] D [0, 1, 1, 0]

Feature	Adjacency List	Adjacency Matrix
Space	O(V + E) — sparse-friendly	O(V²) — always
Check edge (u,v)	O(degree of u)	O(1)
Get all neighbors	O(degree)	O(V)
Best for	Sparse graphs (most real graphs)	Dense graphs, fast edge lookup

What is BFS and DFS? When do you use each?

BeginnerVery Common

Feature	BFS (Breadth-First)	DFS (Depth-First)
Data structure	Queue	Stack (or recursion)
Traversal order	Level by level (wide)	Go deep before backtracking
Shortest path?	✅ Guarantees shortest (unweighted)	❌ Not guaranteed
Memory	O(w) width of graph	O(h) height of graph
Best for	Shortest path, nearest node, level-order	Cycle detection, topological sort, maze solving

JavaScript — BFS & DFS
// BFS — shortest path in grid:
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

// DFS — iterative (explicit stack):
function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    for (const neighbor of graph[node])
      stack.push(neighbor);
  }
}

What is a trie (prefix tree) and what is it used for?

BeginnerCommon

A trie is a tree where each node represents a character, and paths from root to terminal nodes represent words. Extremely efficient for prefix-based operations.

Trie storing: "cat", "car", "card", "care"

root └── c └── a ├── t [end] → "cat" └── r [end] → "car" ├── d [end] → "card" └── e [end] → "care"

JavaScript — Trie
class Trie {
  constructor() { this.root = {}; }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.'$' = true; // end of word marker
  }

  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node[ch]) return false;
      node = node[ch];
    }
    return !!node.'$';
  }

  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node[ch]) return false;
      node = node[ch];
    }
    return true;
  }
}
// Insert/search: O(m) where m = word length
// Space: O(ALPHABET_SIZE * max_word_length * word_count)

Use cases: Autocomplete, spell-checkers, IP routing (longest prefix match), word game dictionaries, prefix-based rate limiting.

⚡Intermediate QuestionsQ15–Q28

What is dynamic programming and what are the two main approaches?

IntermediateVery Common

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems, solving each once, and storing results to avoid redundant computation. It applies when a problem has optimal substructure and overlapping subproblems.

Approach	Top-Down (Memoization)	Bottom-Up (Tabulation)
Direction	Start at problem, recurse down	Start at base case, build up
Implementation	Recursion + cache (memo)	Iterative loops + DP table
Space	Call stack + memo O(n)	DP array O(n) or O(1) optimised
Easier to write?	✅ Follows natural recursion	Requires understanding DP order

JavaScript — Fibonacci: Both Approaches
// Top-Down (memoization) — O(n) time, O(n) space:
function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fib(n-1, memo) + fib(n-2, memo);
  memo.set(n, result);
  return result;
}

// Bottom-Up (tabulation) — O(n) time, O(1) space:
function fib(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

What is the 0/1 Knapsack problem?

IntermediateVery Common

Given items with weights and values, and a knapsack of capacity W, find the maximum value you can fit. Each item can be included at most once (0 or 1).

JavaScript — 0/1 Knapsack
// dp[i][w] = max value using first i items, capacity w
// Recurrence:
//   Skip item i:  dp[i-1][w]
//   Take item i:  dp[i-1][w - weight[i]] + value[i]
//   dp[i][w] = max(skip, take)  if w >= weight[i]

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({length: n+1}, () => new 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]; // skip
      if (weights[i-1] <= w)
        dp[i][w] = Math.max(dp[i][w],
          dp[i-1][w - weights[i-1]] + values[i-1]); // take
    }
  }
  return dp[n][W];
}
// Time: O(n*W)  Space: O(n*W) → can optimise to O(W)

💡Space optimisation: Use a 1D DP array and iterate w from W down to weight[i]. This makes it O(W) space. The classic pattern for knapsack-style problems.

What is Longest Common Subsequence (LCS)?

IntermediateVery Common

LCS finds the longest subsequence present in both strings (characters don't need to be contiguous). Classic DP problem that underlies git diff, DNA alignment, and plagiarism detection.

JavaScript — LCS
// LCS of "ABCBDAB" and "BDCAB" → "BCAB" length 4
// dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
// If s1[i-1] === s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
// Else:                   dp[i][j] = max(dp[i-1][j], dp[i][j-1])

function lcs(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}
// Time: O(m*n)  Space: O(m*n) → O(n) with rolling array

What is Dijkstra's algorithm?

IntermediateVery Common

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Uses a min-heap (priority queue) to always process the nearest unvisited vertex next.

JavaScript — Dijkstra's Algorithm
// graph: adjacency list { node: [[neighbor, weight], ...] }
function dijkstra(graph, start) {
  const dist = {};
  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;

  // Min-heap: [distance, node]
  const pq = [[0, start]]; // use a proper heap in production

  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]); // O(log n) with real heap
    const [d, u] = pq.shift();
    if (d > dist[u]) continue; // stale entry

    for (const [v, w] of graph[u]) {
      const newDist = dist[u] + w;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        pq.push([newDist, v]);
      }
    }
  }
  return dist;
}
// Time: O((V + E) log V) with binary heap

⚠️Dijkstra fails with negative weights. Use Bellman-Ford (O(VE)) for graphs with negative edges. For negative cycles, Bellman-Ford detects them. For all-pairs shortest paths, use Floyd-Warshall O(V³).

What is a Union-Find (Disjoint Set Union) data structure?

IntermediateVery Common

Union-Find efficiently tracks which elements belong to the same group (connected component). Supports two operations: find (which group?) and union (merge two groups). Used for detecting cycles, Kruskal's MST, network connectivity.

JavaScript — Union-Find with Path Compression
class UnionFind {
  constructor(n) {
    this.parent = Array.from({length: n}, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }

  find(x) {
    // Path compression — flatten tree
    if (this.parent[x] !== x)
      this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }

  union(x, y) {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false; // already connected
    // Union by rank
    if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
    else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
    else { this.parent[ry] = rx; this.rank[rx]++; }
    this.components--;
    return true;
  }
}
// With path compression + union by rank: nearly O(1) per op

What is topological sort and when is it used?

IntermediateVery Common

Topological sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every edge u→v, u comes before v. Used for task scheduling, build order, course prerequisites.

JavaScript — Topological Sort (Kahn's BFS)
// Kahn's Algorithm — O(V + E):
function topoSort(numNodes, prerequisites) {
  const inDegree = new Array(numNodes).fill(0);
  const adj = Array.from({length: numNodes}, () => []);

  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course);
    inDegree[course]++;
  }

  // Start with all nodes with no prerequisites
  const queue = [];
  for (let i = 0; i < numNodes; i++)
    if (inDegree[i] === 0) queue.push(i);

  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const next of adj[node])
      if (--inDegree[next] === 0) queue.push(next);
  }

  // If order.length !== numNodes → cycle exists (not a DAG)
  return order.length === numNodes ? order : [];
}

What is the two-pointer technique?

IntermediateVery Common

The two-pointer technique uses two indices (pointers) that move toward each other or in the same direction. It converts O(n²) brute-force solutions to O(n) for many array/string problems.

JavaScript — Two Pointer Patterns
// Pattern 1: Opposite ends → squeeze toward middle
// 3Sum problem — find all triplets summing to 0:
function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i-1]) continue; // skip dups
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if      (sum === 0) { result.push([nums[i], nums[left++], nums[right--]]); }
      else if (sum < 0)  left++;
      else               right--;
    }
  }
  return result;
}

// Pattern 2: Same direction (fast/slow — Floyd's cycle)
// Pattern 3: Sliding window (fixed or variable window size)

// Container with most water — O(n):
function maxWater(heights) {
  let lo = 0, hi = heights.length - 1, max = 0;
  while (lo < hi) {
    max = Math.max(max, Math.min(heights[lo], heights[hi]) * (hi - lo));
    heights[lo] < heights[hi] ? lo++ : hi--;
  }
  return max;
}

What is the sliding window technique?

IntermediateVery Common

The sliding window technique maintains a contiguous subarray/substring of a certain property, expanding or shrinking from one end to avoid reprocessing elements. Converts O(n²) or O(n³) solutions to O(n).

JavaScript — Sliding Window Patterns
// Fixed window — maximum sum of k consecutive elements:
function maxSumFixed(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;
}

// Variable window — longest substring with at most k distinct chars:
function longestKDistinct(s, k) {
  const freq = new Map();
  let left = 0, maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    freq.set(s[right], (freq.get(s[right]) || 0) + 1);
    while (freq.size > k) {
      freq.set(s[left], freq.get(s[left]) - 1);
      if (freq.get(s[left]) === 0) freq.delete(s[left]);
      left++;
    }
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

What is backtracking and how does it differ from brute force?

IntermediateVery Common

Backtracking builds a solution incrementally, pruning branches as soon as it determines they cannot lead to a valid solution. It's smarter than brute force because it abandons partial candidates early.

JavaScript — Backtracking Template
// General backtracking template:
function backtrack(state, choices, result) {
  if (isComplete(state)) { result.push([...state]); return; }

  for (const choice of choices) {
    if (!isValid(state, choice)) continue; // ← pruning!
    state.push(choice);         // choose
    backtrack(state, choices, result); // explore
    state.pop();               // unchoose (backtrack)
  }
}

// Permutations of [1,2,3]:
function permute(nums) {
  const result = [];
  function bt(current, remaining) {
    if (!remaining.length) { result.push([...current]); return; }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      bt(current, [...remaining.slice(0,i), ...remaining.slice(i+1)]);
      current.pop();
    }
  }
  bt([], nums);
  return result;
}

Classic backtracking problems: N-Queens, Sudoku solver, word search in grid, generate all subsets/combinations/permutations, letter combinations of phone number.

What is a monotonic stack and when do you use it?

IntermediateCommon

A monotonic stack maintains elements in increasing or decreasing order. When a new element violates the order, elements are popped — and at the moment of popping, you know the "next greater/smaller element" relationship.

JavaScript — Monotonic Stack Patterns
// Next Greater Element — O(n):
function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // monotonic decreasing stack of indices
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      result[stack.pop()] = nums[i]; // nums[i] is next greater
    }
    stack.push(i);
  }
  return result;
}

// Largest rectangle in histogram — O(n):
function largestRectangle(heights) {
  const stack = [-1];
  let max = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.at(-1) !== -1 && heights[stack.at(-1)] >= h) {
      const height = heights[stack.pop()];
      const width  = i - stack.at(-1) - 1;
      max = Math.max(max, height * width);
    }
    stack.push(i);
  }
  return max;
}

What is a segment tree?

IntermediateCommon

A segment tree is a binary tree that enables efficient range queries (sum, min, max) and point updates on an array in O(log n) — compared to O(n) for naive approaches.

Segment Tree for sum query on [1,3,5,7,9,11]

[0..5 = 36] / \ [0..2 = 9] [3..5 = 27] / \ / \ [0..1=4] [2=5] [3..4=16] [5=11] / \ / \ [0=1] [1=3] [3=7] [4=9]

JavaScript — Segment Tree (Sum)
class SegTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 1, 0, this.n - 1);
  }
  build(arr, node, start, end) {
    if (start === end) { this.tree[node] = arr[start]; return; }
    const mid = (start + end) >> 1;
    this.build(arr, 2*node, start, mid);
    this.build(arr, 2*node+1, mid+1, end);
    this.tree[node] = this.tree[2*node] + this.tree[2*node+1];
  }
  query(node, start, end, l, r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.tree[node];
    const mid = (start + end) >> 1;
    return this.query(2*node, start, mid, l, r)
         + this.query(2*node+1, mid+1, end, l, r);
  }
}

What is Kadane's algorithm?

IntermediateVery Common

Kadane's algorithm finds the maximum sum contiguous subarray in O(n) time and O(1) space. It's a classic DP problem where at each position you decide: extend the previous subarray or start fresh.

JavaScript — Kadane's Algorithm
// Max subarray sum — O(n) time, O(1) space:
function maxSubArray(nums) {
  let maxSum = nums[0], currentSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // Extend or start fresh:
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

// Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
//          → [4, -1, 2, 1] = 6

// Extension — track start/end indices:
function maxSubArrayWithIndices(nums) {
  let maxSum = nums[0], curSum = nums[0];
  let start = 0, end = 0, tempStart = 0;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > curSum + nums[i]) { curSum = nums[i]; tempStart = i; }
    else curSum += nums[i];
    if (curSum > maxSum) { maxSum = curSum; start = tempStart; end = i; }
  }
  return { maxSum, subarray: nums.slice(start, end + 1) };
}

What are greedy algorithms and when do they work?

IntermediateVery Common

Greedy algorithms make the locally optimal choice at each step, hoping to reach a globally optimal solution. They work when a problem has the greedy choice property (local optimum leads to global optimum) and optimal substructure.

JavaScript — Greedy Examples
// Activity selection — max non-overlapping intervals:
function maxActivities(intervals) {
  intervals.sort((a, b) => a[1] - b[1]); // sort by end time
  let count = 1, lastEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= lastEnd) { // starts after last ends
      count++;
      lastEnd = intervals[i][1];
    }
  }
  return count;
}

// Jump Game — can you reach end? Greedy O(n):
function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}

// Coin change — GREEDY FAILS for general case!
// [1, 5, 6, 9], target=11 → greedy gives 9+1+1=3 coins
// DP gives 6+5=2 coins. Use DP for coin change.

What is the fast and slow pointer technique?

IntermediateVery Common

The fast/slow pointer (Floyd's cycle detection) technique uses two pointers moving at different speeds. Used for cycle detection, finding middle elements, and more.

JavaScript — Fast & Slow Pointers
// Find middle of linked list:
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow; // slow is at middle
}

// Find cycle start:
function detectCycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) {
      // Found meeting point. Reset slow to head.
      slow = head;
      while (slow !== fast) { slow = slow.next; fast = fast.next; }
      return slow; // cycle start
    }
  }
  return null;
}

// Happy Number — cycle in sequence:
function isHappy(n) {
  const next = n => String(n).split('').reduce((s, d) => s + d*d, 0);
  let slow = n, fast = next(n);
  while (fast !== 1 && slow !== fast) { slow = next(slow); fast = next(next(fast)); }
  return fast === 1;
}

🔥Advanced QuestionsQ29–Q40

What are the key DP patterns you need to know?

AdvancedVery Common

Pattern	Recurrence	Examples
Linear DP	`dp[i] = f(dp[i-1], dp[i-2])`	Fibonacci, climbing stairs, coin change
2D DP	`dp[i][j] = f(dp[i-1][j], dp[i][j-1])`	LCS, edit distance, unique paths
Interval DP	`dp[i][j] = f(dp[i][k], dp[k+1][j])`	Matrix chain multiply, burst balloons
Knapsack	`dp[i][w] = max(skip, take)`	0/1 knapsack, partition equal subset
Tree DP	`dp[node] = f(dp[children])`	House robber III, diameter of tree
Bitmask DP	`dp[mask] = f(dp[mask ^ bit])`	TSP, assignment problem

JavaScript — Edit Distance (2D DP)
// Minimum edits (insert, delete, replace) to convert s1→s2:
function editDistance(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({length:m+1}, (_, i) =>
    Array.from({length:n+1}, (_, j) => i || j)
  );
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = s1[i-1] === s2[j-1]
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
  return dp[m][n];
}
// "horse" → "ros" = 3 edits

How does QuickSort work and how do you handle the pivot?

AdvancedVery Common

QuickSort picks a pivot, partitions the array (elements < pivot left, > pivot right), then recursively sorts each half. Average O(n log n), worst O(n²) when pivot is always min/max.

JavaScript — QuickSort
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
}

function partition(arr, lo, hi) {
  // Lomuto partition — pivot = arr[hi]
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) { [arr[++i], arr[j]] = [arr[j], arr[i]]; }
  }
  [arr[i+1], arr[hi]] = [arr[hi], arr[i+1]];
  return i + 1;
}

// Pivot strategies:
// 1. Last element  — simple but O(n²) on sorted arrays
// 2. Random        — O(n log n) expected, hard to degrade
// 3. Median-of-3   — first, middle, last median

// QuickSelect — find kth smallest in O(n) average:
function quickSelect(arr, k, lo = 0, hi = arr.length - 1) {
  const p = partition(arr, lo, hi);
  if (p === k) return arr[p];
  return p > k ? quickSelect(arr, k, lo, p-1) : quickSelect(arr, k, p+1, hi);
}

What is a minimum spanning tree (MST)?

AdvancedCommon

An MST of a connected, weighted, undirected graph spans all vertices with minimum total edge weight, using exactly V-1 edges and no cycles. Used in network design, clustering, and approximation algorithms.

JavaScript — Kruskal's MST Algorithm
// Kruskal's — O(E log E): sort edges, greedily add if no cycle
function kruskalMST(edges, n) {
  edges.sort((a, b) => a[2] - b[2]); // sort by weight
  const uf = new UnionFind(n);
  const mst = [];
  let totalCost = 0;

  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) { // add if it doesn't create cycle
      mst.push([u, v, w]);
      totalCost += w;
      if (mst.length === n - 1) break; // MST complete
    }
  }
  return { mst, totalCost };
}

// Prim's — O(E log V) with heap: grow MST from arbitrary root
// At each step, add minimum weight edge connecting MST to a new vertex

What is the Longest Increasing Subsequence (LIS)?

AdvancedVery Common

JavaScript — LIS: O(n²) DP and O(n log n) Patience Sorting
// O(n²) DP — dp[i] = LIS ending at index i:
function lisDP(nums) {
  const dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++)
    for (let j = 0; j < i; j++)
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
  return Math.max(...dp);
}

// O(n log n) — patience sorting with binary search:
function lis(nums) {
  const tails = [];
  for (const n of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      tails[mid] < n ? lo = mid + 1 : hi = mid;
    }
    tails[lo] = n; // replace or extend
  }
  return tails.length;
}
// Example: [10,9,2,5,3,7,101,18] → LIS length = 4 ([2,3,7,101])

What are balanced BSTs and how do AVL trees work?

AdvancedCommon

A balanced BST maintains O(log n) height by rebalancing after insertions and deletions. This guarantees O(log n) worst-case for all operations — unlike a regular BST which can degrade to O(n).

AVL Tree: Every node's left and right subtree heights differ by at most 1 (balance factor ∈ {-1, 0, 1}). Rebalances via rotations after each insert/delete. Stricter balance → faster lookup but more rotations than Red-Black.
Red-Black Tree: Each node is red or black. Rules ensure path from root to leaf is at most 2× shortest path → height ≤ 2 log n. Used in Java TreeMap, C++ std::map, Linux kernel scheduler. Fewer rotations than AVL → faster inserts/deletes.
Rotations: Left rotation (LL case), Right rotation (RR case), Left-Right (LR case), Right-Left (RL case). Rotations are O(1) and restore balance.
B-Tree / B+Tree: Used in databases and file systems. Nodes can have many children (high branching factor reduces height). B+Tree stores all data in leaves with linked list — enables efficient range queries.

💡In interviews: You rarely implement AVL/Red-Black from scratch. Know the concept (self-balancing, rotations, O(log n) guarantee) and be able to discuss trade-offs vs regular BST. Language built-ins handle this for you.

What is Bellman-Ford algorithm?

AdvancedCommon

Bellman-Ford finds shortest paths from a source to all vertices in a weighted graph — including graphs with negative edge weights. It also detects negative cycles. Slower than Dijkstra but more general.

JavaScript — Bellman-Ford
// O(V*E) time, O(V) space
function bellmanFord(n, edges, src) {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  // Relax all edges V-1 times:
  for (let i = 0; i < n - 1; i++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v])
        dist[v] = dist[u] + w;
    }
  }

  // V-th iteration: if relaxation still occurs → negative cycle:
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v])
      return null; // negative cycle detected
  }
  return dist;
}

💡Algorithm comparison: Dijkstra O((V+E)log V) — non-negative weights only. Bellman-Ford O(VE) — handles negatives, detects cycles. Floyd-Warshall O(V³) — all-pairs shortest paths, handles negatives.

What is the N-Queens problem and how do you solve it?

AdvancedVery Common

Place N queens on an N×N board so no two queens attack each other (same row, column, or diagonal). Classic backtracking problem.

JavaScript — N-Queens
function solveNQueens(n) {
  const solutions = [];
  const cols = new Set();
  const diag1 = new Set(); // row - col (same for all cells on / diagonal)
  const diag2 = new Set(); // row + col (same for all cells on \ diagonal)
  const board = Array.from({length: n}, () => '.'.repeat(n).split(''));

  function bt(row) {
    if (row === n) {
      solutions.push(board.map(r => r.join('')));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row-col) || diag2.has(row+col)) continue;
      // Place queen
      cols.add(col); diag1.add(row-col); diag2.add(row+col);
      board[row][col] = 'Q';
      bt(row + 1);
      // Remove queen (backtrack)
      cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
      board[row][col] = '.';
    }
  }

  bt(0);
  return solutions;
}
// N=4 has 2 solutions, N=8 has 92 solutions

What is the difference between BFS and Bidirectional BFS?

Advanced

Standard BFS explores all nodes up to distance d from the source. Bidirectional BFS runs BFS from both source AND destination simultaneously, meeting in the middle — dramatically reducing nodes explored.

Standard BFS: Explores O(b^d) nodes where b = branching factor, d = distance.
Bidirectional BFS: Each direction explores O(b^(d/2)) nodes → total O(2 × b^(d/2)) = exponentially fewer nodes.
Example: b=10, d=6. Standard: 10⁶ = 1,000,000 nodes. Bidirectional: 2 × 10³ = 2,000 nodes. 500× faster!

JavaScript — Bidirectional BFS (Word Ladder)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  let front = new Set([beginWord]);
  let back  = new Set([endWord]);
  let steps = 1;

  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front]; // always expand smaller
    const next = new Set();
    for (const word of front) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const w = word.slice(0,i) + String.fromCharCode(c) + word.slice(i+1);
          if (back.has(w)) return steps + 1;
          if (wordSet.has(w)) { next.add(w); wordSet.delete(w); }
        }
      }
    }
    front = next; steps++;
  }
  return 0;
}

What is a suffix array and suffix tree?

Advanced

Suffix arrays and suffix trees are data structures for efficient string operations, used in text search engines, bioinformatics (DNA sequencing), and data compression.

Suffix Array for "banana$"

Suffixes: Sorted suffixes: Suffix Array: 0: banana$ → 6: $ → [6, 5, 3, 1, 0, 4, 2] 1: anana$ 5: a$ 2: nana$ 3: ana$ 3: ana$ 1: anana$ 4: na$ 0: banana$ 5: a$ 4: na$ 6: $ 2: nana$

Suffix Array: Sorted array of all suffix starting positions. O(n log n) construction. Uses O(n) space. Pattern matching in O(m log n) with binary search.
Suffix Tree: Compressed trie of all suffixes. O(n) construction (Ukkonen's algorithm). O(m) pattern matching. Enables many O(n) string algorithms (LCS of two strings, longest repeated substring).
LCP Array: Longest Common Prefix between adjacent suffixes in sorted order. Combined with suffix array enables efficient repeated substring queries.

What is the KMP string matching algorithm?

AdvancedCommon

Knuth-Morris-Pratt (KMP) finds all occurrences of a pattern in a text in O(n + m) — faster than naive O(nm) because it avoids re-examining characters by using a failure function (partial match table).

JavaScript — KMP Algorithm
// Build failure function (partial match table):
function buildLPS(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0, i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) lps[i++] = ++len;
    else if (len > 0) len = lps[len - 1];
    else lps[i++] = 0;
  }
  return lps;
}

// KMP search:
function kmpSearch(text, pattern) {
  const lps = buildLPS(pattern);
  const matches = [];
  let i = 0, j = 0;
  while (i < text.length) {
    if (text[i] === pattern[j]) { i++; j++; }
    if (j === pattern.length) {
      matches.push(i - j); // found at index i-j
      j = lps[j - 1];
    } else if (i < text.length && text[i] !== pattern[j]) {
      j > 0 ? j = lps[j - 1] : i++;
    }
  }
  return matches;
}
// Time: O(n + m)  Space: O(m)

What is a Fenwick Tree (Binary Indexed Tree)?

Advanced

A Fenwick Tree (BIT) supports prefix sum queries and point updates in O(log n) time with O(n) space — simpler to implement than a segment tree for this specific use case.

JavaScript — Fenwick Tree
class BIT {
  constructor(n) {
    this.tree = new Array(n + 1).fill(0);
  }

  update(i, delta) { // add delta at index i (1-indexed)
    for (; i < this.tree.length; i += i & (-i))
      this.tree[i] += delta;
  }

  query(i) { // prefix sum [1..i]
    let sum = 0;
    for (; i > 0; i -= i & (-i))
      sum += this.tree[i];
    return sum;
  }

  range(l, r) { // range sum [l..r]
    return this.query(r) - this.query(l - 1);
  }
}

// i & (-i) isolates the lowest set bit — the "responsibility"
// each index covers a power-of-2 range of elements

// Use case: Count inversions in array, range sum with updates,
// rank queries, coordinate compression problems

What are common DSA problem-solving patterns and how do you choose the right one?

AdvancedVery Common

Recognising patterns is what separates strong candidates. Map problem characteristics to the right technique:

If the problem involves...	Think about...
Top/bottom K elements	Heap (priority queue)
Sorted array, find pair/triplet	Two pointers
Subarray/substring with constraint	Sliding window
Tree/graph traversal	BFS (level, shortest path) / DFS (path, cycle)
All possible combinations/subsets	Backtracking
Overlapping subproblems, optimisation	Dynamic programming
Sorted array, efficient search	Binary search
Connected components, cycle detection	Union-Find
Prefix/word lookup	Trie
Range queries + updates	Segment tree / Fenwick tree
Next greater/smaller element	Monotonic stack
Task ordering with dependencies	Topological sort
Shortest path, weighted graph	Dijkstra / Bellman-Ford
Interval scheduling / merging	Sort by start/end + greedy

💡Interview approach: (1) Clarify examples + edge cases. (2) Brute-force first — state it aloud. (3) Identify the bottleneck. (4) Apply the right pattern. (5) Code it. (6) Test with examples + edge cases. (7) Discuss time and space complexity.

Last One: DevOps & Docker

DSA done. The final page in this series covers DevOps fundamentals — Docker, Kubernetes, CI/CD pipelines, monitoring, and cloud infrastructure.

← System Design Q&A

JavaScript Python React TypeScript System Design All Articles

Data Structures & Algorithms
Interview Questions & Answers

🌱Beginner QuestionsQ1–Q14

⚡Intermediate QuestionsQ15–Q28

🔥Advanced QuestionsQ29–Q40

Last One: DevOps & Docker

we believe learning is more than just acquiring knowledge

quick link

help center

Get In Touch

Info@rankweb3.com

©2026, Rankweb3. All Rights Reserved

Data Structures & AlgorithmsInterview Questions & Answers

🌱Beginner QuestionsQ1–Q14

⚡Intermediate QuestionsQ15–Q28

🔥Advanced QuestionsQ29–Q40

Last One: DevOps & Docker

we believe learning is more than just acquiring knowledge

quick link

help center

Get In Touch

Info@rankweb3.com

©2026, Rankweb3. All Rights Reserved

Data Structures & Algorithms
Interview Questions & Answers