Shorts

function countPairs(nums, target) {
  const seen = new Map(); // value -> times seen so far
  let pairs = 0;
  for (const x of nums) {
    pairs += seen.get(target - x) ?? 0;  // look up first...
    seen.set(x, (seen.get(x) ?? 0) + 1); // ...then record x
  }
  return pairs;
}

// m bits and k hash functions for n items at false-positive rate p
function bloomSize(n, p) {
  const m = Math.ceil((-n * Math.log(p)) / Math.LN2 ** 2);
  const k = Math.round((m / n) * Math.LN2);
  return { m, k };
}

bloomSize(1e6, 0.01); // { m: 9585059, k: 7 }, about 1.2 MB

const nums = [7, 3, 9];
const i = nums.indexOf(7);          // 0: found at index 0
if (i) console.log("never runs");   // 0 is falsy
if (i !== -1) console.log("found"); // test what you mean

const count = new Map([["a", 0]]);
console.log(count.get("a") || 5);   // 5: the real 0 is lost
console.log(count.get("a") ?? 5);   // 0: ?? skips null/undefined only
console.log(count.has("a"));        // true

const qps = (dau, actions) => (dau * actions) / 86_400;
const servers = (peak, perServer = 1_000, busy = 0.6) =>
  Math.ceil(peak / (perServer * busy));

const avg = qps(10e6, 10); // ~1,157/s
const peak = avg * 3;      // ~3,472/s
servers(peak);             // 6

function pairSum(nums, target) { // nums sorted ascending
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++; // nums[left] is too small for all
    else right--;             // nums[right] is too big for all
  }
  return [-1, -1];
}

function gossipRounds(n, fanout = 3) { // node 0 has news to spread
  const knows = new Set([0]);
  const randomPeer = () => Math.floor(Math.random() * n);
  for (let round = 1; ; round++) {
    const sends = knows.size * fanout; // everyone who knows tells 3
    for (let i = 0; i < sends; i++) knows.add(randomPeer());
    if (knows.size === n) return round;
  }
}
gossipRounds(1_000); // about 8; with 100_000 nodes, about 13

async function get(key, load) {
  const e = l1.get(key);
  if (e && e.exp > Date.now()) return e.value;  // L1: microseconds
  const cached = await redis.get(key);          // L2: about 1 ms
  const value = cached ? JSON.parse(cached) : await load(key);
  if (!cached) await redis.set(key, JSON.stringify(value), 'EX', 300);
  l1.set(key, { value, exp: Date.now() + 5000 }); // short L1 TTL
  return value;
}

const overhead = (slice, sw, refill = 0) =>
  (sw + refill) / (slice + sw + refill);

overhead(4000, 5);   // 0.00125
overhead(50, 5);     // 0.09

console.log(7 / 2, Math.floor(7 / 2));              // 3.5 3
console.log(Math.floor(-7 / 2), Math.trunc(-7 / 2)); // -4 -3
console.log(-7 % 3);                                // -1, not 2
const mod = (a, m) => ((a % m) + m) % m;
console.log(mod(-7, 3));                            // 2
const ring = ["a", "b", "c", "d", "e"];
console.log(ring[mod(0 - 1, ring.length)]);         // "e"
console.log(3e9 | 0);                               // -1294967296

function longestNoRepeat(s) {
  const inWindow = new Set();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    while (inWindow.has(s[right])) inWindow.delete(s[left++]);
    inWindow.add(s[right]);
    best = Math.max(best, right - left + 1); // record after shrinking
  }
  return best;
}

function nodeFor(ring, key) {     // ring: [{ pos, node }], sorted
  const h = hash(key);
  let lo = 0, hi = ring.length;
  while (lo < hi) {                   // first point at or after h
    const mid = (lo + hi) >> 1;
    if (ring[mid].pos < h) lo = mid + 1; else hi = mid;
  }
  return ring[lo % ring.length].node; // wrap around the ring
}

const MOD = 1_000_000_007;
const mulMod = (x, y) =>
  Number((BigInt(x) * BigInt(y)) % BigInt(MOD));
const a = 999_999_999;
console.log((a * a) % MOD); // wrong: a * a is past 2^53
console.log(mulMod(a, a));  // exact
let ways = 1; // reduce after every step so values stay small
for (let i = 0; i < 100; i++) ways = (ways * 2) % MOD;
console.log(ways); // 976371285, which is 2^100 mod 1e9 + 7

function pickP2C(servers) {
  const healthy = servers.filter((s) => s.healthy);
  if (healthy.length < 2) return healthy[0];
  const i = Math.floor(Math.random() * healthy.length);
  let j = Math.floor(Math.random() * (healthy.length - 1));
  if (j === i) j = healthy.length - 1; // j !== i, uniformly
  const a = healthy[i], b = healthy[j];
  return a.active <= b.active ? a : b;
}

function countSubarrays(nums, k) { // subarrays summing to k
  const seen = new Map([[0, 1]]); // the empty prefix, seen once
  let sum = 0, count = 0;
  for (const x of nums) {
    sum += x;
    count += seen.get(sum - k) ?? 0; // look up first...
    seen.set(sum, (seen.get(sum) ?? 0) + 1); // ...then record
  }
  return count;
}

// Redis HyperLogLog: 2^14 registers of 6 bits each
const m = 2 ** 14;                    // 16384 registers
const bytes = (m * 6) / 8;            // 12288 bytes = 12 KB
const stdError = 1.04 / Math.sqrt(m); // 0.008125, about 0.81%

function removeAdjacentPairs(s) { // "abbaca" -> "ca"
  const stack = []; // an array of characters, joined once
  for (const ch of s) {
    if (stack.at(-1) === ch) stack.pop();
    else stack.push(ch);
  }
  return stack.join("");
}
const chars = [..."stressed"]; // edit an array, not the string
console.log(chars.reverse().join("")); // "desserts"

let shuttingDown = false;
app.get("/readyz", async (_req, res) => { // send traffic here?
  if (shuttingDown) return res.sendStatus(503);
  try { await pool.query("SELECT 1"); res.sendStatus(200); }
  catch { res.sendStatus(503); }
});
process.on("SIGTERM", () => {
  shuttingDown = true; // readiness fails, the LB stops routing
  setTimeout(() => server.close(() => process.exit(0)), 10_000);
});

// First x in [lo, hi) where ok(x) is true, or hi if none.
function firstTrue(lo, hi, ok) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (ok(mid)) hi = mid; // mid might be the first true
    else lo = mid + 1;     // mid and everything before fail
  }
  return lo;
}
const lowerBound = (a, x) => firstTrue(0, a.length, (i) => a[i] >= x);

// Phi accrual, simplest model: heartbeat gaps are exponential
function phi(msSinceLast, gaps) { // gaps: recent intervals in ms
  const mean = gaps.reduce((a, b) => a + b) / gaps.length;
  return msSinceLast / (mean * Math.LN10); // -log10(P(this late))
}
phi(1_000, [1_000, 1_000]); // 0.43: on time
phi(7_000, [1_000, 1_000]); // 3.04: a 0.1% chance it's just late
phi(7_000, [3_000, 4_000]); // 0.87: normal on a slow network

// one global order: lock the lower id first
const inLockOrder = (a, b) => (a < b ? [a, b] : [b, a]);

inLockOrder(7, 3); // [3, 7]
inLockOrder(3, 7); // [3, 7]

const bad = new Array(3).fill(new Array(2).fill(0));
bad[0][0] = 1;
console.log(bad); // [[1, 0], [1, 0], [1, 0]]: one shared row

const grid = Array.from({ length: 3 }, () => new Array(2).fill(0));
grid[0][0] = 1;
console.log(grid); // [[1, 0], [0, 0], [0, 0]]

const adj = Array.from({ length: 4 }, () => []); // 4 separate lists

async function claim(req, res) { // true: go ahead and do the work
  const key = `idem:${req.user.id}:${req.get("Idempotency-Key")}`;
  if (await redis.set(key, "pending", "EX", 86400, "NX")) return true;
  const saved = await redis.get(key);
  if (saved === "pending") { res.sendStatus(409); return false; }
  const { status, body } = JSON.parse(saved);
  res.status(status).json(body); // replay the first response
  return false;
}
// Then store { status, body } under the key, or DEL it on a 5xx.

function nextGreater(nums) { // index of next bigger value, or -1
  const answer = new Array(nums.length).fill(-1);
  const stack = []; // indices still waiting for an answer
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack.at(-1)] < nums[i])
      answer[stack.pop()] = i; // nums[i] answers every smaller top
    stack.push(i);
  }
  return answer;
}

console.log([10, 9, 1, 100, 25].sort()); // [1, 10, 100, 25, 9]
console.log([10, 9, 1].sort((a, b) => a - b)); // [1, 9, 10]

const intervals = [[5, 8], [1, 4], [1, 2]];
intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
console.log(intervals); // [[1, 2], [1, 4], [5, 8]]

const nums = [3, 1, 2];
const sorted = nums.toSorted((a, b) => a - b); // nums unchanged

function merge(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (const [start, end] of sorted) {
    const last = merged.at(-1);
    if (last && start <= last[1]) last[1] = Math.max(last[1], end);
    else merged.push([start, end]); // a gap: start a new group
  }
  return merged;
}

const d = 5, w = 2719; // ε = 0.1%, δ = 1%: about 54 KB
const rows = Array.from({ length: d }, () => new Uint32Array(w));
function slot(key, row) { // FNV-1a, seeded differently per row
  let h = 2166136261 ^ row;
  for (const c of key) h = Math.imul(h ^ c.charCodeAt(0), 16777619);
  return (h >>> 0) % w;
}
const add = (key) => rows.forEach((r, i) => r[slot(key, i)]++);
const estimate = (key) =>
  Math.min(...rows.map((r, i) => r[slot(key, i)]));

const poolSize = (cores, wait, compute) =>
  Math.round(cores * (1 + wait / compute));

poolSize(8, 0, 10);   // 8
poolSize(8, 90, 10);  // 80

const count = {};
for (const n of [3, 10, 3]) count[n] = (count[n] ?? 0) + 1;
console.log(Object.keys(count)); // ["3", "10"]: strings

const m = new Map();
for (const n of [3, 10, 3]) m.set(n, (m.get(n) ?? 0) + 1);
console.log([...m.keys()], m.size); // [3, 10] 2

const seen = new Set([[0, 1], "0,1"]);
console.log(seen.has([0, 1]), seen.has("0,1")); // false true

function cycleStart(head) { // entry node of the loop, or null
  let slow = head, fast = head;
  do {
    if (!fast || !fast.next) return null; // fell off: no loop
    [slow, fast] = [slow.next, fast.next.next];
  } while (slow !== fast);
  slow = head; // phase 2: from the head and from the meeting point
  while (slow !== fast) [slow, fast] = [slow.next, fast.next];
  return slow;
}

const majority = (n) => Math.floor(n / 2) + 1; // 2 of 3, 3 of 5
// The highest log index a majority stores (the leader counts too)
function commitIndex(matchIndex) {
  const sorted = [...matchIndex].sort((a, b) => b - a);
  return sorted[majority(sorted.length) - 1];
}
commitIndex([7, 7, 5, 4, 3]); // 5: three of five nodes have entry 5
// Raft also requires that entry to be from the leader's current term

// Full jitter: a random wait between 0 and a growing cap
function backoffDelay(attempt, baseMs = 1000, capMs = 30000) {
  return Math.random() * Math.min(capMs, baseMs * 2 ** attempt);
}

const countDown = (n) => (n === 0 ? 0 : countDown(n - 1));
console.log(countDown(1000)); // 0: a depth of 1000 is fine
try {
  countDown(1e6);
} catch (e) {
  console.log(e.message); // Maximum call stack size exceeded
}
let n = 1e6; // the same steps as a loop: O(1) stack
while (n !== 0) n -= 1;
console.log(n); // 0

const STICKY_MS = 5_000; // longer than typical replica lag
async function query(sql, params, { userId, write = false }) {
  if (write) {
    const result = await primary.query(sql, params);
    await redis.set(`rw:${userId}`, Date.now(), "PX", STICKY_MS);
    return result;
  }
  const recent = await redis.exists(`rw:${userId}`);
  return (recent ? primary : pickReplica()).query(sql, params);
}

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next; // 1. save the rest
    curr.next = prev;       // 2. flip the arrow
    prev = curr;            // 3. advance both pointers
    curr = next;
  }
  return prev; // the old tail is the new head
}

function bfsOrder(adj, start) {
  const queue = [start], seen = new Set([start]);
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++]; // O(1) dequeue: nothing moves
    for (const next of adj[node])
      if (!seen.has(next)) { seen.add(next); queue.push(next); }
  }
  return queue; // every node, in BFS order
}

async function getProduct(id) {
  const hit = await redis.get(`p:${id}`);
  if (hit) return JSON.parse(hit);
  const row = await db.product(id); // miss: load the truth
  const ttl = 300 + Math.floor(Math.random() * 60); // jitter
  await redis.set(`p:${id}`, JSON.stringify(row), "EX", ttl);
  return row;
}

function isBalanced(root) {
  const check = (node) => { // height, or -1 if unbalanced below
    if (node === null) return 0;
    const left = check(node.left), right = check(node.right);
    if (left === -1 || right === -1) return -1;
    if (Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right); // combine on the way up
  };
  return check(root) !== -1;
}

// Start in the top lane: go right while the next key is smaller,
// otherwise drop down a level. Level 0 holds every node.
function find(head, key) {
  let x = head;
  for (let lvl = head.next.length - 1; lvl >= 0; lvl--)
    while (x.next[lvl] && x.next[lvl].key < key) x = x.next[lvl];
  x = x.next[0];
  return x && x.key === key ? x : null;
}

// Behind a load balancer, keep idle sockets open LONGER than it does
// (AWS ALB: 60 s), or Node closes one as the LB reuses it: a 502.
server.keepAliveTimeout = 65_000;
server.headersTimeout = 66_000;   // keep above keepAliveTimeout

function heapPush(heap, x, cmp = (a, b) => a - b) { // min-heap
  heap.push(x); // add as the last leaf, then sift it up
  for (let i = heap.length - 1; i > 0; ) {
    const parent = (i - 1) >> 1;
    if (cmp(heap[i], heap[parent]) >= 0) break; // parent first: done
    [heap[i], heap[parent]] = [heap[parent], heap[i]];
    i = parent;
  }
}

async function updatePrice(id, price) {
  await db.query("UPDATE products SET price = $1 WHERE id = $2",
    [price, id]);
  await redis.del(`p:${id}`); // the next read loads the truth
  setTimeout(() => redis.del(`p:${id}`), 1_000); // second delete
}

function rightSideView(root) {
  const view = [];
  let level = root ? [root] : []; // exactly one level at a time
  while (level.length) {
    view.push(level.at(-1).val); // the last node on this level
    level = level.flatMap((n) => [n.left, n.right]).filter(Boolean);
  }
  return view;
}

const majority = (n) => Math.floor(n / 2) + 1;
const tolerates = (n) => n - majority(n); // failures it survives
[2, 3, 4, 5].map(tolerates); // [0, 1, 1, 2]
// Split 5 nodes into 3 + 2: only the side with 3 can elect a leader
const canLead = (side, n) => side >= majority(n);
canLead(3, 5); canLead(2, 5); // true, false

// cwnd per round trip
// slow start: 10, 20, 40, 64 (ssthresh)
// then: 65, 66, 67 ...
// 3 dup ACKs at 66: 33, 34, 35 ...
// timeout at 66: 1, 2, 4, 8 ...

console.log(1 << 30, 1 << 31, 1 << 32); // 1073741824 -2147483648 1
console.log((2 ** 32 + 5) | 0, 3.9 | 0); // 5 3
console.log(-1 >>> 0); // 4294967295: the same bits, unsigned
const x = 6;
console.log(x & 1 === 0, (x & 1) === 0); // 0 true
console.log(1n << 40n); // 1099511627776n: BigInt for wide masks

const inflight = new Map();
function singleFlight(key, load) {
  if (!inflight.has(key)) {
    const p = load().finally(() => inflight.delete(key));
    inflight.set(key, p);
  }
  return inflight.get(key); // every caller shares one promise
}

// node = { children: Map<char, node>, isEnd: boolean }
function find(root, prefix) { // the node for prefix, or null
  let node = root;
  for (const ch of prefix) {
    node = node.children.get(ch); // one edge per character
    if (!node) return null;       // the path breaks off here
  }
  return node;
}
const search = (root, w) => find(root, w)?.isEnd === true;

const crypto = require("node:crypto");
// Sign path + expiry; the edge recomputes the HMAC with the same key
function signUrl(path, key, ttlSeconds) {
  const exp = Math.floor(Date.now() / 1000) + ttlSeconds;
  const sig = crypto.createHmac("sha256", key)
    .update(`${path}:${exp}`).digest("base64url");
  return `${path}?exp=${exp}&sig=${sig}`;
}
signUrl("/videos/42.mp4", key, 300); // valid for 5 minutes

app.post('/reports', async (req, res) => {
  const job = await reports.add('build', req.body, {
    attempts: 3, backoff: { type: 'exponential', delay: 5000 },
  });
  res.status(202)
    .location('/reports/' + job.id)   // the status resource
    .json({ jobId: job.id });
});

function uniqueSlow(nums) { // O(n²): includes scans out each time
  const out = [];
  for (const x of nums) if (!out.includes(x)) out.push(x);
  return out;
}
// O(n): a Set answers membership in O(1) on average
const unique = (nums) => [...new Set(nums)];

// Heap: the comparator heap class from Template 1
function kthLargest(nums, k) {
  const heap = new Heap((a, b) => a - b); // a MIN-heap
  for (const x of nums) {
    heap.push(x);
    if (heap.size() > k) heap.pop(); // evict the smallest
  }
  return heap.peek(); // the weakest of the top k
}

const { rows } = await db.query(`
  UPDATE spots SET ticket_id = $1, taken_at = now()
  WHERE id = (SELECT id FROM spots
              WHERE lot_id = $2 AND type = ANY($3)
                AND ticket_id IS NULL
              ORDER BY array_position($3, type), floor, id
              LIMIT 1 FOR UPDATE SKIP LOCKED)
  RETURNING id, floor`, [ticketId, lotId, fits]);

async function handle(msg) {
  const done = `done:${msg.id}`, lock = `processing:${msg.id}`;
  if (await redis.exists(done)) return; // already delivered
  if (!(await redis.set(lock, 1, "EX", 60, "NX"))) return; // taken
  try {
    await sendEmail(msg); // pass msg.id to the provider too
    await redis.set(done, 1, "EX", 7 * 86_400); // only now: done
  } finally { await redis.del(lock); } // a failed send can retry
}

function bfs(adj, start) { // edges from start, -1 = unreachable
  const dist = new Array(adj.length).fill(-1), queue = [start];
  dist[start] = 0; // mark when queued, never when popped
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head]; // head index: no O(n) shift()
    for (const v of adj[u])
      if (dist[v] === -1) { dist[v] = dist[u] + 1; queue.push(v); }
  }
  return dist;
}

function compare(a, b) { // a, b: { nodeId: counter }
  let less = false, more = false;
  for (const id of new Set([...Object.keys(a), ...Object.keys(b)])) {
    if ((a[id] ?? 0) < (b[id] ?? 0)) less = true;
    if ((a[id] ?? 0) > (b[id] ?? 0)) more = true;
  }
  if (less && more) return "concurrent"; // keep both as siblings
  return less ? "before" : more ? "after" : "equal";
}
compare({ A: 2, B: 1 }, { A: 1, B: 2 }); // "concurrent"

hasMoney: {
  coin: (m, { coin }) => { m.escrow.push(coin); return 'hasMoney'; },
  cancel: m => { m.refund('cancelled'); return 'idle'; },
  // select: sold out or short -> rejected; no change -> refund
},
dispensing: {                       // only the drop sensor gets in
  dropped: m => { m.commit(); return 'idle'; },
  dropFailed: m => { m.refund('nothing dropped'); return 'idle'; },
},