While working at your start-up company, you are assigned the job of improving the performance of the company web server. You notice that users frequently browse the same web pages at your site. Being smart, you realize you can speed up the performance of your web server by keeping the most frequently accessed web pages in a cache, which can be uploaded more quickly than pages stored in memory.
Your job is to set up the web server for a hundred web pages numbered from 1 to 100. As requests come in, you must decide which web page to keep in the cache. At the end you should report on the total number of requests and the number of requests which were supplied from the cache.
The problem you must face is your cache is small, and can hold only four web pages at a time. You must thus decide which pages to keep in the cache instead of memory. You decide to apply the ``least recently used'' (LRU) algorithm, where you throw out the web page which was used furthest in the past whenever space is needed to store a new web page.
The input will consist of a sequence of requests for web pages 1 to 100, each on a separate line. The sequence will be terminated by a line containing only -1.
For each web page request, display the contents of your web cache. Print on a single line the numbers of the web pages in your cache, from most recent to least recently used. You should print 0 for empty pages in your cache. When all requests have been served, output a line displaying the number of service requests satisfied from cache and the total number of requests, in the form ``X of Y requests found in cache".
Input:
1 2 1 -1
Output:
1 0 0 0 2 1 0 0 1 2 0 0 1 of 3 requests found in cache
Input:
1 5 21 44 8 21 8 5 -1
Output:
1 0 0 0 5 1 0 0 21 5 1 0 44 21 5 1 8 44 21 5 21 8 44 5 8 21 44 5 5 8 21 44 3 of 8 requests found in cache
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
Next: Finger-Friendly Domain Names Up: No Title Previous: Web Page Encryption
Chau-Wen Tseng