AlgoViz
HomeGreedy

Program for Least Recently Used (LRU) Page Replacement Algorithm

Medium

Evict the page unused for longest

Problem

Simulate LRU page replacement: given a page reference stream and a frame capacity, count the number of page faults.

In simple words

Keep recent pages; when full, kick out the one used longest ago.

The idea

Keep the pages currently in frames along with their last use time. On a miss with no free frame, evict the page whose last use is oldest and count a page fault. It is a direct simulation, so the only design question is how quickly you can find that oldest page.

The trick

  • A hash map plus a doubly linked list makes each step O(1).
  • Count a fault on every miss, including the initial fills.
  • A hit still updates the recency.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

7
0
1
2
0
3
0
4
0
1
2
3
4
5
6
7

Step 1 of 2. Here's the example — pages=[7,0,1,2,0,3,0,4], capacity=4 Values: 7, 0, 1, 2, 0, 3, 0, 4.

1/2
Optimal
timeO(n)spaceO(capacity)
1cache = ordered set2for page in pages:3  if page not in cache: fault++; if full: evict least-recently-used4  mark page as most-recently-used

Input

array
[7, 0, 1, 2, 0, 3, 0, 4]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
pages=[7,0,1,2,0,3,0,4], capacity=4
Output:
6

Practice this problem:LeetCode(opens in a new tab)GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.