{ "@context": "https://schema.org", "@type": "Organization", "name": "Brainscape", "url": "https://www.brainscape.com/", "logo": "https://www.brainscape.com/pks/images/cms/public-views/shared/Brainscape-logo-c4e172b280b4616f7fda.svg", "sameAs": [ "https://www.facebook.com/Brainscape", "https://x.com/brainscape", "https://www.linkedin.com/company/brainscape", "https://www.instagram.com/brainscape/", "https://www.tiktok.com/@brainscapeu", "https://www.pinterest.com/brainscape/", "https://www.youtube.com/@BrainscapeNY" ], "contactPoint": { "@type": "ContactPoint", "telephone": "(929) 334-4005", "contactType": "customer service", "availableLanguage": ["English"] }, "founder": { "@type": "Person", "name": "Andrew Cohen" }, "description": "Brainscape’s spaced repetition system is proven to DOUBLE learning results! Find, make, and study flashcards online or in our mobile app. Serious learners only.", "address": { "@type": "PostalAddress", "streetAddress": "159 W 25th St, Ste 517", "addressLocality": "New York", "addressRegion": "NY", "postalCode": "10001", "addressCountry": "USA" } }

Hashing Flashcards

(5 cards)

1
Q

What is Hashing and when is it used?

A

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

Example: LRU Cache.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the key steps in Hashing?

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

Explain steps for LRU Cache aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How does Hashing apply to LRU Cache?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the complexity and gotchas of Hashing?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Code example of Hashing.

A

```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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly