Interview Q&A / Data Structures & Algorithms

1. How do you implement merge sort in JavaScript?

   Recursively split the array into two halves until single elements remain, then merge the sorted halves by repeatedly taking the smaller front element. It runs in O(n log n) time with O(n) extra space.

   BeginnerQuick answerCoding1 min read
2. What happens if a recursive function has no base case?

   It keeps calling itself, each call adds a frame to the call stack, and eventually the stack runs out of space. JavaScript throws a RangeError: Maximum call stack size exceeded.

   BeginnerQuick answer1 min read
3. How do you compute x to the power n efficiently with recursion?

   Use divide and conquer: x^n equals (x^(n/2)) squared, times x if n is odd. That halves n each time, so it needs only O(log n) multiplications instead of O(n).

   IntermediateQuick answerCoding1 min read
4. How do you generate all permutations of an array using backtracking?

   Build the permutation one position at a time. Try every unused element at the current position, mark it used, recurse, then unmark it. A complete path of length n is one permutation; there are n! of them.

   IntermediateQuick answerCoding1 min read
5. How do you generate all subsets of an array using backtracking?

   At each step, record the current path as a subset, then try adding each remaining element, recurse, and remove it again. An array of n items has 2^n subsets.

   IntermediateQuick answerCoding1 min read
6. How do you generate all valid combinations of n pairs of parentheses?

   Build the string character by character. You may add an opening bracket while fewer than n have been used, and a closing bracket only when it would not exceed the number of openings. A string of length 2n is valid.

   IntermediateQuick answerCoding1 min read
7. How do you implement quick sort, and when does it become slow?

   Pick a pivot, partition so smaller elements go left and larger go right, then recursively sort both sides. It averages O(n log n) but becomes O(n squared) when the pivot is always the smallest or largest element.

   IntermediateQuick answerCoding1 min read
8. How do you solve Combination Sum, finding all combinations that add up to a target when numbers can be reused?

   Sort the candidates and backtrack with a start index. Add a candidate, recurse with the reduced target (same start index so it can be reused), and stop a branch when the target is zero or the candidate exceeds it.

   IntermediateQuick answerCoding1 min read
9. How do you solve the N-Queens problem with backtracking?

   Place one queen per row. For each column in the row, check that no earlier queen shares the column or a diagonal. If safe, place it and recurse to the next row; otherwise skip. Undo and try the next column.

   AdvancedQuick answerCoding1 min read