DSA interview questions

function twoSum(nums, target) {
  const seen = new Map()                 // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
  }
  return []
}
console.log(twoSum([2, 7, 11, 15], 9))   // [0, 1]
console.log(twoSum([3, 2, 4], 6))        // [1, 2]
console.log(twoSum([3, 3], 6))           // [0, 1]

const node = (val, next = null) => ({ val, next })
const fromArray = (a) => a.reduceRight((next, v) => node(v, next), null)
const toArray = (h) => { const out = []; for (; h; h = h.next) out.push(h.val); return out }

function reverse(head) {
  let prev = null
  let curr = head
  while (curr) {
    const next = curr.next   // save
    curr.next = prev         // flip
    prev = curr
    curr = next
  }
  return prev
}
console.log(toArray(reverse(fromArray([1, 2, 3, 4, 5]))))
console.log(toArray(reverse(fromArray([]))))

function cycleStart(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           // entrance of the cycle
    }
  }
  return null
}
const nodes = [1, 2, 3, 4, 5].map((val) => ({ val, next: null }))
nodes.forEach((n, i) => (n.next = nodes[i + 1] ?? null))
console.log(cycleStart(nodes[0]))        // null: no cycle
nodes[4].next = nodes[2]                 // 5 -> 3
console.log(cycleStart(nodes[0]).val)    // 3

function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' }
  const stack = []
  for (const ch of s) {
    if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false
    } else stack.push(ch)
  }
  return stack.length === 0
}
for (const s of ['()[]{}', '([{}])', '(]', '([)]', '((', ''])
  console.log(JSON.stringify(s), isValid(s))

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
}
console.log(search([1, 3, 5, 7, 9, 11], 7), search([1, 3, 5], 4))

// On the answer: smallest capacity to ship weights within D days
function shipWithinDays(w, days) {
  const daysNeeded = (cap) => { let d = 1, load = 0; for (const x of w) { if (load + x > cap) { d++; load = 0 } load += x } return d }
  let lo = Math.max(...w), hi = w.reduce((a, b) => a + b)
  while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (daysNeeded(mid) <= days) hi = mid; else lo = mid + 1 }
  return lo
}
console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)) // 15

function lengthOfLongestSubstring(s) {
  const last = new Map()          // char -> last index seen
  let left = 0, best = 0
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]
    if (last.has(ch) && last.get(ch) >= left) left = last.get(ch) + 1
    last.set(ch, right)
    best = Math.max(best, right - left + 1)
  }
  return best
}
console.log(lengthOfLongestSubstring('abcabcbb')) // 3 (abc)
console.log(lengthOfLongestSubstring('bbbbb'))    // 1
console.log(lengthOfLongestSubstring('pwwkew'))   // 3 (wke)
console.log(lengthOfLongestSubstring(''))         // 0

function maxArea(h) {
  let l = 0, r = h.length - 1, best = 0
  while (l < r) {
    best = Math.max(best, Math.min(h[l], h[r]) * (r - l))
    if (h[l] < h[r]) l++
    else r--
  }
  return best
}
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))  // 49

function removeDuplicates(a) {           // sorted array, in place
  let w = 0
  for (let i = 0; i < a.length; i++) if (i === 0 || a[i] !== a[i - 1]) a[w++] = a[i]
  return a.slice(0, w)
}
console.log(removeDuplicates([1, 1, 2, 3, 3, 3, 4]))

function maxSubArray(nums) {
  let cur = nums[0], best = nums[0]
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i])
    best = Math.max(best, cur)
  }
  return best
}
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) // 6 ([4,-1,2,1])
console.log(maxSubArray([-3, -1, -2]))                    // -1
console.log(maxSubArray([5, 4, -1, 7, 8]))                // 23

function merge(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0])
  const out = []
  for (const [s, e] of sorted) {
    const last = out[out.length - 1]
    if (last && s <= last[1]) last[1] = Math.max(last[1], e)
    else out.push([s, e])
  }
  return out
}
console.log(JSON.stringify(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))) // [[1,6],[8,10],[15,18]]
console.log(JSON.stringify(merge([[1, 4], [4, 5]])))                    // [[1,5]]
console.log(JSON.stringify(merge([[1, 4], [0, 4]])))                    // [[0,4]]

class MinHeap {
  constructor(key) { this.a = []; this.key = key }
  get size() { return this.a.length }
  push(x) { const a = this.a; a.push(x); let i = a.length - 1
    while (i > 0) { const p = (i - 1) >> 1; if (this.key(a[p]) <= this.key(a[i])) break; [a[p], a[i]] = [a[i], a[p]]; i = p } }
  pop() { const a = this.a, top = a[0], last = a.pop()
    if (a.length) { a[0] = last; let i = 0
      while (true) { let m = i; const l = 2 * i + 1, r = l + 1
        if (l < a.length && this.key(a[l]) < this.key(a[m])) m = l
        if (r < a.length && this.key(a[r]) < this.key(a[m])) m = r
        if (m === i) break; [a[m], a[i]] = [a[i], a[m]]; i = m } }
    return top }
}
function topKFrequent(nums, k) {
  const count = new Map()
  for (const n of nums) count.set(n, (count.get(n) ?? 0) + 1)
  const heap = new MinHeap(([, c]) => c)
  for (const entry of count) { heap.push(entry); if (heap.size > k) heap.pop() }
  return heap.a.map(([n]) => n)
}
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2))      // [2, 1] in some order
console.log(topKFrequent([4, 4, 5, 6, 6, 6, 7], 1))   // [6]

function findKthLargest(nums, k) {
  const a = [...nums], target = a.length - k
  let lo = 0, hi = a.length - 1
  while (true) {
    const r = lo + Math.floor(Math.random() * (hi - lo + 1))
    ;[a[r], a[hi]] = [a[hi], a[r]]
    let p = lo                                   // Lomuto partition
    for (let i = lo; i < hi; i++) if (a[i] < a[hi]) { [a[i], a[p]] = [a[p], a[i]]; p++ }
    ;[a[p], a[hi]] = [a[hi], a[p]]
    if (p === target) return a[p]
    if (p < target) lo = p + 1
    else hi = p - 1
  }
}
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2))          // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) // 4

// Number of islands (DFS) and shortest path in a grid (BFS)
const grid = ['11000', '11010', '00011'].map((r) => [...r])
function islands(g) {
  const seen = new Set(), R = g.length, C = g[0].length
  const dfs = (r, c) => {
    if (r < 0 || c < 0 || r >= R || c >= C || g[r][c] !== '1' || seen.has(r * C + c)) return
    seen.add(r * C + c); dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
  }
  let n = 0
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (g[r][c] === '1' && !seen.has(r * C + c)) { n++; dfs(r, c) }
  return n
}
function shortest(g, [sr, sc], [tr, tc]) {
  const q = [[sr, sc, 0]], seen = new Set([sr + ',' + sc])
  for (const [r, c, d] of q) {                  // array used as a queue
    if (r === tr && c === tc) return d
    for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]])
      if (g[nr]?.[nc] === '0' && !seen.has(nr + ',' + nc)) { seen.add(nr + ',' + nc); q.push([nr, nc, d + 1]) }
  }
  return -1
}
console.log('islands:', islands(grid))                   // 2
console.log('steps:', shortest(grid, [2, 0], [0, 4]))    // 6

const t = (val, left = null, right = null) => ({ val, left, right })
//        4
//      2   6
//     1 3 5 7
const root = t(4, t(2, t(1), t(3)), t(6, t(5), t(7)))
const pre = (n) => (n ? [n.val, ...pre(n.left), ...pre(n.right)] : [])
const post = (n) => (n ? [...post(n.left), ...post(n.right), n.val] : [])
function inorder(n) {                     // iterative
  const out = [], stack = []
  while (n || stack.length) {
    while (n) { stack.push(n); n = n.left }
    n = stack.pop(); out.push(n.val); n = n.right
  }
  return out
}
function levels(r) {
  const out = []; let q = r ? [r] : []
  while (q.length) { out.push(q.map((n) => n.val)); q = q.flatMap((n) => [n.left, n.right].filter(Boolean)) }
  return out
}
console.log('pre ', pre(root).join(' '))
console.log('in  ', inorder(root).join(' '))
console.log('post', post(root).join(' '))
console.log('levels', JSON.stringify(levels(root)))

const t = (val, left = null, right = null) => ({ val, left, right })
const maxDepth = (n) => (n ? 1 + Math.max(maxDepth(n.left), maxDepth(n.right)) : 0)

function diameter(root) {
  let best = 0
  const h = (n) => {
    if (!n) return 0
    const l = h(n.left), r = h(n.right)
    best = Math.max(best, l + r)       // longest path through n (edges)
    return 1 + Math.max(l, r)
  }
  h(root)
  return best
}
const root = t(3, t(9), t(20, t(15), t(7, t(1))))
console.log(maxDepth(root), maxDepth(null))   // 4 0
console.log(diameter(root))                    // 4

const t = (val, left = null, right = null) => ({ val, left, right })
function isValidBST(n, min = -Infinity, max = Infinity) {
  if (!n) return true
  if (n.val <= min || n.val >= max) return false
  return isValidBST(n.left, min, n.val) && isValidBST(n.right, n.val, max)
}
console.log(isValidBST(t(2, t(1), t(3))))                 // true
console.log(isValidBST(t(5, t(1), t(4, t(3), t(6)))))     // false
console.log(isValidBST(t(5, t(4), t(6, t(3), t(7)))))     // false: 3 is in 5's right subtree

const t = (val, left = null, right = null) => ({ val, left, right })
//          6
//      2       8
//    0   4   7   9
//       3 5
const root = t(6, t(2, t(0), t(4, t(3), t(5))), t(8, t(7), t(9)))
function lcaBST(n, p, q) {
  while (n) {
    if (p < n.val && q < n.val) n = n.left
    else if (p > n.val && q > n.val) n = n.right
    else return n.val
  }
  return null
}
function lca(n, p, q) {                     // any binary tree
  if (!n || n.val === p || n.val === q) return n
  const l = lca(n.left, p, q), r = lca(n.right, p, q)
  return l && r ? n : l || r
}
console.log(lcaBST(root, 2, 8), lcaBST(root, 2, 4), lcaBST(root, 3, 5)) // 6 2 4
console.log(lca(root, 7, 9).val, lca(root, 0, 5).val)                   // 8 2

const sumRec = (n) => (n === 0 ? 0 : n + sumRec(n - 1))
function sumIter(n) { let s = 0; for (let i = 1; i <= n; i++) s += i; return s }
console.log(sumRec(100), sumIter(100))
try { sumRec(1e6) } catch (e) { console.log('recursion:', e.name) } // RangeError: stack overflow
console.log('iteration:', sumIter(1e6))

function climbMemo(n, memo = new Map()) {          // top-down
  if (n <= 2) return n
  if (!memo.has(n)) memo.set(n, climbMemo(n - 1, memo) + climbMemo(n - 2, memo))
  return memo.get(n)
}
function climbTab(n) {                              // bottom-up, O(1) space
  let a = 1, b = 1
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b]
  return b
}
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for (let a = 1; a <= amount; a++)
    for (const c of coins) if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1)
  return dp[amount] === Infinity ? -1 : dp[amount]
}
console.log(climbMemo(10), climbTab(10), climbTab(45))  // 89 89 1836311903
console.log(coinChange([1, 3, 4], 6))   // 2 (3+3), greedy would give 3
console.log(coinChange([2], 3))         // -1

class LRUCache {
  constructor(capacity) { this.cap = capacity; this.map = new Map() }
  get(key) {
    if (!this.map.has(key)) return -1
    const v = this.map.get(key)
    this.map.delete(key); this.map.set(key, v)       // mark most recent
    return v
  }
  put(key, value) {
    this.map.delete(key)
    this.map.set(key, value)
    if (this.map.size > this.cap) this.map.delete(this.map.keys().next().value) // oldest
  }
}
const c = new LRUCache(2)
c.put(1, 'a'); c.put(2, 'b')
console.log(c.get(1))      // a (1 is now most recent)
c.put(3, 'c')              // evicts 2
console.log(c.get(2), c.get(3), [...c.map.keys()])  // -1 c [1, 3]

function mergeSort(a) {
  if (a.length <= 1) return a
  const mid = a.length >> 1
  const l = mergeSort(a.slice(0, mid)), r = mergeSort(a.slice(mid))
  const out = []
  let i = 0, j = 0
  while (i < l.length && j < r.length) out.push(l[i].age <= r[j].age ? l[i++] : r[j++]) // <= keeps it stable
  return out.concat(l.slice(i), r.slice(j))
}
const people = [{ n: 'Asha', age: 30 }, { n: 'Ben', age: 25 }, { n: 'Cai', age: 30 }, { n: 'Dev', age: 25 }]
console.log(mergeSort(people).map((p) => p.n + p.age).join(' ')) // Ben25 Dev25 Asha30 Cai30

function groupAnagrams(words) {
  const groups = new Map()
  for (const w of words) {
    const count = new Array(26).fill(0)
    for (const ch of w) count[ch.charCodeAt(0) - 97]++
    const key = count.join(',')
    if (!groups.has(key)) groups.set(key, [])
    groups.get(key).push(w)
  }
  return [...groups.values()]
}
console.log(JSON.stringify(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat'])))
// [["eat","tea","ate"],["tan","nat"],["bat"]]

class Trie {
  constructor() { this.root = { children: new Map(), end: false } }
  insert(word) {
    let n = this.root
    for (const ch of word) {
      if (!n.children.has(ch)) n.children.set(ch, { children: new Map(), end: false })
      n = n.children.get(ch)
    }
    n.end = true
  }
  #walk(s) { let n = this.root; for (const ch of s) { n = n.children.get(ch); if (!n) return null } return n }
  search(word) { return this.#walk(word)?.end === true }
  startsWith(prefix) { return this.#walk(prefix) !== null }
}
const trie = new Trie()
for (const w of ['car', 'card', 'care', 'dog']) trie.insert(w)
console.log(trie.search('car'), trie.search('ca'), trie.startsWith('ca'), trie.startsWith('x'))
// true false true false

function courseOrder(n, prereqs) {          // [course, needs]
  const adj = Array.from({ length: n }, () => [])
  const indeg = new Array(n).fill(0)
  for (const [c, p] of prereqs) { adj[p].push(c); indeg[c]++ }
  const queue = []
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i)
  const order = []
  for (const u of queue) {                      // queue grows while we iterate
    order.push(u)
    for (const v of adj[u]) if (--indeg[v] === 0) queue.push(v)
  }
  return order.length === n ? order : null     // null: cycle
}
console.log(courseOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  // [0, 1, 2, 3]
console.log(courseOrder(2, [[0, 1], [1, 0]]))                  // null

function dijkstra(graph, src) {
  const dist = Object.fromEntries(Object.keys(graph).map((k) => [k, Infinity]))
  dist[src] = 0
  const pq = [[0, src]]                 // sorted array as a simple PQ (use a heap for big graphs)
  while (pq.length) {
    const [d, u] = pq.shift()
    if (d > dist[u]) continue           // stale entry
    for (const [v, w] of graph[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w
        pq.push([dist[v], v])
        pq.sort((a, b) => a[0] - b[0])
      }
    }
  }
  return dist
}
const graph = { A: [['B', 4], ['C', 1]], B: [['D', 1]], C: [['B', 2], ['D', 5]], D: [] }
console.log(dijkstra(graph, 'A'))  // { A: 0, B: 3, C: 1, D: 4 }

function sortColors(a) {
  let low = 0, mid = 0, high = a.length - 1
  while (mid <= high) {
    if (a[mid] === 0) { [a[low], a[mid]] = [a[mid], a[low]]; low++; mid++ }
    else if (a[mid] === 1) mid++
    else { [a[mid], a[high]] = [a[high], a[mid]]; high-- }
  }
  return a
}
console.log(sortColors([2, 0, 2, 1, 1, 0]))   // [0, 0, 1, 1, 2, 2]
console.log(sortColors([2, 0, 1]))            // [0, 1, 2]
console.log(sortColors([1, 1, 1]))