# Design

[170. Two Sum III - Data structure design](https://leetcode.com/problems/two-sum-iii-data-structure-design/)

**Approach 1 - binary search + sorted array**

```typescript
class TwoSum {
    private sortArr: number[];
    constructor() {
        this.sortArr = new Array();
    }
    // O(logn)
    add(number: number): void {
        let l = 0, r = this.sortArr.length;
        while (l < r) {
            const mid = l + Math.floor((r - l) / 2);
            if (this.sortArr[mid] < number) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        this.sortArr.splice(l, 0, number);
    }
    
    // O(n)
    find(value: number): boolean {
        let l = 0, r = this.sortArr.length - 1;
    
        while (l < r) {
            const sum = this.sortArr[l] + this.sortArr[r];
            if (sum === value) return true;
            if (sum < value) l++;
            else r--;
        }
    
        // Check if value is twice a number that appears at least twice
        for (let i = 1; i < this.sortArr.length; i++) {
            if (this.sortArr[i] === this.sortArr[i - 1] && this.sortArr[i] * 2 === value) {
            return true;
            }
        }
    
        return false;
    }
}
```

**Approach 2: HashMap / LinkedHashMap**

```typescript
class TwoSum {
    private map: Map<number, number>;
    constructor() {
        this.map = new Map();
    }

    add(number: number): void {
        this.map.set(number, (this.map.get(number) || 0) + 1);
    }

    find(value: number): boolean {
        for (const [k, v] of this.map.entries()) {
            const target = value - k;
            if (target === k) {
                if (this.map.get(target) >= 2) return true;
            } else if (this.map.has(target)) {
                return true;
            }
        }
        return false;
    }
}
```

```java
class TwoSum {
    Map<Integer, Integer> map; // number : count
    /** Initialize your data structure here. */
    public TwoSum() {
        map = new HashMap<>();
    }
    // O(1)    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        map.put(number, map.getOrDefault(number, 0) + 1);
    }
    // O(n)
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        Iterator<Integer> it = map.keySet().iterator();
        while (it.hasNext()) {
            int curt = it.next();
            if ((curt * 2 != value && map.containsKey(value - curt)) 
                || curt * 2 == value && map.get(curt) >= 2) return true;
        }
        return false;
    }
}


class TwoSum {
    LinkedHashMap<Integer, Integer> map; // number : count
    /** Initialize your data structure here. */
    int min, max;
    public TwoSum() {
        map = new LinkedHashMap<>();
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        map.put(number, map.getOrDefault(number, 0) + 1);
        min = Math.min(min, number);
        max = Math.max(max, number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        if (value > max * 2 || value < min * 2) return false;
        Iterator<Integer> it = map.keySet().iterator();
        while (it.hasNext()) {
            int curt = it.next();
            if ((curt * 2 != value && map.containsKey(value - curt)) 
                || curt * 2 == value && map.get(curt) >= 2) return true;
        }
        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */
```

#### [346. Moving Average from Data Stream](https://leetcode.com/problems/moving-average-from-data-stream/)

```java
class MovingAverage {
    Queue<Integer> list;
    int capacity;
    double sum;
    public MovingAverage(int size) {
        this.capacity = size;
        this.list = new LinkedList<>();
        this.sum = 0;
    }
    
    public double next(int val) {
        list.add(val);
        sum += val;
        while (list.size() > this.capacity) {
            sum -= list.poll();
        }
        return sum / (double)list.size();
    }
}
```

#### [359. Logger Rate Limiter](https://leetcode.com/problems/logger-rate-limiter/)

Use a map to store the last time the log is printed.

```java
Map<String, Integer> memo;
/** Initialize your data structure here. */
public Logger() {
    memo = new HashMap<>();
}

/** Returns true if the message should be printed in the given timestamp, otherwise returns false.
    If this method returns false, the message will not be printed.
    The timestamp is in seconds granularity. */
public boolean shouldPrintMessage(int timestamp, String message) {
    if (!memo.containsKey(message)) {
        memo.put(message, timestamp);
        return true;
    } else if (memo.containsKey(message) && memo.get(message) <= timestamp - 10) {
        memo.put(message, timestamp);
        return true;
    } else {
        return false;
    }
}
```

#### [380. Insert Delete GetRandom O(1)](https://leetcode.com/problems/insert-delete-getrandom-o1/)

Use a list to store all numbers, use Hashmap \<number, it is position> to find the position of each number.&#x20;

* insert: add val to the list and map
* remove: check if the val is the last element of the list. If yes, simply remove the last element from list and map. Otherwise, replace val with the last element in the list, and remove the last element.
* getRandom: `return list.get(rand.nextInt(list.size()));`

```java
    List<Integer> list;
    Random rand;
    Map<Integer, Integer> map;
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int valpos = map.get(val);
        if (valpos != list.size() - 1) {
            int lastval = list.get(list.size() - 1);
            list.set(valpos, lastval);
            map.put(lastval, valpos);
        }
        map.remove(val);
        list.remove(list.size() - 1);
        return true;
    }
    
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
```

#### [381. Insert Delete GetRandom O(1) - Duplicates allowed](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/)

Use Map\<Integer, Set\<Integer>> to store val and corresponding positions. When remove, random pick one from the current val set by using iterator, swap with the last position.

{% tabs %}
{% tab title="Java" %}

```java
    List<Integer> list;
    Random rand;
    Map<Integer, Set<Integer>> map;
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        boolean res = !map.containsKey(val);
        map.putIfAbsent(val, new HashSet<>());
        map.get(val).add(list.size());
        list.add(val);
        return res;
    }
    
   public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int valpos = map.get(val).iterator().next();
        map.get(val).remove(valpos);
        int lastval = list.get(list.size() - 1);
        Set<Integer> lastset = map.get(lastval);
        if (valpos != list.size() - 1) {
            lastset.remove(list.size() - 1);
            lastset.add(valpos);
        }
        list.set(valpos, lastval);
        list.remove(list.size() - 1);
        if (map.get(val).isEmpty()) map.remove(val);
        return true;
    }
    
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
```

{% endtab %}

{% tab title="Python" %}

```python
def __init__(self):
    """
    Initialize your data structure here.
    """
    self.list = []
    self.map = collections.defaultdict(set)

def insert(self, val: int) -> bool:
    """
    Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
    """
    res = val not in self.map
    self.map[val].add(len(self.list))
    self.list.append(val)
    return res

def remove(self, val: int) -> bool:
    """
    Removes a value from the collection. Returns true if the collection contained the specified element.
    """
    if self.map[val]:
        inVal, outIndex = self.list[-1], self.map[val].pop()
        self.list[outIndex] = inVal
        if self.map[inVal]:
            self.map[inVal].add(outIndex)
            self.map[inVal].discard(len(self.list) - 1)
        self.list.pop()
        return True
    return False

def getRandom(self) -> int:
    """
    Get a random element from the collection.
    """
    return random.choice(self.list)
```

{% endtab %}
{% endtabs %}

#### [155. Min Stack](https://leetcode.com/problems/min-stack/)

When new value <= min, add min to the stack then add new value. When pop, check if the popped element equals to min, if yes, pop again.

{% tabs %}
{% tab title="Java" %}

```java
int min;
Stack<Integer> stack;
public MinStack() {
    min = Integer.MAX_VALUE;
    stack = new Stack<>();
}

public void push(int x) {
    if (x <= min) {
        stack.add(min);
        min = x;
    }
    stack.add(x);
}

public void pop() {
    int pop = stack.pop();
    if (pop == min) {
        min = stack.pop();
    }
}

public int top() {
    return stack.peek();
}

public int getMin() {
    return min;
}
```

{% endtab %}

{% tab title="Java (Two Stacks)" %}

```java
/** initialize your data structure here. */
Stack<Integer> stack;
Stack<Integer> mstack;
public MinStack() {
    stack = new Stack<>();
    mstack = new Stack<>();
}

public void push(int x) {
    stack.push(x);
    if (mstack.isEmpty() || x <= mstack.peek()) {
        mstack.push(x);
    }
}

public void pop() {
    int pop = stack.pop();
    if (!mstack.isEmpty() && pop == mstack.peek()) {
        mstack.pop();
    }
}

public int top() {
    return stack.peek();
}

public int getMin() {
    return mstack.peek();
}
```

{% endtab %}

{% tab title="TypeScript (Two Stacks)" %}

```typescript
class MinStack {
    private stack: number[];
    private minStack: number[];

    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    push(val: number): void {
        this.stack.push(val);
        if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }

    pop(): void {
        const val:number = this.stack.pop();
        if (val === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
    }

    top(): number {
        return this.stack[this.stack.length - 1];
    }

    getMin(): number {
        return this.minStack[this.minStack.length - 1];
    }
}
```

{% endtab %}
{% endtabs %}

#### [622. Design Circular Queue](https://leetcode.com/problems/design-circular-queue/)

Use an array of size k to store the elements, a `start` and `end` to set the boundary and size to maintain the queue size.&#x20;

```java
    int[] arr;
    int start, end, size;
    public MyCircularQueue(int k) {
        arr = new int[k];
        start = 0;
        end = -1;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull()) return false;
        end = (end + 1) % arr.length;
        arr[end] = value;
        size++;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty()) return false;
        start = (start + 1) % arr.length;
        size--;
        return true;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        return isEmpty() ? -1 : arr[start];
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        return isEmpty() ? -1 : arr[end];
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return size == arr.length;
    }
```

#### [706. Design HashMap](https://leetcode.com/problems/design-hashmap/)

Clarifications:

* For simplicity, are the keys integers only?
* For collision resolution, can we use chaining?
* Do we have to worry about load factors?
* Can we assume inputs are valid or do we have to validate them?
* Can we assume this fits memory?

Method: Use a list of buckets to store the node. Each bucket is a linked-list:

* int getIndex(int key):  get index in the list based on the provide key
* ListNode getPrev(int index, int key): get the last node with the right key for insertion or deletion. &#x20;

Follow-up:

* What if there are too many nodes in one bucket? Load factor + rehashing or use Red-Black tree on each node
* What if there key is a String? Multiply ASCII value of each character and MOD by 31 to get the index.

```java
class MyHashMap {
    ListNode[] list;
    int SIZE = 10000;
    public MyHashMap() {
        list = new ListNode[SIZE];
    }
    
    private int getIndex(int key) {
        return Integer.hashCode(key) % SIZE;
    }
    
    private ListNode getPrev(int index, int key) {
        if (list[index] == null) {
            list[index] = new ListNode(-1, -1);
            return list[index];
        }
        ListNode prev = list[index];
        while (prev.next != null && prev.next.key != key) {
            prev = prev.next;
        }
        return prev;
    }
    
    public void put(int key, int value) {
        int index = getIndex(key);
        ListNode prev = getPrev(index, key);
        if (prev.next == null) {
            prev.next = new ListNode(key, value);
        } else {
            prev.next.val = value;
        }
    }
    
    public int get(int key) {
        int index = getIndex(key);
        ListNode prev = getPrev(index, key);
        if (prev.next == null) {
            return -1;
        }
        return prev.next.val;
    }
    
    public void remove(int key) {
        int index = getIndex(key);
        ListNode prev = getPrev(index, key);
        if (prev.next == null) {
            return;
        }
        prev.next = prev.next.next;
    }
    
    class ListNode {
        int val, key;
        ListNode next;
        ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}
```

#### [146. LRU Cache](https://leetcode.com/problems/lru-cache/)

```java
class LRUCache {
    Node head, tail;
    int size, capacity;
    Map<Integer, Node> map;
    public LRUCache(int capacity) {
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
        this.capacity = capacity;
        map = new HashMap<>();
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node curt = map.get(key);
            removeNode(curt);
            addToFirst(curt);
            return curt.value;
        } 
        return -1;
    }
    
    public void put(int key, int value) {
        Node curt = null;
        if (map.containsKey(key)) {
            curt = map.get(key);
            curt.value = value;
            removeNode(curt);
        } else {
            curt = new Node(key, value);
            if (++size > capacity) {
                Node temp = tail.prev;
                removeNode(temp);
                map.remove(temp.key);
            }
        }
        addToFirst(curt);
        map.put(key, curt);
    }
    
    private void removeNode(Node curt) {
        Node nxt = curt.next;
        Node pre = curt.prev;
        pre.next = nxt;
        nxt.prev = pre;
        curt.prev = null;
        curt.next = null;
    }
    
    private void addToFirst(Node curt) {
        Node sec = head.next;
        head.next = curt;
        curt.prev = head;
        curt.next = sec;
        sec.prev = curt;
    }
    
    class Node {
        int key, value;
        Node prev, next;
        Node(int key, int val) {
            this.key = key;
            this.value = val;
        }
    }
}
```

#### [460. LFU Cache](https://leetcode.com/problems/lfu-cache/)

```java
class LFUCache {
  Map<Integer, DoublyLinkedList> freqListMap;
  Map<Integer, ListNode> keyNodeMap;
  int size, capacity, minFrequency;
  public LFUCache(int capacity) {
    this.freqListMap = new HashMap<>();
    this.keyNodeMap = new HashMap<>();
    this.size = 0;
    this.capacity = capacity;
    this.minFrequency = 0;
  }

  public int get(int key) {
    ListNode curt = keyNodeMap.get(key);
    if (curt == null) {
      return -1;
    }
    updateNode(curt);
    return curt.val;
  }

  public void put(int key, int value) {
    if (capacity == 0) return;
    if (keyNodeMap.containsKey(key)) {
      ListNode curt = keyNodeMap.get(key);
      curt.val = value;
      updateNode(curt);
    } else {
      size++;
      if (size > capacity) {
        DoublyLinkedList minList = freqListMap.get(minFrequency);
        ListNode deleteNode = minList.popLast();
        keyNodeMap.remove(deleteNode.key);
        size--;
      }
      minFrequency = 1;
      ListNode curt = new ListNode(value);
      curt.key = key;
      DoublyLinkedList ddl = freqListMap.getOrDefault(
          curt.freq, new DoublyLinkedList());
      ddl.addToFirst(curt);
      keyNodeMap.put(key, curt);
      freqListMap.put(curt.freq, ddl);
    }
  }

  private void updateNode(ListNode curt) {
    int curtFeq = curt.freq;
    DoublyLinkedList ddl = freqListMap.get(curtFeq);
    ddl.popNode(curt);

    if (curtFeq == minFrequency && ddl.emptyList()) {
      minFrequency++;
    }
    curt.freq += 1;

    DoublyLinkedList nextDDL = freqListMap.getOrDefault(
        curtFeq + 1, new DoublyLinkedList());
    nextDDL.addToFirst(curt);
    freqListMap.put(curtFeq + 1, nextDDL);
  }

  class DoublyLinkedList {
    ListNode head, tail;
    DoublyLinkedList() {
      this.head = new ListNode(-1);
      this.tail = new ListNode(-1);
      head.next = tail;
      tail.prev = head;
    }
    public void addToFirst(ListNode curtNode) {
      ListNode next = head.next;
      curtNode.next = next;
      next.prev = curtNode;
      head.next = curtNode;
      curtNode.prev = head;
    }

    public ListNode popNode(ListNode node) {
      ListNode next = node.next;
      node.prev.next = next;
      next.prev = node.prev;
      node.prev = null;
      node.next = null;
      return node;
    }

    public ListNode popLast() {
      ListNode last = tail.prev;
      return popNode(last);
    }

    private boolean emptyList() {
      return head.next == tail && tail.prev == head;
    }
  }

  class ListNode {
    ListNode prev, next;
    int freq;
    int val;
    int key;
    ListNode(int val) {
      this.val = val;
      this.freq = 1;
    }
  }
}
```

#### [716. Max Stack](https://leetcode.com/problems/max-stack/)

Solution1: two stacks

Solution2: Use a LinkedList and TreeMap to store value.&#x20;

{% tabs %}
{% tab title="Solution1" %}

```java
class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> maxStack;

    public MaxStack() {
        stack = new Stack();
        maxStack = new Stack();
    }

    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        stack.push(x);
    }

    public int pop() {
        maxStack.pop();
        return stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return maxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}
```

{% endtab %}

{% tab title="Solution2" %}

```java
    TreeMap<Integer, LinkedList<ListNode>> map;
    ListNode head, tail;
    /** initialize your data structure here. */
    public MaxStack() {
        map = new TreeMap<>();
        head = new ListNode(-1);
        tail = new ListNode(-1);
        head.next = tail;
        tail.prev = head;
    }
    
    private void addToFirst(ListNode node) {
        map.putIfAbsent(node.val, new LinkedList<>());
        map.get(node.val).add(node);
        ListNode next = head.next;
        head.next = node;
        node.prev = head;
        node.next = next;
        next.prev = node;
    }
    
    private void removeNode(ListNode node) {
        map.get(node.val).removeLast();
        if (map.get(node.val).size() == 0) map.remove(node.val);
        ListNode prev = node.prev;
        ListNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }
    
    public void push(int x) {
        ListNode curt = new ListNode(x);
        addToFirst(curt);
    }
    
    public int pop() {
        if (head.next == tail) return -1;
        ListNode pop = map.get(head.next.val).peekLast();
        removeNode(pop);
        return pop.val;
    }
    
    public int top() {
        return head.next == tail ? -1 : head.next.val;
    }
    
    public int peekMax() {
        return map.isEmpty() ? -1 : map.lastKey();
    }
    
    public int popMax() {
        int maxKey = map.lastKey();
        removeNode(map.get(maxKey).peekLast());
        return maxKey;
    }
    
    class ListNode {
        int val;
        ListNode prev, next;
        ListNode(int val) {
            this.val = val;
        }
    }
```

{% endtab %}
{% endtabs %}

#### [432. All O\`one Data Structure](https://leetcode.com/problems/all-oone-data-structure/)

This is similar to LFU. Each bucket is has a pre bucket and a next buck, also has a keySet to store all keys in the frequency, and the frequency itself. Build two maps:

* Key: Count Value: Bucket
* Key: String Key Value: Count &#x20;

```java
    // maintain a doubly linked list of Buckets
    private Bucket head;
    private Bucket tail;
    // for accessing a specific Bucket among the Bucket list in O(1) time
    private Map<Integer, Bucket> countBucketMap;
    // keep track of count of keys
    private Map<String, Integer> keyCountMap;

    // each Bucket contains all the keys with the same count
    private class Bucket {
        int count;
        Set<String> keySet;
        Bucket next;
        Bucket pre;
        public Bucket(int cnt) {
            count = cnt;
            keySet = new HashSet<>();
        }
    }

    /** Initialize your data structure here. */
    public AllOne() {
        head = new Bucket(Integer.MIN_VALUE);
        tail = new Bucket(Integer.MAX_VALUE);
        head.next = tail;
        tail.pre = head;
        countBucketMap = new HashMap<>();
        keyCountMap = new HashMap<>();
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (keyCountMap.containsKey(key)) {
            changeKey(key, 1);
            return;
        } 
        keyCountMap.put(key, 1);
        if (head.next.count != 1) {
            addBucketAfter(new Bucket(1), head);
        }
        head.next.keySet.add(key);
        countBucketMap.put(1, head.next);
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (keyCountMap.containsKey(key)) {
            int count = keyCountMap.get(key);
            if (count == 1) {
                removeKeyFromBucket(countBucketMap.get(1), key);   
                keyCountMap.remove(key);
            } else {
                changeKey(key, -1);
            }
        }
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return tail.pre == head ? "" : (String) tail.pre.keySet.iterator().next();
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        return head.next == tail ? "" : (String) head.next.keySet.iterator().next();        
    }
    
  // helper function to make change on given key according to offset
    private void changeKey(String key, int offset) {
        int count = keyCountMap.get(key);
        keyCountMap.put(key, count + offset);
        Bucket curBucket = countBucketMap.get(count);
        Bucket newBucket;
        if (countBucketMap.containsKey(count + offset)) {
            // target Bucket already exists
            newBucket = countBucketMap.get(count + offset);
        } else {
            // add new Bucket
            newBucket = new Bucket(count + offset);
            countBucketMap.put(count + offset, newBucket);
            addBucketAfter(newBucket, offset == 1 ? curBucket : curBucket.pre);
        }
        newBucket.keySet.add(key);
        removeKeyFromBucket(curBucket, key);
    }
    
    private void removeKeyFromBucket(Bucket bucket, String key) {
        bucket.keySet.remove(key);
        if (bucket.keySet.size() == 0) {
            removeBucketFromList(bucket);
            countBucketMap.remove(bucket.count);
        }
    }
    
    private void removeBucketFromList(Bucket bucket) {
        bucket.pre.next = bucket.next;
        bucket.next.pre = bucket.pre;
        bucket.next = null;
        bucket.pre = null;
    }
    
    // add newBucket after preBucket
    private void addBucketAfter(Bucket newBucket, Bucket preBucket) {
        newBucket.pre = preBucket;
        newBucket.next = preBucket.next;
        preBucket.next.pre = newBucket;
        preBucket.next = newBucket;
    }
```

#### [981. Time Based Key-Value Store](https://leetcode.com/problems/time-based-key-value-store/)

BinarySearch version

```java
    Map<String, List<Pair>> map;
    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(new Pair(timestamp, value));
    }
    
    public String get(String key, int timestamp) {
        List<Pair> list = map.get(key);
        if (list == null || list.get(0).timestamp > timestamp) return "";
        if (list.get(list.size() - 1).timestamp < timestamp) return list.get(list.size() - 1).value;
        return binarySearch(list, timestamp);
    }
    
       public String binarySearch(List<Pair> list, int timestamp) {
        int left=0, right = list.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int ts = list.get(mid).timestamp;
            if (timestamp == ts) {
                return list.get(mid).value;
            } else if (timestamp > ts) {
                if (mid + 1 < list.size() && timestamp < list.get(mid+1).timestamp) {
                    return list.get(mid).value;
                } else {
                    left = mid + 1;
                }
            } else {
                right = mid -1;
            }
        }
        return  "";
    }
    
    class Pair {
        int timestamp;
        String value;
        Pair(int t, String v) {
            this.timestamp = t;
            this.value = v;
        }
    }
```

TreeMap version

```java
Map<String,TreeMap<Integer, String>> map;
    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
        
    }
    
    public String get(String key, int timestamp) {
        if(map.containsKey(key)){
            TreeMap<Integer, String> m = map.get(key);
            Integer val = m.floorKey(timestamp);
            if(val!=null)
              return  m.get(val);
        }
        return "";
    }
```

#### [855. Exam Room](https://leetcode.com/problems/exam-room/)

Store all seats in a TreeMap, loop over it to detect the largest gap.

```java
class ExamRoom {
    TreeSet<Integer> set;
    int N;
    public ExamRoom(int N) {
        set = new TreeSet<>();
        this.N = N;
    }
    
    public int seat() {
        if (set.isEmpty()) {
            set.add(0);
            return 0;
        }
        int maxInterval = set.first();
        int pre = set.first(), seat = 0;
        for (int curt : set) {
            if ((curt - pre) / 2 > maxInterval) {
                maxInterval = (curt - pre) / 2;
                seat = (curt + pre) / 2;
            }
            pre = curt;
        }
        if (N - pre - 1 > maxInterval) {
            seat = N - 1;
        }
        set.add(seat);
        return seat;
    }
    
    public void leave(int p) {
        set.remove(p);
    }
}
```

#### [1472. Design Browser History](https://leetcode.com/problems/design-browser-history/)

```cpp
class BrowserHistory {
    /**
    4. linkedin.com
    3. youtube.com
    2. facebook.com
    1. google.com
    
    */

public:
    vector<string> list;
    int index;
    BrowserHistory(string homepage) {
        list.push_back(homepage);
        index = 0;
    }
    
    void visit(string url) {
        list.resize(index + 1);
        list.push_back(url);
        index++;
    }
    
    string back(int steps) {
        index = max(0, index - steps);
        return list[index];
    }
    
    string forward(int steps) {
        index = min((int)list.size() - 1, index + steps);
        return list[index];
    }
};

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory* obj = new BrowserHistory(homepage);
 * obj->visit(url);
 * string param_2 = obj->back(steps);
 * string param_3 = obj->forward(steps);
 */
```

[1169. Invalid Transactions](https://leetcode.com/problems/invalid-transactions/)

```java
import java.util.*;

class Solution {
    class Transaction {
        String raw;
        String name;
        int time;
        int amount;
        String city;

        Transaction(String s) {
            raw = s;
            String[] parts = s.split(",");
            name = parts[0];
            time = Integer.parseInt(parts[1]);
            amount = Integer.parseInt(parts[2]);
            city = parts[3];
        }
    }

    public List<String> invalidTransactions(String[] transactions) {
        int n = transactions.length;
        Transaction[] txns = new Transaction[n];
        boolean[] invalid = new boolean[n];

        // Parse all transactions and group them by name
        Map<String, List<Integer>> nameToIndices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            txns[i] = new Transaction(transactions[i]);
            nameToIndices
                .computeIfAbsent(txns[i].name, k -> new ArrayList<>())
                .add(i);

            // Rule 1: amount > 1000
            if (txns[i].amount > 1000) {
                invalid[i] = true;
            }
        }

        // Rule 2: check conflicting transactions by name
        for (Map.Entry<String, List<Integer>> entry : nameToIndices.entrySet()) {
            List<Integer> indices = entry.getValue();
            for (int i : indices) {
                Transaction t1 = txns[i];
                for (int j : indices) {
                    if (i == j) continue;
                    Transaction t2 = txns[j];
                    if (!t1.city.equals(t2.city) && Math.abs(t1.time - t2.time) <= 60) {
                        invalid[i] = true;
                        break;
                    }
                }
            }
        }

        List<String> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (invalid[i]) {
                result.add(txns[i].raw);
            }
        }

        return result;
    }
}

```

#### [2408. Design SQL](https://leetcode.com/problems/design-sql/)

```cpp
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

class SQL {
    map<string, int> tableMap;
    map<string, int> columnCount;
    map<string, int> nextRowId;
    vector<vector<pair<int, vector<string>>>> tables;

public:
    SQL(vector<string>& names, vector<int>& columns) {
        int n = names.size();
        tables.resize(n);
        for (int i = 0; i < n; ++i) {
            tableMap[names[i]] = i;
            columnCount[names[i]] = columns[i];
            nextRowId[names[i]] = 1;
        }
    }

    bool ins(string name, vector<string> row) {
        if (tableMap.find(name) == tableMap.end()) return false;
        if (row.size() != columnCount[name]) return false;

        int tableId = tableMap[name];
        int rowId = nextRowId[name]++;
        tables[tableId].push_back({rowId, row});
        return true;
    }

    void rmv(string name, int rowId) {
        if (tableMap.find(name) == tableMap.end()) return;
        int tableId = tableMap[name];
        auto& table = tables[tableId];
        for (auto it = table.begin(); it != table.end(); ++it) {
            if (it->first == rowId) {
                table.erase(it);
                break;
            }
        }
    }

    string sel(string name, int rowId, int columnId) {
        if (tableMap.find(name) == tableMap.end()) return "<null>";
        int tableId = tableMap[name];
        auto& table = tables[tableId];
        for (auto& [rid, row] : table) {
            if (rid == rowId) {
                if (columnId < 1 || columnId > row.size()) return "<null>";
                return row[columnId - 1];
            }
        }
        return "<null>";
    }

    vector<string> exp(string name) {
        if (tableMap.find(name) == tableMap.end()) return {};
        int tableId = tableMap[name];
        auto& table = tables[tableId];
        vector<string> result;
        for (auto& [rowId, row] : table) {
            vector<string> outputRow;
            outputRow.push_back(to_string(rowId));
            outputRow.insert(outputRow.end(), row.begin(), row.end());
            result.push_back(joinWithComma(outputRow));
        }
        return result;
    }

private:
    string joinWithComma(const vector<string>& vec) {
        ostringstream oss;
        for (size_t i = 0; i < vec.size(); ++i) {
            if (i > 0) oss << ",";
            oss << vec[i];
        }
        return oss.str();
    }
};

```

#### [1206. Design Skiplist](https://leetcode.com/problems/design-skiplist/)

{% embed url="<https://mp.weixin.qq.com/s?__biz=MzUzMDQxNTI4OQ==&mid=2247484374&idx=1&sn=5ca5df5659f1860847f55129b25465e1&chksm=fa536800cd24e11674dace66861f7411f7c7c0fddce5abee884555875acfa40efaed908913bc&token=1817182455&lang=zh_CN#rd>" %}

**Mine Sweeper**

```java
import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Minesweeper minesweeper = new Minesweeper(5, 5, 4);
    minesweeper.print();

    System.out.println("\nClick (0, 0)");
    minesweeper.click(0, 0);
    minesweeper.print();

    System.out.println("\nClick (0, 4)");
    minesweeper.click(0, 4);
    minesweeper.print();

    System.out.println("\nClick (2, 0)");
    minesweeper.click(2, 0);
    minesweeper.print();
  }

  static class Minesweeper {
    String[][] grid;      // What user sees
    String[][] mineGrid;  // Actual state with mine counts
    int rows, cols;
    int[][] dirs = {
      {1, 0}, {0, 1}, {-1, 0}, {0, -1},
      {1, 1}, {-1, 1}, {1, -1}, {-1, -1}
    };

    Minesweeper(int rows, int cols, int mineCount) {
      this.rows = rows;
      this.cols = cols;
      this.grid = new String[rows][cols];
      this.mineGrid = new String[rows][cols];
      for (String[] r : grid) Arrays.fill(r, "-");
      for (String[] r : mineGrid) Arrays.fill(r, "-");
      generateMines(mineCount);
      preProcess();
    }

    public void click(int x, int y) {
      if (!inbound(x, y) || !grid[x][y].equals("-")) return;

      if (mineGrid[x][y].equals("X")) {
        System.out.println("Hit Mine, Game Over");
        // Reveal all mines
        for (int i = 0; i < rows; i++) {
          for (int j = 0; j < cols; j++) {
            if (mineGrid[i][j].equals("X")) {
              grid[i][j] = "X";
            }
          }
        }
        return;
      }

      // DFS to reveal all connected 0-cells and borders
      dfsReveal(x, y);
    }

    private void dfsReveal(int x, int y) {
      if (!inbound(x, y) || !grid[x][y].equals("-")) return;
      String val = mineGrid[x][y];
      grid[x][y] = val;

      if (val.equals("0")) {
        for (int[] d : dirs) {
          dfsReveal(x + d[0], y + d[1]);
        }
      }
    }

    public void print() {
      System.out.println("User Grid:");
      for (String[] row : grid) {
        System.out.println(Arrays.toString(row));
      }

      System.out.println("Mine Grid:");
      for (String[] row : mineGrid) {
        System.out.println(Arrays.toString(row));
      }
    }

    private void generateMines(int count) {
      Random rand = new Random();
      int placed = 0;
      while (placed < count) {
        int x = rand.nextInt(rows);
        int y = rand.nextInt(cols);
        if (mineGrid[x][y].equals("-")) {
          mineGrid[x][y] = "X";
          placed++;
        }
      }
    }

    private void preProcess() {
      for (int x = 0; x < rows; x++) {
        for (int y = 0; y < cols; y++) {
          if (mineGrid[x][y].equals("X")) continue;

          int count = 0;
          for (int[] d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (inbound(nx, ny) && mineGrid[nx][ny].equals("X")) {
              count++;
            }
          }
          mineGrid[x][y] = String.valueOf(count);
        }
      }
    }

    private boolean inbound(int x, int y) {
      return x >= 0 && x < rows && y >= 0 && y < cols;
    }
  }
}

```

[631. Design Excel Sum Formula](https://leetcode.com/problems/design-excel-sum-formula/)

```cpp
class Excel {
public:
    int table[27][27]; // fixed-size table for up to 26 columns (A-Z) and 27 rows
    map<pair<int, int>, vector<pair<int, int>>> graph;

    Excel(int height, char width) {
        memset(table, 0, sizeof(table));
    }

    void set(int row, char column, int val) {
        int x = row, y = column - 'A';
        table[x][y] = val;
        graph[{x, y}] = {}; // clear formula dependencies
    }

    int get(int row, char column) {
        int x = row, y = column - 'A';
        map<pair<int, int>, int> memo;
        return dfs(x, y, memo);
    }

    int sum(int row, char column, vector<string> numbers) {
        int x = row, y = column - 'A';
        graph[{x, y}].clear(); // reset existing formula
        table[x][y] = 0;        // reset value

        for (const string& num : numbers) {
            vector<int> n = split(num); // returns [col1, row1] or [col1, row1, col2, row2]

            if (n.size() == 2) {
                graph[{x, y}].emplace_back(n[1], n[0]);
            } else {
                for (int i = n[1]; i <= n[3]; ++i) {
                    for (int j = n[0]; j <= n[2]; ++j) {
                        graph[{x, y}].emplace_back(i, j);
                    }
                }
            }
        }

        map<pair<int, int>, int> memo;
        return dfs(x, y, memo);
    }

private:
    int dfs(int i, int j, map<pair<int, int>, int>& memo) {
        pair<int, int> key = {i, j};
        if (memo.count(key)) return memo[key];

        int ans = table[i][j];
        for (const auto& [ni, nj] : graph[key]) {
            ans += dfs(ni, nj, memo);
        }

        memo[key] = ans;
        return ans;
    }

    vector<int> split(const string& s) {
        vector<int> res;
        string number;
        for (char c : s) {
            if (isalpha(c)) {
                if (!number.empty()) {
                    res.push_back(stoi(number));
                    number.clear();
                }
                res.push_back(c - 'A'); // Convert letter to 0-based column index
            } else if (isdigit(c)) {
                number += c;
            } else if (c == ':' && !number.empty()) {
                res.push_back(stoi(number));
                number.clear();
            }
        }
        if (!number.empty()) {
            res.push_back(stoi(number));
        }
        return res;
    }
};

```

#### Config support Cache

Design a simple caching mechanism that supports configuration. An example of configuration would be the ability to provide different eviction policies, e.g. least recently used, least frequently used, most memory consuming, etc. Another example of configuration might be to specify the type of storage used, e.g. local heap, local disc, remote, etc.

{% tabs %}
{% tab title="Simple Solution" %}

```java
import java.util.*;

interface Configuration {
    void add(String key, String value);
    Optional<String> evict();
}

public class Cache {
    private final Map<String, String> cacheMap = new HashMap<>();
    private final Map<String, Integer> timeUpdatedMap = new HashMap<>();
    private final Map<String, Integer> frequencyMap = new HashMap<>();
    private final Map<String, Integer> memoryMap = new HashMap<>();

    private Configuration configuration;
    private int capacity;
    private long memoryLimit;
    private long memorySize = 0;

    enum Config {
        LRU, LFU, MOST_MEMORY, LEAST_MEMORY
    }

    public Cache(String rule, int capacity, long memoryLimit) {
        this.capacity = capacity;
        this.memoryLimit = memoryLimit;

        // Create eviction strategy with shared maps
        Config configEnum = Config.valueOf(rule);
        switch (configEnum) {
            case LRU -> configuration = new LRU(cacheMap, timeUpdatedMap);
            case LFU -> configuration = new LFU(cacheMap, frequencyMap);
            case MOST_MEMORY -> configuration = new MostMemory(cacheMap, memoryMap);
            case LEAST_MEMORY -> configuration = new LeastMemory(cacheMap, memoryMap);
        }
    }

    public void add(String key, String val) {
        int size = getMemorySize(val);
        if (cacheMap.size() == capacity || memorySize + size > memoryLimit) {
            configuration.evict().ifPresent(evictedKey -> {
                memorySize -= memoryMap.getOrDefault(evictedKey, 0);
                cacheMap.remove(evictedKey);
                memoryMap.remove(evictedKey);
                timeUpdatedMap.remove(evictedKey);
                frequencyMap.remove(evictedKey);
            });
        }

        memorySize += size;
        memoryMap.put(key, size);
        timeUpdatedMap.put(key, (int)(System.currentTimeMillis() / 1000));
        frequencyMap.put(key, frequencyMap.getOrDefault(key, 0) + 1);
        configuration.add(key, val);
    }

    public Optional<String> evict() {
        return configuration.evict();
    }

    private int getMemorySize(String val) {
        return val == null ? 0 : val.length() * 2; // example approximation
    }

    // ---- Eviction Strategies ----

    static class LRU implements Configuration {
        private final Map<String, String> cacheMap;
        private final Map<String, Integer> timeUpdatedMap;

        public LRU(Map<String, String> cacheMap, Map<String, Integer> timeUpdatedMap) {
            this.cacheMap = cacheMap;
            this.timeUpdatedMap = timeUpdatedMap;
        }

        @Override
        public void add(String key, String val) {
            cacheMap.put(key, val);
            timeUpdatedMap.put(key, (int)(System.currentTimeMillis() / 1000));
        }

        @Override
        public Optional<String> evict() {
            return timeUpdatedMap.entrySet().stream()
                .min(Comparator.comparingInt(Map.Entry::getValue))
                .map(Map.Entry::getKey);
        }
    }

    static class LFU implements Configuration {
        private final Map<String, String> cacheMap;
        private final Map<String, Integer> frequencyMap;

        public LFU(Map<String, String> cacheMap, Map<String, Integer> frequencyMap) {
            this.cacheMap = cacheMap;
            this.frequencyMap = frequencyMap;
        }

        @Override
        public void add(String key, String val) {
            cacheMap.put(key, val);
            frequencyMap.put(key, frequencyMap.getOrDefault(key, 0) + 1);
        }

        @Override
        public Optional<String> evict() {
            return frequencyMap.entrySet().stream()
                .min(Comparator.comparingInt(Map.Entry::getValue))
                .map(Map.Entry::getKey);
        }
    }

    static class MostMemory implements Configuration {
        private final Map<String, String> cacheMap;
        private final Map<String, Integer> memoryMap;

        public MostMemory(Map<String, String> cacheMap, Map<String, Integer> memoryMap) {
            this.cacheMap = cacheMap;
            this.memoryMap = memoryMap;
        }

        @Override
        public void add(String key, String val) {
            cacheMap.put(key, val);
            memoryMap.put(key, val.length() * 2);
        }

        @Override
        public Optional<String> evict() {
            return memoryMap.entrySet().stream()
                .max(Comparator.comparingInt(Map.Entry::getValue))
                .map(Map.Entry::getKey);
        }
    }

    static class LeastMemory implements Configuration {
        private final Map<String, String> cacheMap;
        private final Map<String, Integer> memoryMap;

        public LeastMemory(Map<String, String> cacheMap, Map<String, Integer> memoryMap) {
            this.cacheMap = cacheMap;
            this.memoryMap = memoryMap;
        }

        @Override
        public void add(String key, String val) {
            cacheMap.put(key, val);
            memoryMap.put(key, val.length() * 2);
        }

        @Override
        public Optional<String> evict() {
            return memoryMap.entrySet().stream()
                .min(Comparator.comparingInt(Map.Entry::getValue))
                .map(Map.Entry::getKey);
        }
    }
}

```

{% endtab %}

{% tab title="Optimized Solution" %}

```java
import java.util.*;

// CacheEntry to encapsulate metadata
class CacheEntry {
    String value;
    long lastAccessTime;
    int frequency;
    int memorySize;

    public CacheEntry(String value) {
        this.value = value;
        this.lastAccessTime = System.currentTimeMillis();
        this.frequency = 1;
        this.memorySize = value.length() * 2; // rough estimate
    }
}

interface EvictionPolicy {
    void onPut(String key, CacheEntry entry);
    void onGet(String key);
    Optional<String> evictKey();
    void onRemove(String key);
}

// LRU using LinkedHashMap for access order
class LRUPolicy implements EvictionPolicy {
    private final LinkedHashMap<String, Boolean> orderMap = new LinkedHashMap<>(16, 0.75f, true);

    @Override
    public void onPut(String key, CacheEntry entry) {
        orderMap.put(key, true);
    }

    @Override
    public void onGet(String key) {
        orderMap.get(key); // triggers access-order
    }

    @Override
    public Optional<String> evictKey() {
        Iterator<String> it = orderMap.keySet().iterator();
        return it.hasNext() ? Optional.of(it.next()) : Optional.empty();
    }

    @Override
    public void onRemove(String key) {
        orderMap.remove(key);
    }
}

// LFU using frequency buckets
class LFUPolicy implements EvictionPolicy {
    private final Map<String, Integer> freqMap = new HashMap<>();
    private final TreeMap<Integer, LinkedHashSet<String>> freqBuckets = new TreeMap<>();

    @Override
    public void onPut(String key, CacheEntry entry) {
        freqMap.put(key, 1);
        freqBuckets.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key);
    }

    @Override
    public void onGet(String key) {
        int freq = freqMap.getOrDefault(key, 0);
        if (freq > 0) {
            freqBuckets.get(freq).remove(key);
            if (freqBuckets.get(freq).isEmpty()) freqBuckets.remove(freq);
        }
        freqMap.put(key, freq + 1);
        freqBuckets.computeIfAbsent(freq + 1, x -> new LinkedHashSet<>()).add(key);
    }

    @Override
    public Optional<String> evictKey() {
        if (freqBuckets.isEmpty()) return Optional.empty();
        Map.Entry<Integer, LinkedHashSet<String>> first = freqBuckets.firstEntry();
        String key = first.getValue().iterator().next();
        return Optional.of(key);
    }

    @Override
    public void onRemove(String key) {
        int freq = freqMap.getOrDefault(key, 0);
        freqBuckets.getOrDefault(freq, new LinkedHashSet<>()).remove(key);
        if (freqBuckets.containsKey(freq) && freqBuckets.get(freq).isEmpty()) {
            freqBuckets.remove(freq);
        }
        freqMap.remove(key);
    }
}

// Memory-aware eviction
class MostMemoryPolicy implements EvictionPolicy {
    private final TreeMap<Integer, Set<String>> memoryMap = new TreeMap<>(Collections.reverseOrder());
    private final Map<String, Integer> keyMemoryMap = new HashMap<>();

    @Override
    public void onPut(String key, CacheEntry entry) {
        int mem = entry.memorySize;
        memoryMap.computeIfAbsent(mem, x -> new HashSet<>()).add(key);
        keyMemoryMap.put(key, mem);
    }

    @Override
    public void onGet(String key) {}

    @Override
    public Optional<String> evictKey() {
        for (Set<String> keys : memoryMap.values()) {
            if (!keys.isEmpty()) return Optional.of(keys.iterator().next());
        }
        return Optional.empty();
    }

    @Override
    public void onRemove(String key) {
        Integer mem = keyMemoryMap.get(key);
        if (mem != null) {
            Set<String> keys = memoryMap.get(mem);
            if (keys != null) keys.remove(key);
            if (keys != null && keys.isEmpty()) memoryMap.remove(mem);
            keyMemoryMap.remove(key);
        }
    }
}

public class Cache {
    private final Map<String, CacheEntry> store = new HashMap<>();
    private final EvictionPolicy policy;
    private final int capacity;
    private long memoryLimit;
    private long currentMemory = 0;

    public Cache(EvictionPolicy policy, int capacity, long memoryLimit) {
        this.policy = policy;
        this.capacity = capacity;
        this.memoryLimit = memoryLimit;
    }

    public void put(String key, String value) {
        int size = value.length() * 2;
        if (store.containsKey(key)) {
            currentMemory -= store.get(key).memorySize;
            policy.onRemove(key);
            store.remove(key);
        }

        while ((store.size() >= capacity || currentMemory + size > memoryLimit) && !store.isEmpty()) {
            policy.evictKey().ifPresent(evictedKey -> {
                currentMemory -= store.get(evictedKey).memorySize;
                store.remove(evictedKey);
                policy.onRemove(evictedKey);
            });
        }

        CacheEntry entry = new CacheEntry(value);
        store.put(key, entry);
        currentMemory += size;
        policy.onPut(key, entry);
    }

    public Optional<String> get(String key) {
        CacheEntry entry = store.get(key);
        if (entry == null) return Optional.empty();
        entry.lastAccessTime = System.currentTimeMillis();
        entry.frequency++;
        policy.onGet(key);
        return Optional.of(entry.value);
    }

    public boolean contains(String key) {
        return store.containsKey(key);
    }

    public int size() {
        return store.size();
    }

    public long memoryUsed() {
        return currentMemory;
    }
}

// Example usage
class CacheTest {
    public static void main(String[] args) {
        Cache lruCache = new Cache(new LRUPolicy(), 3, 1000);
        lruCache.put("a", "apple");
        lruCache.put("b", "banana");
        lruCache.put("c", "carrot");
        lruCache.get("a");
        lruCache.put("d", "dragonfruit"); // should evict b

        System.out.println(lruCache.contains("b")); // false
        System.out.println(lruCache.contains("a")); // true
    }
}

```

{% endtab %}
{% endtabs %}

[1396. Design Underground System](https://leetcode.com/problems/design-underground-system/)

```java
class UndergroundSystem {
    private Map<String, int[]> tripStats; // key -> [totalTime, tripCount]
    private Map<Integer, Pair<String, Integer>> checkIns;

    public UndergroundSystem() {
        tripStats = new HashMap<>();
        checkIns = new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        checkIns.put(id, new Pair<>(stationName, t));
    }

    public void checkOut(int id, String endStation, int t) {
        Pair<String, Integer> checkInInfo = checkIns.remove(id);
        String startStation = checkInInfo.first;
        int startTime = checkInInfo.second;

        String key = startStation + "_" + endStation;
        int travelTime = t - startTime;

        tripStats.putIfAbsent(key, new int[2]); // [totalTime, tripCount]
        int[] stats = tripStats.get(key);
        stats[0] += travelTime;
        stats[1]++;
    }

    public double getAverageTime(String startStation, String endStation) {
        String key = startStation + "_" + endStation;
        int[] stats = tripStats.get(key);
        return (double) stats[0] / stats[1];
    }
}

class Pair<U, V> {
    public final U first;
    public final V second;

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}

```

### Problem: **Logs LiveTail Matcher**

You're implementing a **"Live Tail" feature** similar to Datadog, which:

* Lets users **enter queries** (like search terms).
* Continuously ingests **logs** as they appear.
* Matches incoming logs against previously submitted queries and emits results.

***

### 🧾 Input

You're given a list of strings in the following format:

* Lines that begin with `"Q: "` are **queries**.
  * Each query is a list of **space-separated words**.
  * **All** words in the query must match a log for it to be considered a match.
  * Matching is **case-insensitive** and only for **whole words**.
  * Each query is assigned a **unique ID** (starting from 1).
* Lines that begin with `"L: "` are **log lines**.
  * A log is checked against **all previous queries**.
  * If a log matches **any query**, output a match result with the matching query ID(s).

### Output

Produce a list of result strings:

1. For each query, output:

   ```
   php-templateCopyEditACK: <query_text>; ID=<query_id>
   ```
2. For each log that matches one or more queries:

   ```
   php-templateCopyEditM: <log_text>; Q=<comma-separated list of matching query IDs>
   ```

***

### 📌 Matching Rules

* Matching is **case-insensitive**
* **All** words in a query must be present in the log (as **whole words**)
* Word comparison is based on whitespace tokenization
* If no queries match a log, the log is **ignored**

***

### 🔢 Example

#### Input:

```java
javaCopyEditList<String> livetailStream = List.of(
  "Q: database",
  "Q: Stacktrace",
  "Q: loading failed",
  "L: Database service started",
  "Q: snapshot loading",
  "Q: fail",
  "L: Started processing events",
  "L: Loading main DB snapshot",
  "L: Loading snapshot failed no stacktrace available"
);
```

#### Output:

```java
javaCopyEditList<String> livetailOutput = List.of(
  "ACK: database; ID=1",
  "ACK: Stacktrace; ID=2",
  "ACK: loading failed; ID=3",
  "M: Database service started; Q=1",
  "ACK: snapshot loading; ID=4",
  "ACK: fail; ID=5",
  "M: Loading main DB snapshot; Q=4",
  "M: Loading snapshot failed no stacktrace available; Q=2,3,4"
);
```

```java
import java.io.*;
import java.util.*;
import java.util.stream.Stream;

class Solution {

  private final static String LOG_PREFIX = "L: ";
  private final static String QUERY_PREFIX = "Q: ";
  private final static String ACK_PREFIX = "ACK: ";
  private final static String M_PREFIX = "M: ";
  private final static String SPACE = " ";

  public static List<String> processLogAndQueries(List<String> input) {
    List<List<String>> storage = new ArrayList<>();
    List<String> result = new ArrayList<>();
    int query = 1;

    for (String line : input) {
      if (line.startsWith(LOG_PREFIX)) {
        String actualLog = line.substring(LOG_PREFIX.length());
        List<Integer> matchedQueries = findForLog(storage, actualLog);
        if (!matchedQueries.isEmpty()) {
          String formatted = String.format("%s%s; Q=%s",
                  M_PREFIX,
                  actualLog,
                  String.join(",", matchedQueries.stream()
                        .map(id -> String.valueOf(id + 1))
                        .toList()));
          result.add(formatted);
        }
      } else if (line.startsWith(QUERY_PREFIX)) {
        String actualQuery = line.substring(QUERY_PREFIX.length());
        // Store pre-lowercased words for faster matching
        List<String> words = Stream.of(actualQuery.split(SPACE))
                                   .map(String::toLowerCase)
                                   .toList();
        storage.add(words);
        result.add(String.format("%s%s; ID=%d", ACK_PREFIX, actualQuery, query++));
      }
    }
    return result;
  }

  private static List<Integer> findForLog(List<List<String>> storage, String log) {
    List<Integer> res = new ArrayList<>();
    Set<String> logWords = new HashSet<>(Stream.of(log.toLowerCase().split(SPACE)).toList());

    for (int i = 0; i < storage.size(); i++) {
      List<String> queryWords = storage.get(i);
      if (logWords.containsAll(queryWords)) {
        res.add(i);
      }
    }
    return res;
  }

  public static void main(String[] args) {
    List<String> livetailStream = Arrays.asList(
      "Q: database",
      "Q: Stacktrace",
      "Q: loading failed",
      "L: Database service started",
      "Q: snapshot loading",
      "Q: fail",
      "L: Started processing events",
      "L: Loading main DB snapshot",
      "L: Loading snapshot failed no stacktrace available"
    );

    List<String> actual = processLogAndQueries(livetailStream);
    System.out.println("Results:");
    for (String s : actual) System.out.println(s);
  }
}

```

```python
def process_log_and_queries(lines):
    result = []
    queries = []  # list of list-of-words (lowercased)
    for line in lines:
        if line.startswith("Q: "):
            query = line[3:]
            query_words = query.lower().split()
            queries.append(query_words)
            result.append(f"ACK: {query}; ID={len(queries)}")
        elif line.startswith("L: "):
            log = line[3:]
            log_words = set(log.lower().split())
            matched = [str(i + 1) for i, q in enumerate(queries) if all(w in log_words for w in q)]
            if matched:
                result.append(f"M: {log}; Q={','.join(matched)}")
    return result


# Test run
livetail_stream = [
    "Q: database",
    "Q: Stacktrace",
    "Q: loading failed",
    "L: Database service started",
    "Q: snapshot loading",
    "Q: fail",
    "L: Started processing events",
    "L: Loading main DB snapshot",
    "L: Loading snapshot failed no stacktrace available",
]

output = process_log_and_queries(livetail_stream)
for line in output:
    print(line)

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/design.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.