LRU cache design with hash map and doubly linked list in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does LRU stand for in LRU cache?

LRU stands for Least Recently Used. It is a cache eviction policy that removes the least recently accessed item when the cache is full.

beginner

Why is a hash map used in an LRU cache design?

A hash map provides fast access to cache items by their keys, allowing O(1) average time complexity for lookups.

intermediate

What role does a doubly linked list play in an LRU cache?

The doubly linked list keeps track of the order of item usage. The most recently used item is moved to the front, and the least recently used item is at the end, enabling quick removal.

intermediate

How do the hash map and doubly linked list work together in an LRU cache?

The hash map stores keys and pointers to nodes in the doubly linked list. This allows quick access and updates of the usage order when items are accessed or added.

beginner

What happens when the LRU cache reaches its capacity and a new item is added?

The least recently used item (at the end of the doubly linked list) is removed from both the list and the hash map to make space for the new item, which is added to the front.

What is the main purpose of using a doubly linked list in an LRU cache?

A To track the order of item usage for quick eviction

B To store cache keys in sorted order

C To speed up hash map lookups

D To reduce memory usage

The doubly linked list tracks the order of usage, allowing quick updates when items are accessed or evicted.

Which data structure provides O(1) average time complexity for key lookups in an LRU cache?

A Hash map

B Doubly linked list

C Array

D Stack

A hash map allows fast key lookups, which is essential for efficient cache access.

When an item is accessed in an LRU cache, what happens to its position in the doubly linked list?

A It stays in the same place

B It moves to the front

C It moves to the end

D It is removed

Accessed items are moved to the front to mark them as most recently used.

What is removed from the cache when it reaches capacity and a new item is added?

A Most recently used item

B Random item

C All items

D Least recently used item

The least recently used item is removed to make space for the new item.

Which two data structures are combined to implement an efficient LRU cache?

A Array and linked list

B Stack and queue

C Hash map and doubly linked list

D Binary tree and hash map

A hash map and doubly linked list together provide fast access and efficient order tracking.

Explain how a hash map and a doubly linked list work together to implement an LRU cache.

Think about fast access and order management.

Describe the process that happens when the LRU cache is full and a new item needs to be added.

Focus on eviction and insertion steps.