LRU Page Replacement

Problem

Simulate least-recently-used page replacement and return the total number of page faults.

Keep frames ordered from least to most recently used: a hit moves the page to the back, and a fault evicts the front page when all frames are full. An empty request sequence produces no faults.

Hint

Removing and re-appending on a hit keeps the most recently used page at the back.

Test cases

case 1

in: [[1,2,3,1,4,1,2,3,4],3]

expected: 7

case 2

in: [[1,2,1,2,1,2],2]

expected: 2

case 3

in: [[1,1,1],1]

expected: 1

case 4

in: [[],3]

expected: 0

case 5

in: [[1,2,3,4],4]

expected: 4

case 6

in: [[1,2,3,4,1,2],4]

expected: 4

Starter codePython

def lru_page_faults(pages, capacity):
    # Your code here
    pass

6 test cases · run your code against them in the editor