TypeDrop

2026-10-12 Challenge

2026-10-12 Hard

Typed LRU Cache with TTL and Generational Eviction

You're building the in-process caching layer for a high-throughput data pipeline. Each cache instance is parameterised over a strict key–value schema, enforces per-entry TTL expiry, and reports hits, misses, and evictions through a strongly-typed audit log — all verified by the compiler with zero unsafe casts.

Goals

Define CacheEvent<S> as a mapped discriminated union so each 'hit' variant carries exactly S[K] for its specific key K — not a union of all value types.
Implement the LRU ordering with MRU promotion on get and LRU eviction when capacity is exceeded, emitting the correct typed CacheEvent for every state change.
Implement per-entry TTL tracking with lazy eviction inside get (emit 'evict' then 'miss') and eager bulk eviction in purgeExpired.
Ensure makeKey brands its return type so that raw strings and invalid key names are rejected by the compiler with no unsafe casts anywhere.

          
          challenge.ts

interface AppSchema {
  userId: string;
  sessionToken: string;
  requestCount: number;
}

type CacheKey<S extends CacheSchema, K extends keyof S> =
  K & { readonly [__brand]: S };

// Discriminated union — each variant's `value` is tied to its exact key type:
type CacheEvent<S extends CacheSchema> = /* TODO: mapped discriminated union */
  never;

// Factory + Cache interface
declare function createCache<S extends CacheSchema>(
  options: CacheOptions<S>
): Cache<S>;

interface Cache<S extends CacheSchema> {
  get<K extends keyof S>(key: CacheKey<S, K>): S[K] | undefined;
  set<K extends keyof S>(key: CacheKey<S, K>, value: S[K], ttlMs?: number): void;
  delete<K extends keyof S>(key: CacheKey<S, K>): boolean;
  purgeExpired(): number;
  snapshot(): ReadonlyMap<keyof S, S[keyof S]>;
  stats(): CacheStats;
}

Hints (click to reveal)

Hints

For CacheEvent<S>, try: `type CacheEvent<S> = { [K in keyof S]: { kind: 'hit'; key: K; value: S[K] } | { kind: 'miss'; key: K } | { kind: 'evict'; key: K; reason: EvictReason } }[keyof S]` — a distributive mapped type.
A doubly-linked list (or insertion-ordered Map) is the classic O(1) LRU structure; TypeScript's built-in Map iterates in insertion order, which you can exploit.
Store each entry as `{ value: S[keyof S]; expiresAt: number | undefined }` — compare `Date.now()` against `expiresAt` on every read to implement lazy TTL eviction.

Useful resources

StackBlitz

CodeSandbox

Or clone locally

git clone -b challenge/2026-10-12 https://github.com/niltonheck/typedrop.git