Design (Algo)
Binary Search Tree Iterator
very important, should be pretty familiar with that. Use stack to store all the elements from root to the current element.
private Deque<TreeNode> stack = new LinkedList<>();
public BSTIterator(TreeNode root) {
while (root != null) {
stack.push(root);
root = root.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode cur = stack.peek(); // return the current node...
TreeNode node = cur;
// move to the next node
if (node.right == null) {
node = stack.pop();
// need to consider one case that is current node is the right child...
// we need to pop parent child ...
while (!stack.isEmpty() && stack.peek().right == node) {
node = stack.pop();
}
} else {
node = node.right;
while (node != null) {
stack.push(node);
node = node.left;
}
}
return cur;
}
Flatten Nested List Iterator
note that we need to use stack to store list of NestedInteger.
Deque<NestedInteger> stack;
public NestedIterator(List<NestedInteger> nestedList) {
stack = new LinkedList<>();
pushListToStack(nestedList);
}
private void pushListToStack(List<NestedInteger> nestedList) {
Deque<NestedInteger> temp = new LinkedList<>();
for (NestedInteger nest : nestedList) {
temp.push(nest);
}
while (!temp.isEmpty()) {
stack.push(temp.pop());
}
}
@Override
public Integer next() {
if (!hasNext()) {
return null;
}
return stack.pop().getInteger();
}
@Override
public boolean hasNext() {
while (!stack.isEmpty() && !stack.peek().isInteger()) {
pushListToStack(stack.pop().getList());
}
return !stack.isEmpty();
}
Flatten 2D vector
note that, here, we need to use two stack, one is used for storing list of integers, while the other is used for storing integers.
Deque<List<Integer>> stack = new LinkedList<>(); // store the list of integer in the stack
Deque<Integer> stackj;
public Vector2D(List<List<Integer>> vec2d) {
pushListListToStack(vec2d);
stackj = new LinkedList<>();
}
void pushListListToStack(List<List<Integer>> vec2d) {
Deque<List<Integer>> temp = new LinkedList<>();
for (List<Integer> nested : vec2d) {
temp.push(nested);
}
while (!temp.isEmpty()) {
stack.push(temp.pop());
}
}
void pushListToStack(List<Integer> vec) {
Deque<Integer> temp = new LinkedList<>();
for (Integer nested : vec) {
temp.push(nested);
}
while (!temp.isEmpty()) {
stackj.push(temp.pop());
}
}
@Override
public Integer next() {
if (!hasNext()) {
return null;
}
return stackj.pop();
}
@Override
public boolean hasNext() {
while (stackj.isEmpty() && !stack.isEmpty()) {
pushListToStack(stack.pop());
}
return !stackj.isEmpty();
}
LRU
Least Recently Used cache, which evict least recently used entry. As cache purpose is to provide fast and efficient way of retrieving data. it need to meet certain requirement.
requirements:
- Fixed Size: cache needs to have some bounds to limit memory usages.
- Fast Access: cache insert and lookup operation should be fast, preferably O(1) time. /// hashmap
- Replacement of Entry in case, memory limit is reached. //
when we think about O(1) lookup, we prefer using hashmap data structure, since it provides O(1) insertion and lookup. But hashmap does not has mechanism of tracking which entry has been queried recently and which not. To track this, we need to require another data structure like Doubly LinkedList, which can provide fast insertion, deletion and updation.
Then how to track the recently used entry?
We will remove element from head and add element on the tail of LinkedList and whenever any entry is accessed. so that recently used entries will be on tail and Least used will be on head.
for the get operation, what step we need to take?
- if not found, return -1 directly.
- remove the current node
- move it to the tail of linked list
for the set operation, what step we need to take?
- if found, set the value and return directly.
- check the capacity of cache
- insert the new node to the tail.
class LRUCache {
private class Node{
Node prev;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
private int capacity;
private HashMap<Integer, Node> hs = new HashMap<>(); // store the key value pair
private Node head = new Node(-1, -1);
private Node tail = new Node(-1, -1);
public LRUCache(int capacity) {
this.capacity = capacity;
tail.prev = head;
head.next = tail;
}
public int get(int key) {
if (!hs.containsKey(key)) {
return -1;
}
// remove current
Node current = hs.get(key);
current.prev.next = current.next;
current.next.prev = current.prev;
// move current to tail
move_to_tail(current);
return hs.get(key).value;
}
public void put(int key, int value) {
if (get(key) != -1) { // if not found, return -1 directly.
hs.get(key).value = value;
return;
}
if (hs.size() == capacity) {
hs.remove(head.next.key); // remove head.next node,
head.next = head.next.next;
head.next.prev = head;
}
Node insert = new Node(key, value);
hs.put(key, insert);
move_to_tail(insert);
}
private void move_to_tail(Node current) { // first prev, then next
current.prev = tail.prev;
tail.prev = current;
current.prev.next = current;
current.next = tail;
}
}
another method is to use LinkedHashMap in java
note that we need to override the removeEldestEntry() to tell java when to remove eldest entry.
import java.util.LinkedHashMap;
public class LRUCache {
private Map<Integer, Integer> map;
public LRUCache(int capacity) {
map = new LinkedCappedHashMap<>(capacity);
}
public int get(int key) {
if(!map.containsKey(key)) { return -1; }
return map.get(key);
}
public void put(int key, int value) {
map.put(key,value);
}
private static class LinkedCappedHashMap<K,V> extends LinkedHashMap<K,V> {
int maximumCapacity;
LinkedCappedHashMap(int maximumCapacity) {
super(16, 0.75f, true);
this.maximumCapacity = maximumCapacity;
}
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > maximumCapacity; // size() is the Collections method.
}
}
}