Top 50 DSA Interview Questions

Master the most frequently asked Data Structures and Algorithms questions in tech interviews with detailed solutions and optimization techniques.

Question Frequency (FAANG 2023)

Arrays (25%)

Strings (20%)

Trees (18%)

Graphs (15%)

DP (12%)

Other (10%)

1. Array Problems

Two Sum


function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

Time: O(n)
Space: O(n)

Best Time to Buy/Sell Stock


function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;
  
  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }
  return maxProfit;
}

Time: O(n)
Space: O(1)

Common Patterns:

Sliding Window: Max subarray, Minimum window substring
Two Pointers: 3Sum, Container with most water
Prefix Sum: Subarray sum equals K

2. String Problems

Longest Substring Without Repeats


function lengthOfLongestSubstring(s) {
  const map = new Map();
  let maxLen = 0;
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right])) {
      left = Math.max(left, map.get(s[right]) + 1);
    }
    map.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Time: O(n)
Space: O(min(m,n))

Longest Palindromic Substring


function longestPalindrome(s) {
  let max = '';
  
  for (let i = 0; i < s.length; i++) {
    for (const j of [i, i+1]) {
      let [l, r] = [i, j];
      while (s[l] && s[l] === s[r]) {
        l--; r++;
      }
      if (r - l - 1 > max.length) {
        max = s.substring(l + 1, r);
      }
    }
  }
  return max;
}

Time: O(n²)
Space: O(1)

3. Tree Problems

Validate BST


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)

Lowest Common Ancestor


function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  return left && right ? root : left || right;
}

Time: O(n)
Space: O(h)

4. Graph Problems

Clone Graph


function cloneGraph(node, map = new Map()) {
  if (!node) return null;
  if (map.has(node)) return map.get(node);
  
  const clone = new Node(node.val);
  map.set(node, clone);
  
  for (const neighbor of node.neighbors) {
    clone.neighbors.push(cloneGraph(neighbor, map));
  }
  return clone;
}

Time: O(V+E)
Space: O(V)

Course Schedule (Topological Sort)


function canFinish(numCourses, prerequisites) {
  const graph = Array(numCourses).fill().map(() => []);
  const inDegree = Array(numCourses).fill(0);
  
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    inDegree[course]++;
  }
  
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  
  let count = 0;
  while (queue.length) {
    const course = queue.shift();
    count++;
    for (const neighbor of graph[course]) {
      if (--inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }
  return count === numCourses;
}

Time: O(V+E)
Space: O(V+E)

5. Dynamic Programming

House Robber


function rob(nums) {
  let prev = 0, curr = 0;
  for (const num of nums) {
    const temp = curr;
    curr = Math.max(prev + num, curr);
    prev = temp;
  }
  return curr;
}

Time: O(n)
Space: O(1)

Coin Change


function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  
  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Time: O(n×amount)
Space: O(amount)

Problem-Solving Patterns

Pattern	Example Questions	Approach
Sliding Window	Max Subarray, Longest Substring	Maintain window with start/end pointers
DFS/BFS	Tree/Graph Traversal, Islands	Stack/Queue with visited tracking
Topological Sort	Course Schedule, Dependency Resolution	Kahn's algorithm (in-degree counting)
Memoization	Fibonacci, Unique Paths	Cache repeated subproblems

Interview Strategy Checklist

✓ Clarify problem constraints and edge cases

✓ Start with brute force solution

✓ Optimize with appropriate data structures

✓ Walk through examples manually

✓ Discuss time/space complexity

Expert Tip: During interviews, focus on communication first. Verbalize your thought process even if you haven't arrived at the optimal solution yet. Interviewers value problem-solving approach as much as the final answer.

0 Interaction

0 Views

0 Likes