LRU Cache (LeetCode Data Structure)

Question: Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Idea: Use a bi-directional linked list to store the inserted data. At the same time use a hashmap<key, node> to achieve O(1) access. Whenever a key is visited or modified, move it out of the bi-directional linked list, then insert it to the tail of the list. Whenever an insertion is required and the capacity is full, remove the node at the head.

Time: O(1) Space: O(n)

Code:

 public class LRUCache {  
   class Node{  
     int key;  
     int val;  
     Node prev;  
     Node next;  
     public Node(int key,int val)  
     {  
       this.key=key;  
       this.val=val;  
       this.prev=null;  
       this.next=null;  
     }  
   }  
   public int capacity;  
   public HashMap<Integer,Node> keyToNode;  
   public Node head;  
   public Node tail;  
   public LRUCache(int capacity) {  
     this.capacity=capacity;  
     keyToNode=new HashMap<Integer,Node>();  
     head=new Node(-1,-1);  
     tail=new Node(-1,-1);  
     head.next=tail;  
     tail.prev=head;  
   }  
   public int get(int key) {  
     if(keyToNode.containsKey(key)==false)  
       return -1;  
     Node tmp=keyToNode.get(key);  
     tmp.prev.next=tmp.next;  
     tmp.next.prev=tmp.prev;  
     moveToTail(tmp);  
     return keyToNode.get(key).val;  
   }  
   public void set(int key, int value) {  
     if(get(key)!=-1)  
     {  
       keyToNode.get(key).val=value;  
       return;  
     }  
     if(keyToNode.size()==capacity)  
     {  
       keyToNode.remove(head.next.key);  
       head.next=head.next.next;  
       head.next.prev=head;  
     }  
     Node newNode=new Node(key,value);  
     keyToNode.put(key,newNode);  
     moveToTail(newNode);  
   }  
   public void moveToTail(Node cur)  
   {  
     cur.prev=tail.prev;  
     tail.prev=cur;  
     cur.prev.next=cur;  
     cur.next=tail;  
   }  
 }  

Min Stack (LeetCode Data Structure)

Question: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Idea: Use two stacks. One stack (valStack) is a normal stack to store the values. The other stack (minStack) only pushes the minimum values until now and only pops if the popped value from valStack equals the top of the minStack.
For example: input 5, 3,9, 1, 1, 2
Push:
valStack:   5,  3,   9,            1, 1, 2
minStack:  5,  3,  not push, 1, 1, not push
Pop:
valStack:            2,  1,  1,  9,     3,  5
minStack:not pop,   1,  1, not,   3,  5
So we can see the minStack pushes only if the new input is smaller than its top and only pops if the value popped from the valStack equals the top of the minStack.

Time: O(1) Space: O(n) (we used an extra stack)

Code:

 class MinStack {  
   Stack<Integer> minStack=new Stack<Integer>();  
   Stack<Integer> valStack=new Stack<Integer>();  
   public void push(int x) {  
     if(minStack.isEmpty()||x<=minStack.peek())  
       minStack.push(x);  
     valStack.push(x);  
   }  
   public void pop() {  
     if(valStack.isEmpty())  
       return;  
     int val=valStack.pop();  
     if(val==minStack.peek())  
       minStack.pop();  
   }  
   public int top() {  
     if(valStack.isEmpty())  
       return -1;  
     return valStack.peek();  
   }  
   public int getMin() {  
     if(minStack.isEmpty())  
       return Integer.MAX_VALUE;  
     return minStack.peek();  
   }  
 }  

Read N Characters Given Read4 II - Call multiple times (LeetCode String)

Question: The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note:
The read function may be called multiple times.

Idea: The problem statement is not quite clear. The note "the read function may be called multiple times" means the current read() may continue fro the middle of a read4() done in the last read()
For example:
First read(), read 3 characters from 15 characters original data
1): read4(), but we only need 3, so we have the fourth character read by not assigned to the destination.

Second read(): read 6 characters from the same data
1)now we can only read 1, since the forth character has been read by the first read(), we need to first use this character read in the first read() but not assigned.
2) continue to repeat read4() until we meet the 6 characters requirement.

If the problem is understood clearly, we can design the algorithm as following:
1) use a char[] to cache the characters read in the last time
2) use a pointer "offset" to point to the end of the last read()
3) if there are some characters left in the last read(), we first copy these characters to the destination buf[].
4) continue with the rest of reading by using read4().

Time: O(n) Space: O(1)

Code:

 public class Solution extends Reader4 {  
   /**  
    * @param buf Destination buffer  
    * @param n  Maximum number of characters to read  
    * @return  The number of characters read  
    */  
    char[] buffer=new char[4];  
    int offset=0,bufSize=0;  
   public int read(char[] buf, int n) {  
     int readBytes=0;  
     boolean eof=false;  
     while(readBytes<n&&eof==false)  
     {  
       if(bufSize==0)  
       {  
         bufSize=read4(buffer);  
         if(bufSize<4)  
           eof=true;  
       }  
       int actuallyRead=Math.min(n-readBytes,bufSize);  
       for(int i=0;i<actuallyRead;i++)  
         buf[readBytes+i]=buffer[offset+i];  
       offset=(offset+actuallyRead)%4;  
       bufSize-=actuallyRead;  
       readBytes+=actuallyRead;  
     }  
     return readBytes;  
   }  
 }  

Read N Characters Given Read4 (LeetCode String)

Question: The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note:
The read function will only be called once for each test case.

Idea: With two simple examples, we can understand this problem easily.
Example 1:  read 15 characters from a buffer with only 11 characters.
Run 1: read 4 characters
Run 2: read 4
Run 3: can only read 3, since there are only 3 characters left in the original data.

Example 2: read 15 characters from a buffer with 20 characters.
Run 1: read 4
Run 2: read 4
Run 3: read 4
Run 4: read 4, but only assign the first 3 to the destination buf[], since we only need to read 3 characters in this run.

So the characters read at the each run = Math.min(original data length - read in former runs==read4(buf), n-read in former runs).

Time: O(n) Space: O(1)

Code:

 /* The read4 API is defined in the parent class Reader4.  
    int read4(char[] buf); */  
 public class Solution extends Reader4 {  
   /**  
    * @param buf Destination buffer  
    * @param n  Maximum number of characters to read  
    * @return  The number of characters read  
    */  
   public int read(char[] buf, int n) {  
     int readBytes=0;  
     boolean eof=false;  
     while(readBytes<n&&eof==false)  
     {  
       char[] buffer=new char[4];  
       int read4Result=read4(buffer);  
       if(read4Result<4)  
         eof=true;  
       int actuallyRead=Math.min(n-readBytes,read4Result);  
       for(int i=0;i<actuallyRead;i++)  
         buf[readBytes+i]=buffer[i];  
       readBytes+=actuallyRead;  
     }  
     return readBytes;  
   }  
 }  

Binary Search Tree Iterator (LeetCode Data Structure)

Question: Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Idea: The question requires average O(1) time and O(h) memory. So we can not either traverse the tree when next() and hasNext() are called for the least memory usage (O(n) time, O(1) space), nor store the whole tree in an ArrayList for fast access (O(1) time, O(n) space). We need some tradeoff between these two methods.

The idea is to only store one part of the tree. Whenever a tree node "current" is given, the first returned value when next() is called is the most left number of the tree. However, the next value of next() is in "current"'s right subtree.

So the algorithm is clear. When the root is given (constructor), we push its left subtree with only left children into the stack. When next() is called, pop the current value and push the right substree into the stack.

Time: O(1) on average Space: O(h)

Code: 

 public class BSTIterator {  
   private Stack<TreeNode> stack=new Stack<TreeNode>();  
   public BSTIterator(TreeNode root) {  
     pushToStack(root);  
   }  
   /** @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.pop();  
     pushToStack(cur.right);  
     return cur.val;  
   }  
   private void pushToStack(TreeNode root)  
   {  
     while(root!=null)  
     {  
       stack.push(root);  
       root=root.left;  
     }  
   }  
 }  

Two Sum III - Data structure design (LeetCode HashMap)

Question:  Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Idea: Since duplicate insertion is allowed, e.g. "add(4) add(4) find(8) = true, but add(4) find(8) =false", we need to count the times of insertion of each inserted value. I used a Hashmap <value, inserted times> to store the inserted numbers. If a desired pair is found, check if the HashMap has enough number of insertions, otherwise "continue".

Time: O(1) for add. O(n) for find. Space: O(n)

Discussion: To use less space, I design the algorithm as Time O(1) for add and Time O(n) for find. If we need Time O(1) for find, we can add another HashSet to store the possible sums whenever a new number is inserted. Therefore it will be Time O(n) for add, Time O(1) for find, and Space is O(n^2).

Code:

 public class TwoSum {  
   private HashMap<Integer,Integer> elements=new HashMap<Integer,Integer>();  
      public void add(int number) {  
        if(elements.containsKey(number))  
        {  
          elements.put(number,elements.get(number)+1);  
        }  
        else  
        {  
          elements.put(number,1);  
        }  
      }  
      public boolean find(int value) {  
        for(Integer i:elements.keySet())  
        {  
          int needed=value-i;  
          if(elements.containsKey(needed))  
          {  
            if(i==needed&&elements.get(needed)<2)  
            {  
              continue;  
            }  
            return true;  
          }  
        }  
        return false;  
      }  
 }