Interview Prep

// JavaScript
function getFirst(arr) {
  return arr[0];
}

const map = new Map();
map.set('key', 42);
map.get('key'); // O(1) average

# Python
def get_first(arr):
    return arr[0]

lookup = {'key': 42}
lookup['key']  # O(1) average

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

# Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

// JavaScript
function findMax(arr) {
  let max = -Infinity;
  for (const val of arr) {
    if (val > max) max = val;
  }
  return max;
}

# Python
def find_max(arr):
    maximum = float('-inf')
    for val in arr:
        if val > maximum:
            maximum = val
    return maximum

// JavaScript
// Merge sort achieves O(n log n) guaranteed
const sorted = [5, 2, 8, 1, 9].sort((a, b) => a - b);
// Built-in sort: V8 uses TimSort → O(n log n)

# Python
# Python's sorted() uses TimSort → O(n log n)
result = sorted([5, 2, 8, 1, 9])
# list.sort() is in-place, also O(n log n)

// JavaScript
function hasDuplicateBrute(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

# Python
def has_duplicate_brute(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

// JavaScript
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}
// Each call branches into 2 → O(2^n)

# Python
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# Fix with memoization → O(n)

// JavaScript
function permutations(arr) {
  if (arr.length <= 1) return [arr];
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const perm of permutations(rest)) {
      result.push([arr[i], ...perm]);
    }
  }
  return result;
}

# Python
def get_permutations(arr):
    if len(arr) <= 1:
        return [arr[:]]
    result = []
    for i in range(len(arr)):
        rest = arr[:i] + arr[i+1:]
        for perm in get_permutations(rest):
            result.append([arr[i]] + perm)
    return result

// JavaScript — Analyzing a function
function example(arr) {
  // Loop 1: O(n)
  for (let i = 0; i < arr.length; i++) { /* ... */ }
  // Loop 2 (nested): O(n^2)
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) { /* ... */ }
  }
}
// Total: O(n) + O(n^2) = O(n^2) — dominated by the larger term

# Python — Same analysis
def example(arr):
    for x in arr:        # O(n)
        pass
    for x in arr:        # O(n^2)
        for y in arr:
            pass
# Total: O(n^2)

// JavaScript
// O(1) space — in-place swap
function reverseInPlace(arr) {
  let l = 0, r = arr.length - 1;
  while (l < r) {
    [arr[l], arr[r]] = [arr[r], arr[l]];
    l++; r--;
  }
}

// O(n) space — new array
function reversed(arr) {
  return arr.slice().reverse();
}

# Python
def reverse_in_place(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]
        l += 1; r -= 1

def reversed_copy(arr):
    return arr[::-1]  # O(n) space

// JavaScript
// Dynamic array (push) — occasionally resizes (O(n) copy)
// but amortized cost per push is O(1)
const arr = [];
for (let i = 0; i < 1000; i++) {
  arr.push(i); // Amortized O(1) per push
}

# Python
# Python list.append is amortized O(1)
arr = []
for i in range(1000):
    arr.append(i)  # Amortized O(1)

// JavaScript — Find pair that sums to target in sorted array
function twoSumSorted(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return [-1, -1];
}

# Python
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

// JavaScript — Max sum subarray of size k
function maxSumWindow(arr, k) {
  let windowSum = 0, maxSum = -Infinity;
  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];
    if (i >= k) windowSum -= arr[i - k];
    if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

# Python — Max sum subarray of size k
def max_sum_window(arr, k):
    window_sum = 0
    max_sum = float('-inf')
    for i in range(len(arr)):
        window_sum += arr[i]
        if i >= k:
            window_sum -= arr[i - k]
        if i >= k - 1:
            max_sum = max(max_sum, window_sum)
    return max_sum

// JavaScript
function buildPrefix(arr) {
  const prefix = [0];
  for (const val of arr) {
    prefix.push(prefix[prefix.length - 1] + val);
  }
  return prefix;
}
function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

# Python
def build_prefix(arr):
    prefix = [0]
    for val in arr:
        prefix.append(prefix[-1] + val)
    return prefix

def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

// JavaScript
function maxSubarraySum(arr) {
  let current = arr[0], best = arr[0];
  for (let i = 1; i < arr.length; i++) {
    current = Math.max(arr[i], current + arr[i]);
    best = Math.max(best, current);
  }
  return best;
}

# Python
def max_subarray_sum(arr):
    current = best = arr[0]
    for num in arr[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

// JavaScript
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

# Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

// JavaScript
function reverseString(s) {
  const chars = s.split('');
  let l = 0, r = chars.length - 1;
  while (l < r) {
    [chars[l], chars[r]] = [chars[r], chars[l]];
    l++; r--;
  }
  return chars.join('');
}
// Built-in: s.split('').reverse().join('')

# Python
def reverse_string(s):
    chars = list(s)
    l, r = 0, len(chars) - 1
    while l < r:
        chars[l], chars[r] = chars[r], chars[l]
        l += 1; r -= 1
    return ''.join(chars)
# Built-in: s[::-1]

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

# Python
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for ch in t:
        if freq.get(ch, 0) == 0:
            return False
        freq[ch] -= 1
    return True

// JavaScript — Hash set approach
function containsDuplicate(arr) {
  const seen = new Set();
  for (const val of arr) {
    if (seen.has(val)) return true;
    seen.add(val);
  }
  return false;
}

function findDuplicate(arr) {
  // Values in range [1, n], exactly one duplicate
  const seen = new Set();
  for (const val of arr) {
    if (seen.has(val)) return val;
    seen.add(val);
  }
}

# Python
def contains_duplicate(arr):
    seen = set()
    for val in arr:
        if val in seen:
            return True
        seen.add(val)
    return False

def find_duplicate(arr):
    seen = set()
    for val in arr:
        if val in seen:
            return val
        seen.add(val)

// JavaScript
function frequencyMap(arr) {
  const freq = new Map();
  for (const item of arr) {
    freq.set(item, (freq.get(item) || 0) + 1);
  }
  return freq;
}

function mostFrequent(arr) {
  const freq = frequencyMap(arr);
  let maxCount = 0, result = null;
  for (const [key, count] of freq) {
    if (count > maxCount) { maxCount = count; result = key; }
  }
  return result;
}

# Python
from collections import Counter

def frequency_map(arr):
    freq = {}
    for item in arr:
        freq[item] = freq.get(item, 0) + 1
    return freq

def most_frequent(arr):
    return Counter(arr).most_common(1)[0][0]

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

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

// JavaScript
function groupAnagrams(words) {
  const groups = new Map();
  for (const word of words) {
    const key = word.split('').sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return Array.from(groups.values());
}

# Python
def group_anagrams(words):
    groups = {}
    for word in words:
        key = ''.join(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())

// JavaScript
function subarraySum(nums, k) {
  const prefixCount = new Map([[0, 1]]);
  let prefix = 0, count = 0;
  for (const num of nums) {
    prefix += num;
    if (prefixCount.has(prefix - k)) {
      count += prefixCount.get(prefix - k);
    }
    prefixCount.set(prefix, (prefixCount.get(prefix) || 0) + 1);
  }
  return count;
}

# Python
def subarray_sum(nums, k):
    prefix_count = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        count += prefix_count.get(prefix - k, 0)
        prefix_count[prefix] = prefix_count.get(prefix, 0) + 1
    return count

// JavaScript
function intersection(arr1, arr2) {
  const set1 = new Set(arr1);
  const result = [];
  const seen = new Set();
  for (const val of arr2) {
    if (set1.has(val) && !seen.has(val)) {
      result.push(val);
      seen.add(val);
    }
  }
  return result;
}

# Python
def intersection(arr1, arr2):
    return list(set(arr1) & set(arr2))

# With duplicates preserved:
def intersect_with_dupes(arr1, arr2):
    from collections import Counter
    c1, c2 = Counter(arr1), Counter(arr2)
    return list((c1 & c2).elements())

// JavaScript — Simplified using Map (preserves insertion order)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val); // move to end (most recent)
    return val;
  }
  put(key, value) {
    this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const oldest = this.cache.keys().next().value;
      this.cache.delete(oldest);
    }
  }
}

# Python — Using OrderedDict
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

// JavaScript
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function traverse(head) {
  const values = [];
  let current = head;
  while (current !== null) {
    values.push(current.val);
    current = current.next;
  }
  return values;
}

# Python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def traverse(head):
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next
    return values

// JavaScript — Iterative
function reverseList(head) {
  let prev = null, current = head;
  while (current !== null) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

// Recursive
function reverseListRecursive(head) {
  if (!head || !head.next) return head;
  const newHead = reverseListRecursive(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

# Python — Iterative
def reverse_list(head):
    prev, current = None, head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

# Recursive
def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

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

function findCycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow; // cycle start node
    }
  }
  return null;
}

# Python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

// JavaScript
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

# Python
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

// JavaScript
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  return dummy.next;
}

# Python
def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

// JavaScript
function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let lead = dummy, trail = dummy;
  for (let i = 0; i <= n; i++) lead = lead.next;
  while (lead) {
    lead = lead.next;
    trail = trail.next;
  }
  trail.next = trail.next.next;
  return dummy.next;
}

# Python
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    lead = trail = dummy
    for _ in range(n + 1):
        lead = lead.next
    while lead:
        lead = lead.next
        trail = trail.next
    trail.next = trail.next.next
    return dummy.next

// JavaScript
function isPalindrome(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // Reverse second half
  let prev = null;
  while (slow) {
    const next = slow.next;
    slow.next = prev;
    prev = slow;
    slow = next;
  }
  // Compare halves
  let left = head, right = prev;
  while (right) {
    if (left.val !== right.val) return false;
    left = left.next;
    right = right.next;
  }
  return true;
}

# Python
def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

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

# Python
def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0

// JavaScript
class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }
  push(val) {
    this.stack.push(val);
    const curMin = this.minStack.length === 0
      ? val : Math.min(val, this.minStack[this.minStack.length - 1]);
    this.minStack.push(curMin);
  }
  pop() {
    this.stack.pop();
    this.minStack.pop();
  }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.minStack[this.minStack.length - 1]; }
}

# Python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        cur_min = min(val, self.min_stack[-1]) if self.min_stack else val
        self.min_stack.append(cur_min)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.min_stack[-1]

// JavaScript
function evalRPN(tokens) {
  const stack = [];
  const ops = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),
  };
  for (const token of tokens) {
    if (token in ops) {
      const b = stack.pop(), a = stack.pop();
      stack.push(ops[token](a, b));
    } else {
      stack.push(Number(token));
    }
  }
  return stack[0];
}

# Python
def eval_rpn(tokens):
    stack = []
    ops = {'+', '-', '*', '/'}
    for token in tokens:
        if token in ops:
            b, a = stack.pop(), stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            else: stack.append(int(a / b))  # truncate toward zero
        else:
            stack.append(int(token))
    return stack[0]

// JavaScript
function nextGreaterElements(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = []; // stores indices
  for (let i = 0; i < arr.length; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      result[stack.pop()] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

# Python
def next_greater_elements(arr):
    result = [-1] * len(arr)
    stack = []  # stores indices
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

// JavaScript — BFS level order traversal of binary tree
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

# Python
from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            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

// JavaScript — Largest rectangle in histogram
function largestRectangle(heights) {
  const stack = []; // indices of increasing heights
  let maxArea = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i < heights.length ? heights[i] : 0;
    while (stack.length > 0 && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

# Python
def largest_rectangle(heights):
    stack = []
    max_area = 0
    for i in range(len(heights) + 1):
        h = heights[i] if i < len(heights) else 0
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

// JavaScript
function inorder(root) {
  const result = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    result.push(node.val);
    dfs(node.right);
  }
  dfs(root);
  return result;
}

// Iterative with stack
function inorderIterative(root) {
  const result = [], stack = [];
  let current = root;
  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
}

# Python
def inorder(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

// JavaScript
function preorder(root) {
  const result = [];
  function dfs(node) {
    if (!node) return;
    result.push(node.val);  // process before children
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return result;
}

function postorder(root) {
  const result = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    dfs(node.right);
    result.push(node.val);  // process after children
  }
  dfs(root);
  return result;
}

# Python
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

// JavaScript
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

# Python
from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            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

// JavaScript
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

# Python
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

// JavaScript
function isValidBST(root) {
  function validate(node, min, max) {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val)
        && validate(node.right, node.val, max);
  }
  return validate(root, -Infinity, Infinity);
}

# Python
def is_valid_bst(root):
    def validate(node, lo, hi):
        if not node:
            return True
        if node.val <= lo or node.val >= hi:
            return False
        return validate(node.left, lo, node.val) and \
               validate(node.right, node.val, hi)
    return validate(root, float('-inf'), float('inf'))

// JavaScript
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);
  if (left && right) return root;
  return left || right;
}

# Python
def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left or right

// JavaScript — Has path with target sum (root to leaf)
function hasPathSum(root, target) {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === target;
  return hasPathSum(root.left, target - root.val)
      || hasPathSum(root.right, target - root.val);
}

# Python
def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target
    return has_path_sum(root.left, target - root.val) or \
           has_path_sum(root.right, target - root.val)

// JavaScript — Preorder approach
function serialize(root) {
  const parts = [];
  function dfs(node) {
    if (!node) { parts.push('X'); return; }
    parts.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return parts.join(',');
}

function deserialize(data) {
  const vals = data.split(',');
  let idx = 0;
  function dfs() {
    if (vals[idx] === 'X') { idx++; return null; }
    const node = new TreeNode(Number(vals[idx++]));
    node.left = dfs();
    node.right = dfs();
    return node;
  }
  return dfs();
}

# Python
def serialize(root):
    parts = []
    def dfs(node):
        if not node:
            parts.append('X')
            return
        parts.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ','.join(parts)

def deserialize(data):
    vals = iter(data.split(','))
    def dfs():
        val = next(vals)
        if val == 'X':
            return None
        node = TreeNode(int(val))
        node.left = dfs()
        node.right = dfs()
        return node
    return dfs()

// JavaScript
// Build adjacency list from edge list
function buildGraph(edges, directed = false) {
  const graph = new Map();
  for (const [u, v] of edges) {
    if (!graph.has(u)) graph.set(u, []);
    if (!graph.has(v)) graph.set(v, []);
    graph.get(u).push(v);
    if (!directed) graph.get(v).push(u);
  }
  return graph;
}

# Python
def build_graph(edges, directed=False):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

# Example
edges = [[0,1], [0,2], [1,3], [2,3]]
g = build_graph(edges)
# {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]}

// JavaScript
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of (graph.get(node) || [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

# Python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

// JavaScript — Iterative
function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];
  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    for (const neighbor of (graph.get(node) || [])) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return order;
}

# Python — Recursive
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            order.extend(dfs(graph, neighbor, visited))
    return order

// JavaScript — Directed graph cycle detection
function hasCycleDirected(graph, numNodes) {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(numNodes).fill(WHITE);
  function dfs(node) {
    color[node] = GRAY; // in current path
    for (const neighbor of (graph.get(node) || [])) {
      if (color[neighbor] === GRAY) return true; // back edge = cycle
      if (color[neighbor] === WHITE && dfs(neighbor)) return true;
    }
    color[node] = BLACK; // completed
    return false;
  }
  for (let i = 0; i < numNodes; i++) {
    if (color[i] === WHITE && dfs(i)) return true;
  }
  return false;
}

# Python — Directed graph
def has_cycle_directed(graph, num_nodes):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_nodes

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(color[i] == WHITE and dfs(i) for i in range(num_nodes))

// JavaScript — Kahn's algorithm (BFS)
function topologicalSort(graph, numNodes) {
  const inDegree = new Array(numNodes).fill(0);
  for (const [, neighbors] of graph) {
    for (const n of neighbors) inDegree[n]++;
  }
  const queue = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of (graph.get(node) || [])) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return order.length === numNodes ? order : []; // empty = has cycle
}

# Python — Kahn's algorithm
from collections import deque

def topological_sort(graph, num_nodes):
    in_degree = [0] * num_nodes
    for neighbors in graph.values():
        for n in neighbors:
            in_degree[n] += 1
    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == num_nodes else []

// JavaScript
function countComponents(n, edges) {
  const graph = new Map();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u).push(v);
    graph.get(v).push(u);
  }
  const visited = new Set();
  let components = 0;
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      components++;
      const queue = [i];
      visited.add(i);
      while (queue.length) {
        const node = queue.shift();
        for (const nb of graph.get(node)) {
          if (!visited.has(nb)) {
            visited.add(nb);
            queue.push(nb);
          }
        }
      }
    }
  }
  return components;
}

# Python
def count_components(n, edges):
    from collections import defaultdict, deque
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = set()
    components = 0
    for i in range(n):
        if i not in visited:
            components += 1
            queue = deque([i])
            visited.add(i)
            while queue:
                node = queue.popleft()
                for nb in graph[node]:
                    if nb not in visited:
                        visited.add(nb)
                        queue.append(nb)
    return components

// JavaScript — using a simple priority queue approach
function dijkstra(graph, start, n) {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  // Min-heap: [distance, node]
  const pq = [[0, start]];
  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]); // simplified; use real heap
    const [d, u] = pq.shift();
    if (d > dist[u]) continue;
    for (const [v, w] of (graph.get(u) || [])) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

# Python
import heapq

def dijkstra(graph, start, n):
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]  # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

// JavaScript
function numIslands(grid) {
  if (!grid.length) return 0;
  const rows = grid.length, cols = grid[0].length;
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited
    dfs(r + 1, c); dfs(r - 1, c);
    dfs(r, c + 1); dfs(r, c - 1);
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

# Python
def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

// JavaScript
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted
  }
  return arr;
}

# Python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

// JavaScript
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

# Python
def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

// JavaScript
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

# Python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

// JavaScript
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(a, b) {
  const result = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  return result.concat(a.slice(i), b.slice(j));
}

# Python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

// JavaScript
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const pivotIdx = partition(arr, lo, hi);
  quickSort(arr, lo, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

# Python
def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return arr
    pivot_idx = partition(arr, lo, hi)
    quick_sort(arr, lo, pivot_idx - 1)
    quick_sort(arr, pivot_idx + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

// JavaScript
function countingSort(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0);
  for (const val of arr) count[val]++;
  const result = [];
  for (let i = 0; i <= maxVal; i++) {
    for (let j = 0; j < count[i]; j++) {
      result.push(i);
    }
  }
  return result;
}

# Python
def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    for val in arr:
        count[val] += 1
    result = []
    for i in range(max_val + 1):
        result.extend([i] * count[i])
    return result

// JavaScript — just use built-in for interviews
const nums = [5, 3, 8, 1];
nums.sort((a, b) => a - b);  // ALWAYS pass comparator for numbers!
// Without comparator, JS sorts lexicographically: [1, 3, 5, 8]
// But [10, 9, 80].sort() → [10, 80, 9] — WRONG!

# Python
nums = [5, 3, 8, 1]
nums.sort()               # in-place, returns None
sorted_nums = sorted(nums) # returns new list
# Custom: sorted(items, key=lambda x: x[1])

// JavaScript — Stability matters for multi-key sorting
const students = [
  { name: 'Alice', grade: 'B' },
  { name: 'Bob',   grade: 'A' },
  { name: 'Carol', grade: 'B' },
  { name: 'Dave',  grade: 'A' },
];
// Sort by grade — stable sort keeps Alice before Carol (both B)
students.sort((a, b) => a.grade.localeCompare(b.grade));
// Result: Bob, Dave, Alice, Carol (A's first, original order preserved)

# Python
students = [('Alice','B'), ('Bob','A'), ('Carol','B'), ('Dave','A')]
students.sort(key=lambda x: x[1])
# [('Bob','A'), ('Dave','A'), ('Alice','B'), ('Carol','B')]

// JavaScript
function search(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

# Python
def search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

// JavaScript
function searchRotated(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    // Left half is sorted
    if (arr[lo] <= arr[mid]) {
      if (target >= arr[lo] && target < arr[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // Right half is sorted
      if (target > arr[mid] && target <= arr[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

# Python
def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] <= arr[mid]:  # left half sorted
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # right half sorted
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

// JavaScript
function searchRange(arr, target) {
  return [findFirst(arr, target), findLast(arr, target)];
}

function findFirst(arr, target) {
  let lo = 0, hi = arr.length - 1, result = -1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) { result = mid; hi = mid - 1; }
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

function findLast(arr, target) {
  let lo = 0, hi = arr.length - 1, result = -1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) { result = mid; lo = mid + 1; }
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

# Python
def search_range(arr, target):
    def find_bound(is_left):
        lo, hi, result = 0, len(arr) - 1, -1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] == target:
                result = mid
                if is_left:
                    hi = mid - 1
                else:
                    lo = mid + 1
            elif arr[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return result
    return [find_bound(True), find_bound(False)]

// JavaScript
function searchInsert(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return lo; // insertion point
}

# Python
import bisect

def search_insert(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo

# Or simply: bisect.bisect_left(arr, target)

// JavaScript
function findPeak(arr) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < arr[mid + 1]) {
      lo = mid + 1; // peak is to the right
    } else {
      hi = mid; // mid could be the peak
    }
  }
  return lo; // lo === hi, pointing to a peak
}

# Python
def find_peak(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < arr[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

// JavaScript — Minimum capacity to ship packages in d days
function shipWithinDays(weights, days) {
  let lo = Math.max(...weights); // must fit largest package
  let hi = weights.reduce((a, b) => a + b, 0); // ship everything in 1 day
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canShip(weights, days, mid)) {
      hi = mid; // try smaller capacity
    } else {
      lo = mid + 1; // need more capacity
    }
  }
  return lo;
}

function canShip(weights, days, capacity) {
  let daysNeeded = 1, currentLoad = 0;
  for (const w of weights) {
    if (currentLoad + w > capacity) {
      daysNeeded++;
      currentLoad = 0;
    }
    currentLoad += w;
  }
  return daysNeeded <= days;
}

# Python
def ship_within_days(weights, days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(weights, days, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def can_ship(weights, days, capacity):
    days_needed, current_load = 1, 0
    for w in weights:
        if current_load + w > capacity:
            days_needed += 1
            current_load = 0
        current_load += w
    return days_needed <= days

// JavaScript — Fibonacci both ways
// Top-down (memoization)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

// Bottom-up (tabulation)
function fibTab(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

# Python
# Top-down
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Bottom-up
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

// JavaScript
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

# Python
def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

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

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

// JavaScript
function longestCommonSubsequence(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

# Python
def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

// JavaScript
function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(capacity + 1).fill(0)
  );
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]; // skip item
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }
  return dp[n][capacity];
}

# Python
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

// JavaScript — O(n^2) DP
function lisDP(arr) {
  const dp = new Array(arr.length).fill(1);
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return Math.max(...dp);
}

// O(n log n) with binary search
function lisBinarySearch(arr) {
  const tails = [];
  for (const num of arr) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
  }
  return tails.length;
}

# Python — O(n log n)
import bisect

def lis(arr):
    tails = []
    for num in arr:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

// JavaScript
function editDistance(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
  );
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete
          dp[i][j - 1],     // insert
          dp[i - 1][j - 1]  // replace
        );
      }
    }
  }
  return dp[m][n];
}

# Python
def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

// JavaScript
function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  let prev2 = 0, prev1 = 0;
  for (const num of nums) {
    const current = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

# Python
def rob(nums):
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

// JavaScript — Sum of array using recursion
function sumArray(arr, idx = 0) {
  if (idx >= arr.length) return 0;      // base case
  return arr[idx] + sumArray(arr, idx + 1); // recursive case
}

// Power function
function power(base, exp) {
  if (exp === 0) return 1;               // base case
  if (exp % 2 === 0) {
    const half = power(base, exp / 2);
    return half * half;                  // O(log n)
  }
  return base * power(base, exp - 1);
}

# Python
def sum_array(arr, idx=0):
    if idx >= len(arr):
        return 0
    return arr[idx] + sum_array(arr, idx + 1)

def power(base, exp):
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half
    return base * power(base, exp - 1)

// JavaScript
function permute(nums) {
  const result = [];
  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
      current.pop(); // undo choice
    }
  }
  backtrack([], nums);
  return result;
}

# Python
def permute(nums):
    result = []
    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
    backtrack([], nums)
    return result

// JavaScript
function combine(n, k) {
  const result = [];
  function backtrack(start, current) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }
    for (let i = start; i <= n; i++) {
      current.push(i);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  backtrack(1, []);
  return result;
}

# Python
def combine(n, k):
    result = []
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    backtrack(1, [])
    return result

// JavaScript
function subsets(nums) {
  const result = [];
  function backtrack(start, current) {
    result.push([...current]); // every state is a valid subset
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  backtrack(0, []);
  return result;
}

// Iterative approach
function subsetsIterative(nums) {
  const result = [[]];
  for (const num of nums) {
    const newSubsets = result.map(sub => [...sub, num]);
    result.push(...newSubsets);
  }
  return result;
}

# Python
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

// JavaScript
function solveNQueens(n) {
  const results = [];
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();

  function backtrack(row, board) {
    if (row === n) {
      results.push(board.map(r => '.'.repeat(r) + 'Q' + '.'.repeat(n - r - 1)));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      board.push(col);
      backtrack(row + 1, board);
      board.pop();
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
  }
  backtrack(0, []);
  return results;
}

# Python
def solve_n_queens(n):
    results = []
    cols, diag1, diag2 = set(), set(), set()

    def backtrack(row, board):
        if row == n:
            results.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            board.append(col)
            backtrack(row + 1, board)
            board.pop()
            cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)
    backtrack(0, [])
    return results

// JavaScript
function solveSudoku(board) {
  function isValid(board, row, col, num) {
    const ch = String(num);
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === ch) return false; // row
      if (board[i][col] === ch) return false; // column
      const boxR = 3 * Math.floor(row / 3) + Math.floor(i / 3);
      const boxC = 3 * Math.floor(col / 3) + (i % 3);
      if (board[boxR][boxC] === ch) return false; // box
    }
    return true;
  }

  function solve(board) {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] === '.') {
          for (let num = 1; num <= 9; num++) {
            if (isValid(board, r, c, num)) {
              board[r][c] = String(num);
              if (solve(board)) return true;
              board[r][c] = '.';
            }
          }
          return false; // no valid digit → backtrack
        }
      }
    }
    return true; // all cells filled
  }
  solve(board);
}

# Python
def solve_sudoku(board):
    def is_valid(row, col, num):
        ch = str(num)
        for i in range(9):
            if board[row][i] == ch: return False
            if board[i][col] == ch: return False
            br = 3 * (row // 3) + i // 3
            bc = 3 * (col // 3) + i % 3
            if board[br][bc] == ch: return False
        return True

    def solve():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for num in range(1, 10):
                        if is_valid(r, c, num):
                            board[r][c] = str(num)
                            if solve(): return True
                            board[r][c] = '.'
                    return False
        return True
    solve()

// JavaScript
function exist(board, word) {
  const rows = board.length, cols = board[0].length;
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;
    const saved = board[r][c];
    board[r][c] = '#'; // mark visited
    const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1)
               || dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
    board[r][c] = saved; // unmark
    return found;
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (dfs(r, c, 0)) return true;
  return false;
}

# Python
def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[idx]:
            return False
        saved = board[r][c]
        board[r][c] = '#'
        found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1)
                 or dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1))
        board[r][c] = saved
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

// JavaScript — Remove duplicates from sorted array
function removeDuplicates(arr) {
  if (arr.length === 0) return 0;
  let writeIdx = 1;
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[i - 1]) {
      arr[writeIdx] = arr[i];
      writeIdx++;
    }
  }
  return writeIdx;
}

# Python
def remove_duplicates(arr):
    if not arr:
        return 0
    write_idx = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_idx] = arr[i]
            write_idx += 1
    return write_idx

// JavaScript — Happy number (sum of squared digits eventually reaches 1)
function isHappy(n) {
  function digitSquareSum(num) {
    let sum = 0;
    while (num > 0) {
      const digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }
  let slow = n, fast = n;
  do {
    slow = digitSquareSum(slow);
    fast = digitSquareSum(digitSquareSum(fast));
  } while (slow !== fast);
  return slow === 1;
}

# Python
def is_happy(n):
    def digit_square_sum(num):
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total
    slow = fast = n
    while True:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
        if slow == fast:
            break
    return slow == 1

// JavaScript — Longest substring without repeating characters
function lengthOfLongestSubstring(s) {
  const charIdx = new Map();
  let maxLen = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    if (charIdx.has(s[right]) && charIdx.get(s[right]) >= left) {
      left = charIdx.get(s[right]) + 1;
    }
    charIdx.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

# Python
def length_of_longest_substring(s):
    char_idx = {}
    max_len = left = 0
    for right, ch in enumerate(s):
        if ch in char_idx and char_idx[ch] >= left:
            left = char_idx[ch] + 1
        char_idx[ch] = right
        max_len = max(max_len, right - left + 1)
    return max_len

// JavaScript
function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      merged.push(intervals[i]);
    }
  }
  return merged;
}

# Python
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

// JavaScript — Top K frequent elements using bucket sort
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  // Bucket: index = frequency, value = list of elements
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) buckets[count].push(num);
  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

# Python
import heapq
from collections import Counter

def top_k_frequent(nums, k):
    freq = Counter(nums)
    # nlargest uses a heap internally
    return [item for item, count in freq.most_common(k)]

// JavaScript — Count subarrays with sum divisible by k
function subarraysDivByK(arr, k) {
  const modCount = new Map([[0, 1]]);
  let prefix = 0, count = 0;
  for (const num of arr) {
    prefix = ((prefix + num) % k + k) % k; // handle negatives
    count += modCount.get(prefix) || 0;
    modCount.set(prefix, (modCount.get(prefix) || 0) + 1);
  }
  return count;
}

# Python
def subarrays_div_by_k(arr, k):
    mod_count = {0: 1}
    prefix = 0
    count = 0
    for num in arr:
        prefix = (prefix + num) % k
        count += mod_count.get(prefix, 0)
        mod_count[prefix] = mod_count.get(prefix, 0) + 1
    return count

// JavaScript
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}

# Python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

// Decision guide:
// 'Shortest' or 'minimum steps' → BFS
// 'All paths' or 'does a path exist' → DFS
// 'Level order' → BFS
// 'Permutations/combinations' → DFS (backtracking)

// JavaScript — Minimum steps to reach target in grid
function minSteps(grid, start, end) {
  const rows = grid.length, cols = grid[0].length;
  const queue = [[...start, 0]]; // [row, col, steps]
  const visited = new Set([start.toString()]);
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  while (queue.length) {
    const [r, c, steps] = queue.shift();
    if (r === end[0] && c === end[1]) return steps;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      const key = `${nr},${nc}`;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && grid[nr][nc] === 0 && !visited.has(key)) {
        visited.add(key);
        queue.push([nr, nc, steps + 1]);
      }
    }
  }
  return -1;
}

# Python
from collections import deque

def min_steps(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start[0], start[1], 0)])
    visited = {(start[0], start[1])}
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        pass  # directions defined in loop below
    while queue:
        r, c, steps = queue.popleft()
        if (r, c) == tuple(end):
            return steps
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr,nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, steps + 1))
    return -1

// Key principles:
// 1. Identify bottleneck: CPU-bound? I/O-bound? Memory-bound?
// 2. Scale reads: caching, read replicas, CDN
// 3. Scale writes: sharding, message queues, async processing
// 4. Scale storage: partitioning, object storage, tiered storage

// Quick estimation:
// 1 million users × 10 requests/day = ~100 requests/second
// 1 KB per request = ~100 KB/s = ~8.6 GB/day
// Plan for 10x peak: ~1000 requests/second

// Architecture:
// Client → Load Balancer → Server 1
//                        → Server 2
//                        → Server 3

// Layer 4 (TCP): fast, routes by IP/port
// Layer 7 (HTTP): smarter, can route by URL/headers/cookies

// Health checks: LB periodically pings servers
// If server fails health check → removed from rotation
// When it recovers → added back

// Cache-aside pattern (most common):
// 1. App receives request
// 2. Check cache (Redis/Memcached)
// 3. Cache HIT → return cached data
// 4. Cache MISS → query database → store in cache → return

// Eviction policies:
// LRU: remove least recently used (most common)
// LFU: remove least frequently used
// TTL: expire after fixed time

// Cache invalidation strategies:
// 1. TTL-based: set expiry, eventually consistent
// 2. Event-based: invalidate on write
// 3. Version-based: cache key includes version number

// Hash-based sharding:
// shard_id = hash(user_id) % num_shards
// User 12345 → hash(12345) % 4 → shard 2

// Example with 4 shards:
// Shard 0: users where hash(id) % 4 = 0
// Shard 1: users where hash(id) % 4 = 1
// Shard 2: users where hash(id) % 4 = 2
// Shard 3: users where hash(id) % 4 = 3

// Consistent hashing: minimizes data movement when adding/removing shards
// Instead of hash % N, map keys and shards to a ring

// CP systems (consistency over availability):
// - Bank transactions: must be consistent
// - Examples: HBase, MongoDB (with majority write concern)
// - During partition: some requests may fail

// AP systems (availability over consistency):
// - Social media feeds: slightly stale data is OK
// - Examples: Cassandra, DynamoDB
// - During partition: may serve stale data

// Real-world: most systems mix both
// Critical data (payments) → strong consistency
// Non-critical data (user profile pic) → eventual consistency

// REST:
// GET /users/123        → full user object
// GET /users/123/posts  → all posts
// Problem: 2 requests, might get unused fields

// GraphQL:
// POST /graphql
// query {
//   user(id: 123) {
//     name
//     posts(limit: 5) {
//       title
//     }
//   }
// }
// → exactly the fields requested, single request

// When to use REST:
// - Simple CRUD APIs, caching is important (HTTP caching)
// - Public APIs, broad adoption

// When to use GraphQL:
// - Mobile apps (bandwidth-sensitive)
// - Complex data relationships
// - Multiple client types needing different data shapes

// Without queue:
// User request → Process image → Respond (slow, 5 seconds)

// With queue:
// User request → Enqueue 'process image' → Respond immediately (50ms)
// Background worker → Dequeue → Process image → Update status

// Kafka vs SQS:
// Kafka: ordered, replayable, high throughput, log-based
// SQS: simple, managed, at-least-once delivery, auto-scaling

// Key concepts:
// At-least-once: message may be delivered multiple times
// At-most-once: message may be lost but never duplicated
// Exactly-once: hardest to achieve, often app-level idempotency

// Token bucket pseudocode:
// bucket has 'tokens' (max capacity), refill rate
// On request:
//   refill tokens based on elapsed time
//   if tokens >= 1:
//     tokens -= 1
//     allow request
//   else:
//     reject (429 Too Many Requests)

// Example: 100 requests/minute, burst of 10
// capacity = 10, refill rate = 100/60 ≈ 1.67 tokens/sec

// Where to implement:
// API Gateway level (centralized)
// Application level (per-service)
// Client-side (self-throttling)

// Distributed rate limiting:
// Use Redis INCR + EXPIRE for shared counter across instances

// Question: 'Tell me about a time you dealt with a difficult bug.'

// Situation: 'Our payment service was intermittently failing
//   for about 2% of transactions on weekends.'

// Task: 'As the on-call engineer, I needed to diagnose and
//   fix it before Monday's peak traffic.'

// Action: 'I correlated the failures with database connection
//   pool exhaustion, traced it to a missing timeout on a
//   third-party API call, added a 3-second timeout with
//   retry logic, and deployed with a feature flag.'

// Result: 'Payment failures dropped to 0.01%, saving an
//   estimated $50K in lost weekend revenue. I also added
//   monitoring alerts so the team would catch similar
//   issues earlier.'

// Tip 1: Don't start coding immediately.
// Spend 5 minutes thinking → saves 15 minutes of rewriting.

// Tip 2: State the brute force first.
// 'The naive approach is O(n^2)...but I think we can do
// O(n) using a hash map. Let me explain before coding.'

// Tip 3: If stuck after 3 minutes, ask for a hint.
// 'I'm thinking about using X, does that sound like the
// right direction?' — This is better than silent struggling.

// Tip 4: Code the core logic first, handle edge cases after.
// Get the main algorithm working, then add null checks,
// empty input handling, etc.

// Tip 5: Talk while you code.
// 'I'm initializing two pointers at each end because...'

// Great clarifying questions by problem type:

// Array/String:
// 'Can there be negative numbers?'
// 'Is the array sorted?'
// 'Should I handle empty input?'
// 'Are there duplicate values?'
// 'ASCII or Unicode characters?'

// Graph:
// 'Is it directed or undirected?'
// 'Can there be cycles?'
// 'Are edge weights positive?'
// 'Is the graph connected?'

// Design:
// 'How many users/requests per second?'
// 'What is the read/write ratio?'
// 'What are the latency requirements?'
// 'Do we need strong or eventual consistency?'

// Instead of going silent, try these phrases:

// 'Let me trace through this example manually to see
//  if I can spot a pattern...'

// 'I've been thinking about a hash map approach, but
//  the ordering constraint makes me think maybe a
//  stack or monotonic structure would be better.'

// 'The brute force would be O(n^2) with nested loops.
//  I wonder if sorting first could help us do better.'

// 'I'm stuck on how to handle this edge case. Can you
//  give me a hint about what should happen when the
//  input has all identical values?'

// 'This reminds me of the two-sum pattern — let me
//  think about whether a complement approach works here.'

// Strong communication pattern:
// Step 1: 'I understand the problem as...'
// Step 2: 'My initial thought is to use X because...'
// Step 3: 'The trade-off is A vs B. I'll go with A because...'
// Step 4: While coding: 'This loop handles the case where...'
// Step 5: 'Let me verify with the example: for input [1,2,3],...'
// Step 6: 'The time complexity is O(n) because we visit each
//          element once. Space is O(n) for the hash map.'

// Weak communication:
// 'Um...let me think...okay I'll try this...'
// *codes silently for 20 minutes*
// 'I think this works.'

// 'Tell me about yourself' template:
// 'I'm a [role] with [X years] of experience focused on [area].
//  Most recently at [Company], I worked on [project] where I
//  [key achievement with metric]. I'm excited about [company]
//  because [specific reason tied to their product/mission].
//  I'm looking for [what you want in next role].'

// Failure question template:
// Situation: what happened
// What went wrong and YOUR role in it (own it)
// What you learned
// How you applied that lesson later
// Do NOT blame others or external factors

// 'Why this company?' — research 3 specific things:
// 1. A product feature you admire
// 2. A company value that resonates
// 3. A technical challenge they face that excites you