LRU cache design with hash map and doubly linked list in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the main data structure used to store cache entries for fast access.

Data Structures Theory

cache = [1]()

Drag options to blanks, or click blank then click option'

Aset

Bdict

Clist

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Using a list instead of a dictionary causes slow lookups.

Using a set does not store key-value pairs.

The cache uses a hash map (dictionary) to store keys and their corresponding nodes for O(1) access.

2fill in blank

medium

Complete the code to add a new node to the front of the doubly linked list representing the most recently used item.

Data Structures Theory

def add_to_front(node):
    node.prev = None
    node.next = [1]
    if head:
        head.prev = node
    head = node

Drag options to blanks, or click blank then click option'

Ahead

Btail

Cnode

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Setting next to tail instead of head.

Setting next to None breaks the list linkage.

To add a node to the front, its next pointer should point to the current head.

3fill in blank

hard

Fix the error in the code that removes the least recently used node from the tail of the doubly linked list.

Data Structures Theory

def remove_tail():
    if not tail:
        return
    prev_node = tail.prev
    if prev_node:
        prev_node.next = [1]
    tail = prev_node

Drag options to blanks, or click blank then click option'

Ahead

Bprev_node

CNone

Dtail

Attempts:

3 left

💡 Hint

Common Mistakes

Setting next to tail creates a cycle.

Setting next to prev_node is incorrect.

When removing the tail, the previous node's next pointer should be set to None to mark the new end.

4fill in blank

hard

Fill both blanks to update the cache when a key is accessed: move the node to the front and update pointers.

Data Structures Theory

def access_key(key):
    node = cache[key]
    # Remove node from current position
    node.prev.next = [1]
    node.next.prev = [2]

Drag options to blanks, or click blank then click option'

Anode.next

Bnode.prev

Cnode

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Linking nodes incorrectly causing broken list.

Setting pointers to None prematurely.

To remove the node, link its previous node's next to its next node, and its next node's prev to its previous node.

5fill in blank

hard

Fill all three blanks to implement the put operation: add new node, update cache, and remove LRU if capacity exceeded.

Data Structures Theory

def put(key, value):
    if key in cache:
        node = cache[key]
        node.value = value
        access_key(key)
    else:
        new_node = Node(key, value)
        cache[[1]] = new_node
        add_to_front(new_node)
        if len(cache) > capacity:
            lru_key = tail.key
            remove_tail()
            del cache[[2]]
            # Optional: clear tail pointer
            tail = [3]

Drag options to blanks, or click blank then click option'

Akey

Blru_key

CNone

Dnew_node

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable names for keys.

Not deleting the LRU key from cache.

Not updating tail pointer after removal.

When adding a new node, store it in cache with the key. When removing LRU, delete the lru_key from cache and set tail to None if empty.