Weighted Cache Pool Walk Through. Explaination Video: https://youtu.be/k3rKetctNug

01-weighted-cache-pool.js

let time = 0
Date.now = () => {
  time++
  return time
}

class Cache {
  pool = {}
  size = 0

  constructor(capacity) {
    this.capacity = capacity
  }

  calcScore(weight, current_time, last_accessed_time) {
    return weight / (Math.log(current_time - last_accessed_time + 1) + 1)
  }

  getMinScoreKey(current_time) {
    let min_score = Number.POSITIVE_INFINITY
    let min_key
    for (let key in this.pool) {
      let { weight, last_accessed_time } = this.pool[key]
      let score = this.calcScore(weight, current_time, last_accessed_time)
      console.log('compare:', {
        key,
        weight,
        diff_time: current_time - last_accessed_time,
        score,
      })
      if (score < min_score) {
        min_score = score
        min_key = key
      }
    }
    return min_key
  }

  put(key, value, weight) {
    let current_time = Date.now()
    if (this.size >= this.capacity) {
      console.log('full, the pool:', this.pool)
      let min_key = this.getMinScoreKey(current_time)
      console.log('remove from pool:', min_key)
      delete this.pool[min_key]
      this.size--
    }
    this.pool[key] = {
      value,
      weight,
      last_accessed_time: current_time,
    }
    this.size++
  }

  get(key) {
    if (key in this.pool) {
      let item = this.pool[key]
      item.last_accessed_time = Date.now()
      return item.value
    }
    return -1
  }
}

let cache = new Cache(3)

cache.put('pie1', 'v01', 50)
cache.put('pie2', 'v02', 30)
cache.put('pie3', 'v03', 10)
cache.put('pie4', 'v04', 20)

function get(key) {
  console.log(key, '->', cache.get(key))
}

get('apple')
get('pie1')
get('pie2')
get('pie3')
get('pie4')

cache.put('pie5', 'v05', 20)
cache.put('pie6', 'v06', 20)
cache.put('pie7', 'v07', 20)
cache.put('pie8', 'v08', 20)
cache.put('pie9', 'v09', 20)
cache.put('pie10', 'v10', 20)
cache.put('pie11', 'v11', 20)

get('pie1')
get('pie2')
get('pie3')
get('pie4')
get('pie5')
get('pie6')
get('pie7')
get('pie8')
get('pie9')
get('pie10')
get('pie11')

02-adt.ts

let numbers: number[] = new Array(10)

numbers[5] = 50

class LinkedList<T> {
  head: LinkedListNode<T> | null = null

  add(data: T) {
    this.add_to_head(data)
  }

  *iterate() {
    let node = this.head
    while (node) {
      yield node.data
      node = node.next
    }
  }

  add_to_head(data: T) {
    this.head = { data, next: this.head }
  }

  add_to_tail(data: T) {
    if (!this.head) {
      this.head = {
        data,
        next: null,
      }
      return
    }
    let node = this.head
    while (true) {
      if (node.next) {
        node = node.next
        continue
      }
      node.next = {
        data,
        next: null,
      }
    }
  }
}

interface LinkedListNode<T> {
  data: T
  next: LinkedListNode<T> | null
}

export class HashTable<T> {
  buckets: Array<LinkedList<{ key: string; value: T }>>

  constructor() {
    this.buckets = new Array(10)
    for (let i = 0; i < this.buckets.length; i++) {
      this.buckets[i] = new LinkedList()
    }
  }

  set(key: string, value: T) {
    let index: number = this.hash(key)
    let bucket = this.buckets[index]
    bucket.add({ key, value })
  }

  get(key: string): T | null {
    let index: number = this.hash(key)
    let bucket = this.buckets[index]
    for (let item of bucket.iterate()) {
      if (item.key == key) {
        return item.value
      }
    }
    return null
  }

  hash(key: string): number {
    // return key.length % this.buckets.length
    let acc = 0
    for (let i = 0; i < key.length; i++) {
      acc += key.charCodeAt(i)
    }
    return acc % this.buckets.length
  }
}

let map = new HashTable()

map.set('apple', 10)
map.set('banana', 20)
map.set('cherry', 30)
map.set('123456', 40)

function get(key: string) {
  console.log(key, '->', map.get(key))
}

get('apple')
get('banana')
get('cherry')

console.dir(map, { depth: 20 })