Question 1

What is Big-O Notation, and how do you calculate Time and Space Complexity?

Accepted Answer

Big-O notation describes the upper bound (worst-case scenario) of an algorithm's growth rate in terms of time (execution steps) or space (memory usage) relative to the input size N.

Key Complexity Levels:
1. O(1) Constant: Execution time stays constant regardless of N (e.g., array index lookup, hash table search).
2. O(log N) Logarithmic: Input is halved at each step (e.g., Binary Search, BST lookup).
3. O(N) Linear: Time grows proportionally with N (e.g., single loop, linear search).
4. O(N log N) Linearithmic: Efficient sorting algorithms (e.g., Merge Sort, Quick Sort).
5. O(N^2) Quadratic: Nested loops over input N (e.g., Bubble Sort, Matrix multiplication).
6. O(2^N) Exponential: Recursive algorithms solving subproblems independently (e.g., naive Fibonacci).

Space Complexity measures additional memory allocated during execution (excluding input storage). Stack space used by recursive call stacks is counted in auxiliary space.
Code Example:
// O(1) Constant Time
function getFirstElement(arr) {
  return arr[0]; 
}

// O(N) Linear Time
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(log N) Logarithmic Time - Binary Search
function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Question 2

How are Arrays stored in memory? What is the difference between Static and Dynamic Arrays?

Accepted Answer

An Array is a collection of elements stored in contiguous (adjacent) memory locations. Because memory addresses are sequential, any element can be accessed in O(1) constant time using its base address and index formula: address = base_address + index * element_size.

Static Arrays:
- Fixed size allocated at initialization (e.g., in C/C++ or Java standard arrays).
- Memory reallocation is not possible; inserting beyond size causes index out of bounds error.

Dynamic Arrays (e.g., JavaScript Arrays, Python Lists, C++ std::vector):
- Automatically resizes when capacity is exceeded.
- When full, creates a new array with double capacity (usually 2x growth factor) and copies existing elements over.
- Amortized Time Complexity for insertion at end: O(1) average, O(N) worst-case during resize.
Code Example:
// Dynamic Array Resizing Concept
class DynamicArray {
  constructor() {
    this.capacity = 2;
    this.length = 0;
    this.data = new Array(this.capacity);
  }

push(element) {
    if (this.length === this.capacity) {
      this._resize(this.capacity * 2); // Double capacity
    }
    this.data[this.length] = element;
    this.length++;
  }

_resize(newCapacity) {
    const newData = new Array(newCapacity);
    for (let i = 0; i < this.length; i++) {
      newData[i] = this.data[i];
    }
    this.data = newData;
    this.capacity = newCapacity;
  }
}

Question 3

What is a Linked List? Compare Arrays vs Linked Lists and show how to Reverse a Linked List.

Accepted Answer

A Linked List is a linear data structure where elements (nodes) are stored non-contiguously in memory. Each node contains a data field and a pointer/reference (`next`) to the next node in the list.

Arrays vs Linked Lists Comparison:
- Access Time: Array is O(1) indexed access; Linked List is O(N) sequential traversal.
- Insertion/Deletion at head: Linked List is O(1) pointer updates; Array is O(N) element shifts.
- Insertion at middle/tail: Array is O(N); Linked List is O(1) if node reference is given, otherwise O(N) to traverse.
- Memory Overhead: Linked List uses extra memory for node pointers.

Reversing a Linked List iteratively requires three pointers: `prev`, `curr`, and `next`.
Code Example:
class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Iterative Reversal - O(N) Time, O(1) Space
function reverseLinkedList(head) {
  let prev = null;
  let curr = head;

while (curr !== null) {
    let nextNode = curr.next; // Store next node
    curr.next = prev;         // Reverse current pointer
    prev = curr;              // Move prev forward
    curr = nextNode;          // Move curr forward
  }

return prev; // New head of reversed list
}

Question 4

Explain Stacks (LIFO) and Queues (FIFO). How do you solve the Valid Parentheses problem using a Stack?

Accepted Answer

Stack (LIFO - Last In First Out):
- Elements are added and removed from the same end (top).
- Primary operations: push() - O(1), pop() - O(1), peek() - O(1).
- Applications: Function call stacks (recursion), Undo/Redo operations, Expression evaluation, Parentheses matching.

Queue (FIFO - First In First Out):
- Elements are inserted at the rear (enqueue) and removed from the front (dequeue).
- Primary operations: enqueue() - O(1), dequeue() - O(1).
- Applications: CPU Task Scheduling, Breadth-First Search (BFS), Printer spooling.

Valid Parentheses Algorithm:
Use a stack to track open brackets `(`, `{`, `[`. When encountering a closing bracket, check if it matches the top element of the stack. If not or if stack is empty, return false. At the end, stack must be empty.
Code Example:
function isValidParentheses(s) {
  const stack = [];
  const map = {
    ')': '(',
    '}': '{',
    ']': '['
  };

for (let char of s) {
    if (char in map) {
      // Closing bracket
      const topElement = stack.length > 0 ? stack.pop() : '#';
      if (topElement !== map[char]) {
        return false;
      }
    } else {
      // Opening bracket
      stack.push(char);
    }
  }

return stack.length === 0;
}

Question 5

How does Binary Search work? What are its prerequisites and Time Complexity?

Accepted Answer

Binary Search is a divide-and-conquer search algorithm that finds the position of a target value within a SORTED array.

Prerequisite: The input array MUST be sorted.

Algorithm Steps:
1. Maintain two pointers: `low` (0) and `high` (length - 1).
2. Calculate midpoint `mid = Math.floor((low + high) / 2)` (or `low + Math.floor((high - low) / 2)` to avoid integer overflow).
3. Compare target with `arr[mid]`:
   - If `arr[mid] == target`, target found, return `mid`.
   - If `arr[mid] < target`, search right half (`low = mid + 1`).
   - If `arr[mid] > target`, search left half (`high = mid - 1`).

Complexities:
- Time Complexity: O(log N) because search space is halved every iteration.
- Auxiliary Space Complexity: O(1) iterative, O(log N) recursive due to call stack.
Code Example:
function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

while (low <= high) {
    let mid = low + Math.floor((high - low) / 2);

if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1; // Search right
    } else {
      high = mid - 1; // Search left
    }
  }

return -1; // Not found
}

Question 6

Compare Insertion Sort, Selection Sort, and Bubble Sort. When is Insertion Sort preferred?

Accepted Answer

Elementary Sorting Algorithms Comparison: 1. Bubble Sort: Repeatedly swaps adjacent out-of-order elements. Time: O(N^2) worst/avg, O(N) best with swap flag. Space: O(1). Stable. 2. Selection Sort: Repeatedly finds minimum element from unsorted portion and swaps with first unsorted element. Time: O(N^2) all cases. Space: O(1). Unstable. 3. Insertion Sort: Builds sorted array one element at a time by shifting larger elements to the right. Time: O(N^2) worst/avg, O(N) best (already sorted). Space: O(1). Stable. Why Insertion Sort is preferred in practical systems: - Adaptive: Performs in O(N) linear time for nearly-sorted data. - Low constant factors: Performs faster than QuickSort/MergeSort for tiny arrays (N < 15-20). - Used in hybrid sorting algorithms like Timsort (Python/JS Array.prototype.sort) and Introsort. Code Example: function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { let key = arr[i]; let j = i - 1; // Shift elements of arr[0..i-1] that are greater than key to one position ahead while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } return arr; }

Question 7

Explain the Two Pointers Pattern. How does it optimize Two Sum II (Sorted Array) from O(N^2) to O(N)?

Accepted Answer

The Two Pointers pattern utilizes two index markers moving towards each other (left & right) or in the same direction (fast & slow) to process array sequences without nested iteration. Two Sum II (Sorted Array Problem): Given a 1-indexed array of integers sorted in non-decreasing order, find two numbers such that they add up to a specific target. Naive Approach: Two nested loops testing all pairs -> O(N^2) time, O(1) space. Two Pointers Approach: 1. Place `left = 0` and `right = arr.length - 1`. 2. Calculate `sum = arr[left] + arr[right]`: - If `sum === target`, solution found! - If `sum < target`, increment `left++` to increase sum (since array is sorted). - If `sum > target`, decrement `right--` to decrease sum. 3. Time Complexity: O(N) single pass. Space: O(1). Code Example: function twoSumSorted(numbers, target) { let left = 0; let right = numbers.length - 1; while (left < right) { let sum = numbers[left] + numbers[right]; if (sum === target) { return [left + 1, right + 1]; // 1-indexed output } else if (sum < target) { left++; } else { right--; } } return []; }

Question 8

What is the Sliding Window Pattern? Solve 'Maximum Sum Subarray of Size K' and 'Longest Substring Without Repeating Characters'.

Accepted Answer

The Sliding Window pattern is used to perform operations on a contiguous sub-segment (window) of an array or string, avoiding redundant recalculation.

1. Fixed-size Window: Window size K remains constant. Slide by adding incoming element and subtracting outgoing element (O(N) time vs O(N*K) naive).
2. Dynamic-size Window: Expand window (right pointer) to satisfy condition, contract window (left pointer) when condition is violated.

Longest Substring Without Repeating Characters (Dynamic Window):
Maintain a Set/Map of characters in current window. Expand `right`. If duplicate encountered, contract `left` until character becomes unique.
Code Example:
// Fixed Window: Max Sum Subarray of size K
function maxSubarraySum(arr, k) {
  if (arr.length < k) return 0;
  let maxSum = 0, windowSum = 0;

for (let i = 0; i < k; i++) windowSum += arr[i];
  maxSum = windowSum;

for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // Add incoming, remove outgoing
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

// Dynamic Window: Longest Substring Without Repeats
function lengthOfLongestSubstring(s) {
  let charSet = new Set();
  let left = 0, maxLength = 0;

for (let right = 0; right < s.length; right++) {
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    charSet.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  return maxLength;
}

Question 9

Explain Kadane's Algorithm for Maximum Subarray Sum. What is its Time and Space Complexity?

Accepted Answer

Kadane's Algorithm finds the contiguous subarray within a one-dimensional numeric array which has the largest sum in O(N) time and O(1) space.

Core Dynamic Programming Intuition:
At each index `i`, we decide whether to:
1. Extend the existing contiguous subarray sum: `currentSum + arr[i]`
2. Start a brand new contiguous subarray starting at `arr[i]`

Recurrence Relation:
`currentSum = Math.max(arr[i], currentSum + arr[i])`
`maxSum = Math.max(maxSum, currentSum)`

Handling all negative numbers:
Initialize `maxSum = arr[0]` and `currentSum = arr[0]`. This correctly handles arrays with all negative values.
Code Example:
function maxSubArray(nums) {
  if (nums.length === 0) return 0;

let currentSum = nums[0];
  let maxSum = nums[0];

for (let i = 1; i < nums.length; i++) {
    // Choose to join current subarray or start fresh
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }

return maxSum;
}

Question 10

How does Floyd's Cycle Detection Algorithm (Fast & Slow Pointers) detect a loop in a Linked List?

Accepted Answer

Floyd's Cycle Detection Algorithm uses two pointers moving at different speeds (Slow moves 1 step, Fast moves 2 steps) to detect if a cycle exists in a linked list.

Mathematical Proof:
If a cycle exists, Fast enters the cycle first. When Slow enters the cycle, Fast is some distance `d` behind Slow. At every step, Fast reduces the gap distance by 1 (`2 - 1 = 1`). Eventually, the distance becomes 0, meaning Fast and Slow MUST meet inside the cycle.

Finding the Start of the Cycle:
Once Fast and Slow meet, reset Slow to `head`. Move both Slow and Fast at 1 step per turn. The point where they meet again is the exact start node of the cycle!
Code Example:
function hasCycle(head) {
  let slow = head;
  let fast = head;

while (fast !== null && fast.next !== null) {
    slow = slow.next;        // Move 1 step
    fast = fast.next.next;   // Move 2 steps

if (slow === fast) {
      return true; // Cycle detected
    }
  }

return false; // No cycle
}

// Find Cycle Start Node
function detectCycleStart(head) {
  let slow = head, fast = head;
  let isCycle = false;

while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      isCycle = true;
      break;
    }
  }

if (!isCycle) return null;

slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow; // Cycle start node
}

Question 11

Design a Min Stack that supports push, pop, top, and getMin in O(1) time.

Accepted Answer

To retrieve the minimum element in O(1) constant time without scanning the stack, we must store tracking information alongside each element.

Two Common Approaches:
1. Auxiliary Min Stack: Maintain a primary `stack` and an auxiliary `minStack`. When pushing `val`, push `Math.min(val, minStack.top)` onto `minStack`. When popping, pop from both.
2. Single Stack with Value Pairs: Store objects `{ val, currentMin }` on a single stack.

Both approaches achieve O(1) time complexity for all methods at the cost of O(N) extra space.
Code Example:
class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }

push(val) {
    this.stack.push(val);
    if (this.minStack.length === 0) {
      this.minStack.push(val);
    } else {
      const currentMin = this.minStack[this.minStack.length - 1];
      this.minStack.push(Math.min(val, currentMin));
    }
  }

pop() {
    this.stack.pop();
    this.minStack.pop();
  }

top() {
    return this.stack[this.stack.length - 1];
  }

getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

Question 12

What is a Binary Search Tree (BST)? How do you validate if a Binary Tree is a valid BST?

Accepted Answer

A Binary Search Tree (BST) is a binary tree with the property: - For every node N, all values in N's left subtree are strictly LESS than N's value. - All values in N's right subtree are strictly GREATER than N's value. - Both left and right subtrees must also be valid BSTs. Inorder Traversal Property: An Inorder Traversal (Left -> Root -> Right) of a valid BST produces elements in strictly increasing sorted order. Validating a BST correctly: Comparing a node only against its immediate parent is INCORRECT. Each node must be validated against lower and upper bound ranges `[min, max]`. When traversing left, upper bound becomes `node.val`. When traversing right, lower bound becomes `node.val`. Code Example: function isValidBST(root) { function validate(node, min, max) { if (node === null) return true; if ((min !== null && node.val <= min) || (max !== null && node.val >= max)) { return false; } // Left subtree values must be < node.val // Right subtree values must be > node.val return validate(node.left, min, node.val) && validate(node.right, node.val, max); } return validate(root, null, null); }

Question 13

Compare Tree Traversals: DFS (Preorder, Inorder, Postorder) vs BFS (Level-Order Traversal).

Accepted Answer

Tree Traversals explore all nodes of a tree structure:

Depth-First Search (DFS) - Uses Stack / Recursion:
- Preorder (Root -> Left -> Right): Used for cloning trees, expression trees.
- Inorder (Left -> Root -> Right): Gives sorted order in BST.
- Postorder (Left -> Right -> Root): Used for bottom-up node deletion, evaluating postfix operations.

Breadth-First Search (BFS) - Uses Queue:
- Level-Order Traversal: Visits nodes level by level from top to bottom, left to right.
- Applications: Finding shortest distance in unweighted trees/graphs, finding minimum depth of a tree.
Code Example:
// DFS Inorder Recursive - O(N) Time, O(H) Space
function inorderTraversal(root) {
  const result = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    result.push(node.val);
    dfs(node.right);
  }
  dfs(root);
  return result;
}

// BFS Level-Order Traversal - O(N) Time, O(W) Space
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(currentLevel);
  }
  return result;
}

Question 14

How do you find the Lowest Common Ancestor (LCA) of two nodes in a Binary Tree?

Accepted Answer

The Lowest Common Ancestor (LCA) of two nodes p and q in a tree is the lowest node that has both p and q as descendants (where a node can be a descendant of itself).

Recursive DFS Strategy:
1. If current `node` is null, or `node === p`, or `node === q`, return `node`.
2. Recursively search left subtree (`left = LCA(node.left, p, q)`) and right subtree (`right = LCA(node.right, p, q)`).
3. Decision Logic:
   - If both `left` and `right` are non-null, `p` and `q` are found in separate subtrees, so current `node` is the LCA!
   - If only `left` is non-null, return `left`.
   - If only `right` is non-null, return `right`.

Time Complexity: O(N) where N is number of nodes. Space Complexity: O(H) call stack height.
Code Example:
function lowestCommonAncestor(root, p, q) {
  if (root === null || root === p || root === q) {
    return root;
  }

const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

if (left !== null && right !== null) {
    return root; // Found LCA
  }

return left !== null ? left : right;
}

Question 15

What is a Heap / Priority Queue? Explain Heapify and how to find the Kth Largest Element.

Accepted Answer

A Heap is a complete binary tree satisfied by Heap Property: - Max-Heap: Parent node value >= children node values (root is maximum). - Min-Heap: Parent node value <= children node values (root is minimum). Array Representation (0-indexed): For node at index `i`: - Left child = `2*i + 1` - Right child = `2*i + 2` - Parent = `Math.floor((i - 1) / 2)` Finding Kth Largest Element using Min-Heap of size K: 1. Maintain a Min-Heap of size K. 2. Iterate through array. Push elements into Min-Heap. 3. If heap size exceeds K, remove min element (`pop()`). 4. At end of array, top of Min-Heap is the Kth Largest Element! Time Complexity: O(N log K), Space: O(K). Code Example: // Finding Kth Largest using Min-Heap concept (Optimized QuickSelect achieves O(N) avg time) function findKthLargest(nums, k) { // Min-Heap array representation nums.sort((a, b) => b - a); // Simple sorting concept O(N log N) return nums[k - 1]; } // Manual Heapify Down for Max-Heap - O(log N) function heapify(arr, n, i) { let largest = i; let left = 2 * i + 1; let right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest !== i) { [arr[i], arr[largest]] = [arr[largest], arr[i]]; heapify(arr, n, largest); } }

Question 16

Compare Merge Sort vs Quick Sort in terms of Time, Space, and Stability.

Accepted Answer

Comparison of Divide-and-Conquer Sorting Algorithms:

Merge Sort:
- Time: O(N log N) in Best, Average, and Worst cases.
- Space: O(N) auxiliary array space.
- Stability: Stable (preserves relative order of duplicate elements).
- Use Case: External sorting (large datasets), Linked Lists.

Quick Sort:
- Time: O(N log N) Average/Best, O(N^2) Worst case (when pivot selection is poor on sorted data).
- Space: O(log N) auxiliary call stack space (in-place partitioning).
- Stability: Unstable by default.
- Use Case: General in-memory array sorting (fast cache locality).

Randomized Pivot Selection reduces QuickSort worst-case probability to near zero.
Code Example:
// Merge Sort Implementation - O(N log N) Time, O(N) Space
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

return result.concat(left.slice(i)).concat(right.slice(j));
}

Question 17

Explain Graph Representations and Graph Traversals: BFS vs DFS.

Accepted Answer

Graph Representations:
1. Adjacency Matrix: 2D array `matrix[u][v] = weight`. O(1) edge lookup, O(V^2) memory space. Suitable for dense graphs.
2. Adjacency List: Map/Array of lists `adj[u] = [v1, v2]`. O(V + E) memory space. Suitable for sparse graphs.

BFS (Breadth-First Search):
- Uses Queue data structure.
- Explores graph level-by-level.
- Guarantees shortest path in unweighted graphs.
- Time: O(V + E), Space: O(V).

DFS (Depth-First Search):
- Uses Stack / Recursion.
- Explores deeply down one path before backtracking.
- Used for topological sorting, cycle detection, connected components.
- Time: O(V + E), Space: O(V).
Code Example:
// Graph BFS Traversal
function bfsGraph(graph, startNode) {
  const visited = new Set();
  const queue = [startNode];
  visited.add(startNode);

while (queue.length > 0) {
    const node = queue.shift();
    console.log(node);

for (let neighbor of (graph[node] || [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

// Graph DFS Recursive
function dfsGraph(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node);

for (let neighbor of (graph[node] || [])) {
    dfsGraph(graph, neighbor, visited);
  }
}

Question 18

What is a Trie (Prefix Tree)? Implement Insert, Search, and StartsWith operations.

Accepted Answer

A Trie (Prefix Tree) is a tree-like search data structure used for storing strings where nodes share common prefixes.

Why use a Trie over a Hash Table?
- Hash Table lookup: O(L) where L is string length, but Hash Table cannot efficiently find all words starting with a prefix.
- Trie prefix search (`startsWith`): O(L) time without needing to scan all words.

Applications: Search engine autocomplete, spell checker, IP routing tables (longest prefix match).
Code Example:
class TrieNode {
  constructor() {
    this.children = {}; // Map of char -> TrieNode
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

insert(word) {
    let curr = this.root;
    for (let char of word) {
      if (!curr.children[char]) {
        curr.children[char] = new TrieNode();
      }
      curr = curr.children[char];
    }
    curr.isEndOfWord = true;
  }

search(word) {
    let curr = this.root;
    for (let char of word) {
      if (!curr.children[char]) return false;
      curr = curr.children[char];
    }
    return curr.isEndOfWord;
  }

startsWith(prefix) {
    let curr = this.root;
    for (let char of prefix) {
      if (!curr.children[char]) return false;
      curr = curr.children[char];
    }
    return true;
  }
}

Question 19

Explain Bitwise Operations and Bit Tricks: Solve Single Number and Count Set Bits.

Accepted Answer

Bitwise Operators operate directly on binary representations: - AND (`&`): 1 if both bits are 1. - OR (`|`): 1 if at least one bit is 1. - XOR (`^`): 1 if bits are DIFFERENT. Key properties: `x ^ x = 0`, `x ^ 0 = x`, Commutative & Associative. - NOT (`~`): Inverts bits. - Left Shift (`<<`): Multiply by 2. - Right Shift (`>>`): Divide by 2. Single Number Problem: Every element appears twice except one. Find that single one. Using XOR: `a ^ b ^ a = b`. XORing all elements cancels duplicates in O(N) time and O(1) space! Counting Set Bits (Brian Kernighan's Algorithm): Operation `n = n & (n - 1)` clears the lowest set bit in O(number of set bits) iterations. Code Example: // Single Number using XOR - O(N) Time, O(1) Space function singleNumber(nums) { let result = 0; for (let num of nums) { result ^= num; // Duplicate numbers cancel out to 0 } return result; } // Count Set Bits (Brian Kernighan's Algorithm) function countSetBits(n) { let count = 0; while (n > 0) { n = n & (n - 1); // Clears the lowest set bit count++; } return count; }

Question 20

Explain Dynamic Programming (DP) Principles: Memoization (Top-Down) vs Tabulation (Bottom-Up).

Accepted Answer

Dynamic Programming is an optimization technique used to solve complex problems by breaking them down into simpler overlapping subproblems and storing subproblem results to avoid redundant work.

Two Necessary Conditions for DP:
1. Overlapping Subproblems: Subproblems are computed repeatedly.
2. Optimal Substructure: Optimal solution to the main problem can be constructed from optimal solutions to subproblems.

Memoization (Top-Down DP):
- Start from original problem and recursively break down.
- Store computed results in a memo cache (Array/Hash Map).
- Easy to write from recursive relation.

Tabulation (Bottom-Up DP):
- Start from base cases and iteratively build up solution table.
- Avoids recursion stack overhead.
- Allows space optimization (e.g. keeping only previous state rows).
Code Example:
// Climbing Stairs / Fibonacci - Memoization O(N) Time, O(N) Space
function climbStairsMemo(n, memo = {}) {
  if (n <= 2) return n;
  if (n in memo) return memo[n];

memo[n] = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
  return memo[n];
}

// Climbing Stairs - Tabulation Space Optimized O(N) Time, O(1) Space
function climbStairsTab(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;

for (let i = 3; i <= n; i++) {
    let current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

Question 21

Solve the 0/1 Knapsack Problem using Dynamic Programming.

Accepted Answer

0/1 Knapsack Problem:
Given N items with weights `weights[]` and values `values[]`, and a knapsack of capacity `W`. Determine maximum value achievable without exceeding weight `W`. (Each item can be included AT MOST ONCE).

Recurrence Relation:
For item `i` and weight capacity `w`:
- Exclude item `i`: `dp[i][w] = dp[i-1][w]`
- Include item `i` (if `weights[i-1] <= w`): `values[i-1] + dp[i-1][w - weights[i-1]]`
`dp[i][w] = Math.max(exclude, include)`

Complexities:
- Time Complexity: O(N * W)
- Space Complexity: O(N * W), optimizable to O(W) using 1D space array backwards.
Code Example:
function knapsack01(weights, values, W) {
  const n = weights.length;
  const dp = Array(n + 1).fill(0).map(() => Array(W + 1).fill(0));

for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i - 1] <= w) {
        // Max of excluding or including item i
        dp[i][w] = Math.max(
          dp[i - 1][w],
          values[i - 1] + dp[i - 1][w - weights[i - 1]]
        );
      } else {
        dp[i][w] = dp[i - 1][w]; // Cannot include
      }
    }
  }

return dp[n][W]; // Maximum profit
}

Question 22

Explain the Longest Common Subsequence (LCS) Problem and its DP Solution.

Accepted Answer

Longest Common Subsequence (LCS):
Given two strings `text1` and `text2`, return the length of their longest common subsequence. A subsequence is a sequence derived without changing relative order.

Recurrence Relation:
If `text1[i-1] === text2[j-1]`:
  `dp[i][j] = 1 + dp[i-1][j-1]`
Else:
  `dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])`

Complexities:
- Time Complexity: O(M * N) where M and N are string lengths.
- Space Complexity: O(M * N).
Code Example:
function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

return dp[m][n];
}

Question 23

Solve the Coin Change Problem (Minimum Coins required for Amount) using DP.

Accepted Answer

Coin Change Problem:
Given integer array `coins` and total `amount`, return the FEWEST number of coins needed to make up `amount`. If not possible, return `-1`.

Dynamic Programming State:
`dp[i]` represents minimum coins needed to make amount `i`.
Initialize `dp[0] = 0` and all other `dp[i] = Infinity`.

Recurrence Relation:
For each `amount` from 1 to total:
  For each `coin` in coins:
    If `amount - coin >= 0`:
      `dp[amount] = Math.min(dp[amount], 1 + dp[amount - coin])`

Complexities:
- Time Complexity: O(amount * coins.length)
- Space Complexity: O(amount).
Code Example:
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // Base case: 0 coins needed for 0 amount

for (let i = 1; i <= amount; i++) {
    for (let coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
      }
    }
  }

return dp[amount] === Infinity ? -1 : dp[amount];
}

Question 24

What is Topological Sort? Implement Kahn's Algorithm (BFS) for Dependency Scheduling.

Accepted Answer

Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge `u -> v`, vertex `u` comes before vertex `v`.

Prerequisite: Must be a Directed Acyclic Graph (DAG). If graph has a cycle, topological sorting is impossible.

Applications: Build order compilation (e.g., Webpack/npm dependencies), Course Schedule prerequisites, Task scheduling.

Kahn's Algorithm (BFS Indegree Approach):
1. Compute indegree (number of incoming edges) for every vertex.
2. Push all vertices with `indegree == 0` into a Queue.
3. Dequeue vertex `u`, append to result list.
4. For each neighbor `v` of `u`, decrement `indegree[v]`. If `indegree[v]` becomes 0, push `v` into Queue.
5. If processed nodes count == total nodes, return topological order; else graph has a cycle!
Code Example:
function topologicalSortKahn(numNodes, edges) {
  const adj = Array(numNodes).fill(0).map(() => []);
  const inDegree = Array(numNodes).fill(0);

// Build Adjacency List & Indegrees
  for (let [u, v] of edges) {
    adj[u].push(v);
    inDegree[v]++;
  }

const queue = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

const topoOrder = [];
  while (queue.length > 0) {
    const node = queue.shift();
    topoOrder.push(node);

for (let neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

return topoOrder.length === numNodes ? topoOrder : []; // [] if cycle exists
}

Question 25

Explain Dijkstra's Algorithm for Shortest Path in Weighted Graphs.

Accepted Answer

Dijkstra's Algorithm finds the single-source shortest path from a starting node to all other nodes in a weighted graph with non-negative edge weights. Greedy Principle: Maintains a tentative distance array initialized to `Infinity` (start node distance = 0) and repeatedly picks the unvisited node with the minimum tentative distance using a Priority Queue / Min-Heap. Algorithm Steps: 1. Initialize `dist[start] = 0`, all other `dist[v] = Infinity`. 2. Push `(0, start)` into Priority Queue. 3. Pop node `u` with smallest distance `d`. 4. For each edge `(u, v, weight)`: If `dist[u] + weight < dist[v]`: `dist[v] = dist[u] + weight` Push `(dist[v], v)` into Priority Queue. Why non-negative weights only? Dijkstra assumes once a node is popped from Min-Heap, its shortest distance is finalized. Negative edge weights break this assumption (requires Bellman-Ford algorithm). Time Complexity: O((V + E) log V) with Min-Heap Priority Queue. Code Example: function dijkstra(numNodes, graph, startNode) { const dist = new Array(numNodes).fill(Infinity); dist[startNode] = 0; // Min Priority Queue stored as [distance, node] const pq = [[0, startNode]]; while (pq.length > 0) { // Sort array to simulate Min-Heap pq.sort((a, b) => a[0] - b[0]); const [d, u] = pq.shift(); if (d > dist[u]) continue; for (let [v, weight] of (graph[u] || [])) { if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push([dist[v], v]); } } } return dist; // Shortest distances from startNode }

Question 26

Explain Disjoint Set Union (DSU / Union-Find) with Path Compression and Union by Rank.

Accepted Answer

Disjoint Set Union (DSU / Union-Find) is a data structure that tracks a partition of a set into disjoint (non-overlapping) subsets.

Two Core Operations:
1. `find(i)`: Determine which subset element `i` belongs to (returns representative root).
2. `union(i, j)`: Merge subset containing `i` with subset containing `j`.

Optimizations:
- Path Compression: During `find(i)`, flatten the tree structure by pointing all traversed nodes directly to the root.
- Union by Rank/Size: Attach smaller tree under root of larger tree to keep tree height minimal.

Amortized Time Complexity:
O(α(N)) per operation, where α is Inverse Ackermann function (effectively O(1) constant time in practice).

Applications: Kruskal's Minimum Spanning Tree algorithm, Connected Components in dynamic graphs, Cycle Detection in undirected graphs.
Code Example:
class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = Array(size).fill(0);
  }

// Find with Path Compression - O(α(N))
  find(i) {
    if (this.parent[i] === i) return i;
    this.parent[i] = this.find(this.parent[i]); // Path compression
    return this.parent[i];
  }

// Union by Rank - O(α(N))
  union(i, j) {
    let rootI = this.find(i);
    let rootJ = this.find(j);

if (rootI !== rootJ) {
      if (this.rank[rootI] < this.rank[rootJ]) {
        this.parent[rootI] = rootJ;
      } else if (this.rank[rootI] > this.rank[rootJ]) {
        this.parent[rootJ] = rootI;
      } else {
        this.parent[rootJ] = rootI;
        this.rank[rootI]++;
      }
      return true; // Merged successfully
    }
    return false; // Already in same set (Cycle detected!)
  }
}

Question 27

What is a Monotonic Stack? Solve 'Next Greater Element' in O(N) time.

Accepted Answer

A Monotonic Stack is a stack whose elements are always sorted in either strictly increasing or strictly decreasing order.

Types:
- Monotonic Decreasing Stack: Elements from bottom to top are decreasing. Used to find Next Greater Element.
- Monotonic Increasing Stack: Elements from bottom to top are increasing. Used to find Next Smaller Element / Largest Rectangle in Histogram.

Next Greater Element Problem:
For each element in an array, find the first element to its right that is greater than it.

Algorithm:
Traverse array. Maintain decreasing stack of indices. While current element > stack top element, pop top index and record `result[topIndex] = currentElement`. Then push current index.

Time Complexity: O(N) because each index is pushed and popped AT MOST ONCE.
Code Example:
function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // Stores indices

for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const poppedIndex = stack.pop();
      result[poppedIndex] = nums[i];
    }
    stack.push(i);
  }

return result;
}

Question 28

Design an LRU (Least Recently Used) Cache with O(1) Get and Put operations.

Accepted Answer

An LRU Cache discards the least recently used item when capacity limit is reached.

Data Structures Required for O(1) Operations:
1. Hash Map: Maps `key -> DoublyLinkedListNode` for O(1) key lookup.
2. Doubly Linked List: Stores items ordered by usage. Head = Most Recently Used (MRU), Tail = Least Recently Used (LRU).

Operations:
- `get(key)`: If key exists in Hash Map, move node to Head (MRU) and return value. Return -1 if absent.
- `put(key, value)`: If key exists, update value and move node to Head. If new key, add to Head. If capacity exceeded, remove node from Tail (LRU) and delete from Hash Map.
Code Example:
class DLLNode {
  constructor(key, val) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new DLLNode(0, 0); // Dummy head
    this.tail = new DLLNode(0, 0); // Dummy tail
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

_addNode(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

_removeNode(node) {
    const prev = node.prev;
    const next = node.next;
    prev.next = next;
    next.prev = prev;
  }

_moveToHead(node) {
    this._removeNode(node);
    this._addNode(node);
  }

get(key) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      this._moveToHead(node);
      return node.val;
    }
    return -1;
  }

put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = value;
      this._moveToHead(node);
    } else {
      if (this.map.size >= this.capacity) {
        const lru = this.tail.prev; // Least recently used node
        this.map.delete(lru.key);
        this._removeNode(lru);
      }
      const newNode = new DLLNode(key, value);
      this.map.set(key, newNode);
      this._addNode(newNode);
    }
  }
}

Question 29

How do you find the Median in a Data Stream in O(log N) insert and O(1) findMedian?

Accepted Answer

Designing a data structure that continuously receives numbers and returns the median in real-time. Two Heaps Strategy: Maintain two heaps: 1. Max-Heap (`small`): Stores the smaller half of numbers. 2. Min-Heap (`large`): Stores the larger half of numbers. Heap Balancing Invariants: - Size condition: `small.length` is equal to or 1 greater than `large.length` (`0 <= small.size - large.size <= 1`). - Value condition: Every element in `small` <= every element in `large` (`max(small) <= min(large)`). Complexities: - `addNum(num)`: O(log N) heap push and rebalance. - `findMedian()`: O(1) constant time! - If total elements is odd: `small.top()` - If total elements is even: `(small.top() + large.top()) / 2` Code Example: // Dual Heap Concept Algorithm class MedianFinder { constructor() { this.small = []; // Simulated Max-Heap (stores smaller half) this.large = []; // Simulated Min-Heap (stores larger half) } addNum(num) { // 1. Push to small (Max-Heap) this.small.push(num); this.small.sort((a, b) => b - a); // 2. Ensure max(small) <= min(large) if (this.small.length > 0 && this.large.length > 0 && this.small[0] > this.large[0]) { const val = this.small.shift(); this.large.push(val); this.large.sort((a, b) => a - b); } // 3. Balance heap sizes if (this.small.length > this.large.length + 1) { const val = this.small.shift(); this.large.push(val); this.large.sort((a, b) => a - b); } else if (this.large.length > this.small.length) { const val = this.large.shift(); this.small.push(val); this.small.sort((a, b) => b - a); } } findMedian() { if (this.small.length > this.large.length) { return this.small[0]; } return (this.small[0] + this.large[0]) / 2; } }

Question 30

Solve the 3Sum Problem in O(N^2) Time using Sorting and Two Pointers.

Accepted Answer

3Sum Problem: Given an array `nums`, find all unique triplets `[nums[i], nums[j], nums[k]]` such that `i != j != k` and `nums[i] + nums[j] + nums[k] == 0`. Optimized Strategy (Sorting + Two Pointers): 1. Sort the input array in non-decreasing order O(N log N). 2. Iterate index `i` from 0 to N-3: - Skip duplicate values for `nums[i]` (`if (i > 0 && nums[i] === nums[i-1]) continue`). - Initialize `left = i + 1` and `right = N - 1`. - Calculate `sum = nums[i] + nums[left] + nums[right]`: - If `sum === 0`, save triplet `[nums[i], nums[left], nums[right]]`. - Advance `left` and `right`, skipping duplicates for both pointers. - If `sum < 0`, `left++` to increase sum. - If `sum > 0`, `right--` to decrease sum. Complexities: - Time Complexity: O(N^2) nested two-pointer search. - Auxiliary Space: O(1) excluding output storage. Code Example: function threeSum(nums) { nums.sort((a, b) => a - b); // O(N log N) const result = []; for (let i = 0; i < nums.length - 2; i++) { // Avoid duplicate triplets for i if (i > 0 && nums[i] === nums[i - 1]) continue; let left = i + 1; let right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { result.push([nums[i], nums[left], nums[right]]); // Skip duplicates for left and right while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (sum < 0) { left++; } else { right--; } } } return result; }

Data Structures & Algorithms (DSA) Interview Questions

Difficulty Filters

Tools & Options