Day 57: Design HashMap

Day 57 — Design HashMap

Coding problem

Solution outline (coding)

• Choose chaining (linked lists per bucket) or open addressing.
• Hash function + compression mod buckets; resize when load factor exceeds threshold.
• Implement put, get, remove with lazy deletion if needed.

Time complexity: O(1) average per op; O(n) worst if all collide.

Space complexity: O(n) — entries stored.

class MyHashMap:
  def __init__(self):
    self.size = 1009
    self.buckets = [[] for _ in range(self.size)]

  def _idx(self, key: int) -> int:
    return key % self.size

  def put(self, key: int, value: int) -> None:
    i = self._idx(key)
    for j, (k, _) in enumerate(self.buckets[i]):
      if k == key:
        self.buckets[i][j] = (key, value)
        return
    self.buckets[i].append((key, value))

  def get(self, key: int) -> int:
    i = self._idx(key)
    for k, v in self.buckets[i]:
      if k == key:
        return v
    return -1

  def remove(self, key: int) -> None:
    i = self._idx(key)
    self.buckets[i] = [(k, v) for k, v in self.buckets[i] if k != key]


# Input:  put(1,1), get(1)->1, remove(1), get(1)->-1
# Output: as above

SQL interview practice

1. Interview question

Companies / track: OpenAI, Anthropic

Frontier AI labs: SQL mirrors ML infra and evaluation—experiment tables, logging joins, and metric definitions with reproducible grain and clear ownership of keys.

What you are asked to write (SQL prompt):

Frame this as metrics work for **OpenAI, Anthropic**-scale surfaces (ads, product, or engagement — as the tables suggest).
Design a BigQuery-backed key/value store abstraction: kv(store, key, value, updated_at). Write queries for point lookups, historical versions, and hot key detection.

Tables implied by the prompt:

• kv(store, key, value, updated_at)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map Hash Design to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT store, key, ARRAY_AGG(STRUCT(value, updated_at) ORDER BY updated_at DESC LIMIT 5) AS recent_versions
FROM kv
GROUP BY store, key;