Clock Algorithm Second-Chance

Problem

Count page faults under the clock (second-chance) replacement algorithm.

pages is the reference string and capacity is the number of frames. Each frame has a reference bit set on a hit or load; the clock hand clears bits as it sweeps, and the first frame with a cleared bit (or an empty frame) is replaced.

Return the number of faults. A non-positive capacity faults on every reference.

Hint

A hit only sets the reference bit; the hand does the eviction work later.

Test cases

case 1

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

expected: 9

case 2

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

expected: 3

case 3

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

expected: 3

case 4

in: [[7],1]

expected: 1

case 5

in: [[],2]

expected: 0

Starter codePython

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

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