simple-lru-cache-node.ts

/**
 * A Least Recently Used (LRU) cache with Time-to-Live (TTL) support. Items are kept in the cache until they either
 * reach their TTL or the cache reaches its size and/or item limit. When the limit is exceeded, the cache evicts the
 * item that was least recently accessed (based on the timestamp of access). Items are also automatically evicted if they
 * are expired, as determined by the TTL.
 * An item is considered accessed, and its last accessed timestamp is updated, whenever `has`, `get`, or `set` is called with its key.
 *
 * Implement the LRU cache provider here and use the lru-cache.test.ts to check your implementation.
 * You're encouraged to add additional functions that make working with the cache easier for consumers.
 */

type LRUCacheProviderOptions = {
  ttl: number; // Time to live in milliseconds
  itemLimit: number;
};
type LRUCacheProvider<T> = {
  has: (key: string) => boolean;
  get: (key: string) => T | undefined;
  set: (key: string, value: T) => void;
};
interface LRUCacheData<T> {
  item: T,
  createdAt: Date;
}

export function createLRUCacheProvider<T>({ ttl, itemLimit }: LRUCacheProviderOptions): LRUCacheProvider<T> {
  let cacheQueue: string[] = [];
  let cacheStore: Map<string, LRUCacheData<T>> = new Map<string, LRUCacheData<T>>()
  let capacity: number = 0;

  const moveKeyToLast = (key: string) => {
    const idx = cacheQueue.indexOf(key);
    const newQueue = [
      ...cacheQueue.slice(0, idx),
      ...cacheQueue.slice(idx+1),
      key
    ]
    cacheQueue = newQueue;
  }

  const removeKey = (key: string) => {
    const idx = cacheQueue.indexOf(key);
    const newQueue = [
      ...cacheQueue.slice(0, idx),
      ...cacheQueue.slice(idx+1)
    ]
    cacheQueue = newQueue;
  }

  return {
    has: (key: string) => {
      if (!cacheStore.has(key)) {
        return false;
      }

      const data = cacheStore.get(key);
      if (!data) {
        return false;
      }

      if (Date.now() - data.createdAt.valueOf() >= ttl) {
        removeKey(key);
        cacheStore.delete(key);
        capacity--;
        return false;
      }

      return true;
    },
    get: (key: string) => {
      if (!cacheStore.has(key)) {
        return undefined;
      }

      const data = cacheStore.get(key)!;
      if (Date.now() - data.createdAt.valueOf() >= ttl) {
        removeKey(key);
        cacheStore.delete(key);
        capacity--;
        return undefined;
      }

      moveKeyToLast(key);
      cacheStore.set(key, {
        item: data.item,
        createdAt: new Date()
      })
      
      return data.item;
    },
    set: (key: string, value: T) => {
      if (capacity == itemLimit) {
        if (cacheStore.has(key)) {
          moveKeyToLast(key);
          cacheStore.set(key, {
            item: value,
            createdAt: new Date()
          })

          return;
        }

        const lru = cacheQueue[0];
        capacity--;
        removeKey(lru);
        cacheStore.delete(lru);
      }
      

      capacity++;
      cacheStore.set(key, {
        item: value,
        createdAt: new Date()
      })
      cacheQueue.push(key);
    },
  };
}