Leetcode Object Oriented Programming System Questions

Photo by Jonathan Petersson on Unsplash

I don’t really know how to term this category of questions so i will just call them ‘systems questions’.

208. Implement Trie (Prefix Tree)

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

// Each Trie object holds a single char and links to subsequent chars (children)...
class Trie {

    // using map we can extend our solution to other english characters apart from lowercase
    public Map<Character, Trie> children;
    public Character curr;
    // denotes if current character marks end of word
    public boolean isWord = false;
    public Trie() {
        children = new HashMap<>();
        // dummy character for root trie
        curr = '-';
    }

    public Trie(Character curr) {
        children = new HashMap<>();
        this.curr = curr;
    }
    
    public void insert(String word) {
        // traversal is  similar to linked list but next node is 
//determined by characters of word
        Trie temp = this;
        for(char ch: word.toCharArray()){
            temp.children.putIfAbsent(ch, new Trie(ch));
            temp = temp.children.get(ch);
        }
// for word we assign last character trie's isWord property to be true
        temp.isWord=true; // temp is not pointing to last char of word
    }
    
    public boolean search(String word) {
        // traversal is similar to linked list but next node is 
//determined by characters of word
        Trie temp = this;
        for(char ch: word.toCharArray()){
            if(!temp.children.containsKey(ch)){
                return false;
            }
            temp = temp.children.get(ch);
        }
// for word it is necessary for isWord property to be true
        return temp.isWord; // end of word...check if it is indeed true
    }
    
    public boolean startsWith(String prefix) {
// traverse similar to linked list but next node is 
//determined by characters of word
        Trie temp = this;
        for(char ch: prefix.toCharArray()){
            if(!temp.children.containsKey(ch)){
                return false;
            }
            temp = temp.children.get(ch);
        }
// for prefix it is not necessary for isWord property to be true
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Create a Trie class for each character in the word. Similar to linked list.

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

When i first read this question, i thought that i had to use a list…

class MinStack {
    
    private Stack<int[]> stack = new Stack<>();
    
    public MinStack() { }
    
    
    public void push(int x) {
        
        /* If the stack is empty, then the min value
         * must just be the first value we add. */
        if (stack.isEmpty()) {
            stack.push(new int[]{x, x});
            return;
        }
        
        int currentMin = stack.peek()[1];
        stack.push(new int[]{x, Math.min(x, currentMin)});
    }
    
    
    public void pop() {
        stack.pop();
    }
    
    
    public int top() {
        return stack.peek()[0];
    }
    
    
    public int getMin() {
        return stack.peek()[1];
    }
}

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<int[]> minStack = new Stack<>();
    
    public MinStack() { }
    
    
    public void push(int x) {
        
        // We always put the number onto the main stack.
        stack.push(x);
        
        // If the min stack is empty, or this number is smaller than
        // the top of the min stack, put it on with a count of 1.
        if (minStack.isEmpty() || x < minStack.peek()[0]) {
            minStack.push(new int[]{x, 1});
        }
        
        // Else if this number is equal to what's currently at the top
        // of the min stack, then increment the count at the top by 1.
        else if (x == minStack.peek()[0]) {
            minStack.peek()[1]++;
        }
    }
    
    
    public void pop() {
        
        // If the top of min stack is the same as the top of stack
        // then we need to decrement the count at the top by 1.
        if (stack.peek().equals(minStack.peek()[0])) {
            minStack.peek()[1]--;
        }
        
        // If the count at the top of min stack is now 0, then remove
        // that value as we're done with it.
        if (minStack.peek()[1] == 0) {
            minStack.pop();
        }
        
        // And like before, pop the top of the main stack.
        stack.pop();
    }
    
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek()[0];
    }
}

716. Max Stack (premium hard)

Design a max stack data structure that supports the stack operations and supports finding the stack’s maximum element.

Implement the MaxStack class:

• MaxStack() Initializes the stack object.
• void push(int x) Pushes element x onto the stack.
• int pop() Removes the element on top of the stack and returns it.
• int top() Gets the element on the top of the stack without removing it.
• int peekMax() Retrieves the maximum element in the stack without removing it.
• int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

You must come up with a solution that supports O(1) for each top call and O(logn) for each other call.

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

Constraints:

• -107 <= x <= 107
• At most 105 calls will be made to push, pop, top, peekMax, and popMax.
• There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

I guess the challenging part is having to popMax(). So need to dig through stack and remove the max.

class MaxStack {
    private TreeSet<int[]> stack; // store all the int sorted by order of insert
    private TreeSet<int[]> values; // store all the int sorted by value
    private int cnt;
    public MaxStack() {
        Comparator<int[]> comp = (a, b) -> {
            return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
        }; // sort by val in position 0 by default, otherwise position 1
        stack = new TreeSet<>(comp);
        values = new TreeSet<>(comp);
        cnt = 0;
    }
    public void push(int x) {
        stack.add(new int[] { cnt, x });
        values.add(new int[] { x, cnt });
        cnt++;
    }
    public int pop() {
        int[] pair = stack.pollLast();
        values.remove(new int[] { pair[1], pair[0] });
        return pair[1];
    }
    public int top() {
        return stack.last()[1];
    }
    public int peekMax() {
        return values.last()[0];
    }
    public int popMax() {
        int[] pair = values.pollLast();
        stack.remove(new int[] { pair[1], pair[0] });
        return pair[0];
    }
}

class MaxStack {
    TreeSet<int[]> orderStack = new TreeSet<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    TreeSet<int[]> valueStack = new TreeSet<>((a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
    
    int order;

    public MaxStack() {
        order = 0;
    }
    
    public void push(int x) {
        int[] item = new int[]{order, x};
        orderStack.add(item);
        valueStack.add(item);
        order++;
    }
    
    public int pop() {
        int[] toRemove = orderStack.pollLast();
        valueStack.remove(toRemove);
        return toRemove[1];
    }
    
    public int top() {  
        int[] toPeek = orderStack.last();
        return toPeek[1];
    }
    
    public int peekMax() {
        int[] toPeekMax = valueStack.last();
        return toPeekMax[1];
    }
    
    public int popMax() {
        int[] toRemoveMax = valueStack.pollLast();
        orderStack.remove(toRemoveMax);
        return toRemoveMax[1];
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */

1381. Design a Stack With Increment Operation

Design a stack that supports increment operations on its elements.

Implement the CustomStack class:

• CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack.
• void push(int x) Adds x to the top of the stack if the stack has not reached the maxSize.
• int pop() Pops and returns the top of the stack or -1 if the stack is empty.
• void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack stk = new CustomStack(3); // Stack is Empty []
stk.push(1);                          // stack becomes [1]
stk.push(2);                          // stack becomes [1, 2]
stk.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
stk.push(2);                          // stack becomes [1, 2]
stk.push(3);                          // stack becomes [1, 2, 3]
stk.push(4);                          // stack still [1, 2, 3], Do not add another elements as size is 4
stk.increment(5, 100);                // stack becomes [101, 102, 103]
stk.increment(2, 100);                // stack becomes [201, 202, 103]
stk.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
stk.pop();                            // return 202 --> Return top of the stack 202, stack becomes [201]
stk.pop();                            // return 201 --> Return top of the stack 201, stack becomes []
stk.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

• 1 <= maxSize, x, k <= 1000
• 0 <= val <= 100
• At most 1000 calls will be made to each method of increment, push and pop each separately.

class CustomStack {

    int[] stack;
    int index;
    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        Arrays.fill(stack, -1);
        index = 0;
    }
    
    public void push(int x) {
        if(index>=stack.length) return;
        stack[index]=x;
        index++;
    }
    
    public int pop() {
        if((index-1)<0) return -1;
        int val = stack[index-1];
        stack[index-1]=-1; // reset
        index = Math.max(index-1, 0);
        return val;
    }
    
    public void increment(int k, int val) {
        int min = Math.min(index-1, k-1);
        for(int i=0; i<=min; i++){
            if(stack[i]!=-1){
                stack[i] += val;
            }
        }
    }
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack obj = new CustomStack(maxSize);
 * obj.push(x);
 * int param_2 = obj.pop();
 * obj.increment(k,val);
 */

232. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Solution

The implementation uses two stacks to simulate a queue’s behavior, with stack1 acting as the temporary storage for incoming elements and stack2 storing the elements in the correct order for queue operations. By utilizing the front variable and reversing the elements when necessary, the class provides the correct functionality of a queue.

class MyQueue {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    Integer front = -1;

    public MyQueue() {
        
    }
    
    public void push(int x) {
        if(stack1.isEmpty()){
            front = x;
        }
        stack1.push(x);
    }
    
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if(!stack2.isEmpty()){
            return stack2.peek();
        }
        return front;
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

225. Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

class MyStack {
    Queue<Integer> q1 = new LinkedList<>();
   
    public MyStack() {
        
    }
    
    // push a new element to the back of the queue
    // since we want to impl stack, the new elm shold be added
    // to the front of the queue
    public void push(int x) {
        q1.add(x);
        int sz = q1.size();
        while(sz>1){
            q1.add(q1.remove());
            sz--;
        }
    }
    
    // remove the last added element, at the front of the queue
    public int pop() {
        return q1.remove(); // remove first elm at the queue
    }
    
    // get the last added element at the front of the queue
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        super.put(key, value);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

class LRUCache {
    Map<Integer, Node> map;
    LinkedNodeList list;
    Integer capacity;
    public LRUCache(int capacity) {
        this.list = new LinkedNodeList();
        this.map = new HashMap(capacity);
        this.capacity=capacity;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if(node == null) return -1;
        list.moveToHead(node); // indicate most recently used
        return node.value;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if(node != null){
            list.moveToHead(node);
            node.value=value;
        } else {
            Node newNode = new Node(key, value);
            if(map.size() == capacity){
                Node tail = list.getTail();
                map.remove(tail.key);
                list.removeTail();
            }
            map.put(key, newNode);
            list.addToHead(newNode);
        }
    }
}

class Node {
    int key;
    int value;
    Node next;
    Node prev;
    public Node(int key, int value){
        this.key=key;
        this.value=value;
    }
}
class LinkedNodeList{
    Node dummyHead;
    Node dummyTail;
    LinkedNodeList(){
        dummyHead = new Node(0,0);
        dummyTail = new Node(0,0);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    void moveToHead(Node node){
        // remove node from being attached to it's prev and next
        node.prev.next=node.next;
        node.next.prev=node.prev;
        addToHead(node);
    }
    void addToHead(Node node){
        Node tmp = dummyHead.next;
        dummyHead.next=node;
        node.next=tmp;
        tmp.prev=node;
        node.prev=dummyHead;
    }
    void removeTail(){
        Node tmp = dummyTail.prev.prev;
        tmp.next=dummyTail;
        dummyTail.prev=tmp;
    }
    Node getTail(){
        return dummyTail.prev;
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

An improvement to above is to use Object as value.

To make the above thread safe, add synchronised keyword to get() and put().

1166. Design File System

You are asked to design a file system that allows you to create new paths and associate them with different values.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string "" and "/" are not.

Implement the FileSystem class:

• bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn't exist.
• int get(string path) Returns the value associated with path or returns -1 if the path doesn't exist.

Example 1:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

Example 2:

Input: 
["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
Output: 
[null,true,true,2,false,-1]
Explanation: 
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/leet", 1); // return true
fileSystem.createPath("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return -1 because this path doesn't exist.

class FileSystem {

    HashMap<String, FileSystem> folders;
    HashMap<String, Integer> files;
    public FileSystem() {
        folders = new HashMap<>();
        files = new HashMap<>();
    }
    
    public boolean createPath(String path, int value) {
        if(path.isEmpty() || path.equals("/")) return false;
        if(path.startsWith("/")){
            path = path.substring(1);
        }
        String[] splitPath = path.split("/");
        String firstElement = splitPath[0];

        if(splitPath.length == 1){
            if(files.containsKey(path)) return false;
            files.put(firstElement, value);
            return true;
        } else {
            if(!files.containsKey(firstElement)) return false; // does not contain parent folder so we dont create subfolder
            FileSystem newSubFileSystem = folders.getOrDefault(firstElement, new FileSystem());
            String remainingPath = String.join("/", Arrays.copyOfRange(splitPath, 1, splitPath.length));
            folders.put(firstElement, newSubFileSystem);
            return newSubFileSystem.createPath(remainingPath, value);
        }
    }
    
    public int get(String path) {
        if(path.isEmpty() || path.equals("/")) return -1;
        if(path.startsWith("/")){
            path = path.substring(1);
        }
        String[] pathParts = path.split("/");
        String firstPath = pathParts[0];

        if(pathParts.length == 1){
            return files.getOrDefault(path, -1);
        } else {
            if(!folders.containsKey(firstPath)) return -1;
            String remainingPath = String.join("/", Arrays.copyOfRange(pathParts, 1, pathParts.length));
            return folders.get(firstPath).get(remainingPath);
        }
    }
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem obj = new FileSystem();
 * boolean param_1 = obj.createPath(path,value);
 * int param_2 = obj.get(path);
 */

The idea is that a FileSystem class contains 2 types of items: Files and Folders.

A Folder contains links to other FileSystem class as values.

Whenever we have calls to createPath or get, we need to find out whether the path provided is a terminal path (means, not a folder). If it is, we try to find the value or put the value in the files map.

If it is a folder, we need to find the corresponding folder in folders map. Then, trim the path to exclude the current firstPath call recursively call the functions.

Time complexity:

• O(T) to create (T refers to number of components in a path)
• O(T) to get

Space complexity

• Create: O(TN) Worse case is that there won’t be any common prefixes for the paths….Need to create a new path for each unique path and each path will take up T nodes. T refers to path components and N refers to total paths.
• Get: O(1)

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

class MyHashMap {
    
    private int key_space;
    private List<Bucket> hash_table;

    public MyHashMap() {
        this.key_space = 2069; // prime number
        this.hash_table = new ArrayList<Bucket>();
        for (int i = 0; i < this.key_space; i++) {
            this.hash_table.add(new Bucket());
        }
    }

    public void put(int key, int value) {
        int hash_key = key % this.key_space;
        this.hash_table.get(hash_key).update(key, value);
    }

    public int get(int key) {
        int hash_key = key % this.key_space;
        return this.hash_table.get(hash_key).get(key);
    }

    public void remove(int key) {
        int hash_key = key % this.key_space;
        this.hash_table.get(hash_key).remove(key);
    }
}

class Bucket {
    // list of key-value 
    List<BucketItem> items;

    public Bucket() {
        items = new ArrayList<>();
    }

    public void update(int key, int value) {
        for (BucketItem item : items) {
            if (item.key == key) {
                item.value = value;
                return;
            }
        }
        items.add(new BucketItem(key, value));
    }

    public int get(int key) {
        for (BucketItem item : items) {
            if (item.key == key) {
                return item.value;
            }
        }
        return -1; // not found
    }

    public void remove(int key) {
        Iterator<BucketItem> iter = items.iterator();
        while (iter.hasNext()) {
            BucketItem curr = iter.next();
            if (curr.key == key) {
                iter.remove();
                break;
            }
        }
    }
}

class BucketItem {
    int key;
    int value;

    public BucketItem(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

// /**
//  * Your MyHashMap object will be instantiated and called as such:
//  * MyHashMap obj = new MyHashMap();
//  * obj.put(key,value);
//  * int param_2 = obj.get(key);
//  * obj.remove(key);
//  */

// c++ version

class BucketItem {
public:
    int key;
    int value;

    BucketItem(int key, int value) : key(key), value(value) {}

    // BucketItem(int key, int value) {
    //     this->key = key;
    //     this->value = value;
    // } // also can use this as constructor

};

class Bucket {
private:
    list<BucketItem> items;

public:
    Bucket() {} // can omit
    void update(int key, int value) {
        for (auto& item : items) {
            if (item.key == key) {
                item.value = value;
                return;
            }
        }
        items.push_back(BucketItem(key, value));
    }

    int get(int key) {
        for (const auto& item : items) {
            if (item.key == key) {
                return item.value;
            }
        }
        return -1; // not found
    }

    void remove(int key) {
        for (auto it = items.begin(); it != items.end(); ++it) {
            if (it->key == key) {
                items.erase(it);
                break;
            }
        }
    }
};

class MyHashMap {
private:
    int key_space;
    std::vector<Bucket> hash_table;

public:
    MyHashMap() {
        key_space = 2069; // prime number
        hash_table.resize(key_space);
    }

    void put(int key, int value) {
        int hash_key = key % key_space;
        hash_table[hash_key].update(key, value);
    }

    int get(int key) {
        int hash_key = key % key_space;
        return hash_table[hash_key].get(key);
    }

    void remove(int key) {
        int hash_key = key % key_space;
        hash_table[hash_key].remove(key);
    }
};


/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

705. Design HashSet

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

• void add(key) Inserts the value key into the HashSet.
• bool contains(key) Returns whether the value key exists in the HashSet or not.
• void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example 1:

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

class Bucket{
    public:
    vector<int> container; // linkedlist -> Contain a chain of int that hashes to the same slot
    Bucket(){}
    void insert(int key){
        for(auto &itr: container){
            if(itr == key){
                return;
            }
        }
        container.push_back(key);
    }

    void deleteItem(int key){
        for (auto it = container.begin(); it != container.end(); ++it) {
            if (*it == key) {
                container.erase(it);
                break;
            }
        }
    }

    bool exists(int key){
        for (auto it = container.begin(); it != container.end(); ++it) {
            if (*it == key) {
                return true;
            }
        }
        return false;
    }
};

class MyHashSet {
public:
    int key_space;
    vector<Bucket> hash_table;
    MyHashSet() {
        key_space = 2069;
        hash_table.resize(key_space);
    }
    
    void add(int key) {
        int hash_key = key % key_space;
        hash_table[hash_key].insert(key);
    }
    
    void remove(int key) {
        int hash_key = key % key_space;
        hash_table[hash_key].deleteItem(key);
    }
    
    bool contains(int key) {
        int hash_key = key % key_space;
        return hash_table[hash_key].exists(key);
    }
};


/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

Alternative

Instead of using linked list for each bucket, we can use a BST.

class MyHashSet {
  private Bucket[] bucketArray;
  private int keyRange;

  /** Initialize your data structure here. */
  public MyHashSet() {
    this.keyRange = 769;
    this.bucketArray = new Bucket[this.keyRange];
    for (int i = 0; i < this.keyRange; ++i)
      this.bucketArray[i] = new Bucket();
  }

  protected int _hash(int key) {
    return (key % this.keyRange);
  }

  public void add(int key) {
    int bucketIndex = this._hash(key);
    this.bucketArray[bucketIndex].insert(key);
  }

  public void remove(int key) {
    int bucketIndex = this._hash(key);
    this.bucketArray[bucketIndex].delete(key);
  }

  /** Returns true if this set contains the specified element */
  public boolean contains(int key) {
    int bucketIndex = this._hash(key);
    return this.bucketArray[bucketIndex].exists(key);
  }
}


class Bucket {
  private BSTree tree;

  public Bucket() {
    tree = new BSTree();
  }

  public void insert(Integer key) {
    this.tree.root = this.tree.insertIntoBST(this.tree.root, key);
  }

  public void delete(Integer key) {
    this.tree.root = this.tree.deleteNode(this.tree.root, key);
  }

  public boolean exists(Integer key) {
    TreeNode node = this.tree.searchBST(this.tree.root, key);
    return (node != null);
  }
}

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

class BSTree {
  TreeNode root = null;

  public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || val == root.val)
      return root;

    return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
  }

  public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null)
      return new TreeNode(val);

    if (val > root.val)
      // insert into the right subtree
      root.right = insertIntoBST(root.right, val);
    else if (val == root.val)
      // skip the insertion
      return root;
    else
      // insert into the left subtree
      root.left = insertIntoBST(root.left, val);
    return root;
  }

  /*
   * One step right and then always left
   */
  public int successor(TreeNode root) {
    root = root.right;
    while (root.left != null)
      root = root.left;
    return root.val;
  }

  /*
   * One step left and then always right
   */
  public int predecessor(TreeNode root) {
    root = root.left;
    while (root.right != null)
      root = root.right;
    return root.val;
  }

  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null)
      return null;

    // delete from the right subtree
    if (key > root.val)
      root.right = deleteNode(root.right, key);
    // delete from the left subtree
    else if (key < root.val)
      root.left = deleteNode(root.left, key);
    // delete the current node
    else {
      // the node is a leaf
      if (root.left == null && root.right == null)
        root = null;
      // the node is not a leaf and has a right child
      else if (root.right != null) {
        root.val = successor(root);
        root.right = deleteNode(root.right, root.val);
      }
      // the node is not a leaf, has no right child, and has a left child
      else {
        root.val = predecessor(root);
        root.left = deleteNode(root.left, root.val);
      }
    }
    return root;
  }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */

Recap on delete method on BST

Implement a jigsaw puzzle

A jigsaw puzzle is a picture divided into irregularly shaped pieces that can be assembled together to form a complete picture. A puzzle has a fixed number of pieces that can only fit together in exactly one way. We can solve the jigsaw puzzle by aligning the pieces in a way that they fit with each other and also create a coherent picture.

Questions we can ask, as a candidate

• What does a jigsaw puzzle look like. Is there a picture or a pattern on the puzzle?
• What type of shape does our board have? Is it rectangular, circular, or any other shape?
• What kind of shape do the puzzle pieces have? How many sides does a piece have?
• How do the pieces fit together?
• Will all the pieces of a jigsaw puzzle be unique?

// summary
enum Edge {
  INDENTATION, 
  EXTRUSION, 
  FLAT
};

public class Side {
  private Edge edge;
}

public class Piece {
  private List<Side> sides = Arrays.asList(new Side[4]);
  public boolean checkCorner() {}
  public boolean checkEdge() {}
  public boolean checkMiddle() {}
}

/*
The Puzzle class includes the entire board of the jigsaw puzzle as well
as the unused pieces. Since the board is a rectangle, it will be represented 
using a 2-D array. In addition, there will be only one instance of the puzzle 
board in the jigsaw puzzle. Therefore, the Puzzle class will be a Singleton 
class to ensure that only one instance for the board is created in the entire 
system. The definition of this class is given below:
*/

public class Puzzle {
  private List<List<Piece>> board;
  private List<Piece> free; // represents the currently free pieces (yet to be inserted in board)
  public void insertPiece(Piece piece, int row, int column) {};

  // Puzzle is a singleton class that ensures it will have only one active instance at a time
  private static Puzzle puzzle = null;
    
  // Created a static method to access the singleton instance of Puzzle class
  public static Puzzle getInstance() {
      if (puzzle == null) {
          puzzle = new Puzzle();
      }
      return puzzle;
  }  
}

// solves the puzzle
public class PuzzleSolver {
  public Puzzle matchPieces(Puzzle board) {}
}

// actual code
// The code below is not correct. There is currently no logic to 
// initialise the free pieces...
// but the idea is there.
// Also, we don't differentiate the case between neighbour node being out of bound or not
// initialised..need to do checking on the row, col to figure out out of bound.
// Currently not done in the findMatchingPiece algorithm
import java.util.*;

// Design a jigsaw puzzle algorithm, given a Piece class, a Side class containing sideTypes, and a helper function which returns whether or not two pieces are a match
public class PuzzleSolver {
    public Puzzle matchPieces(Puzzle puzzle){
        List<List<Piece>> board = puzzle.getBoard();
        List<Piece> freePieces = puzzle.getFreePieces();

        int numRows = board.size();
        int numCols = numRows > 0 ? board.get(0).size(): 0;

        for(int row=0; row<numRows; row++){
            for(int col=0; col<numCols; col++){
                Piece currentPiece = board.get(row).get(col);
                if(currentPiece != null){
                    continue; // piece is already placed.
                }

                Piece topPiece = row > 0 ? board.get(row-1).get(col) : null;
                Piece rightPiece = col<numCols-1 ? board.get(row).get(col+1) : null;
                Piece bottomPiece = row<numRows-1 ? board.get(row+1).get(col) : null;
                Piece leftPiece = col > 0 ? board.get(row).get(col-1) : null;

                Piece matchedPiece = findMatchingPiece(topPiece, rightPiece, bottomPiece, leftPiece, freePieces);
                if(matchedPiece != null){
                    puzzle.insertPiece(matchedPiece, row, col);
                    freePieces.remove(matchedPiece);
                }
            }
        }
        return puzzle;
    }

    private Piece findMatchingPiece(Piece top, Piece right, Piece bottom, Piece left, List<Piece> freePieces) {
        for(Piece piece: freePieces){
            if(matchesEdge(piece, top, right, bottom, left)){
                return piece;
            }
        }
        return null;
    }

    public Boolean matchesEdge(Piece piece, Piece top, Piece right, Piece bottom, Piece left){
        Edge bottomOfTopPiece = top != null ? top.sides.get(2).getEdge() : null;
        Edge leftOfRightPiece = right != null ? right.sides.get(3).getEdge() : null;
        Edge topOfBottomPiece = bottom != null ? bottom.sides.get(0).getEdge() : null;
        Edge rightOfLeftPiece = left != null ? left.sides.get(1).getEdge() : null;

        if(piece.checkCorner()){
            return matchCornerEdge(piece, bottomOfTopPiece, leftOfRightPiece, topOfBottomPiece, rightOfLeftPiece);
        } else if (piece.checkMiddle()){
            return matchMiddleEdge(piece, bottomOfTopPiece, leftOfRightPiece, topOfBottomPiece, rightOfLeftPiece);
        } else if (piece.checkEdge()){
            return matchEdge(piece, bottomOfTopPiece, leftOfRightPiece, topOfBottomPiece, rightOfLeftPiece);
        }
        return false;
    }

    private Boolean matchEdge(Piece piece, Edge bottomOfTopPiece, Edge leftOfRightPiece, Edge topOfBottomPiece, Edge rightOfLeftPiece){
        if(piece.sides.get(0).getEdge() == Edge.FLAT){
            return matchBottom(piece, topOfBottomPiece) && matchLeft(piece, rightOfLeftPiece) && matchRight(piece, leftOfRightPiece);
        } else if (piece.sides.get(1).getEdge() == Edge.FLAT){
            return matchBottom(piece, topOfBottomPiece) && matchLeft(piece, rightOfLeftPiece) && matchTop(piece, bottomOfTopPiece);
        } else if (piece.sides.get(2).getEdge() == Edge.FLAT){
            return matchRight(piece, leftOfRightPiece) && matchLeft(piece, rightOfLeftPiece) && matchTop(piece, bottomOfTopPiece);
        } else if (piece.sides.get(3).getEdge() == Edge.FLAT){
            return matchRight(piece, leftOfRightPiece) && matchBottom(piece, topOfBottomPiece) && matchTop(piece, bottomOfTopPiece);
        }
        return false;
    }
    private Boolean matchMiddleEdge(Piece piece, Edge bottomOfTopPiece, Edge leftOfRightPiece, Edge topOfBottomPiece, Edge rightOfLeftPiece) {
        return matchTop(piece, bottomOfTopPiece) && matchRight(piece, leftOfRightPiece) && matchBottom(piece, topOfBottomPiece) && matchLeft(piece, rightOfLeftPiece);
    }
    
    private Boolean matchCornerEdge(Piece piece, Edge bottomOfTopPiece, Edge leftOfRightPiece, Edge topOfBottomPiece, Edge rightOfLeftPiece) {
         // right upp corner
        if (piece.sides.get(0).getEdge() == Edge.FLAT && piece.sides.get(1).getEdge() == Edge.FLAT) {
            return matchRight(piece, leftOfRightPiece) && matchBottom(piece, topOfBottomPiece);
        // right lower corner
        } else if (piece.sides.get(1).getEdge() == Edge.FLAT && piece.sides.get(2).getEdge() == Edge.FLAT) {
            return matchTop(piece, bottomOfTopPiece) && matchRight(piece, leftOfRightPiece);
        // left upp corner
        } else if (piece.sides.get(0).getEdge() == Edge.FLAT && piece.sides.get(3).getEdge() == Edge.FLAT) {
            return matchLeft(piece, rightOfLeftPiece) && matchBottom(piece, topOfBottomPiece);
        // left lower corner
        } else if (piece.sides.get(2).getEdge() == Edge.FLAT && piece.sides.get(3).getEdge() == Edge.FLAT) {
            return matchTop(piece, bottomOfTopPiece) && matchLeft(piece, rightOfLeftPiece);
        }
        return false;
    }

    private boolean matchLeft(Piece piece, Edge rightOfLeftPiece) {
        return (rightOfLeftPiece == null || (rightOfLeftPiece == Edge.EXTRUSION && piece.sides.get(3).getEdge() == Edge.INDENTATION) ||
            (rightOfLeftPiece == Edge.INDENTATION && piece.sides.get(3).getEdge() == Edge.EXTRUSION));
    }

    private boolean matchRight(Piece piece, Edge leftOfRightPiece) {
        return (leftOfRightPiece == null || (leftOfRightPiece == Edge.EXTRUSION && piece.sides.get(1).getEdge() == Edge.INDENTATION) ||
            (leftOfRightPiece == Edge.INDENTATION && piece.sides.get(1).getEdge() == Edge.EXTRUSION));
    }

    private boolean matchBottom(Piece piece, Edge topOfBottomPiece) {
        return (topOfBottomPiece == null || (topOfBottomPiece == Edge.EXTRUSION && piece.sides.get(2).getEdge() == Edge.INDENTATION) ||
            (topOfBottomPiece == Edge.INDENTATION && piece.sides.get(2).getEdge() == Edge.EXTRUSION));
    }
    
    private boolean matchTop(Piece piece, Edge bottomOfTopPiece) {
        return (bottomOfTopPiece == null || (bottomOfTopPiece == Edge.EXTRUSION && piece.sides.get(0).getEdge() == Edge.INDENTATION) ||
            (bottomOfTopPiece == Edge.INDENTATION && piece.sides.get(0).getEdge() == Edge.EXTRUSION));
    }
    
}

class Puzzle {
    private List<List<Piece>> board;
    private List<Piece> free; // represents the currently free pieces (yet to be inserted in board)
    int numRows;
    int numCols;
  
    private Puzzle(int numRows, int numCols) {
      board = new ArrayList<>();
      free = new ArrayList<>();
      this.numRows = numRows;
      this.numCols = numCols;
  
      initializeBoard();
    }
    // Need to create a method for someone to add pieces to free
    // TODO

    private void initializeBoard() {
          for (int i = 0; i < numRows; i++) {
              List<Piece> row = new ArrayList<>();
              for (int j = 0; j < numCols; j++) {
                  row.add(null);
              }
              board.add(row);
          }
    }
  
    public static Puzzle getInstance() {
      return PuzzleHolder.INSTANCE;
    }
    
    private static class PuzzleHolder {
      // tentatively hardcode size
      private static final Puzzle INSTANCE = new Puzzle(4,4);
    }
    
    public void insertPiece(Piece piece, int row, int column) {
      if (row < 0 || row >= numRows || column < 0 || column >= numCols) {
        throw new IllegalArgumentException("Invalid row or column specified.");
      }
      board.get(row).set(column, piece);
    }

    public List<List<Piece>> getBoard() {
        return board;
    }

    public List<Piece> getFreePieces() {
        return free;
    }
}
class Piece {
    public List<Side> sides = Arrays.asList(new Side[4]);

    public Piece(Edge top, Edge right, Edge bottom, Edge left) {
      sides.set(0, new Side(top));
      sides.set(1, new Side(right));
      sides.set(2, new Side(bottom));
      sides.set(3, new Side(left));
    }
  
    public boolean checkCorner() {
      int flatCount = 0;
      for (Side side : sides) {
        if (side.getEdge() == Edge.FLAT) {
          flatCount++;
        }
      }
      return flatCount == 2;
    }
  
    public boolean checkEdge() {
      int flatCount = 0;
      for (Side side : sides) {
        if (side.getEdge() == Edge.FLAT) {
          flatCount++;
        }
      }
      return flatCount == 1;
    }
  
    public boolean checkMiddle() {
      int flatCount = 0;
      for (Side side : sides) {
        if (side.getEdge() == Edge.FLAT) {
          flatCount++;
        }
      }
      return flatCount == 0;
    }
}

class Side {
    private Edge edge;
  
    public Side(Edge edge) {
      this.edge = edge;
    }

    public Edge getEdge(){
        return this.edge;
    }
}

enum Edge {
    INDENTATION, 
    EXTRUSION, 
    FLAT
};

Design 2048 game

Solve 2048

import java.util.*;

public class Game{
    public static void main(String[] args){
        // initialise board
        BoardService service = new BoardService();
        Scanner sc = new Scanner(System.in);
        while(true){
            String command = sc.nextLine();
            if(command.equals("EXIT")) break;
           
            if(command.equals(Move.UP.name())){
                service.move(Move.UP);
            } else if (command.equals(Move.DOWN.name())){
                service.move(Move.DOWN);
            } else if (command.equals(Move.LEFT.name())){
                service.move(Move.LEFT);
            } else {
                service.move(Move.RIGHT);
            }

            if(service.hasGameBeenWon()){
                System.out.println("CONGRATS!!! 2048 number has been formed :)");
                break;
            }
        }
        sc.close();
    }


}

enum Move{
    UP, DOWN, LEFT, RIGHT
}

class BoardService{
    Board board;

    public BoardService(){
        this.board = new Board();
        board.addRandomCell();
        board.addRandomCell();
        System.out.println("Initialising Board ... ");
        System.out.println(board); 
    }

    public void move(Move move){
        switch(move){
            case UP:
                board.slideUp();
                break;
            case DOWN:
                board.slideDown();
                break;
            case LEFT:
                board.slideLeft();
                break;
            case RIGHT:
                board.slideRight();
                break;
        }

        board.addRandomCell();
        System.out.println(board); 
    }

    public boolean hasGameBeenWon(){
        return board.hasGameBeenWon();
    }

}

class Board {
    Cell[][] items;

    public Board(){
        items = new Cell[4][4];
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                items[i][j]=new Cell(0);
            }
        }
    }

    public Boolean hasGameBeenWon(){
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                if(items[i][j].value == 2048) return true;
            }
        }
        return false;
    }

    public void putNonZerosToLeft(Cell[] row){
        int count = 0;
        for(int i=0; i<row.length; i++){
            Cell curr = row[i];
            if(curr.value != 0){
                row[count++] = row[i];
            }
        }
        while(count<row.length){
            row[count++]= new Cell(0);
        }
    }

    // right to left
    public void slide(Cell[] row){
        putNonZerosToLeft(row);
    
        // Combine similar numbers
        for(int i=0; i<row.length-1; i++){
            if(row[i].value==row[i+1].value){
                row[i].value*=2;
                row[i+1].value=0;
            }
        }

        putNonZerosToLeft(row);
    }

    public void slideLeft(){
        for(int i=0; i<4; i++){
            slide(items[i]);
        }
    }

    public void reverse(Cell[] items, Cell[] copy){
        int count2 = 0;
        for(int j=3; j>=0; j--){
            items[j]=copy[count2++];
        }
    }

    public void slideRight(){
        for(int i=0; i<4; i++){
            Cell[] reversedArr = new Cell[4];
            reverse(reversedArr, items[i]);
            slide(reversedArr);
            reverse(items[i], reversedArr);
        }
    }
    
    // Up to down map to left to right
    public void makeColIntoRow(Cell[] row, int col){
        for(int j=0; j<4; j++){
            row[j]=items[j][col];
        }
    }

    public void makeRowIntoCol(Cell[] colArr, int col){
        for(int j=0; j<4; j++){
            items[j][col]=colArr[j];
        }
    }

    public void slideUp(){
        for(int i=0; i<4; i++){
            Cell[] row = new Cell[4];
            makeColIntoRow(row, i);
            slide(row);
            makeRowIntoCol(row, i);
        }
    }

    public void slideDown(){
        for(int i=0; i<4; i++){
            Cell[] row = new Cell[4];
            makeColIntoRow(row, i);
            Cell[] reversedArr = new Cell[4];
            reverse(reversedArr, row);
            slide(reversedArr);
            reverse(row, reversedArr);
            makeRowIntoCol(row, i);
        }
    }

    public boolean isGridFull(){
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                if(items[i][j].value == 0) return false;
            }
        }
        return true;
    }

    public void addRandomCell(){
        if(isGridFull()) return;
        while(true){
            int randomRow = (int) (Math.random() * 4);
            int randomCol = (int) (Math.random() * 4);
            if(items[randomRow][randomCol].value == 0){
                items[randomRow][randomCol].value = 2;
                break;
            }
        }
    }

    public String toString(){
        String result = "";
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                result += items[i][j].toString() + " ";
            }
            result += "\n";
        }
        return result;
    }

}


class Cell{
    int value;
    public Cell(int val){
        this.value = val;
    }
    public String toString(){
        return String.valueOf(value);
    }
}

353. Design Snake Game

Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.

You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).

Implement the SnakeGame class:

• SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
• int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.

Example 1:

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border

Constraints:

• 1 <= width, height <= 104
• 1 <= food.length <= 50
• food[i].length == 2
• 0 <= ri < height
• 0 <= ci < width
• direction.length == 1
• direction is 'U', 'D', 'L', or 'R'.
• At most 104 calls will be made to move.

class SnakeGame {
    HashSet<Cell> occupiedCells;
    Cell head;
    Cell tail;
    int width;
    int height;
    Queue<Cell> cellsWithFood;
    int score;
    public SnakeGame(int width, int height, int[][] food) {
        this.score = 0;
        this.width = width;
        this.height = height;
        occupiedCells = new HashSet<>();
        Cell firstCell = new Cell(0, 0);
        occupiedCells.add(firstCell);
        head = new Cell(-1, -1); // dummy
        head.setNext(firstCell);
        firstCell.prev = head;
        
        tail = new Cell(-1, -1);
        tail.setPrev(firstCell);
        firstCell.next = tail; 
        // [-1,-1] -> [0,0] -> [-1,-1] 
        cellsWithFood = new LinkedList<>(); // Will be a queue of Cells, pop out one by one
        for(int[] f: food){
            cellsWithFood.add(new Cell(f[0], f[1]));
        }
    }
    
    public int move(String direction) {
        Cell currHead = head.next;
        Cell newCell = new Cell(-1,-1);
        if(direction.equals("U")){
            if(currHead.row-1<0){
                return -1;
            }
            newCell = new Cell(currHead.row-1, currHead.col);
        } else if (direction.equals("D")){
            if(currHead.row+1>=height){
                return -1;
            }
            newCell = new Cell(currHead.row+1, currHead.col);
        } else if (direction.equals("L")){
            if(currHead.col-1<0){
                return -1;
            }
            newCell = new Cell(currHead.row, currHead.col-1);
        } else if (direction.equals("R")){
            if(currHead.col+1>=width){
                return -1;
            }
            newCell = new Cell(currHead.row, currHead.col+1);
        }
        Boolean hasFoodInNewCell = cellsWithFood.size()>0 && cellsWithFood.peek().equals(newCell);
        // Add new head
        Cell temp = head.next;
        head.next = newCell;
        newCell.prev = head;
        newCell.next=temp;
        temp.prev = newCell;
        if(!hasFoodInNewCell){
            // remove last node from tail
            Cell toRemove = tail.prev;
            occupiedCells.remove(toRemove);
            // Reassign pointers
            Cell tempLast = tail.prev.prev;
            tempLast.next = tail;
            tail.prev = tempLast;
        }
        // Can only put this check after we shift the body   
        if(!hasFoodInNewCell && occupiedCells.contains(newCell)){
            // After shifting all the cells (except the head), we check if the head is already 
            // covered by the body. if yes, it means there is a cut of it's own body
            return -1;
        } 
        // modify hashset
        occupiedCells.add(newCell);
        if(hasFoodInNewCell){
            score += 1;
            cellsWithFood.remove(); // time to move to the next food in the queue
        }
        return score;
    }
}
class Cell{
    int row;
    int col;
    Cell next;
    Cell prev;
    public Cell(int row, int col){
        this.row = row;
        this.col = col;
        next = null;
        prev = null;
    }
    public void setNext(Cell next){
        this.next = next;
    }
    public void setPrev(Cell prev){
        this.prev = prev;
    }
    public String toString(){
        return row+"-"+col;
    }
    
    /*
     * Override the hashcode and equality for Hashset comparison
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        Cell other = (Cell) obj;
        return row == other.row && col == other.col;
    }
    @Override
    public int hashCode() {
        return 31 * row + col;
    }
}
/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */

// IDEA ON HOW TO SOLVE
// represent snack body as a linked list.
// If the snake moves and grows in length, create a new node ad add to the front of the list node
// If it moves but doesn't grow, then on top of doing the above, need to remove the tail node.
// To detect collision with own tail, need to check if any node contains the new head
// ...Can use a separate hash map for fast checks...

348. Design Tic-Tac-Toe

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

1. A move is guaranteed to be valid and is placed on an empty block.
2. Once a winning condition is reached, no more moves are allowed.
3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

• TicTacToe(int n) Initializes the object the size of the board n.
• int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Return
• 0 if there is no winner after the move,
• 1 if player 1 is the winner after the move, or
• 2 if player 2 is the winner after the move.

Example 1:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

Explanation
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is "X" and player 2 is "O" in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |
ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |
ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|
ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|
ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|
ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|
ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

class TicTacToe {
    int[][] board;
    public TicTacToe(int n) {
        board = new int[n][n];
    }
    
    public int move(int row, int col, int player) {
        board[row][col]=player;
        return getWinner(row, col, player);
    }

    public int getWinner(int row, int col, int player){
        // check entire row
        int countRow=0;
        for(int i=0; i<board.length; i++){
            if(board[row][i] == player){
                countRow ++;
            } else {
                break;
            }
        }
        if(countRow == board.length) return player;
        
        // check entire col
        int countCol=0;
        for(int i=0; i<board.length; i++){
            if(board[i][col] == player){
                countCol ++;
            } else {
                break;
            }
        }
        if(countCol == board.length) return player;

        // LEFT TO RIGHT DIAGONAL
        // check upp diagonal
        int i = row;
        int j = col;
        int countUppDiag = 0;
        while(i >= 0 && j >= 0){
            if(board[i][j] == player){
                countUppDiag ++;
            } else {
                break;
            }
            i--;
            j--;
        }

        // check bottom diagonal
        int i2 = row+1;
        int j2 = col+1;
        int countBotDiag = 0;
        while(i2 < board.length && j2 < board.length){
            if(board[i2][j2] == player){
                countBotDiag ++;
            } else {
                break;
            }
            i2++;
            j2++;
        }
        if((countBotDiag+countUppDiag) == board.length) return player;

        // RIGHT TO LEFT INFLATION
        // check upp diagonal
        int i3 = row;
        int j3 = col;
        int countUppDiagRight = 0;
        while(i3 >= 0 && j3 <board.length){
            if(board[i3][j3] == player){
                countUppDiagRight ++;
            } else {
                break;
            }
            i3--;
            j3++;
        }

        // check bottom diagonal
        int i4 = row+1;
        int j4 = col-1;
        int countBotDiagRight = 0;
        while(i4 < board.length && j4 >=0){
            if(board[i4][j4] == player){
                countBotDiagRight ++;
            } else {
                break;
            }
            i4++;
            j4--;
        }
        if((countUppDiagRight+countBotDiagRight) == board.length) return player;

        return 0;
        
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

Can we improve upon the algorithm above? (Validation part?) Can we find this in constant time without iterating over each of the horizontal, vertical, and diagonal rows on every move?

We will need to use a data structure to count how many times a player has marked a particular row, column, or diagonal.

class TicTacToe {
    int[][] board;
    int[] rows;
    int[] cols;
    int diagonal;
    int antiDiagonal;

    public TicTacToe(int n) {
        board = new int[n][n];
        rows = new int[n];
        cols = new int[n];
    }
    
    public int move(int row, int col, int player) {
        board[row][col]=player;
        return getWinner(row, col, player);
    }

    public int getWinner(int row, int col, int player){
        int currentPlayer = (player == 1) ? 1 : -1;
        rows[row]+=currentPlayer;
        cols[col]+=currentPlayer;
        // diagonal
        if(row == col) {
            diagonal += currentPlayer;
        }
        // anti-diagonal
        if((col+row) == cols.length-1){
            antiDiagonal += currentPlayer;
        }

        int n = rows.length;
        if(Math.abs(rows[row]) == n || Math.abs(cols[col])==n || 
        Math.abs(diagonal)==n || Math.abs(antiDiagonal)==n){
            return player;
        }

        return 0;
        
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

1172. Dinner Plate Stacks

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

• DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks capacity.
• void push(int val) Pushes the given integer val into the leftmost stack with a size less than capacity.
• int pop() Returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all the stacks are empty.
• int popAtStack(int index) Returns the value at the top of the stack with the given index index and removes it from that stack or returns -1 if the stack with that given index is empty.

Example 1:

Input
["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"]
[[2], [1], [2], [3], [4], [5], [0], [20], [21], [0], [2], [], [], [], [], []]
Output
[null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]

Explanation: 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

Constraints:

• 1 <= capacity <= 2 * 104
• 1 <= val <= 2 * 104
• 0 <= index <= 105
• At most 2 * 105 calls will be made to push, pop, and popAtStack.

Time limit exceeded solution

class DinnerPlates {

    int capacity;
    List<Stack<Integer>> stacks;
    public DinnerPlates(int capacity) {
        this.capacity = capacity;
        this.stacks = new ArrayList<>();
    }
    
    public void push(int val) {
        for(Stack<Integer> s: stacks){
            if(s.size()<this.capacity){
                s.push(val);
                return;
            }
        }
        Stack<Integer> newStack = new Stack<>();
        newStack.push(val);
        this.stacks.add(newStack);
    }
    
    public int pop() {
        if(stacks.size()==0) return -1;
        for(int i=stacks.size()-1; i>=0; i--){
            Stack<Integer> lastStack = stacks.get(i);
            if(lastStack.size()>0){
                return lastStack.pop();
            }
        }
        return -1;
    }
    
    public int popAtStack(int index) {
        if(index>stacks.size()-1) return -1;
        Stack<Integer> st = stacks.get(index);
        if(st.size()>0){
            return st.pop();
        }
        return -1;
    }
}

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates obj = new DinnerPlates(capacity);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAtStack(index);
 */

Leetcode solution

We will use a List to store all stacks and a TreeSet (Binary Tree) to store the indexes of all unfull stacks. As an invariant, we will stipulate that the last element in our list of stacks MUST be nonempty. This way we can perform pop() without having to loop from right to left in the list to find the first nonempty stack.

class DinnerPlates {

    List<Stack<Integer>> stacks;
    TreeSet<Integer> openStacks;
    int capacity;
    public DinnerPlates(int capacity) {
        this.stacks = new ArrayList<>();
        this.openStacks = new TreeSet();
        this.capacity = capacity;
    }
    
    public void push(int val) {
        if(openStacks.isEmpty()){
            stacks.add(new Stack());
            openStacks.add(stacks.size()-1); // index
        }
        stacks.get(openStacks.first()).push(val);
        if(stacks.get(openStacks.first()).size() == capacity){
            openStacks.pollFirst();
        }
    }
    
    public int pop() {
        return myPop(stacks.size()-1);
    }
    
    public int popAtStack(int index) {
        return myPop(index);
    }

    private int myPop(int i){
        if(i<0 || i>=stacks.size() || stacks.get(i).isEmpty()){
            return -1;
        }
        int ret = stacks.get(i).pop();
        openStacks.add(i);
        while(stacks.size()>0 && stacks.get(stacks.size()-1).isEmpty()){
            stacks.remove((int) openStacks.pollLast());// remove empty stack
        }
        return ret;
    }
}

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates obj = new DinnerPlates(capacity);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAtStack(index);
 */

981. Time Based Key-Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

• TimeMap() Initializes the object of the data structure.
• void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
• String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Example 1:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

Constraints:

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 107
• All the timestamps timestamp of set are strictly increasing.
• At most 2 * 105 calls will be made to set and get.

Time limit exceeded solution

class TimeMap {

    Map<String, LinkedHashMap<Integer, String>> map; // key -> time -> value

    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        LinkedHashMap<Integer, String> valueTimestamp = map.getOrDefault(key, new LinkedHashMap<>());
        valueTimestamp.put(timestamp, value);
        map.put(key, valueTimestamp);
    }
    
    public String get(String key, int timestamp) {
       
        LinkedHashMap<Integer, String> valueTimestamp = map.getOrDefault(key, new LinkedHashMap<>());
 
        if (valueTimestamp.containsKey(timestamp)) {
            return valueTimestamp.get(timestamp);
        }
        ListIterator<Integer> iterator = new ArrayList(valueTimestamp.keySet()).listIterator(valueTimestamp.size());
        while (iterator.hasPrevious()) {
            Integer key2 = iterator.previous();
            if (key2 < timestamp) {
                return valueTimestamp.get(key2);
            }
        }
        return "";
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

Solution from editorial

In the previous approach, the set function is efficient, but in the get function we iterate linearly over the time range. If the timestamps in the inner map were sorted, then we can use binary search to find the target time more efficiently.

Thus, we can use a sorted map instead of a hashmap.
A sorted map keeps the stored key-value pairs sorted based on the key.

So now our data structure keyTimeMap will look like:
HashMap(key, SortedMap(timestamp, value)).

set(key, value, timestamp) function:
To store a value for a given key and timestamp, we just need to store it at the (key, timestamp) location in keyTimeMap.

keyTimeMap[key][timestamp] = value;

get(key, timestamp) function:
We have to return a value from the key bucket, which has time equal to or just less than the given timestamp.
So, we will find the upper_bound of the given timestamp, upper_bound function returns an iterator pointing to the first element that is greater than the searched value. Thus, the left element of the iterator will be equal to or just smaller than the searched value.

If upper_bound points to the beginning of the map it means no time less than or equal to the given timestamp exists in the map thus we return a null string.
Otherwise, the target time exists at one position left of the position pointed by the upper_bound.

it = results[key].upper_bound(timestamp);
if (it == results[key].begin()) {
    return "";
}
return prev(it)->second;

class TimeMap {
    HashMap<String, TreeMap<Integer, String>> keyTimeMap;
    
    public TimeMap() {
        keyTimeMap = new HashMap<String, TreeMap<Integer, String>>();
    }
    
    public void set(String key, String value, int timestamp) {
        if (!keyTimeMap.containsKey(key)) {
            keyTimeMap.put(key, new TreeMap<Integer, String>());
        }
        
        // Store '(timestamp, value)' pair in 'key' bucket.
        keyTimeMap.get(key).put(timestamp, value);
    }
    
    public String get(String key, int timestamp) {
        // If the 'key' does not exist in map we will return empty string.
        if (!keyTimeMap.containsKey(key)) {
            return "";
        }
        
        Integer floorKey = keyTimeMap.get(key).floorKey(timestamp);
        // Return searched time's value, if exists.
        if (floorKey != null) {
            return keyTimeMap.get(key).get(floorKey);
        }
        
        return "";
    }
}

// Note: Java has a little different implementation, here we will use thefloorKey method,
// which returns a key equal to or less than searched key or null if no such key exists that satisfies the above condition.

2408. Design SQL

You are given n tables represented with two arrays names and columns, where names[i] is the name of the ith table and columns[i] is the number of columns of the ith table.

You should be able to perform the following operations:

• Insert a row in a specific table. Each row you insert has an id. The id is assigned using an auto-increment method where the id of the first inserted row is 1, and the id of each other row inserted into the same table is the id of the last inserted row (even if it was deleted) plus one.
• Delete a row from a specific table. Note that deleting a row does not affect the id of the next inserted row.
• Select a specific cell from any table and return its value.

Implement the SQL class:

• SQL(String[] names, int[] columns) Creates the n tables.
• void insertRow(String name, String[] row) Adds a row to the table name. It is guaranteed that the table will exist, and the size of the array row is equal to the number of columns in the table.
• void deleteRow(String name, int rowId) Removes the row rowId from the table name. It is guaranteed that the table and row will exist.
• String selectCell(String name, int rowId, int columnId) Returns the value of the cell in the row rowId and the column columnId from the table name.

Example 1:

Input
["SQL", "insertRow", "selectCell", "insertRow", "deleteRow", "selectCell"]
[[["one", "two", "three"], [2, 3, 1]], ["two", ["first", "second", "third"]], ["two", 1, 3], ["two", ["fourth", "fifth", "sixth"]], ["two", 1], ["two", 2, 2]]
Output
[null, null, "third", null, null, "fifth"]

Explanation
SQL sql = new SQL(["one", "two", "three"], [2, 3, 1]); // creates three tables.
sql.insertRow("two", ["first", "second", "third"]); // adds a row to the table "two". Its id is 1.
sql.selectCell("two", 1, 3); // return "third", finds the value of the third column in the row with id 1 of the table "two".
sql.insertRow("two", ["fourth", "fifth", "sixth"]); // adds another row to the table "two". Its id is 2.
sql.deleteRow("two", 1); // deletes the first row of the table "two". Note that the second row will still have the id 2.
sql.selectCell("two", 2, 2); // return "fifth", finds the value of the second column in the row with id 2 of the table "two".

Constraints:

• n == names.length == columns.length
• 1 <= n <= 104
• 1 <= names[i].length, row[i].length, name.length <= 20
• names[i], row[i], and name consist of lowercase English letters.
• 1 <= columns[i] <= 100
• All the strings of names are distinct.
• name exists in the array names.
• row.length equals the number of columns in the chosen table.
• rowId and columnId will be valid.
• At most 250 calls will be made to insertRow and deleteRow.
• At most 104 calls will be made to selectCell.

class SQL {
    HashMap<String, Table> database;
    
    public SQL(List<String> names, List<Integer> columns) {
        database = new HashMap<>();
        for(int i=0; i<names.size(); i++){
            database.put(names.get(i), new Table(columns.get(i)));
        }
    }
    
    public void insertRow(String name, List<String> row) {
        Table t = database.get(name);
        t.insertRow(row);
    }
    
    public void deleteRow(String name, int rowId) {
        Table t = database.get(name);
        t.deleteRow(rowId);
    }
    
    public String selectCell(String name, int rowId, int columnId) {
        Table t = database.get(name);
        return t.selectCell(rowId, columnId);
    }
}

class Table{
    int rowId;
    int cols;
    HashMap<Integer, List<String>> rows;

    public Table(int numCols){
        this.rowId = 1; // first row id
        this.cols = numCols;
        this.rows = new HashMap<>();
    }
    public void insertRow(List<String> row){
        this.rows.put(rowId, row);
        this.rowId++;
    }
    public void deleteRow(int rowId){
        rows.remove(rowId);
    }
    public String selectCell(int rowId, int columnId){
        List<String> row = rows.getOrDefault(rowId, new LinkedList<>());
        if(row.size()==0 || row.size()<columnId){
            return "";
        }
        return row.get(columnId-1);
    }
}
/**
 * Your SQL object will be instantiated and called as such:
 * SQL obj = new SQL(names, columns);
 * obj.insertRow(name,row);
 * obj.deleteRow(name,rowId);
 * String param_3 = obj.selectCell(name,rowId,columnId);
 */

2296. Design a Text Editor

Design a text editor with a cursor that can do the following:

• Add text to where the cursor is.
• Delete text from where the cursor is (simulating the backspace key).
• Move the cursor either left or right.

When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that 0 <= cursor.position <= currentText.length always holds.

Implement the TextEditor class:

• TextEditor() Initializes the object with empty text.
• void addText(string text) Appends text to where the cursor is. The cursor ends to the right of text.
• int deleteText(int k) Deletes k characters to the left of the cursor. Returns the number of characters actually deleted.
• string cursorLeft(int k) Moves the cursor to the left k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.
• string cursorRight(int k) Moves the cursor to the right k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

Example 1:

Input
["TextEditor", "addText", "deleteText", "addText", "cursorRight", "cursorLeft", "deleteText", "cursorLeft", "cursorRight"]
[[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]
Output
[null, null, 4, null, "etpractice", "leet", 4, "", "practi"]

Explanation
TextEditor textEditor = new TextEditor(); // The current text is "|". (The '|' character represents the cursor)
textEditor.addText("leetcode"); // The current text is "leetcode|".
textEditor.deleteText(4); // return 4
                          // The current text is "leet|". 
                          // 4 characters were deleted.
textEditor.addText("practice"); // The current text is "leetpractice|". 
textEditor.cursorRight(3); // return "etpractice"
                           // The current text is "leetpractice|". 
                           // The cursor cannot be moved beyond the actual text and thus did not move.
                           // "etpractice" is the last 10 characters to the left of the cursor.
textEditor.cursorLeft(8); // return "leet"
                          // The current text is "leet|practice".
                          // "leet" is the last min(10, 4) = 4 characters to the left of the cursor.
textEditor.deleteText(10); // return 4
                           // The current text is "|practice".
                           // Only 4 characters were deleted.
textEditor.cursorLeft(2); // return ""
                          // The current text is "|practice".
                          // The cursor cannot be moved beyond the actual text and thus did not move. 
                          // "" is the last min(10, 0) = 0 characters to the left of the cursor.
textEditor.cursorRight(6); // return "practi"
                           // The current text is "practi|ce".
                           // "practi" is the last min(10, 6) = 6 characters to the left of the cursor.

Constraints:

• 1 <= text.length, k <= 40
• text consists of lowercase English letters.
• At most 2 * 104 calls in total will be made to addText, deleteText, cursorLeft and cursorRight.

class TextEditor {
    StringBuilder res;
    int pos = 0;

    public TextEditor() {
        res = new StringBuilder();
    }
    
    public void addText(String text) {
        res.insert(pos, text);
        pos += text.length();
    }
    
    public int deleteText(int k) {
        int tmp = pos;
        pos -= k;
        if(pos<0) pos=0;
        res.delete(pos,tmp);
        return tmp-pos;
    }
    
    public String cursorLeft(int k) {
        pos-=k;
        if(pos<0) pos=0;
        if(pos<10) return res.substring(0, pos);
        return res.substring(pos-10, pos);
    }
    
    public String cursorRight(int k) {
        pos+=k;
        if(pos>res.length()) pos=res.length();
        if(pos<10) return res.substring(0, pos);
        return res.substring(pos-10, pos);
    }
}

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor obj = new TextEditor();
 * obj.addText(text);
 * int param_2 = obj.deleteText(k);
 * String param_3 = obj.cursorLeft(k);
 * String param_4 = obj.cursorRight(k);
 */

362. Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

• HitCounter() Initializes the object of the hit counter system.
• void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
• int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

Example 1:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

class HitCounter {

    LinkedList<Integer> allHits;

    public HitCounter() {
        allHits = new LinkedList<>();
    }
    
    public void hit(int timestamp) {    
        allHits.add(timestamp);
    }
    
    public int getHits(int timestamp) {
        int notOlderThan = timestamp-300;
        Iterator<Integer> iterator = allHits.iterator();
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            if (element<=notOlderThan) {
                iterator.remove(); // Remove the current element from the linked list
            } else {
                break;
            }
        }
        return allHits.size();
    }

}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */