System design,from first array to Netflix scale

const cache = new Map<string, string>(); // hash table -> Redis, Memcachedconst jobs: string[] = []; // queue -> Kafka, SQS, RabbitMQconst topK = [...scores].sort((a, b) => b[0] - a[0]).slice(0, 2); // heap -> trending topicsconst ordersByTime = orders.sort((a, b) => a[0] - b[0]); // sorted -> database B-tree index

// Hash table: constant time lookups, the heart of every cacheconst cache = new Map<string, string>(); // hash table -> Redis, Memcachedcache.set("user:42", JSON.stringify({ name: "Asha" })); // Queue: first in, first out, the heart of every message brokerconst jobs: string[] = []; // queue -> Kafka, SQS, RabbitMQjobs.push("send-welcome-email:42");const nextJob = jobs.shift(); // Heap: always hand me the biggest item quickly, the heart of trending lists.// JS has no built-in heap, so sort once; a real heap does top k in O(n log k).const scores: [number, string][] = [[980, "#worldcup"], [310, "#python"], [1200, "#election"]];const topK = [...scores].sort((a, b) => b[0] - a[0]).slice(0, 2); // heap -> trending topicsconst trending = topK.map(([, tag]) => tag); // ["#election", "#worldcup"] // Sorted structure: ordered keys for range queries, the heart of indexesconst orders: [number, string][] = [[1717000300, "o3"], [1717000100, "o1"], [1717000200, "o2"]];const ordersByTime = orders.sort((a, b) => a[0] - b[0]); // sorted -> database B-tree indexconst recent = ordersByTime.filter(([t]) => t >= 1717000200).map(([, o]) => o); // ["o2", "o3"]

/** O(n) time, O(1) space: check every item. */export function containsLinear(items: number[], x: number): boolean {	for (const item of items) {		if (item === x) return true;	}	return false;}

/** O(n) time, O(1) space: check every item. */export function containsLinear(items: number[], x: number): boolean {	for (const item of items) {		if (item === x) return true;	}	return false;} /** O(log n) time: halve the search space each step. */export function containsSorted(items: number[], x: number): boolean {	let lo = 0;	let hi = items.length;	while (lo < hi) {		const mid = (lo + hi) >>> 1;		if (items[mid] < x) lo = mid + 1;		else hi = mid;	}	return lo < items.length && items[lo] === x;} /** O(1) average time: hash straight to the bucket. */export function containsSet(items: Set<number>, x: number): boolean {	return items.has(x);} /** O(n^2): compares every pair. Fine for 100 items, hopeless for 10 million. */export function hasDuplicatePair(items: number[]): boolean {	for (let i = 0; i < items.length; i++) {		for (let j = i + 1; j < items.length; j++) {			if (items[i] === items[j]) return true;		}	}	return false;}

let window = nums.slice(0, k).reduce((a, b) => a + b, 0);let best = window;for (let i = k; i < nums.length; i++) {	window += nums[i] - nums[i - k]; // slide: add the new item, drop the oldest	best = Math.max(best, window);}return best;

/** Largest sum of any k consecutive items in O(n) instead of O(n*k). */function maxSumWindow(nums: number[], k: number): number {	if (k > nums.length) {		throw new RangeError("window larger than input");	}	let window = nums.slice(0, k).reduce((a, b) => a + b, 0);	let best = window;	for (let i = k; i < nums.length; i++) {		window += nums[i] - nums[i - k]; // slide: add the new item, drop the oldest		best = Math.max(best, window);	}	return best;} /** Two pointers on a sorted array: O(n) time, O(1) space. */function twoSumSorted(nums: number[], target: number): [number, number] | null {	let lo = 0;	let hi = nums.length - 1;	while (lo < hi) {		const s = nums[lo] + nums[hi];		if (s === target) {			return [lo, hi];		}		if (s < target) {			lo++;		} else {			hi--;		}	}	return null;} console.log(maxSumWindow([3, 1, 4, 1, 5, 9, 2, 6], 3)); // 17 (9 + 2 + 6)console.log(twoSumSorted([1, 3, 4, 6, 9], 10)); // [0, 4]

return this.buckets[hash(key) % this.buckets.length];for (const [k, v] of this.bucket(key)) {

type Entry = [key: string, value: unknown]; // JS has no built in hash() for strings, so use a small FNV-1a hash.function hash(key: string): number {	let h = 0x811c9dc5;	for (let i = 0; i < key.length; i++) {		h ^= key.charCodeAt(i);		h = Math.imul(h, 0x01000193);	}	return h >>> 0;} class HashMap {	buckets: Entry[][];	size = 0; 	constructor(capacity = 8) {		this.buckets = Array.from({ length: capacity }, () => []);	} 	private bucket(key: string): Entry[] {		return this.buckets[hash(key) % this.buckets.length];	} 	put(key: string, value: unknown): void {		const bucket = this.bucket(key);		for (const [i, [k]] of bucket.entries()) {			if (k === key) {				bucket[i] = [key, value];				return;			}		}		bucket.push([key, value]); // collision: chain in the same bucket		this.size += 1;		if (this.size > this.buckets.length * 0.75) {			this.resize();		}	} 	get(key: string, fallback?: unknown): unknown {		for (const [k, v] of this.bucket(key)) {			if (k === key) {				return v;			}		}		return fallback;	} 	private resize(): void {		const old = this.buckets.flat();		this.buckets = Array.from({ length: this.buckets.length * 2 }, () => []);		this.size = 0;		for (const [k, v] of old) {			this.put(k, v);		}	}} export { HashMap };

node.prev.next = node.next;node.next.prev = node.prev;

export class Node {	prev: Node = this;	next: Node = this; 	constructor(		public key?: string,		public value?: unknown,	) {}} export class DoublyLinkedList {	readonly head = new Node(); // sentinels remove edge cases	readonly tail = new Node(); 	constructor() {		this.head.next = this.tail;		this.tail.prev = this.head;	} 	pushFront(node: Node): void {		node.prev = this.head;		node.next = this.head.next;		this.head.next.prev = node;		this.head.next = node;	} 	unlink(node: Node): void {		node.prev.next = node.next;		node.next.prev = node.prev;	} 	popBack(): Node | null {		if (this.tail.prev === this.head) {			return null;		}		const node = this.tail.prev;		this.unlink(node);		return node;	}}

undo.push("bold");console.log(undo.pop()); // "bold"requests.push(`req-${i}`);const handle = requests.shift();

// Stack: last in, first outconst undo: string[] = [];undo.push("type 'hello'");undo.push("bold");console.log(undo.pop()); // "bold" // Queue: first in, first out, buffering bursts between producer and consumerconst MAX_QUEUED = 1000; // bounded: protects memoryconst requests: string[] = [];for (let i = 0; i < 5; i++) {	if (requests.length === MAX_QUEUED) requests.shift(); // full: drop the oldest	requests.push(`req-${i}`);}while (requests.length > 0) {	const handle = requests.shift();} // Balanced brackets, the classic stack problemfunction balanced(s: string): boolean {	const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };	const stack: string[] = [];	for (const ch of s) {		if ("([{".includes(ch)) {			stack.push(ch);		} else if (ch in pairs) {			if (stack.length === 0 || stack.pop() !== pairs[ch]) return false;		}	}	return stack.length === 0;} console.log(balanced("{[()]}")); // true

export function search(node: TreeNode | null, key: number): TreeNode | null {	while (node && node.key !== key) {		node = key < node.key ? node.left : node.right;	}	return node;}

export class TreeNode {	left: TreeNode | null = null;	right: TreeNode | null = null;	constructor(readonly key: number) {}} export function insert(root: TreeNode | null, key: number): TreeNode {	if (root === null) return new TreeNode(key);	if (key < root.key) {		root.left = insert(root.left, key);	} else if (key > root.key) {		root.right = insert(root.right, key);	}	return root;} export function search(node: TreeNode | null, key: number): TreeNode | null {	while (node && node.key !== key) {		node = key < node.key ? node.left : node.right;	}	return node;} /** Yields keys in sorted order: the basis of range scans. */export function* inOrder(node: TreeNode | null): Generator<number> {	if (node) {		yield* inOrder(node.left);		yield node.key;		yield* inOrder(node.right);	}} let root: TreeNode | null = null;for (const k of [50, 30, 70, 20, 40, 60, 80]) {	root = insert(root, k);}console.log([...inOrder(root)]); // [20, 30, 40, 50, 60, 70, 80]

heap.push([count, word]);if (heap.size > k) {	heap.pop(); // drop the smallest of the current top k}

/** A small binary min heap: push and pop in O(log n), smallest item on top. */class MinHeap<T> {	private readonly items: T[] = [];	private readonly less: (a: T, b: T) => boolean; 	constructor(less: (a: T, b: T) => boolean) {		this.less = less;	} 	get size(): number {		return this.items.length;	} 	push(item: T): void {		const a = this.items;		a.push(item);		for (let i = a.length - 1; i > 0; ) {			const p = (i - 1) >> 1;			if (!this.less(a[i], a[p])) break;			[a[i], a[p]] = [a[p], a[i]];			i = p;		}	} 	pop(): T | undefined {		const a = this.items;		const top = a[0];		const last = a.pop();		if (a.length > 0 && last !== undefined) {			a[0] = last;			for (let i = 0; ; ) {				const l = 2 * i + 1;				let m = i;				if (l < a.length && this.less(a[l], a[m])) m = l;				if (l + 1 < a.length && this.less(a[l + 1], a[m])) m = l + 1;				if (m === i) break;				[a[i], a[m]] = [a[m], a[i]];				i = m;			}		}		return top;	} 	toArray(): T[] {		return [...this.items];	}} /** Top k by frequency using a min heap of size k: O(n log k). */function topKWords(stream: string[], k: number): [string, number][] {	const counts = new Map<string, number>();	for (const word of stream) counts.set(word, (counts.get(word) ?? 0) + 1);	// Ordered by count, then by word, the same as comparing [count, word] pairs	const heap = new MinHeap<[number, string]>(		(x, y) => x[0] < y[0] || (x[0] === y[0] && x[1] < y[1]),	);	for (const [word, count] of counts) {		heap.push([count, word]);		if (heap.size > k) {			heap.pop(); // drop the smallest of the current top k		}	}	return heap		.toArray()		.map(([c, w]): [string, number] => [w, c])		.sort((x, y) => y[1] - x[1]);} /** k way merge, how databases merge sorted runs and SSTables. */function mergeSorted(...lists: number[][]): number[] {	// [value, which list, position in that list]	const heap = new MinHeap<[number, number, number]>((x, y) => x[0] < y[0]);	lists.forEach((list, li) => {		if (list.length > 0) heap.push([list[0], li, 0]);	});	const out: number[] = [];	for (let top = heap.pop(); top !== undefined; top = heap.pop()) {		const [value, li, pos] = top;		out.push(value);		if (pos + 1 < lists[li].length) heap.push([lists[li][pos + 1], li, pos + 1]);	}	return out;} console.log(topKWords("a b a c b a d a b".split(" "), 2)); // [["a", 4], ["b", 3]]console.log(mergeSorted([1, 4, 9], [2, 3, 10], [5])); // [1, 2, 3, 4, 5, 9, 10]

const queue: [string, number][] = [[start, 0]];const seen = new Set([start]);for (let head = 0; head < queue.length; head++) {const [node, dist] = queue[head];for (const nxt of graph[node]) {

type Graph = Record<string, string[]>; const graph: Graph = {	asha: ["ben", "chen"],	ben: ["asha", "dev"],	chen: ["asha", "dev", "eli"],	dev: ["ben", "chen"],	eli: ["chen"],}; // BFS: shortest number of hops in an unweighted graph.function degreesOfSeparation(graph: Graph, start: string, goal: string): number {	const queue: [string, number][] = [[start, 0]];	const seen = new Set([start]);	// An array read through a moving head index pops from the front in O(1).	for (let head = 0; head < queue.length; head++) {		const [node, dist] = queue[head];		if (node === goal) {			return dist;		}		for (const nxt of graph[node]) {			if (!seen.has(nxt)) {				seen.add(nxt);				queue.push([nxt, dist + 1]);			}		}	}	return -1;} function friendsOfFriends(graph: Graph, user: string): Set<string> {	const direct = new Set(graph[user]);	const fofs = [...direct].flatMap((f) => graph[f]);	return new Set(fofs.filter((fof) => !direct.has(fof) && fof !== user));} console.log(degreesOfSeparation(graph, "asha", "eli")); // 2console.log(friendsOfFriends(graph, "asha")); // Set(2) { 'dev', 'eli' }

let node: TrieNode | undefined = this.root;for (const ch of prefix) {	node = node.children.get(ch);	if (!node) return [];

class TrieNode {	children = new Map<string, TrieNode>();	count = 0; // how often this exact query was searched} export class Trie {	root = new TrieNode(); 	add(word: string, times = 1): void {		let node = this.root;		for (const ch of word) {			let child = node.children.get(ch);			if (!child) {				child = new TrieNode();				node.children.set(ch, child);			}			node = child;		}		node.count += times;	} 	suggest(prefix: string, k = 3): string[] {		let node: TrieNode | undefined = this.root;		for (const ch of prefix) {			node = node.children.get(ch);			if (!node) return [];		}		const found: [number, string][] = [];		const stack: [TrieNode, string][] = [[node, prefix]];		while (stack.length > 0) {			const [cur, word] = stack.pop()!;			if (cur.count) {				found.push([cur.count, word]);			}			for (const [ch, child] of cur.children) {				stack.push([child, word + ch]);			}		}		found.sort((a, b) => b[0] - a[0] || (a[1] < b[1] ? 1 : -1));		return found.slice(0, k).map(([, w]) => w);	}} const t = new Trie();for (const [q, n] of [["netflix", 90], ["news", 70], ["nest", 20], ["nba", 50]] as const) {	t.add(q, n);}console.log(t.suggest("ne")); // [ 'netflix', 'news', 'nest' ]

let lo = 1;let hi = n;while (lo < hi) {const mid = Math.floor((lo + hi) / 2);

function mergeSort(a: number[]): number[] {	if (a.length <= 1) return a;	const mid = Math.floor(a.length / 2);	const left = mergeSort(a.slice(0, mid));	const right = mergeSort(a.slice(mid));	const out: number[] = [];	let i = 0;	let j = 0;	while (i < left.length && j < right.length) {		if (left[i] <= right[j]) out.push(left[i++]);		else out.push(right[j++]);	}	return [...out, ...left.slice(i), ...right.slice(j)];} /** Binary search over deploys: O(log n) checks instead of n. */function firstBadVersion(n: number, isBad: (version: number) => boolean): number {	let lo = 1;	let hi = n;	while (lo < hi) {		const mid = Math.floor((lo + hi) / 2);		if (isBad(mid)) hi = mid;		else lo = mid + 1;	}	return lo;} console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));console.log(firstBadVersion(1000, (v) => v >= 734)); // 734 in about 10 checks

const idx = bisectRight(this.keys, h(key)) % this.keys.length; // next point clockwisereturn this.ring.get(this.keys[idx]) as string;

import { createHash } from "node:crypto"; const h = (value: string): bigint =>	BigInt(`0x${createHash("md5").update(value).digest("hex")}`); /** Index of the first element greater than x, in a sorted array. */function bisectRight(sorted: bigint[], x: bigint): number {	let lo = 0;	let hi = sorted.length;	while (lo < hi) {		const mid = (lo + hi) >>> 1;		if (x < sorted[mid]) hi = mid;		else lo = mid + 1;	}	return lo;} export class HashRing {	private readonly ring = new Map<bigint, string>();	private readonly keys: bigint[] = []; 	constructor(		nodes: string[],		private readonly vnodes = 100,	) {		for (const node of nodes) this.add(node);	} 	add(node: string): void {		for (let i = 0; i < this.vnodes; i++) {			// many points per server			const point = h(`${node}#${i}`);			this.ring.set(point, node);			this.keys.splice(bisectRight(this.keys, point), 0, point);		}	} 	remove(node: string): void {		for (let i = 0; i < this.vnodes; i++) {			const point = h(`${node}#${i}`);			this.ring.delete(point);			this.keys.splice(this.keys.indexOf(point), 1);		}	} 	nodeFor(key: string): string {		const idx = bisectRight(this.keys, h(key)) % this.keys.length; // next point clockwise		return this.ring.get(this.keys[idx]) as string;	}} const ring = new HashRing(["cache-a", "cache-b", "cache-c"]);const keys = Array.from({ length: 10_000 }, (_, i) => `user:${i}`);const before = new Map(keys.map((k) => [k, ring.nodeFor(k)]));ring.add("cache-d");const moved = keys.filter((k) => before.get(k) !== ring.nodeFor(k)).length;console.log(`${(moved / 100).toFixed(1)}% of keys moved`); // about 25%, not 75%

this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.rate); // refillif (this.tokens >= 1) {	this.tokens -= 1;	return true;}

class TokenBucket {	private readonly rate: number;	private readonly capacity: number;	private tokens: number;	private updated: number; 	constructor({ ratePerSec, capacity }: { ratePerSec: number; capacity: number }) {		this.rate = ratePerSec;		this.capacity = capacity;		this.tokens = capacity;		this.updated = performance.now() / 1000; // monotonic clock, in seconds	} 	allow(): boolean {		const now = performance.now() / 1000;		const elapsed = now - this.updated;		this.updated = now;		this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.rate); // refill		if (this.tokens >= 1) {			this.tokens -= 1;			return true;		}		return false;	}} /** Approximates a true sliding window using two fixed windows. */class SlidingWindowCounter {	private readonly limit: number;	private readonly window: number;	private curStart = 0;	private cur = 0;	private prev = 0; 	constructor(limit: number, windowSec: number) {		this.limit = limit;		this.window = windowSec;	} 	allow(): boolean {		const now = Date.now() / 1000;		const start = now - (now % this.window);		if (start !== this.curStart) {			this.prev = start - this.curStart === this.window ? this.cur : 0;			this.cur = 0;			this.curStart = start;		}		const weight = 1 - (now - start) / this.window;		if (this.prev * weight + this.cur < this.limit) {			this.cur += 1;			return true;		}		return false;	}} const bucket = new TokenBucket({ ratePerSec: 5, capacity: 10 });const allowed = Array.from({ length: 15 }, () => bucket.allow()).filter(Boolean).length;console.log(allowed); // 10: a burst of 10, then throttled

this.data.delete(key); // mark as most recently usedthis.data.set(key, value);if (this.data.size > this.capacity) {const oldest = this.data.keys().next().value as string;this.data.delete(oldest); // evict least recently used

// A Map keeps insertion order, so delete and set again moves a key to the end.class LRUCache {	readonly data = new Map<string, unknown>();	hits = 0;	misses = 0; 	constructor(readonly capacity: number) {} 	get(key: string): unknown {		if (!this.data.has(key)) {			this.misses += 1;			return undefined;		}		const value = this.data.get(key);		this.data.delete(key); // mark as most recently used		this.data.set(key, value);		this.hits += 1;		return value;	} 	put(key: string, value: unknown): void {		this.data.delete(key);		this.data.set(key, value);		if (this.data.size > this.capacity) {			const oldest = this.data.keys().next().value as string;			this.data.delete(oldest); // evict least recently used		}	} 	get hitRatio(): number {		const total = this.hits + this.misses;		return total ? this.hits / total : 0;	}} const cache = new LRUCache(2);cache.put("a", 1);cache.put("b", 2);cache.get("a"); // a becomes most recentcache.put("c", 3); // evicts bconsole.log([...cache.data.keys()]); // [ 'a', 'c' ]

for (let i = 0; i < this.k; i++) {	this.bits[this.hash(item, i)] = 1;

import { createHash } from "node:crypto"; export class BloomFilter {	readonly m: number;	readonly k: number;	readonly bits: Uint8Array; 	constructor(expectedItems: number, falsePositiveRate = 0.01) {		this.m = Math.ceil((-expectedItems * Math.log(falsePositiveRate)) / Math.log(2) ** 2);		this.k = Math.max(1, Math.round((this.m / expectedItems) * Math.log(2)));		this.bits = new Uint8Array(this.m);	} 	private hash(item: string, i: number): number {		const digest = createHash("sha256").update(`${i}:${item}`).digest();		return Number(digest.readBigUInt64BE(0) % BigInt(this.m));	} 	add(item: string): void {		for (let i = 0; i < this.k; i++) {			this.bits[this.hash(item, i)] = 1;		}	} 	mightContain(item: string): boolean {		for (let i = 0; i < this.k; i++) {			if (!this.bits[this.hash(item, i)]) return false;		}		return true;	}} const seen = new BloomFilter(1_000_000, 0.01);console.log(Math.floor(seen.m / 8) / 1024 / 1024, "MiB for a million URLs"); // about 1.1 MiBseen.add("https://example.com/a");console.log(seen.mightContain("https://example.com/a")); // trueconsole.log(seen.mightContain("https://example.com/b")); // almost certainly false

while (level.length > 1) {for (let i = 0; i < level.length; i += 2) {parents.push(h(Buffer.concat([level[i], level[i + 1]])));

import { createHash } from "node:crypto"; const h = (data: Buffer): Buffer => createHash("sha256").update(data).digest(); function merkleLevels(blocks: Buffer[]): Buffer[][] {	let level = blocks.map((b) => h(b));	const levels = [level];	while (level.length > 1) {		// duplicate the odd one out		if (level.length % 2) level = [...level, level[level.length - 1]];		const parents: Buffer[] = [];		for (let i = 0; i < level.length; i += 2) {			parents.push(h(Buffer.concat([level[i], level[i + 1]])));		}		level = parents;		levels.push(level);	}	return levels;} /** Find differing blocks by walking down only mismatching branches. */function diffBlocks(a: Buffer[], b: Buffer[]): number[] {	const la = merkleLevels(a);	const lb = merkleLevels(b);	if (la[la.length - 1][0].equals(lb[lb.length - 1][0])) return [];	let suspects = [0];	for (let depth = la.length - 2; depth >= 0; depth--) {		const next: number[] = [];		for (const i of suspects) {			for (const child of [2 * i, 2 * i + 1]) {				if (child < la[depth].length && !la[depth][child].equals(lb[depth][child])) {					next.push(child);				}			}		}		suspects = next;	}	return suspects;} const replicaA = ["row1", "row2", "row3", "row4"].map((s) => Buffer.from(s));const replicaB = ["row1", "row2", "ROW3", "row4"].map((s) => Buffer.from(s));console.log(diffBlocks(replicaA, replicaB)); // [ 2 ]

const rng = even ? lonRng : latRng; // interleave lon and lat bitsconst value = even ? lon : lat;const mid = (rng[0] + rng[1]) / 2;if (value >= mid) {	ch = (ch << 1) | 1;

const BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"; export function geohash(lat: number, lon: number, precision = 7): string {	const latRng: [number, number] = [-90, 90];	const lonRng: [number, number] = [-180, 180];	let even = true;	let bitCount = 0;	let ch = 0;	let out = "";	while (out.length < precision) {		const rng = even ? lonRng : latRng; // interleave lon and lat bits		const value = even ? lon : lat;		const mid = (rng[0] + rng[1]) / 2;		if (value >= mid) {			ch = (ch << 1) | 1;			rng[0] = mid;		} else {			ch = ch << 1;			rng[1] = mid;		}		even = !even;		bitCount += 1;		if (bitCount === 5) {			out += BASE32[ch];			bitCount = 0;			ch = 0;		}	}	return out;} // Two cafes a few hundred metres apart in Delhi share a long prefixconsole.log(geohash(28.6139, 77.209)); // ttnfucjconsole.log(geohash(28.615, 77.2105)); // ttnfucn, same first 6 characters// Cell size by precision: 5 chars ~ 4.9 km, 6 ~ 1.2 km, 7 ~ 153 m

for (let row = 0; row < this.depth; row++) {	this.table[row][this.idx(item, row)] += n;}

import { createHash } from "node:crypto"; class CountMinSketch {	readonly width: number;	readonly depth: number;	private readonly table: Uint32Array[]; 	constructor(width = 2000, depth = 5) {		this.width = width;		this.depth = depth;		this.table = Array.from({ length: depth }, () => new Uint32Array(width));	} 	private idx(item: string, row: number): number {		const digest = createHash("sha256").update(`${row}:${item}`).digest();		return digest.readUInt32BE(0) % this.width;	} 	add(item: string, n = 1): void {		for (let row = 0; row < this.depth; row++) {			this.table[row][this.idx(item, row)] += n;		}	} 	estimate(item: string): number {		let min = Number.POSITIVE_INFINITY;		for (let row = 0; row < this.depth; row++) {			min = Math.min(min, this.table[row][this.idx(item, row)]);		}		return min;	}} class HeavyHitters {	private readonly k: number;	private readonly sketch = new CountMinSketch();	private readonly top = new Map<string, number>(); 	constructor(k: number) {		this.k = k;	} 	add(item: string): void {		this.sketch.add(item);		this.top.set(item, this.sketch.estimate(item));		if (this.top.size > this.k) {			// Drop the first item with the lowest estimate			let [minKey, minVal] = [item, Number.POSITIVE_INFINITY];			for (const [key, val] of this.top) {				if (val < minVal) [minKey, minVal] = [key, val];			}			this.top.delete(minKey);		}	} 	result(): [string, number][] {		return [...this.top].sort((a, b) => b[1] - a[1]).slice(0, this.k);	}} const hh = new HeavyHitters(2);for (const tag of "#ai #ai #cricket #ai #music #cricket #ai".split(" ")) {	hh.add(tag);}console.log(hh.result()); // [["#ai", 4], ["#cricket", 2]]

return (BigInt(ms - EPOCH_MS) << 22n) | (this.machine << 12n) | BigInt(this.sequence);

const EPOCH_MS = 1704067200000; // 2024-01-01, keeps the timestamp field small // 41 bits time | 10 bits machine | 12 bits sequence = 4096 ids per ms per machine.// The id needs 63 bits, more than a number holds exactly, so it is a bigint.class Snowflake {	private readonly machine: bigint;	private lastMs = -1;	private sequence = 0; 	constructor(machineId: number) {		if (!(Number.isInteger(machineId) && machineId >= 0 && machineId < 1024)) {			throw new RangeError("machineId must fit in 10 bits");		}		this.machine = BigInt(machineId);	} 	// Synchronous, so no lock is needed: nothing else runs on this thread meanwhile.	nextId(): bigint {		let ms = Date.now();		if (ms < this.lastMs) {			throw new Error("clock moved backwards, refuse to issue ids");		}		if (ms === this.lastMs) {			this.sequence = (this.sequence + 1) & 0xfff;			if (this.sequence === 0) {				// 4096 used this ms, wait for the next				while (ms <= this.lastMs) {					ms = Date.now();				}			}		} else {			this.sequence = 0;		}		this.lastMs = ms;		return (BigInt(ms - EPOCH_MS) << 22n) | (this.machine << 12n) | BigInt(this.sequence);	}} const gen = new Snowflake(7);const a = gen.nextId();const b = gen.nextId();// true true: ordered and fits a signed 64 bit columnconsole.log(a < b, a.toString(2).length <= 63);

while (n > 0) {	out.push(ALPHABET[n % 62]);	n = Math.floor(n / 62);

const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; export function encode(n: number): string {	if (n === 0) {		return ALPHABET[0];	}	const out: string[] = [];	while (n > 0) {		out.push(ALPHABET[n % 62]);		n = Math.floor(n / 62);	}	return out.reverse().join("");} export function decode(code: string): number {	let n = 0;	for (const ch of code) {		n = n * 62 + ALPHABET.indexOf(ch);	}	return n;} console.log(62 ** 7); // 3521614606208 possible 7 character codesconsole.log(encode(125_000_000_000)); // 2crtgcg: 7 charactersconsole.log(decode(encode(987654321)) === 987654321); // true

1. Requirements  2. Estimates  3. High level design4. API + data model  5. Deep dives  6. Bottlenecks and trade-offs

# 45 minute system design interview, timed 0-5    Clarify: who uses it, core features, what is out of scope5-10   Non functional: scale, latency target, availability, consistency10-15  Estimate: users, QPS (average and peak), storage per year, bandwidth15-25  High level: clients, load balancer, services, data stores, caches, queues25-30  API and data model: endpoints, request and response, tables or documents30-40  Deep dive: the hardest part (hot keys, fan out, consistency, ordering)40-45  Wrap up: bottlenecks, failure modes, monitoring, what you would do next

Functional: create short link, redirect, custom alias, expiryNon functional: 100M links/month, p99 redirect < 50 ms, 99.99% available

## URL shortener: requirements ### Functional- Create a short link for a long URL (optional custom alias)- Redirect a short link to its long URL- Links can expire; owners can delete them- Basic click analytics per link ### Non functional- Scale: 100M new links per month, 10B redirects per month (100:1 read heavy)- Latency: redirect p99 under 50 ms worldwide- Availability: 99.99% for redirects; link creation can be 99.9%- Durability: a created link must never be lost- Consistency: a new link may take a second to resolve everywhere (eventual is fine) ### Out of scope- User accounts beyond an API key, link previews, spam scanning