Challenge 3: Add Eviction to a Memoize Cache — Possible Solution
====================================================================

function memoizeWithLimit<Args extends unknown[], Result>(
  fn: (...args: Args) => Result,
  maxSize: number
): (...args: Args) => Result {
  // Map preserves insertion order, which is exactly what an LRU eviction
  // policy needs: re-inserting a key on access moves it to the "most
  // recently used" end.
  const cache = new Map<string, Result>();

  return (...args: Args): Result => {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      // Move this key to the end (most recently used) by deleting and
      // re-inserting it.
      const value = cache.get(key)!;
      cache.delete(key);
      cache.set(key, value);
      return value;
    }

    const result = fn(...args);

    if (cache.size >= maxSize) {
      // The first key in iteration order is the least recently used one.
      const oldestKey = cache.keys().next().value;
      if (oldestKey !== undefined) {
        cache.delete(oldestKey);
      }
    }

    cache.set(key, result);
    return result;
  };
}

// --- Usage ---

function expensiveCalculation(n: number): number {
  let total = 0;
  for (let i = 0; i < n; i++) total += i;
  return total;
}

const memoizedCalc = memoizeWithLimit(expensiveCalculation, 2);

memoizedCalc(1000); // computed, cached — cache: [1000]
memoizedCalc(2000); // computed, cached — cache: [1000, 2000]
memoizedCalc(3000); // computed, cached, evicts 1000 (least recently used) — cache: [2000, 3000]
memoizedCalc(1000); // cache miss again — 1000 was evicted, must recompute

WHY THIS WORKS
--------------
- A plain Map iterates its keys in insertion order, so the first key
  returned by cache.keys().next() is always the one that has gone longest
  without being accessed — exactly the "least recently used" entry.
- Deleting and re-inserting a key on a cache hit moves it to the end of
  that iteration order, marking it as "recently used" without needing a
  separate data structure to track access order.
- maxSize bounds the cache's memory growth explicitly — trading a small,
  predictable amount of recomputation (occasional cache misses) for a hard
  ceiling on memory usage, instead of the original memoize's unbounded growth.