Algorithms Interview Questions

Common sorts:

• Bubble/Insertion: simple, O(n^2)
• Merge/Quick: O(n log n) average; merge stable; quick in-place
• Counting/Radix: linear for integers in range

Requires sorted array; halves the search space each step.

function binSearch(a, t){
  let l=0, r=a.length-1;
  while(l<=r){
    const m=(l+r)>>1;
    if(a[m]===t) return m;
    if(a[m]<t) l=m+1; else r=m-1;
  }
  return -1;
}

BFS explores level by level (shortest path in unweighted). DFS goes deep first (cycle detection, topological sort).

Break problems into overlapping subproblems; store results (memoization/tabulation).

// Fibonacci with memo
const memo = new Map();
function fib(n){
  if(n<2) return n;
  if(memo.has(n)) return memo.get(n);
  const v=fib(n-1)+fib(n-2);
  memo.set(n,v); return v;
}

Make locally optimal choices hoping for global optimum (activity selection, coin change for canonical systems).

Define base case; progress towards it; watch stack depth; convert to iteration if needed.

Use two indices moving towards each other or in tandem (reverse array, remove duplicates, sum pairs).

Maintain a window to track substring/subarray properties (max sum, longest unique substring).

Finds shortest paths in weighted graphs with non-negative edges using a priority queue (min-heap).

Orders DAG nodes so edges go from earlier to later nodes; implemented via DFS or Kahn's algorithm.

Preprocesses pattern to build LPS array for linear-time substring search; avoids redundant comparisons.

Average cost per operation over sequences, e.g., dynamic array appends or union-find path compression.

NP problems verifiable in polynomial time; NP-complete are the hardest in NP (SAT, Traveling Salesman). Use reductions and approximations.

Break problems into subproblems, solve recursively, and combine (merge sort, quicksort, FFT).

Overlapping subproblems and optimal substructure; common patterns like knapsack, LIS, edit distance.

Make locally optimal choices; correctness via exchange argument or matroid structure (interval scheduling, Huffman coding).

Lower/upper bound, first/last occurrence, searching on answer space; careful with mid and termination conditions.

Find k-th smallest in average O(n) using partitioning; worst-case O(n^2), can be optimized with median-of-medians.