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> top() 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
Post a Comment

Labels

Java (159) Lucene-Solr (110) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (12) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Http Client (8) Maven (8) Problem Solving (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) Lesson Learned (5) Programmer Skills (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) System Design (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts