Richard Vinueza — creative human thinkingCreativeHUMANHUMANHUMANthinking...building...drawing...Richard Vinueza

What it is

An infinite canvas where notes, images and ideas live wherever you drop them. Pan, zoom, cluster. The layout is the thinking.

Why a prototype

It mixes both sides of the Lab: the system design of a canvas that stays fast with thousands of items, and the small algorithmic exercises inside it, hit testing, culling, spatial indexing.

What it is

A draggable globe with a marker per place. Pick a country to fly there; pick a marker to open its stamp: where, when, one line about it.

Why a prototype

Rendering a globe smoothly on a phone is a system design problem in miniature: what to draw, when, and how to keep the frame budget. The camera easing and the marker projection are the exercises.

The problem

Users upload PDFs. Every page is one call to an AI provider that extracts and structures the text. A book is a hundred pages, so one upload is a hundred calls.

Me alone, uploading three or four books one after another: fine. All pages in parallel: still fine. Then we opened it to everyone, a huge queue formed, and the provider said no.

The provider in the lab is a stand-in with the limits real ones have: 1,500 requests and 300,000 tokens per minute, 200 calls in flight at most, three dollars per million tokens. A page is about 800 tokens and takes about two seconds. Nothing leaves your machine and nothing costs money.

Case 1 · One user, one page after another

The first version. A user uploads a book and we process it page by page: send one page, wait for the answer, send the next. One call in flight per user.

for (const page of book.pages) {
  await provider.complete(page) // one after another
}

It works and it is safe. The provider sees one call every two seconds and nobody complains, because nobody else is using it yet. Run case 1

Case 2 · All pages at once, and a few more users

Three minutes per book is too slow, so we fire the hundred calls together with Promise.all. One user: the book finishes in seconds. Then two, three users try at the same time. Every user is now a burst of a hundred calls and eighty thousand tokens.

await Promise.all(book.pages.map((page) => provider.complete(page)))
// 100 calls at once per user; nothing slows them down

The provider answers 503 Overloaded for what does not fit in flight and 429 Too Many Requests with a retry-after once the minute’s tokens run out. Pages die, the user sees a broken book, and we still pay for every page that got through.

Measured: with three users it breaks in the first second. In fifteen seconds, 2,122 pages died at the provider, 3 of 25 books came out clean, and the bill was $0.90 for pages that mostly ended up in broken books. This is the day we opened it. Run case 2

Case 3 · A rate limiter in front: the token bucket

First fix: never let more through than the provider accepts. Two buckets. One per user, small, five pages in a burst and two more per second, so one person cannot flood us. One global, pinned to the provider’s requests per minute, so the sum of everyone never exceeds it. A page takes a token from both or is refused by us, instantly and for free, with our own 429.

// token bucket, per key
tokens = Math.min(capacity, tokens + elapsed * refillPerSec)
if (tokens >= 1) { tokens -= 1; allow() }
else reject({ retryAfterMs: ((1 - tokens) / refillPerSec) * 1000 })

Token bucket over a fixed window

why

A bucket is two numbers per key and lets a user burst a few pages, which is how people actually behave. A fixed per-minute counter is simpler but lets twice the limit through at the minute boundary.

cost

Bursts up to the bucket size are allowed by design.

The same bucket as a Lua script in Redis when there is more than one API instance

why

Read, refill and take must be one atomic step or two instances spend the same last token. Redis runs the script whole, and its own clock removes skew between servers.

cost

Logic lives in a Lua string. Keep it short and test it alone.

The provider never sees the excess again: zero 429 on their side, zero wasted spend. But the failure only moved. Now it is our limiter answering 429 to real people, and a book of a hundred pages against a bucket of five still comes out broken. Good for protecting a paid API; not enough for this product. Run case 3

Case 4 · A work queue: say yes, later

The users are not abusing anything; they are uploading books, which is the product. So instead of saying no, hold the page and send it when the provider can take it.

// the dispatch loop
while (inFlight < concurrency && queue.size > 0) {
  const job = peek(nextUserInTurn())
  if (requestBudget < 1 || tokenBudget < job.tokens) break // wait for the next token
  requestBudget -= 1
  tokenBudget -= job.tokens
  dispatch(take(job))
}
// at the door: if (estimateWait(job) > maxWaitMs) reject busy(position)

Drain on two budgets, requests and tokens

why

Providers limit both, and a page is heavy in tokens. A queue that only counts requests would still hit the token ceiling.

cost

You need an estimate of tokens per job before sending it. For pages, the size of the text is a good enough proxy.

Round-robin between users, not first come first served

why

One user uploading ten books must not delay everyone else by ten books. A lane per user and a turn each keeps the wait proportional to what you asked for.

cost

More bookkeeping than a single FIFO.

Backpressure at the door

why

Accepting work you cannot finish in reasonable time is worse than a fast no. The queue estimates the wait on entry and refuses past a minute, with a position so the client can decide.

cost

Some users get busy on a spike even though the system is healthy. That is the point: it is honest.

No provider errors, no wasted spend, and users get waiting instead of failing: a page might take twenty seconds, but the book arrives whole. The honest part shows up too: the queue protects the provider, it does not create capacity. When more books arrive than the provider can process per minute, the wait grows until the door starts saying busy. Past that point the answer is a bigger tier or more keys, and the numbers tell you exactly when. Run case 4

Case 5 · What actually happened: the queue nobody designed

In production there was no queue and no limiter. So where did “a huge queue formed” come from? From the HTTP client. Every client library keeps a connection pool; ours allowed a couple of hundred connections to the provider. When thousands of pages arrived at once, they did not fail immediately: they waited for a free connection, in a queue we never wrote, with no fairness, no budget and no door. Latency climbed to minutes, users retried, the pool filled again, and when pages finally reached the provider they hit its limits anyway.

Cases 3 and 4 are the same waiting, made explicit and given rules. That is the whole lesson: there is always a queue; the only choice is whether you designed it. Run case 5

Where it breaks

The lab has a ramp that adds users every three seconds, 1, 2, 3, 5, 8, 12, 20, 30, 50, 80…, and notes the first failure. With all pages at once and nothing in front, it broke with 3 users at second 7, on tokens per minute. With the same crowd and the limiter, the provider stayed clean and our own 429 started at the same point. With the queue, nothing failed at the provider; the wait grew instead, and the door started saying busy when it would have passed a minute.

What I would do in production

• Pages one after another per user was never the answer; parallel with a queue in front is.
• Size the queue’s budgets from the provider’s documented limits, not from guesses, and alert when the wait p95 crosses a threshold: that is the signal to buy a bigger tier.
• Show the position in the queue to the user. Waiting with a number is fine; waiting in the dark is what makes people retry and make it worse.
• Treat the HTTP client’s pool as a queue you own: size it, measure it, and never let it be the only thing between you and a 503.

The problem

Design a cache with a fixed capacity. get(key) returns the value or -1. put(key, value) inserts or updates. When the cache is full, evict the item that was least recently used. Both operations must run in O(1).

Questions I would ask first

• Does get count as a use? Yes: reading refreshes the item.
• Does updating an existing key count as a use? Also yes.
• Capacity of 0? Treat as always empty.
• Single thread? For the interview, yes. See “in the real world” for the rest.

Brute force

Keep an array ordered by recency. get scans it (O(n)), moves the hit to the front (O(n)). put does the same and pops the tail when full. Correct, and too slow: every operation touches the whole array.

Where it hurts

Two things need to be fast at once: finding a key and moving an item to the front. An array finds slowly and moves slowly. A hash map finds fast but has no order. A linked list moves fast but finds slowly.

The key idea

Use both, and let each do the one thing it is good at.

1. 01Hash mapkey → node, O(1) lookup
2. 02Doubly linked listmost recent at the head, least at the tail
3. 03Sentinelsfake head and tail so no edge cases on insert or remove

A get looks the node up in the map, unlinks it and relinks it at the head. A put on a new key links a node at the head and, if over capacity, drops the tail node and deletes its key from the map.

Solution

class Node {
  constructor(
    public key: number,
    public value: number,
    public prev: Node | null = null,
    public next: Node | null = null,
  ) {}
}

class LRUCache {
  private map = new Map<number, Node>()
  private head = new Node(0, 0) // sentinel: most recent side
  private tail = new Node(0, 0) // sentinel: least recent side

  constructor(private capacity: number) {
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  get(key: number): number {
    const node = this.map.get(key)
    if (!node) return -1
    this.moveToFront(node)
    return node.value
  }

  put(key: number, value: number): void {
    const existing = this.map.get(key)
    if (existing) {
      existing.value = value
      this.moveToFront(existing)
      return
    }
    const node = new Node(key, value)
    this.map.set(key, node)
    this.linkAtFront(node)
    if (this.map.size > this.capacity) {
      const victim = this.tail.prev!
      this.unlink(victim)
      this.map.delete(victim.key)
    }
  }

  private unlink(node: Node) {
    node.prev!.next = node.next
    node.next!.prev = node.prev
  }

  private linkAtFront(node: Node) {
    node.next = this.head.next
    node.prev = this.head
    this.head.next!.prev = node
    this.head.next = node
  }

  private moveToFront(node: Node) {
    this.unlink(node)
    this.linkAtFront(node)
  }
}

Complexity

get and put are a map lookup plus a constant number of pointer changes: O(1). Memory is one node per entry plus the map: O(capacity).

Variants worth knowing

• LFU (least frequently used): a map of frequency → its own LRU list, plus a minFreq counter. Still O(1), twice the bookkeeping.
• TTL: store an expiry per node and treat expired hits as misses; evict lazily on access.
• JavaScript shortcut: Map keeps insertion order, so delete + set moves a key to the end. Shorter code, same complexity, and worth mentioning before writing the list by hand.

In the real world

Redis implements approximate LRU by sampling a few keys instead of keeping an exact list: exactness is not worth the memory per key. HTTP caches and CPU caches do the same trade. The interview answer is the exact version; production usually is not.

What it will show

Move the pointer across a strip. Three rows draw the events: the raw stream, the debounced output, and the throttled one. Sliders change the wait time and switch leading and trailing edges.

Why

Both words get used for each other in code review. Seeing the two rows side by side settles it faster than a definition.

Status

Idea stage: no build yet.