Data Structures & Algorithms for Seniors

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

class LRU<K, V> {
  private map = new Map<K, V>();
  constructor(private max: number) {}
  get(key: K): V | undefined {
    if (!this.map.has(key)) return undefined;
    const v = this.map.get(key)!;
    this.map.delete(key);   // move to the "newest" end
    this.map.set(key, v);
    return v;
  }
  set(key: K, value: V) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.max) {
      this.map.delete(this.map.keys().next().value!); // oldest
    }
    this.map.set(key, value);
  }
}

class TokenBucket {
  private tokens: number;
  private last = Date.now();
  constructor(private capacity: number, private refillPerSec: number) {
    this.tokens = capacity;
  }
  tryRemove(cost = 1): boolean {
    const now = Date.now();
    this.tokens = Math.min(this.capacity, this.tokens + ((now - this.last) / 1000) * this.refillPerSec);
    this.last = now;
    if (this.tokens < cost) return false;
    this.tokens -= cost;
    return true;
  }
}

async function pool<T, R>(items: T[], limit: number, fn: (x: T, i: number) => Promise<R>): Promise<R[]> {
  const results = new Array<R>(items.length);
  let next = 0;
  async function worker() {
    while (next < items.length) {
      const i = next++;            // claim index before awaiting
      results[i] = await fn(items[i], i);
    }
  }
  await Promise.all(Array.from({ length: Math.min(limit, items.length) }, worker));
  return results;
}

// count then keep a min-heap of size k (MinHeap: any binary heap keyed by count)
const counts = new Map<string, number>();
for (const e of events) counts.set(e.productId, (counts.get(e.productId) ?? 0) + 1);
const heap = new MinHeap<[string, number]>((a, b) => a[1] - b[1]);
for (const entry of counts) {
  heap.push(entry);
  if (heap.size > 10) heap.pop();
}

type Interval = [start: number, end: number];
function merge(xs: Interval[]): Interval[] {
  const s = [...xs].sort((a, b) => a[0] - b[0]);
  const out: Interval[] = [];
  for (const [st, en] of s) {
    const last = out.at(-1);
    if (last && st <= last[1]) last[1] = Math.max(last[1], en);
    else out.push([st, en]);
  }
  return out;
}
merge([[9, 12], [11, 14], [15, 17]]); // [[9,14],[15,17]]

function topoSort(deps: Record<string, string[]>): string[] {
  const indeg = new Map<string, number>();
  const out = new Map<string, string[]>();
  for (const [n, ds] of Object.entries(deps)) {
    indeg.set(n, indeg.get(n) ?? 0);
    for (const d of ds) {
      indeg.set(n, (indeg.get(n) ?? 0) + 1);
      indeg.set(d, indeg.get(d) ?? 0);
      out.set(d, [...(out.get(d) ?? []), n]);
    }
  }
  const q = [...indeg].filter(([, v]) => v === 0).map(([k]) => k);
  const order: string[] = [];
  for (let i = 0; i < q.length; i++) {
    const n = q[i];
    order.push(n);
    for (const m of out.get(n) ?? []) {
      indeg.set(m, indeg.get(m)! - 1);
      if (indeg.get(m) === 0) q.push(m);
    }
  }
  if (order.length !== indeg.size) throw new Error('cycle detected');
  return order;
}
topoSort({ api: ['db', 'cache'], cache: [], db: [], worker: ['db'] });
// ['db', 'cache', 'worker', 'api']

function maxSumK(xs: number[], k: number) {
  let sum = xs.slice(0, k).reduce((a, b) => a + b, 0);
  let best = sum;
  for (let i = k; i < xs.length; i++) {
    sum += xs[i] - xs[i - k];
    best = Math.max(best, sum);
  }
  return best;
}

const queue: Job[] = [];
export const enqueue = (j: Job) => queue.push(j);
export function dequeue(): Job | undefined {
  return queue.shift();
}
export function remove(id: string) {
  const i = queue.findIndex((j) => j.id === id);
  if (i >= 0) queue.splice(i, 1);
}

function debounce<A extends unknown[]>(fn: (...args: A) => void, ms: number) {
  let t: ReturnType<typeof setTimeout> | undefined;
  const debounced = function (this: unknown, ...args: A) {
    clearTimeout(t);
    t = setTimeout(() => fn.apply(this, args), ms);
  };
  debounced.cancel = () => clearTimeout(t);
  return debounced;
}

const o: Record<string, string> = {};
o['b'] = 'x'; o['10'] = 'y'; o['a'] = 'z'; o['2'] = 'w';
console.log(Object.keys(o));

const m = new Map<string, string>([['b', 'x'], ['10', 'y'], ['a', 'z'], ['2', 'w']]);
console.log([...m.keys()]);

function throttle<A extends unknown[]>(fn: (...a: A) => void, ms: number) {
  let last = 0;
  let pending: A | null = null;
  let timer: ReturnType<typeof setTimeout> | undefined;
  return (...args: A) => {
    const now = Date.now();
    const remaining = ms - (now - last);
    if (remaining <= 0) {
      last = now;
      fn(...args);
    } else {
      pending = args;
      timer ??= setTimeout(() => {
        last = Date.now();
        timer = undefined;
        if (pending) fn(...pending);
        pending = null;
      }, remaining);
    }
  };
}

async function enrich(orders: Order[]) {
  const out = [];
  for (const o of orders) {
    const customer = (await db.customers.findAll()).find((c) => c.id === o.customerId);
    if (!out.some((x) => x.id === o.id)) out.push({ ...o, customerName: customer?.name });
  }
  return out;
}

type Node = { id: string; children: Node[] };
function collectIds(n: Node, acc: string[] = []): string[] {
  acc.push(n.id);
  for (const c of n.children) collectIds(c, acc);
  return acc;
}
// prod: an imported tree is a 120,000-level-deep chain; one node references an ancestor

-- KEYS[1] = rl:{userId}; ARGV = now_ms, window_ms, limit, request_id
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, ARGV[1] - ARGV[2])
local n = redis.call('ZCARD', KEYS[1])
if n >= tonumber(ARGV[3]) then return 0 end
redis.call('ZADD', KEYS[1], ARGV[1], ARGV[4])
redis.call('PEXPIRE', KEYS[1], ARGV[2])
return 1

const EMAIL = /^([a-zA-Z0-9]+)*@example\.com$/;
EMAIL.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!'); // takes seconds or longer

function reservoir<T>(stream: Iterable<T>, k: number): T[] {
  const r: T[] = [];
  let i = 0;
  for (const x of stream) {
    if (i < k) r.push(x);
    else {
      const j = Math.floor(Math.random() * (i + 1));
      if (j < k) r[j] = x;
    }
    i++;
  }
  return r;
}