Data Structures & Algorithms Interview Questions

What Data Structures & Algorithms interviews cover

Sample Data Structures & Algorithms interview questions

• Find two numbers in an array that sum to a target (and analyze the complexity).
  What a strong answer covers

  • Hash map for O(n) time, O(n) space
  • Two-pointer after sorting for O(n log n) time, O(1) space
  • Handling duplicate numbers and multiple pairs
  • Common pitfall: forgetting to check for existing complement

  View a sample answer

  The two-sum problem can be solved efficiently using a hash map to store each number's index as we iterate. For each element, we check if its complement (target - current) exists in the map; if so, we return the indices. This gives O(n) time and O(n) space. An alternative is to sort the array first and use two pointers from the ends, which takes O(n log n) time and O(1) space but changes the original order. A common pitfall is assuming the array is sorted or failing to handle duplicates correctly—the hash map approach naturally handles duplicates by storing the latest index. For multiple pairs, you can collect all pairs by checking complements and removing used elements. The problem typically asks for exactly one pair, but follow-ups may ask for all pairs.

  def two_sum(nums, target):
      seen = {}  # value -> index
      for i, num in enumerate(nums):
          complement = target - num
          if complement in seen:
              return [seen[complement], i]
          seen[num] = i
      return []

• Detect a cycle in a linked list.
  What a strong answer covers

  • Floyd's tortoise and hare algorithm
  • Fast and slow pointers for O(n) time, O(1) space
  • Proof of cycle detection and meeting point
  • Common pitfall: null pointer dereference with fast.next

  View a sample answer

  Cycle detection in a linked list is best done using Floyd's algorithm: two pointers, slow (moves one step) and fast (moves two steps). If there is a cycle, they will eventually meet inside the cycle; if fast reaches None, no cycle exists. The time complexity is O(n) and space is O(1). The algorithm works because the fast pointer moves twice as fast, so it will catch up to the slow pointer in a cycle. A common pitfall is not checking fast and fast.next for None before advancing the fast pointer, which can cause a null pointer exception. An alternative is a hash set storing visited nodes, but that uses O(n) space. For detecting the start of the cycle, you reset one pointer to head after they meet and move both one step until they meet again.

  class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  
  def has_cycle(head):
      slow = head
      fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
          if slow == fast:
              return True
      return False

• Find the longest substring without repeating characters.
  What a strong answer covers

  • Sliding window with two pointers and hash map (or set)
  • O(n) time, O(min(m, n)) space where m is character set size
  • Expanding right pointer, shrinking left when duplicate
  • Common pitfall: forgetting to update the start pointer correctly

  View a sample answer

  The longest substring without repeating characters uses a sliding window with a hash map to store the most recent index of each character. We maintain two pointers, left and right, that define the current window. As we move right, if we see a character already in the map, we move left to max(left, last_index + 1) to skip the duplicate. We update the character's index and track the maximum window length. This runs in O(n) time because each character is processed at most twice (once by right, once by left). Space is O(min(m, n)) where m is the size of the character set (e.g., 128 for ASCII). A common pitfall is not updating left correctly when the duplicate is outside the current window; using max ensures we only move forward. An alternative is to use a set and shrink the window by removing characters from the left, but the map approach is more efficient.

  def length_of_longest_substring(s: str) -> int:
      char_index = {}  # character -> most recent index
      left = 0
      max_len = 0
      for right, ch in enumerate(s):
          if ch in char_index:
              left = max(left, char_index[ch] + 1)
          char_index[ch] = right
          max_len = max(max_len, right - left + 1)
      return max_len

• Do a level-order (BFS) traversal of a binary tree.
  What a strong answer covers

  • BFS using queue for level-order traversal
  • O(n) time, O(n) space for queue (worst-case width)
  • Processing levels one by one with size tracking
  • Common pitfall: mixing BFS order with DFS recursion

  View a sample answer

  Level-order traversal of a binary tree uses a queue to process nodes level by level. We start with the root in the queue. While the queue is not empty, we record the number of nodes at the current level (size), then pop that many nodes, adding their values to a level list, and push their left and right children (if any) to the queue. This yields a list of lists, each inner list representing one level. Time complexity is O(n) since each node is processed once. Space complexity is O(n) in the worst case due to the queue holding the maximum width (e.g., a complete tree's last level has n/2 nodes). A common pitfall is not separating levels correctly; without capturing size, you get a flat BFS order. Recursive DFS approaches cannot produce level-order directly without extra depth tracking.

  from collections import deque
  
  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  
  def level_order(root):
      if not root:
          return []
      result = []
      queue = deque([root])
      while queue:
          level_size = len(queue)
          level = []
          for _ in range(level_size):
              node = queue.popleft()
              level.append(node.val)
              if node.left:
                  queue.append(node.left)
              if node.right:
                  queue.append(node.right)
          result.append(level)
      return result

• Number of islands in a grid (BFS/DFS).
  What a strong answer covers

  • DFS/BFS on grid to find connected components
  • O(m * n) time, O(m * n) space in worst-case (recursion stack or queue)
  • Visited tracking or mutating grid to mark visited
  • Common pitfall: index out of bounds or revisiting processed cells

  View a sample answer

  The number of islands problem can be solved with either DFS or BFS. We iterate over every cell; when we find a '1' not visited, we increment the count and perform a traversal (DFS or BFS) to mark all connected '1's as visited. This can be done by modifying the grid in place (setting '1' to '0') or using a separate visited set. The time complexity is O(m * n) because each cell is visited once. Space complexity is O(m * n) in the worst case for recursion depth (DFS) or queue size (BFS). A common pitfall is forgetting to check boundaries before accessing adjacent cells, leading to index errors. BFS is often preferred to avoid recursion depth issues on very large grids. The algorithm is a classic example of connected components in a graph.

  from collections import deque
  
  def num_islands(grid):
      if not grid:
          return 0
      rows, cols = len(grid), len(grid[0])
      count = 0
      for r in range(rows):
          for c in range(cols):
              if grid[r][c] == '1':
                  count += 1
                  # BFS to mark the island
                  queue = deque([(r, c)])
                  grid[r][c] = '0'  # mark visited
                  while queue:
                      x, y = queue.popleft()
                      for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                          nx, ny = x + dx, y + dy
                          if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                              grid[nx][ny] = '0'
                              queue.append((nx, ny))
      return count

• Climbing stairs / coin change (basic dynamic programming).
  What a strong answer covers

  • Dynamic programming with bottom-up table or top-down memoization
  • O(amount * coins) time, O(amount) space for coin change
  • Recurrence: dp[i] = min(dp[i-coin] + 1) for each coin
  • Common pitfall: initializing dp with a large number and handling unreachable amounts

  View a sample answer

  The coin change problem (minimum number of coins) is solved by dynamic programming. We create an array dp of size amount + 1 initialized to a large number (e.g., float('inf')), with dp[0] = 0. For each coin, we iterate from coin to amount and update dp[i] = min(dp[i], dp[i - coin] + 1). This bottom-up approach computes the minimum coins needed for each amount. Time complexity is O(amount * number of coins), space is O(amount). A common pitfall is not handling the case where an amount is unreachable; we return -1 if dp[amount] remains inf. The problem is a classic example of unbounded knapsack dynamic programming. Variants include counting the number of ways or using top-down memoization with recursion, but bottom-up is simpler and avoids recursion depth issues.

  def coin_change(coins, amount):
      dp = [float('inf')] * (amount + 1)
      dp[0] = 0
      for coin in coins:
          for i in range(coin, amount + 1):
              dp[i] = min(dp[i], dp[i - coin] + 1)
      return dp[amount] if dp[amount] != float('inf') else -1

How to prepare

• Learn patterns, not problems — most questions map to a handful of templates.
• Always state the time and space complexity, and look for a better approach if it's brute force.
• Talk through your plan before coding, and test with a small example at the end.
• Practice writing bug-free code on a whiteboard or plain editor without autocomplete.

Frequently asked questions