Design a cache replacement policy for a hard-disk if the stream of sector requests is already known : Solution 1

Problem statement is here.

For the first requests, all the sectors are cached. For every request , we have sectors to put in cache location. To discard one of the sectors, we can give weight to every sector which is equal to the difference between the index of next request for that sector and the index of the current request. So if the next request for sector is appearing at index then the weight of that sector is . Choose the sectors with the minimum weight.

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 and that has a facility to store -sectors in cache such that read time for cache is very less compared to the time to read sector from a hard-disk and . Assume the seek time is negligible compared to read-time. You are given a stream of requests .