Browser Caching

Description:
When you browse the Internet, browser usually caches some documents to reduce the time cost of fetching them from remote servers. Let’s consider a simplified caching problem. Assume the size of browser’s cache can store M pages. When user visits some URL, browser will search it in the cache first. If the page is already cached browser will fetch it from the cache, otherwise browser will fetch it from the Internet and store it in the cache. When the cache is full and browser need to store a new page, the least recently visited page will be discarded.

Now, given a user’s browsing history please tell us where did browser fetch the pages, from the cache or the Internet? At the beginning browser’s cache is empty.

Input:
Line 1: Two integers N(1 <= N <= 20000) and M(1 <= M <= 5000). N is the number of pages visited and M is the cache size.

Line 2~N+1: Each line contains a string consisting of no more than 30 lower letters, digits and dots(‘.’) which is the URL of the page. Different URLs always lead to different pages. For example www.bing.com and bing.com are considered as different pages by browser.

Output:
Line 1~N: For each URL in the input, output “Cache” or “Internet”.

Tips:
Pages in the cache before visiting 1st URL [null, null]

Pages in the cache before visiting 2nd URL [www.bing.com(1), null]

Pages in the cache before visiting 3rd URL [www.bing.com(1), www.microsoft.com(2)]

Pages in the cache before visiting 4th URL [www.bing.com(1), www.microsoft.com(3)]

Pages in the cache before visiting 5th URL [windows.microsoft.com(4), www.microsoft.com(3)]

The number in parentheses is the last visiting timestamp of the page.

Sample input:
5 2
www.bing.com
www.microsoft.com
www.microsoft.com
windows.microsoft.com
www.bing.com

Sample output:
Internet
Internet
Cache
Internet
Internet

分析：

  容易题，没有用到什么算法，就是简单的实现题。最主要的是要清楚“Least Recently Used”，它的优先级定义是“时间”，而不是“次数”。即最近使用的优先级高，而不是使用的次数越多优先级越高。

思路：

  1. 首先查找缓存中是否已有要访问的url，如果有就设置isCached = true; 并输出Cache，否则继续下面步骤。
  2. 如果没有缓存，就需要缓存当前url。首先，判断当前缓存是否已满。
    • 如果缓存未满，就把当前url直接放到缓存的下一个位置。
    • 如果缓存已满，就遍历缓存，根据“Least Recently Used”更新缓存。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    string url;
    bool isCached = false;
    int currPos = 0;
    int n, m;
    cin >> n >> m;
    getchar();
    vector<string> cache(m, "");
    vector<int> urlLeastUsedTime(m, 0);

    for (int i = 0; i < n; i++) {
        cin >> url;
        getchar();
        //getline(cin, url);
        //cout << "url:" << url << endl;

        for (int j = 0; j < m; j++) {
            if (cache[j] == url) {
                urlLeastUsedTime[j] = i;
                isCached = true;
                printf("Cache\n");
            }
        }
        if (!isCached) {
            if (currPos >= m) {
                int leastUsed = urlLeastUsedTime[0];
                int leastUsedIndex = 0;
                for (int j = 1; j < m; j++) {
                    if (leastUsed > urlLeastUsedTime[j]) {
                        leastUsed = urlLeastUsedTime[j];
                        leastUsedIndex = j;
                    }
                }

                cache[leastUsedIndex] = url;
                urlLeastUsedTime[leastUsedIndex] = i;
            }
            else {
                cache[currPos] = url;
                urlLeastUsedTime[currPos] = i;
                currPos++;
            }
            printf("Internet\n");
        }
        isCached = false;
    }

    //system("pause");
    return 0;
}