All Problems, One Page

Problem

O(1) get(key) and put(key, value). Evict least-recently-used on overflow.

Live demo

Code

class Node:
    def __init__(self, k, v):
        self.k, self.v = k, v
        self.prev = self.next = None

class LRU:
    def __init__(self, cap):
        self.cap = cap
        self.map = {}
        self.head = Node(0, 0)  # dummy
        self.tail = Node(0, 0)  # dummy
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, n):
        n.prev.next, n.next.prev = n.next, n.prev

    def _add_front(self, n):
        n.next = self.head.next
        n.prev = self.head
        self.head.next.prev = n
        self.head.next = n

    def get(self, k):
        if k not in self.map: return -1
        n = self.map[k]
        self._remove(n); self._add_front(n)
        return n.v

    def put(self, k, v):
        if k in self.map:
            self._remove(self.map[k])
        n = Node(k, v)
        self.map[k] = n
        self._add_front(n)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.k]

Common follow-ups

• TTL eviction: add expiry. Either lazy (check on access) or active (sweeper thread).
• LFU vs LRU: LFU tracks access counts. More complex with min-frequency tracking.
• Concurrent LRU: guard with lock, or use lock-free design (e.g., Caffeine's W-TinyLFU).

Problem (monday.com framing)

Formula columns can reference other columns: Total = Quantity × Price. When user adds a new formula, detect cycles and return evaluation order.

Live demo

Code (DFS with 3 colors)

def topo_sort(graph):  # node -> [deps]
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {n: WHITE for n in graph}
    order = []

    def dfs(n):
        if color[n] == GRAY:
            raise ValueError(f"Cycle at {n}")
        if color[n] == BLACK: return
        color[n] = GRAY
        for d in graph.get(n, []):
            dfs(d)
        color[n] = BLACK
        order.append(n)

    for n in graph:
        dfs(n)
    return order

Kahn's algorithm (alternative)

BFS-based. Track in-degrees, repeatedly take zero-in-degree nodes. If you can't process all nodes → cycle exists. O(V+E) same as DFS.

Problem

Given comment text and a user/group directory, return distinct user_ids to notify. Watch for @group expanding to multiple users, and dedup.

Live demo

Code

import re

def resolve_mentions(text, users, groups):
    # users: set[str], groups: dict[str, set[str]]
    mentions = re.findall(r"@(\w+)", text)
    recipients = set()
    for name in mentions:
        if name in users:
            recipients.add(name)
        elif name in groups:
            recipients |= groups[name]
    return recipients   # dedup via set

Same set-union pattern as Q1. If they ask this, default to set for resolution + dedup.

Problem

Stream of activity events. Periodically return top K items by event count in the last hour.

Approach

• Counts per item using a hashmap.
• Sliding window: deque of (timestamp, item) → on read, evict old, decrement count.
• Top K: min-heap of size K, ordered by count.

Code

import heapq
from collections import deque

class TopK:
    def __init__(self, k, window):
        self.k, self.window = k, window
        self.events = deque()
        self.counts = {}

    def record(self, item, ts):
        self.events.append((ts, item))
        self.counts[item] = self.counts.get(item, 0) + 1

    def top(self, now):
        while self.events and self.events[0][0] < now - self.window:
            _, item = self.events.popleft()
            self.counts[item] -= 1
            if self.counts[item] == 0:
                del self.counts[item]
        return heapq.nlargest(self.k, self.counts.items(), key=lambda x: x[1])

Scale follow-up

If item space is huge (millions) and you need approximate counts, use Count-Min Sketch — bounded memory, bounded error, ideal for streaming top-K at scale.

Approach

Each user action → Command object with do() and undo(). Two stacks: undo, redo.

class UpdateCell(Command):
    def __init__(self, item, col, new_val):
        self.item, self.col = item, col
        self.old_val = item[col]
        self.new_val = new_val
    def do(self): self.item[self.col] = self.new_val
    def undo(self): self.item[self.col] = self.old_val

Hard parts

• Collaborative undo: Alice's undo shouldn't trample Bob's later edit. Common policy: each user undoes only their own actions, rebased against current state.
• Server authority: client undo sends command to server. Server validates, applies, broadcasts.
• Limits: cap undo stack at ~50 entries. Older actions become non-undoable.

Stack

• Elasticsearch/OpenSearch index per workspace (or sharded).
• Document includes permissions: { users: [...], groups: [...] } for ACL filter.
• Async indexing: item update → Kafka → indexer worker → ES.

Query-time permission filter

{
  "query": {
    "bool": {
      "must": [
        { "match": { "text": "deploy" } }
      ],
      "filter": [
        { "terms": { "permissions.users": ["vikas"] } },
        { "terms": { "permissions.groups": ["engineering", "leads"] } }
      ]
    }
  }
}

Client UX

• Debounce keystrokes ~150ms.
• Cancel in-flight request when user types again (AbortController).
• Cache recent queries (~5 last). Show instantly on re-type.

Schema

• user_pins(user_id, board_id, position) — position is a fractional index for drag-reorder.
• user_visits(user_id, board_id, last_visited_at) — upsert on each board open.

Single endpoint

GET /sidebar
{
  pinned: [board, board, ...],  # ordered by position
  recent: [board, board, ...]   # top 5 by last_visited_at, excluding pinned
}

One round-trip. Don't make the client make two requests for adjacent UI.

API

POST /items/bulk_update
{
  ids: [1, 2, 3, ..., 200],
  changes: { status: "Done" }
}

// Response - per-item status
{
  results: [
    { id: 1, ok: true },
    { id: 2, ok: false, error: "permission denied" },
    ...
  ]
}

Client flow (optimistic)

1. Apply changes to all selected items immediately in UI.
2. Send batch request.
3. On response: revert any items where ok: false. Toast errors.

Large batches (10k+ items)

Switch to async job: POST /items/bulk_update_async returns job_id. Client polls or subscribes via WebSocket for progress. Show progress bar.

Pipeline

Features to bring up

• Per-user preferences: mute channels, quiet hours, digest mode.
• Digest mode: instead of immediate, batch per user. Cron rolls up daily/hourly digest.
• Throttling: max 1 email per user per hour. Redis token bucket.
• Dedup: hash of (user, event_id) checked before send. (The Q1 pattern at scale.)
• Templating: rendered per recipient (locale, name, item title). Edge cache.

Three patterns

monday.com is shared with row-level isolation. account_id on every table, indexed first in composites.

Sharding strategy

• Shard by account_id — all an account's data lives together. Joins stay cheap.
• Lookup service maps account_id → shard_id (cached in app).
• Big accounts get dedicated shards (move via online migration).
• Cross-shard analytics: ETL to data warehouse.

Write path

Async via Kafka. Never block user writes on logging.

Storage tiers

• Hot: last 90 days in Postgres or ClickHouse. Partitioned by (account_id, month).
• Cold: > 90 days as Parquet in S3. Queried via Athena/Trino.
• Analytics: stream into BigQuery / Snowflake for product analytics.

Privacy / GDPR

• User deletion request → tombstone records (don't hard-delete due to legal hold).
• Mask PII fields on tombstoning. Keep IDs for referential integrity.
• Retention policy per tier of account (Enterprise vs Free).

Flow

1. Client requests upload URL: POST /uploads → {url, fields}.
2. Server returns S3 presigned POST. Bytes never touch app servers.
3. Client uploads directly to S3.
4. S3 ObjectCreated event → Lambda → virus scan → quarantine vs clean bucket.
5. Async: generate thumbnails (image), extract preview (PDF).
6. Client polls or subscribes to attachment-ready event.

Serving

• Public attachments: CDN (CloudFront) with origin S3.
• Private: signed URLs expiring in 1h. Sign via Lambda@Edge if you need permission check at edge.
• Thumbnails: separate cache key. Different size variants.