Uber Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
public class MyCache {
int _cacheSize;
int _curCacheSize;
Node _cacheStart;
Node _cacheEnd;
Map<Integer, Node> _map;
public MyCache(int cacheSize) {
_cacheSize = cacheSize;
_curCacheSize = 0;
_map = new HashMap<>();
}
public void get(int no) {
if (_map.containsKey(no)) {
System.out.println(no + " is already in cache");
Node n = removeNodeFromCache(_map.get(no));
addInCache(n);
} else if (_curCacheSize < _cacheSize) {
System.out.println(no + " is not in cache, Cache is not full");
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
} else {
System.out.println(no + " is not in cache, Cache is full, so remove " + _cacheEnd.no + " from cache");
_map.remove(_cacheEnd.no);
removeNodeFromCache(_cacheEnd);
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
}
}
private void addInCache(Node n) {
_curCacheSize++;
if (_cacheStart == null) {
_cacheStart = n;
_cacheEnd = n;
} else {
n.next = _cacheStart;
_cacheStart.pre = n;
_cacheStart = n;
}
}
private Node removeNodeFromCache(@NotNull Node n) {
_curCacheSize--;
if (_cacheSize == 0) {
_cacheStart = null;
_cacheEnd = null;
} else if (_cacheStart == n) {
_cacheStart = _cacheStart.next;
n.next = null;
} else if (_cacheEnd == n) {
_cacheEnd = _cacheEnd.pre;
n.pre = null;
} else {
n.pre.next = n.next;
n.next.pre = n.pre;
n.next = null;
n.pre = null;
}
return n;
}
}
class Node {
int no;
Node next;
Node pre;
public Node(int n) {
no = n;
next = null;
pre = null;
}
}
public class MyCache {
int _cacheSize;
int _curCacheSize;
Node _cacheStart;
Node _cacheEnd;
Map<Integer, Node> _map;
public MyCache(int cacheSize) {
_cacheSize = cacheSize;
_curCacheSize = 0;
_map = new HashMap<>();
}
public void get(int no) {
if (_map.containsKey(no)) {
System.out.println(no + " is already in cache");
Node n = removeNodeFromCache(_map.get(no));
addInCache(n);
} else if (_curCacheSize < _cacheSize) {
System.out.println(no + " is not in cache, Cache is not full");
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
} else {
System.out.println(no + " is not in cache, Cache is full, so remove " + _cacheEnd.no + " from cache");
_map.remove(_cacheEnd.no);
removeNodeFromCache(_cacheEnd);
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
}
}
private void addInCache(Node n) {
_curCacheSize++;
if (_cacheStart == null) {
_cacheStart = n;
_cacheEnd = n;
} else {
n.next = _cacheStart;
_cacheStart.pre = n;
_cacheStart = n;
}
}
private Node removeNodeFromCache(@NotNull Node n) {
_curCacheSize--;
if (_cacheSize == 0) {
_cacheStart = null;
_cacheEnd = null;
} else if (_cacheStart == n) {
_cacheStart = _cacheStart.next;
n.next = null;
} else if (_cacheEnd == n) {
_cacheEnd = _cacheEnd.pre;
n.pre = null;
} else {
n.pre.next = n.next;
n.next.pre = n.pre;
n.next = null;
n.pre = null;
}
return n;
}
}
class Node {
int no;
Node next;
Node pre;
public Node(int n) {
no = n;
next = null;
pre = null;
}
}
public class MyCache {
int _cacheSize;
int _curCacheSize;
Node _cacheStart;
Node _cacheEnd;
Map<Integer, Node> _map;
public MyCache(int cacheSize) {
_cacheSize = cacheSize;
_curCacheSize = 0;
_map = new HashMap<>();
}
public void get(int no) {
if (_map.containsKey(no)) {
System.out.println(no + " is already in cache");
Node n = removeNodeFromCache(_map.get(no));
addInCache(n);
} else if (_curCacheSize < _cacheSize) {
System.out.println(no + " is not in cache, Cache is not full");
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
} else {
System.out.println(no + " is not in cache, Cache is full, so remove " + _cacheEnd.no + " from cache");
_map.remove(_cacheEnd.no);
removeNodeFromCache(_cacheEnd);
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
}
}
private void addInCache(Node n) {
_curCacheSize++;
if (_cacheStart == null) {
_cacheStart = n;
_cacheEnd = n;
} else {
n.next = _cacheStart;
_cacheStart.pre = n;
_cacheStart = n;
}
}
private Node removeNodeFromCache(@NotNull Node n) {
_curCacheSize--;
if (_cacheSize == 0) {
_cacheStart = null;
_cacheEnd = null;
} else if (_cacheStart == n) {
_cacheStart = _cacheStart.next;
n.next = null;
} else if (_cacheEnd == n) {
_cacheEnd = _cacheEnd.pre;
n.pre = null;
} else {
n.pre.next = n.next;
n.next.pre = n.pre;
n.next = null;
n.pre = null;
}
return n;
}
}
class Node {
int no;
Node next;
Node pre;
public Node(int n) {
no = n;
next = null;
pre = null;
}
}
public class MyCache {
int _cacheSize;
int _curCacheSize;
Node _cacheStart;
Node _cacheEnd;
Map<Integer, Node> _map;
public MyCache(int cacheSize) {
_cacheSize = cacheSize;
_curCacheSize = 0;
_map = new HashMap<>();
}
public void get(int no) {
if (_map.containsKey(no)) {
System.out.println(no + " is already in cache");
Node n = removeNodeFromCache(_map.get(no));
addInCache(n);
} else if (_curCacheSize < _cacheSize) {
System.out.println(no + " is not in cache, Cache is not full");
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
} else {
System.out.println(no + " is not in cache, Cache is full, so remove " + _cacheEnd.no + " from cache");
_map.remove(_cacheEnd.no);
removeNodeFromCache(_cacheEnd);
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
}
}
private void addInCache(Node n) {
_curCacheSize++;
if (_cacheStart == null) {
_cacheStart = n;
_cacheEnd = n;
} else {
n.next = _cacheStart;
_cacheStart.pre = n;
_cacheStart = n;
}
}
private Node removeNodeFromCache(@NotNull Node n) {
_curCacheSize--;
if (_cacheSize == 0) {
_cacheStart = null;
_cacheEnd = null;
} else if (_cacheStart == n) {
_cacheStart = _cacheStart.next;
n.next = null;
} else if (_cacheEnd == n) {
_cacheEnd = _cacheEnd.pre;
n.pre = null;
} else {
n.pre.next = n.next;
n.next.pre = n.pre;
n.next = null;
n.pre = null;
}
return n;
}
}
class Node {
int no;
Node next;
Node pre;
public Node(int n) {
no = n;
next = null;
pre = null;
}
}
public class MyCache {
int _cacheSize;
int _curCacheSize;
Node _cacheStart;
Node _cacheEnd;
Map<Integer, Node> _map;
public MyCache(int cacheSize) {
_cacheSize = cacheSize;
_curCacheSize = 0;
_map = new HashMap<>();
}
public void get(int no) {
if (_map.containsKey(no)) {
System.out.println(no + " is already in cache");
Node n = removeNodeFromCache(_map.get(no));
addInCache(n);
} else if (_curCacheSize < _cacheSize) {
System.out.println(no + " is not in cache, Cache is not full");
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
} else {
System.out.println(no + " is not in cache, Cache is full, so remove " + _cacheEnd.no + " from cache");
_map.remove(_cacheEnd.no);
removeNodeFromCache(_cacheEnd);
Node n = new Node(no);
addInCache(n);
_map.put(no, n);
}
}
private void addInCache(Node n) {
_curCacheSize++;
if (_cacheStart == null) {
_cacheStart = n;
_cacheEnd = n;
} else {
n.next = _cacheStart;
_cacheStart.pre = n;
_cacheStart = n;
}
}
private Node removeNodeFromCache(@NotNull Node n) {
_curCacheSize--;
if (_cacheSize == 0) {
_cacheStart = null;
_cacheEnd = null;
} else if (_cacheStart == n) {
_cacheStart = _cacheStart.next;
n.next = null;
} else if (_cacheEnd == n) {
_cacheEnd = _cacheEnd.pre;
n.pre = null;
} else {
n.pre.next = n.next;
n.next.pre = n.pre;
n.next = null;
n.pre = null;
}
return n;
}
}
class Node {
int no;
Node next;
Node pre;
public Node(int n) {
no = n;
next = null;
pre = null;
}
}
1. Use HashMap to store Key Node -> Values pairs.
2. Use LinkedList to maintain the order of usage of these key nodes in the HashMap.
3. Whenever a Key is read or written, put it at the end of the LinkedList.
4. Whenever you need space in cache, remove from LinkedList head and remove these nodes from HashMap as well.
Looks like a duplicate of id=5747511056662528. You may use bidirectional map or some custom searchable heap (google for "Heap structured search trees").
- celicom May 06, 2016