50 Data Structures & Algorithms Interview Questions (With Answers)

Data structures and algorithms (DSA) interviews are the cornerstone of technical hiring at most software companies. This guide covers the 50 most common DSA interview questions — with concise answers, Big O analysis, and runnable code examples.

Quick reference

Arrays & Strings

1. What is the two-pointer technique and when should you use it?

Two pointers maintain two indices that move toward (or away from) each other, turning an O(n²) brute force into O(n).

Use when: the array is sorted (or you can sort it) and you need pairs, triplets, or subarrays satisfying a condition.

// Two Sum II — sorted array
function twoSum(numbers, target) {
  let lo = 0, hi = numbers.length - 1;
  while (lo < hi) {
    const sum = numbers[lo] + numbers[hi];
    if (sum === target) return [lo + 1, hi + 1];
    else if (sum < target) lo++;
    else hi--;
  }
  return [-1, -1];
}
// Time O(n) | Space O(1)

def two_sum_sorted(numbers, target):
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]
        elif s < target:
            lo += 1
        else:
            hi -= 1

2. Explain the sliding window pattern.

A window of fixed or variable size slides across an array/string, maintaining running state to avoid recomputation.

• Fixed window: move right, evict leftmost. O(n).
• Variable window: expand right until invalid, shrink from left.

// Longest substring without repeating characters — variable window
function lengthOfLongestSubstring(s) {
  const seen = new Map();
  let maxLen = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    if (seen.has(s[right]) && seen.get(s[right]) >= left) {
      left = seen.get(s[right]) + 1;
    }
    seen.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}
// Time O(n) | Space O(min(n, charset))

3. How do you find the maximum subarray sum?

Kadane's algorithm: keep a running sum; reset to 0 when it goes negative.

function maxSubArray(nums) {
  let maxSum = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    maxSum = Math.max(maxSum, cur);
  }
  return maxSum;
}
// Time O(n) | Space O(1)

Follow-up: to return the subarray indices, track start, tempStart, and end pointers.

4. How do you rotate an array in place?

Reverse the whole array, then reverse each part.

function rotate(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
}

function reverse(arr, l, r) {
  while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; }
}
// Time O(n) | Space O(1)

5. How do you find all duplicates in an array with values 1..n?

Use the array itself as a hash map: negate nums[abs(nums[i]) - 1]. If already negative, it's a duplicate.

def find_duplicates(nums):
    result = []
    for n in nums:
        idx = abs(n) - 1
        if nums[idx] < 0:
            result.append(abs(n))
        else:
            nums[idx] *= -1
    return result
# Time O(n) | Space O(1) — modifies input

Linked Lists

6. How do you reverse a singly linked list iteratively?

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}
// Time O(n) | Space O(1)

Recursive version uses O(n) call-stack space.

7. How do you detect a cycle in a linked list?

Floyd's tortoise-and-hare: slow pointer moves 1 step, fast moves 2. They meet inside the cycle if one exists.

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;
}
// Time O(n) | Space O(1)

Find entry point: after meeting, move one pointer to head; advance both one step at a time — they meet at the cycle entry.

8. How do you find the middle of a linked list?

Same tortoise-and-hare: when fast reaches the end, slow is at the middle.

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

9. How do you merge two sorted linked lists?

Use a dummy head to simplify edge cases:

function mergeTwoLists(l1, l2) {
  const dummy = { next: null };
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
    else                   { cur.next = l2; l2 = l2.next; }
    cur = cur.next;
  }
  cur.next = l1 || l2;
  return dummy.next;
}
// Time O(m+n) | Space O(1)

10. How do you check if a linked list is a palindrome in O(1) space?

1. Find middle.
2. Reverse second half.
3. Compare both halves.
4. (Optional) restore original list.

def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # reverse second half
    prev, cur = None, slow
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    # compare
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

Stacks & Queues

11. What is a monotonic stack and when is it useful?

A stack that maintains elements in monotonically increasing or decreasing order. Elements are popped when they violate the invariant.

Use cases: Next Greater Element, Largest Rectangle in Histogram, Daily Temperatures, Trapping Rain Water.

// Next Greater Element for each index
function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // indices, monotonically decreasing values
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}
// Time O(n) | Space O(n)

12. How do you implement a queue using two stacks?

Push to stackIn. To dequeue, transfer all items to stackOut (only when empty).

class MyQueue:
    def __init__(self):
        self.in_stack, self.out_stack = [], []

    def push(self, x):
        self.in_stack.append(x)

    def pop(self):
        self._transfer()
        return self.out_stack.pop()

    def peek(self):
        self._transfer()
        return self.out_stack[-1]

    def _transfer(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

Amortised O(1) per operation.

13. How do you design a min-stack with O(1) getMin?

Maintain a parallel minStack that tracks the minimum at each level.

class MinStack {
  constructor() { this.stack = []; this.minStack = []; }
  push(val) {
    this.stack.push(val);
    this.minStack.push(Math.min(val, this.minStack.at(-1) ?? val));
  }
  pop() { this.stack.pop(); this.minStack.pop(); }
  top() { return this.stack.at(-1); }
  getMin() { return this.minStack.at(-1); }
}

Trees

14. What are the four tree traversal orders?

from collections import deque

def level_order(root):
    if not root: return []
    result, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)
    return result

15. How do you validate a Binary Search Tree?

Pass min/max bounds down recursively:

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);
}
// Time O(n) | Space O(h)

16. How do you find the Lowest Common Ancestor (LCA)?

def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    left  = lca(root.left,  p, q)
    right = lca(root.right, p, q)
    return root if left and right else left or right
# Time O(n) | Space O(h)

17. What is the diameter of a binary tree?

The longest path between any two nodes. At each node, left_height + right_height is a candidate.

def diameter_of_binary_tree(root):
    diameter = [0]
    def height(node):
        if not node: return 0
        lh, rh = height(node.left), height(node.right)
        diameter[0] = max(diameter[0], lh + rh)
        return 1 + max(lh, rh)
    height(root)
    return diameter[0]

18. How do you serialize and deserialize a binary tree?

BFS (level-order) with null markers:

import json
from collections import deque

def serialize(root):
    if not root: return "[]"
    q, vals = deque([root]), []
    while q:
        node = q.popleft()
        if node:
            vals.append(node.val)
            q.append(node.left)
            q.append(node.right)
        else:
            vals.append(None)
    return json.dumps(vals)

def deserialize(data):
    vals = json.loads(data)
    if not vals: return None
    root = TreeNode(vals[0])
    q, i = deque([root]), 1
    while q and i < len(vals):
        node = q.popleft()
        if vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

19. What is a balanced binary tree and how do you check it?

A tree where every node's left and right subtree heights differ by at most 1.

def is_balanced(root):
    def check(node):
        if not node: return 0
        lh = check(node.left)
        if lh == -1: return -1
        rh = check(node.right)
        if rh == -1: return -1
        if abs(lh - rh) > 1: return -1
        return 1 + max(lh, rh)
    return check(root) != -1
# Time O(n) — single pass

20. How do you convert a sorted array to a balanced BST?

Pick the midpoint as root recursively:

def sorted_array_to_bst(nums):
    if not nums: return None
    mid = len(nums) // 2
    node = TreeNode(nums[mid])
    node.left  = sorted_array_to_bst(nums[:mid])
    node.right = sorted_array_to_bst(nums[mid+1:])
    return node

Heaps

21. What is a heap and what are its key operations?

A heap is a complete binary tree satisfying the heap property (max-heap: parent ≥ children). Implemented as an array where parent(i) = (i-1)//2, left(i) = 2i+1, right(i) = 2i+2.

22. How do you find the k-th largest element?

Min-heap of size k: maintain the k largest seen so far.

import heapq

def find_kth_largest(nums, k):
    min_heap = []
    for n in nums:
        heapq.heappush(min_heap, n)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]
# Time O(n log k) | Space O(k)

Alternatively, QuickSelect gives O(n) average O(n²) worst.

23. How do you find the median of a data stream?

Use two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep sizes balanced (±1).

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negate values)
        self.hi = []  # min-heap

    def add_num(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Time: O(log n) per insert, O(1) for median.

Hash Tables

24. How does a hash table handle collisions?

Load factor > 0.75 triggers rehash in most implementations.

25. How do you design a hash map from scratch?

class HashMap:
    def __init__(self, capacity=1024):
        self.cap = capacity
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, key):
        return hash(key) % self.cap

    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)
                return
        bucket.append((key, value))

    def get(self, key):
        for k, v in self.buckets[self._hash(key)]:
            if k == key: return v
        return -1

    def remove(self, key):
        bucket = self.buckets[self._hash(key)]
        self.buckets[self._hash(key)] = [(k, v) for k, v in bucket if k != key]

Graphs

26. What is the difference between BFS and DFS?

27. How do you detect a cycle in a directed graph?

DFS with three colours: WHITE (unvisited), GRAY (in current path), BLACK (fully processed). A gray-to-gray edge is a back edge → cycle.

def has_cycle(n, adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY: return True
            if color[v] == WHITE and dfs(v): return True
        color[u] = BLACK
        return False

    return any(dfs(u) for u in range(n) if color[u] == WHITE)

28. How does topological sort work?

Order nodes so every directed edge (u → v) has u before v. Only possible on a DAG.

from collections import deque

def topo_sort(n, adj):
    in_degree = [0] * n
    for u in range(n):
        for v in adj[u]: in_degree[v] += 1

    q = deque(u for u in range(n) if in_degree[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0: q.append(v)

    return order if len(order) == n else []  # empty = cycle exists

29. Explain Dijkstra's algorithm.

Greedy shortest-path algorithm for weighted graphs with non-negative edges.

import heapq

def dijkstra(n, adj, src):
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue  # stale entry
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist
# Time O(E log V) | Space O(V)

For negative weights, use Bellman-Ford O(VE).

30. What is Union-Find and when is it useful?

Disjoint Set Union (DSU) tracks connected components. Path compression + union by rank give near-O(1) amortised operations.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

Use when: number of islands, redundant connections, Kruskal's MST, friend circles.

Sorting

31. Compare common sorting algorithms.

Use mergesort when stability matters; quicksort for in-place average-case performance.

32. Implement quicksort with the partition step.

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

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

Worst case O(n²) with bad pivot (always min/max). Fix: random pivot or median-of-three.

33. When can you sort in O(n)?

When values are bounded integers — use counting sort or radix sort. Comparison-based sorting has a lower bound of Ω(n log n).

def counting_sort(arr, k):  # values in [0, k]
    count = [0] * (k + 1)
    for x in arr: count[x] += 1
    result, i = [], 0
    for val, c in enumerate(count):
        result.extend([val] * c)
    return result

Dynamic Programming

34. What are the key steps to solve a DP problem?

1. Define the state — what does dp[i] or dp[i][j] represent?
2. Write the recurrence — how does state i depend on smaller states?
3. Handle base cases — smallest inputs with known answers.
4. Determine order — bottom-up or top-down (memoisation).
5. Optimise space — rolling array if only previous row/column needed.

35. Solve the 0/1 knapsack problem.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i-1], values[i-1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i-1][c]
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    return dp[n][capacity]
# Time O(n*W) | Space O(n*W) → reduce to O(W) with 1D dp

36. Find the Longest Common Subsequence (LCS).

def lcs(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]
# Time O(m*n) | Space O(m*n)

37. Find the Longest Increasing Subsequence (LIS).

O(n log n) with patience sorting:

import bisect

def lis_length(nums):
    tails = []
    for n in nums:
        pos = bisect.bisect_left(tails, n)
        if pos == len(tails):
            tails.append(n)
        else:
            tails[pos] = n
    return len(tails)

38. What is the coin change problem?

Minimum coins to make an amount — unbounded knapsack variant:

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1
# Time O(amount * len(coins))

Big O Notation

39. What does Big O notation measure?

Big O describes asymptotic upper bound on runtime (or space) as input size n → ∞, ignoring constant factors.

40. What is the difference between best, average, and worst case?

• Worst case (Big O): upper bound — guarantees algorithm won't exceed this.
• Best case (Ω — Omega): lower bound — best possible performance.
• Average case (Θ — Theta): expected performance over all inputs.

Quicksort: O(n²) worst, O(n log n) average. Hash lookup: O(n) worst (all collide), O(1) average.

41. How do you calculate the space complexity of a recursive function?

Space = O(depth of recursion × space per frame).

• Simple recursion with no arrays: O(h) where h is call-stack depth.
• Tree DFS on balanced tree: O(log n).
• Naive Fibonacci: O(n) — each call stays alive.
• Memoised Fibonacci: O(n) time + O(n) space for cache + O(n) stack.

Advanced Topics

42. What is a trie and what is it used for?

A trie (prefix tree) stores strings character-by-character. Each node represents a prefix.

Use cases: autocomplete, spell checking, IP routing, word search.

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 search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.is_end

    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
# Insert/Search: O(m) where m = word length

43. Explain bit manipulation tricks used in interviews.

# Check if n is a power of 2
is_power_of_two = lambda n: n > 0 and (n & (n - 1)) == 0

# Count set bits (Brian Kernighan's)
def count_bits(n):
    count = 0
    while n:
        n &= n - 1  # clears lowest set bit
        count += 1
    return count

# XOR to find single number (all others appear twice)
from functools import reduce
single = lambda nums: reduce(lambda a, b: a ^ b, nums)

# Swap without temp
a, b = 5, 3
a ^= b; b ^= a; a ^= b  # a=3, b=5

# Get / set / clear bit i
get_bit   = lambda n, i: (n >> i) & 1
set_bit   = lambda n, i: n | (1 << i)
clear_bit = lambda n, i: n & ~(1 << i)

44. What is memoisation vs tabulation?

Both give the same time complexity. Prefer tabulation for large inputs; memoisation for sparse state spaces.

45. What is QuickSelect and when does it beat sorting?

QuickSelect finds the k-th smallest element in O(n) average without fully sorting.

import random

def quick_select(nums, k):
    # Returns k-th smallest (0-indexed)
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        pivot_idx = partition(nums, lo, hi)
        if pivot_idx == k: return nums[k]
        elif pivot_idx < k: lo = pivot_idx + 1
        else: hi = pivot_idx - 1
    return nums[lo]

def partition(arr, lo, hi):
    rand = random.randint(lo, hi)
    arr[rand], arr[hi] = arr[hi], arr[rand]
    pivot, i = arr[hi], lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

Use when: only the median/k-th element is needed — O(n) vs O(n log n) sort.

46. How do you solve the "number of islands" problem?

BFS/DFS from each unvisited '1' cell, marking all connected land cells as visited.

def num_islands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # mark visited (mutates input)
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            dfs(r + dr, c + dc)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count
# Time O(m*n) | Space O(m*n) worst case stack

47. What is the difference between a BST and a balanced BST?

48. Explain segment trees.

A segment tree supports range queries and point updates in O(log n).

class SegmentTree:
    def __init__(self, nums):
        n = len(nums)
        self.n = n
        self.tree = [0] * (2 * n)
        # Build
        for i, v in enumerate(nums):
            self.tree[n + i] = v
        for i in range(n - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]

    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]

    def query(self, l, r):  # [l, r)
        l += self.n; r += self.n
        result = 0
        while l < r:
            if l & 1: result += self.tree[l]; l += 1
            if r & 1: r -= 1; result += self.tree[r]
            l //= 2; r //= 2
        return result

Alternatives: Fenwick tree (BIT) — simpler, O(log n), but only for prefix queries.

49. What is the difference between DFS iterative vs recursive?

Recursive DFS uses the call stack implicitly. Iterative DFS uses an explicit stack but pops in the same order only if you push right child before left (for pre-order left-first traversal):

def dfs_iterative(root):
    if not root: return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right: stack.append(node.right)  # push right first
        if node.left:  stack.append(node.left)
    return result  # preorder: root, left, right

Iterative is preferred for very deep trees (avoids stack overflow).

50. What is amortised analysis? Give an example.

Amortised analysis averages the cost over a sequence of operations, even if some individual operations are expensive.

Dynamic array doubling:

• Most append calls are O(1).
• Occasionally triggers O(n) resize.
• Total cost of n appends = n + n/2 + n/4 + … = O(2n) = O(n).
• Amortised cost per append = O(1).

Similarly, stack operations in monotonic stack problems are O(n) total even though individual iterations may pop multiple elements.

Common mistakes

DSA vs related fields

FAQ

Q: How much DSA do I need to know for a FAANG interview? Focus on arrays, linked lists, trees, graphs, sorting, and dynamic programming. Know Big O for every solution. Practice 100–150 LeetCode problems covering all patterns above.

Q: Is recursion always worse than iteration? No — recursive code is often cleaner and equivalent. The risk is stack overflow for very deep inputs (> 10,000 levels). Use iterative DFS or increase stack size when needed.

Q: When does O(n log n) beat O(n²)? For n = 10,000: n² = 100M operations vs n log n ≈ 130K. In practice, algorithms with better Big O win for n > ~100 even with higher constants.

Q: What's the difference between a heap and a priority queue? A priority queue is the abstract data type (highest/lowest priority element first). A heap is the most common implementation. Python's heapq is a min-heap implementing a priority queue.

Q: Graph BFS vs Dijkstra — when to use which? Use BFS for unweighted shortest path (O(V+E)). Use Dijkstra for weighted graphs with non-negative edges (O(E log V)). For negative edges, use Bellman-Ford.

Q: Should I memorise sorting algorithms? Know mergesort and quicksort implementation-level. Understand all algorithms in the comparison table above conceptually — interviewers often ask "which would you choose and why?"