Rs
Data Structures for Interviews
Module 4Interview Patterns LabLesson 22 of 2328 min

Lab: LRU Cache Sketch (HashMap + order)

Interview favorite: O(1) get/put mental model; implement a simple O(n) version then discuss O(1).

LRU idea

  • HashMap: key → value
  • Need order of use: VecDeque of keys (simple O(n) move-to-end) or linked list + map for O(1)

This lab

Implement a small-capacity cache with HashMap + VecDeque keys list:

  • get: if hit, move key to back (most recent), return value

-put: update/insert; if over capacity, pop_front (least recent) and remove from map

Discuss in comments how a doubly linked list upgrades this to O(1).

Challenge

Explain in a println why LinkedList+HashMap is O(1) vs VecDeque position scan.

Tips
  • HashMap + order list
  • Evict front
  • O(1) needs linked list nodes

Try it live

Lab: LRU Cache Sketch (HashMap + order)Rust 2021
Loading editor…
Output
Press Run to compile and execute.