interview/LRUCache.java at master · jimit7patel/interview · GitHub

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.util.LinkedHashMap;
import java.util.Map;

// @include
public class LRUCache {
  LinkedHashMap<Integer, Integer> isbnToPrice;

  LRUCache(final int capacity) {
    this.isbnToPrice
        = new LinkedHashMap<Integer, Integer>(capacity, 1.0f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
              return this.size() > capacity;
            }
          };
  }

  public Integer lookup(Integer key) {
    if (!isbnToPrice.containsKey(key)) {
      return null;
    }
    return isbnToPrice.get(key);
  }

  public void insert(Integer key, Integer value) {
    // We add the value for key only if key is not present - we don't update
    // existing values.
    isbnToPrice.get(key);
    if (!isbnToPrice.containsKey(key)) {
      isbnToPrice.put(key, value);
    }
  }

  public Boolean erase(Object key) { return isbnToPrice.remove(key) != null; }
  // @exclude

  public static void main(String[] args) {
    final int CAPACITY = 2;
    LRUCache c = new LRUCache(CAPACITY);
    System.out.println("c.insert(1, 1)");
    c.insert(1, 1);
    System.out.println("c.insert(1, 10)");
    c.insert(1, 10);
    System.out.println("c.lookup(2, val)");
    assert(null == c.lookup(2));
    System.out.println("c.lookup(1, val)");
    assert(c.lookup(1) == 1);
    c.erase(1);
    assert(null == c.lookup(1));

    // test capacity constraints honored, also FIFO ordering
    c = new LRUCache(CAPACITY);
    c.insert(1, 1);
    c.insert(2, 1);
    c.insert(3, 1);
    c.insert(4, 1);
    assert(null == c.lookup(1));
    assert(null == c.lookup(2));
    assert(1 == c.lookup(3));
    assert(1 == c.lookup(4));

    // test retrieval moves to front
    c = new LRUCache(CAPACITY);
    c.insert(1, 1);
    c.insert(2, 1);
    c.insert(3, 1);
    c.lookup(2);
    c.insert(4, 1);
    assert(null == c.lookup(1));
    assert(1 == c.lookup(2));
    assert(null == c.lookup(3));
    assert(1 == c.lookup(4));

    // test update moves to front
    c = new LRUCache(CAPACITY);
    c.insert(1, 1);
    c.insert(2, 1);
    c.insert(3, 1);
    c.insert(2, 2);
    c.insert(4, 1);
    assert(null == c.lookup(1));
    assert(1 == c.lookup(2));
    assert(null == c.lookup(3));
    assert(1 == c.lookup(4));

    // test erase
    c = new LRUCache(CAPACITY);
    c.insert(1, 1);
    c.insert(2, 1);
    c.erase(2);
    c.insert(3, 3);
    assert(1 == c.lookup(1));
    assert(null == c.lookup(2));
    assert(3 == c.lookup(3));
  }
}