Advanced Data Structures

PriorityQueue
- Related with greedy algorithm
- Use minQueue to get kth max, maxQueue to get kth min
- merge sort with PQ

Misc
- Remove is O(n)

LeetCode 414 - Third Maximum Number
- Use PriorityQueue with HashSet to check duplicate
https://discuss.leetcode.com/topic/63086/java-priorityqueue-o-n-o-1
- TreeSet (not PQ as need call contains)
set.add(num);
if(set.size() > 3) {set.remove(set.first());}
- Maitain state: first, second, third

LeetCode 502 - IPO
find a project with max profit and within current capital capability
- 2 PriorityQueue

        PriorityQueue<int[]> pqCap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        PriorityQueue<int[]> pqPro  = new PriorityQueue<>((a, b) -> (b[1] - a[1]));        
        for (int i = 0; i < k; i++) {
            while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
                pqPro.add(pqCap.poll());
            }
            W += pqPro.poll()[1];
        }

LeetCode 632 - Smallest Range


LeetCode 630 - Course Schedule III
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dthday. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses,(a,b)->a[1]-b[1]); //Sort the courses by their deadlines (Greedy! We have to deal with courses with early deadlines first)
        PriorityQueue pq=new PriorityQueue<>((a,b)->b-a);
        int time=0;
        for (int[] c:courses) 
        {
            time+=c[0]; // add current course to a priority queue
            pq.add(c[0]);
            if (time>c[1]) time-=pq.poll(); //If time exceeds, drop the previous course which costs the most time. (That must be the best choice!)
        }        
        return pq.size();
    }

LeetCode 378 - Kth Smallest Element in a Sorted Matrix
- Bisection O(nlogm) while m = max - min
https://discuss.leetcode.com/topic/52868/java-heap-klog-k

    public int kthSmallest(final int[][] matrix, int k) {
        int c = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>(
            k, (o1, o2) -> matrix[o1[0]][o1[1]] - matrix[o2[0]][o2[1]]);
        queue.offer(new int[] {0, 0});
        while (true) {
            int[] pair = queue.poll();
            if (++c == k) {
                return matrix[pair[0]][pair[1]];
            }
            if (pair[0] == 0 && pair[1] + 1 < matrix[0].length) {
                queue.offer(new int[] {0, pair[1] + 1});
            }
            if (pair[0] + 1 < matrix.length) {
                queue.offer(new int[] {pair[0] + 1, pair[1]});
            }
        }

LeetCode 373 - Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Find elements more than K times
Given m sorted lists, find out the elements more than k times. If an element appear more than once in a list, count it only once.
- Use PriorityQueue instead of HashMap to save space

POJ 4302 Holedox Eating
- 2 PriorityQueue

LeetCode 621 - Task Scheduler
- Use Priority Queue
- Calculating Idle slots
LeetCode 358 - Rearrange String k Distance Apart

Rearrange Characters in String With No Adjacent Duplicate Characters

LeetCode 632 - Smallest Range
You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the klists.
- Merge k sorted list

LeetCode 407 - Trapping Rain Water II

Queue
Double Monotonic Queue

Deque q = new ArrayDeque<>();
Deque doubleQueue = new LinkedList<>();

LeetCode 239 - Sliding Window Maximum
- Store index instead of the value
- Only keep promising elements in the deque

LeetCode 102 - Binary Tree Level Order Traversal
queue.offer(root);
while(!queue.isEmpty()){
  for(int i=0; i}

LeetCode 127 - Word Ladder I
- BFS, Two-end BFS
Deque queue = new ArrayDeque();
queue.offer(start);
Set visited

LeetCode 111 - Minimum Depth of Binary Tree

Interval tree
http://www.davismol.net/2016/02/07/data-structures-augmented-interval-tree-to-search-for-interval-overlapping/
- augmented self-balancing bst: low, high, max
- logn: add/Remove(interval), overlapping(x)

Google – Toggle Problem
https://reeestart.wordpress.com/2016/06/24/google-toggle-problem/

Using Multiple Data Structures 
Google – Manager Peer Problem
- Tree + Hash Table
Map nodeMap
private class TNode {
  int val;
  TNode parent;
  List neighbors;
}

Design a data structure that supports insert, delete, search and getRandom in constant time
//A hash where keys are array elements and vlaues are ndexes in arr[]
HashMap  hash;
ArrayList arr;

LeetCode 432 - All O`one Data Structure
Inc(Key), Dec(Key), GetMaxKey(), GetMinKey()

    private Bucket head;
    private Bucket tail;
    // for accessing a specific Bucket among the Bucket list in O(1) time
    private Map countBucketMap;
    // keep track of count of keys
    private Map keyCountMap; or the value can be Bucket
    // each Bucket contains all the keys with the same count
    private class Bucket {
        int count;
        Set keySet;
        Bucket next, prev;
    }

LeetCode - LRU Cache

    private int capacity;
    private HashMap hs = new HashMap();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        if( !hs.containsKey(key)) {
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);

        return hs.get(key).value;
    }

    public void set(int key, int value) {
        // this internal `get` method will update the key's position in the linked list.
        if (get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {
            hs.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);
        hs.put(key, insert);
        move_to_tail(insert);
    }

    private void move_to_tail(Node current) {
        current.prev = tail.prev;
        tail.prev = current;
        current.prev.next = current;
        current.next = tail;
    }

LeetCode 460 - LFU Cache
when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
- Doubly Linked List + HashMap

    private Node head = null;
    private int cap = 0;
    private HashMap valueHash = null;
    private HashMap nodeHash = null;

Design Phone Directory
isTaken(String phone) takeNumber(String phone) giveMeANumber()
- Trie

Stock Ticker

1. void addOrUpdate(String stock, double price) add or update the price of a stock to the data structure.
2. List return the top k price stocks and their current prices.

- HashMap contains all elements, MinHeap or TreeSet contains top(k)

Sparse Matrix
Implementing Stack using priority queue.
- assign priority to the elements that are being pushed

TimeTravelingHashTable
* insert(key, value, timestamp)
* get(key, timestamp)
//> = =
HashMap> map = new HashMap<>();


Design a stack with operations on middle element
- push, pop
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element.
- Doubly Linked List

Min Stack