Chapter•210 Minutes

Items per page

50 Essential Data Structures & Algorithms Coding Questions

A 50-question DSA problem bank covering arrays, strings, linked lists, trees, graphs, dynamic programming, and algorithm paradigms using the codeExample format.

Q1: Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Use a Hash Map to reduce lookup complexity to O(1).

Hash Map Two Sum Solution

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 [];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

💡 As we iterate through nums, we calculate the complement required to reach target. If the complement exists in our map, we immediately return its stored index and the current index.

Key Takeaways

Hash Map provides O(n) time complexity by storing complement values during iteration.
Avoids the naive O(n²) nested loop approach.

Knowledge Check

What is the time and space complexity of the Hash Map solution for Two Sum?

Q2: Valid Parentheses

Given a string containing (), {}, and [], determine if the input string is valid using a Stack data structure.

Stack Parentheses Validator

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', '}': '{', ']': '[' };
  
  for (let char of s) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  return stack.length === 0;
}

console.log(isValid('({[]})')); // true

💡 Opening brackets are pushed onto the stack. When a closing bracket is encountered, we pop the stack and verify that it matches the corresponding opening bracket type.

Key Takeaways

Stacks enforce Last-In, First-Out (LIFO) tracking for nested structure validations.
The string is invalid if an unexpected closing bracket appears or if brackets remain on the stack at the end.

Knowledge Check

What condition indicates an unclosed opening bracket after processing the entire string?

Q3: Reverse a Singly Linked List

Reverse a singly linked list in-place by reassigning the next pointers using three iteration references: prev, curr, and next.

Iterative Linked List Reversal

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    let nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
  }
  return prev;
}

💡 At each step, we save curr.next, point curr.next backward to prev, advance prev to curr, and move curr to the saved nextTemp pointer.

Key Takeaways

Reverses pointers in linear O(n) time and O(1) auxiliary space.
Requires storing curr.next in a temporary pointer before updating node link.

Knowledge Check

Which reference becomes the new head of the reversed linked list upon loop completion?

Q4: Merge Two Sorted Lists

Merge two sorted linked lists into one single sorted list by creating a dummy node and chaining smaller node values iteratively.

Sorted List Merge

function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  
  while (l1 !== null && l2 !== null) {
    if (l1.val < l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  
  tail.next = l1 !== null ? l1 : l2;
  return dummy.next;
}

💡 Compares front nodes of both lists, attaches the smaller node to tail, and advances that list's pointer. Any remaining nodes are appended at the end.

Key Takeaways

A dummy head node simplifies boundary edge cases when building the merged list.
Runs in O(n + m) time complexity where n and m are lengths of the lists.

Knowledge Check

Why is a dummy node used at the start of the algorithm?

Q5: Binary Search

Search for a target value within a sorted array using the divide-and-conquer strategy, reducing the search space by half in each iteration.

Binary Search Implementation

function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

console.log(binarySearch([-1, 0, 3, 5, 9, 12], 9)); // 4

💡 Calculates mid index safely. If target is larger than nums[mid], discards the left half; otherwise discards the right half.

Key Takeaways

Requires a sorted array input.
Achieves logarithmic O(log n) time complexity.

Knowledge Check

Why is Math.floor(left + (right - left) / 2) preferred over Math.floor((left + right) / 2)?

Q6: Maximum Subarray (Kadane's Algorithm)

Find the contiguous subarray with the largest sum within an array of numbers using Kadane's dynamic programming algorithm.

Kadane's Algorithm Solution

function maxSubArray(nums) {
  let currentSum = nums[0];
  let maxSum = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 (subarray [4,-1,2,1])

💡 currentSum updates to either the current item alone or current item plus previous running sum, whichever is greater, while maxSum tracks global maximum.

Key Takeaways

Kadane's algorithm runs in linear O(n) time complexity with O(1) space.
At each element, decides whether to extend the current sum or start a new subarray sum.

Knowledge Check

What is the time complexity of Kadane's Algorithm?

Q7: Linked List Cycle Detection (Floyd's Tortoise and Hare)

Detect whether a linked list contains a cycle using two pointers moving at different speeds (slow moves 1 step, fast moves 2 steps).

Floyd's Cycle Finding Algorithm

function hasCycle(head) {
  let slow = head;
  let fast = head;
  
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

💡 Slow moves one node at a time while fast moves two nodes. If there is no cycle, fast reaches null. If a cycle exists, fast meets slow inside the loop.

Key Takeaways

Floyd's algorithm detects cycles in O(n) time and O(1) space.
If a cycle exists, the fast pointer eventually catches up and equals the slow pointer.

Knowledge Check

What happens if Floyd's cycle detection is run on a linear list with no cycle?

Q8: Best Time to Buy and Sell Stock

Find the maximum profit possible from buying stock on one day and selling it on a future day given an array of daily stock prices.

Max Profit Calculator

function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;
  
  for (let price of prices) {
    if (price < minPrice) {
      minPrice = price;
    } else if (price - minPrice > maxProfit) {
      maxProfit = price - minPrice;
    }
  }
  return maxProfit;
}

console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5 (Buy at 1, sell at 6)

💡 Tracks minPrice encountered up to the current day. Max profit is updated if selling today yields higher profit than previously recorded maximum.

Key Takeaways

Single pass algorithm maintaining lowest price seen so far.
Achieves O(n) time and O(1) auxiliary space complexity.

Knowledge Check

What profit is returned if stock prices strictly decrease continuously (e.g. [7, 6, 4, 3, 1])?

Q9: Invert Binary Tree

Invert or mirror a binary tree recursively by swapping left and right child pointers for every node in the tree.

Recursive Binary Tree Inversion

function invertTree(root) {
  if (root === null) return null;
  
  const temp = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(temp);
  
  return root;
}

💡 Base case returns null. At each node, its left child receives the inverted right subtree and its right child receives the inverted left subtree.

Key Takeaways

Uses Depth-First Search (DFS) tree recursion.
Swaps .left and .right pointers at every level.

Knowledge Check

What is the time complexity of inverting a binary tree with N nodes?

Q10: Valid Anagram

Given two strings s and t, return true if t is an anagram of s (contains exact same character frequencies).

Frequency Map Anagram Check

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = {};
  
  for (let char of s) {
    count[char] = (count[char] || 0) + 1;
  }
  for (let char of t) {
    if (!count[char]) return false;
    count[char]--;
  }
  return true;
}

console.log(isAnagram('anagram', 'nagaram')); // true

💡 Increments character counts for string s and decrements for string t. If a character in t has zero count or doesn't exist, strings are not anagrams.

Key Takeaways

Return false early if string lengths differ.
Use a single frequency map or fixed 26-character array to count frequencies.

Knowledge Check

What is the space complexity if solving anagram verification using frequency map over ASCII/lowercase letters?

Q1: Two Sum

Q2: Valid Parentheses

Q3: Reverse a Singly Linked List

Q4: Merge Two Sorted Lists

Q5: Binary Search

Q6: Maximum Subarray (Kadane's Algorithm)

Q7: Linked List Cycle Detection (Floyd's Tortoise and Hare)

Q8: Best Time to Buy and Sell Stock

Q9: Invert Binary Tree

Q10: Valid Anagram

STAY UPDATED WITH BYTES!