FilesExpand file tree

 master

/

lru-cache.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

132 lines (125 loc) · 4.14 KB

 master

/

lru-cache.java

Copy path

Top

File metadata and controls

• Code
• Blame

132 lines (125 loc) · 4.14 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

public class Solution {

class Node {

int key;

int val;

Node next;

Node pre;

Node(int key, int val) {

this.key = key;

this.val = val;

}

}

Node head;

Node tail;

Map<Integer, Node> map;

int capacity;

int size;

// Notes to be taken from this problem:

// Classic doubly linkedlist data structure, might be used in ohter problems.

// Find top K words in given article: min-heap solution!!!!

// TripAdvisor actual phone interview question.

// @param capacity, an integer

public Solution(int capacity) {

// write your code here

this.capacity = capacity;

this.size = 0;

map = new HashMap<Integer, Node>();

}

// @return an integer

public int get(int key) {

// write your code here

if (map.containsKey(key)) {

// update the node order in the queue

// then return the value

Node oldEntry = map.get(key);

int val = oldEntry.val;

// update the order of current node in the queue.

if (oldEntry == tail) {

// do nothing

} else if (oldEntry == head) {

// move head to tail

// cut the head and assign next as head

Node next = oldEntry.next;

oldEntry.next = null;

next.pre = null;

head = next;

// append previous head to tail

tail.next = oldEntry;

oldEntry.pre = tail;

tail = oldEntry;

} else {

// current node is in the middle.

Node next = oldEntry.next;

Node pre = oldEntry.pre;

next.pre = pre;

pre.next = next;

oldEntry.next = null;

oldEntry.pre = tail;

tail.next = oldEntry;

tail = oldEntry;

}

return val;

} else {

return -1;

}

}

// @param key, an integer

// @param value, an integer

// @return nothing

public void set(int key, int value) {

// write your code here

// first check if key exist, if so just update

// the value and order

// if not, perform insertion here: should check the

// capacity.

if (map.containsKey(key)) {

// update the existing record

Node oldEntry = map.get(key);

oldEntry.val = value;

// update the order in the queue.

get(key);

} else {

Node newEntry = new Node(key, value);

map.put(key, newEntry);

// first check the capacity

if (size >= capacity) {

// invalidate the LRU

// which node should be invalidated?

// both head and tail might work.

// Here we insert new values to tail,

// so that head node is the LRU node.

Node oldEntry = head;

int oldKey = oldEntry.key;

map.remove(oldKey);

if (oldEntry.next == null) {

// LRU is of capacity of one

head = newEntry;

tail = head;

} else {

// append new record in the tail

tail.next = newEntry;

newEntry.pre = tail;

tail = tail.next;

// remove head

Node newHead = head.next;

// is this line necessary?

head.next = null;

newHead.pre = null;

head = newHead;

}

} else {

// perform insertion

// append new record in the tail

if (head == null) {

head = newEntry;

tail = newEntry;

} else {

tail.next = newEntry;

newEntry.pre = tail;

tail = tail.next;

}

size++;

}

}

}

}