Hashing

Question 1

What is Hashing and when is it used?

Answer 1

Hashing uses hash tables for fast lookup or grouping.
Use case includes frequency counting, grouping, and caching.

Example: LRU Cache.

Question 2

What are the key steps in Hashing?

Answer 2

1. Initialize hash table for data.
2. Store/retrieve with key-value pairs.
3. Handle collisions or updates.

Explain steps for LRU Cache aloud.

Question 3

How does Hashing apply to LRU Cache?

Answer 3

The problem is to implement least recently used cache. The approach is to use a hash table and doubly linked list for O(1) operations.

Verbalize solution logic for LRU Cache aloud.

Question 4

What are the complexity and gotchas of Hashing?

Answer 4

Time complexity is O(1) average, and space complexity is O(n).
Gotchas include capacity=0 and frequent evictions.

List edge cases for LRU Cache aloud.

Question 5

Code example of Hashing.

Answer 5

```python
from typing import Optional
class Node:
def __init__(self, key: int = 0, value: int = 0) -> None:
self.key = key
self.value = value
self.prev: Optional[‘Node’] = None
self.next: Optional[‘Node’] = None
class LRUCache:
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.cache: dict[int, Node] = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self._add(node)
self.cache[key] = node
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
def _add(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
~~~

Sketch cache structure on paper.