Google Interview Question : Design a cache replacement policy for a hard-disk if the stream of sector requests is already known

Problem statement: You are given a hard-disk with large number of sectors say $ N $ and that has a facility to store $ k $-sectors in cache such that read time for cache is very less compared to the time to read sector from a hard-disk and $ N >> k $. Assume the seek time is negligible compared to read-time. You are given a stream of requests $ s_i \text{ such that } 0 <= i <= R, k << R << N $.