Lintcode 793. Intersection of Arrays

Give a number of arrays, find their intersection, and output their intersection size.

Example

Example 1:

 Input:  [[1,2,3],[3,4,5],[3,9,10]]
 Output:  1
 
 Explanation:
 Only '3' in all three array.

Example 2:

 Input: [[1,2,3,4],[1,2,5,6,7][9,10,1,5,2,3]]
 Output:  2
 
 Explanation:
 The set is [1,2].

Notice

• The total number of all array elements is not more than 500000.
• There are no duplicated elements in each array.

Code (Java):

public class Solution {
    /**
     * @param arrs: the arrays
     * @return: the number of the intersection of the arrays
     */
    public int intersectionOfArrays(int[][] arrs) {
        // write your code here
        if (arrs == null || arrs.length == 0) {
            return 0;
        }
        
        return intersectionOfArraysHelper(0, arrs.length - 1, arrs).length;
    }
    
    private int[] intersectionOfArraysHelper(int start, int end, int[][] arrs) {
        if (start == end) {
            return arrs[start];
        }
        
        int mid = start + (end - start) / 2;
        int[] left = intersectionOfArraysHelper(start, mid, arrs);
        int[] right = intersectionOfArraysHelper(mid + 1, end, arrs);
        
        return intersectionOfTwoArray(left, right);
    }
    
    private int[] intersectionOfTwoArray(int[] left, int[] right) {
        Arrays.sort(left);
        Arrays.sort(right);
        
        int i = 0;
        int j = 0;
        
        List<Integer> ans = new ArrayList<>();
        while (i < left.length && j < right.length) {
            if (left[i] == right[j]) {
                ans.add(left[i]);
                i++;
                j++;
            } else if (left[i] < right[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        int[] ans2 = new int[ans.size()];
        for (i = 0; i < ans2.length; i++) {
            ans2[i] = ans.get(i);
        }
        
        return ans2;
    }
}

Lintcode 550. Top K Frequent Words II

ind top k frequent words in realtime data stream.

Implement three methods for Topk Class:

1. TopK(k). The constructor.
2. add(word). Add a new word.
3. topk(). Get the current top k frequent words.

Example

Example 1:

Input：
TopK(2)
add("lint")
add("code")
add("code")
topk()
Output：["code", "lint"]
Explanation：
"code" appears twice and "lint" appears once, they are the two most frequent words.

Example 2:

Input：
TopK(1)
add("aa")
add("ab")
topk()
Output：["aa"]
Explanation：
"aa" and "ab" appear once , but aa's dictionary order is less than ab's.

Notice

If two words have the same frequency, rank them by dictionary order.

Analysis:
The main difference between the top k frequent word I is now we keep adding new words. So the count of each word is changing dynamically. 

It means in the minHeap, we need to support an update operation update(E e), which is a O(N) operation. Why? It first needs to find the node. Since there is no order in priority queue, the search operation takes O(N) time. Once we find the element, we need to first remove it (O(logn)) and insert a new node O(logn). 

So do we have some other data structure providing similar operations but the search can be done in O(log(N)) time? Yes, we can use a TreeSet/TreeMap which is literally a red-black tree. Since it's a ordered tree, the search now takes O(log n) time and update takes O(logn) as well. 

Code (Java):

public class TopK {
    private Map<String, Integer> wordCountMap;
    private TreeSet<String> topKTreeSet;
    private int k;
    
    /*
    * @param k: An integer
    */public TopK(int k) {
        // do intialization if necessary
        this.k = k;
        this.wordCountMap = new HashMap<>();
        this.topKTreeSet = new TreeSet<>(new MyTreeSetComparator());
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        int count = 0;
        if (wordCountMap.containsKey(word)) {
            count = wordCountMap.get(word);
            if (topKTreeSet.contains(word)) {
                topKTreeSet.remove(word);
            }
        }
        
        count += 1;
        wordCountMap.put(word, count);
        topKTreeSet.add(word); // count has been bumped up by 1
        
        if (topKTreeSet.size() > k) {
            topKTreeSet.pollFirst();
        }
    }

    /*
     * @return: the current top k frequent words.
     */
    public List<String> topk() {
        // write your code here
        List<String> ans = new ArrayList<>(k);
        Iterator<String> iter = topKTreeSet.iterator();
        while (iter.hasNext()) {
            String word = iter.next();
            ans.add(word);
        }
        
        Collections.reverse(ans);
        
        return ans;
    }
    
    private class MyTreeSetComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            int freqA = wordCountMap.get(a);
            int freqB = wordCountMap.get(b);
            
            if (freqA != freqB) {
                return freqA - freqB;
            }
            
            return b.compareTo(a);
        }
    }
}

Lintcode 960. First Unique Number in Data Stream II

We need to implement a data structure named DataStream. There are two methods required to be implemented:

1. void add(number) // add a new number
2. int firstUnique() // return first unique number

Example

Example 1:

Input:
add(1)
add(2)
firstUnique()
add(1)
firstUnique()
Output:
[1,2]

Example 2:

Input:
add(1)
add(2)
add(3)
add(4)
add(5)
firstUnique()
add(1)
firstUnique()
add(2)
firstUnique()
add(3)
firstUnique()
add(4)
firstUnique()
add(5)
add(6)
firstUnique()
Output:
[1,2,3,4,5,6]

Notice

You can assume that there must be at least one unique number in the stream when calling the firstUnique.

Solution:
Similar to the "LRU cache" problem. Build a hashMap + doubly linked list. The list is ordered by the sequence of adding the numbers. 

Code (Java):

public class DataStream {
    Map<Integer, ListNode> numToNodeMap;
    LinkedList nodeList;
    
    public DataStream(){
        // do intialization if necessary
        numToNodeMap = new HashMap<>();
        nodeList = new LinkedList();
    }
    /**
     * @param num: next number in stream
     * @return: nothing
     */
    public void add(int num) {
        // write your code here
        if (!numToNodeMap.containsKey(num)) {
            ListNode node = nodeList.appendToTail(num);
            numToNodeMap.put(num, node);
        } else {
            ListNode node = numToNodeMap.get(num);
            nodeList.remove(node);
            numToNodeMap.put(num, null);
        }
    }

    /**
     * @return: the first unique number in stream
     */
    public int firstUnique() {
        // write your code here
        return nodeList.getFirst().val;
    }
}

class ListNode {
    int val;
    ListNode prev, next;
    
    public ListNode(int val) {
        this.val = val;
        prev = next = null;
    }
}

class LinkedList {
    ListNode dummyHead;
    ListNode dummyTail;
    
    public LinkedList() {
        dummyHead = new ListNode(-1);
        dummyTail = new ListNode(-1);
        
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    ListNode appendToTail(int val) {
        ListNode tailNode = new ListNode(val);
        dummyTail.prev.next = tailNode;
        tailNode.prev = dummyTail.prev;
        
        tailNode.next = dummyTail;
        dummyTail.prev = tailNode;
        
        return tailNode;
    }
    
    ListNode getFirst() {
       if (dummyHead.next == dummyTail) {
           return null;
       }
       
       return dummyHead.next;
    }
    
    void remove(ListNode node) {
        if (node == null) {
            return;
        }
        
        ListNode prevNode = node.prev;
        ListNode nextNode = node.next;
        
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        
        node.prev = null;
        node.next = null;
    }
}

Lintcode Insert Node in a Binary Search Tree

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.

Example

Example 1:
 Input:  tree = {}, node = 1
 Output:  1
 
 Explanation:
 Insert node 1 into the empty tree, so there is only one node on the tree.

Example 2:
 Input: tree = {2,1,4,3}, node = 6
 Output: {2,1,4,3,6}
 
 Explanation: 
 Like this:



   2             2
  / \           / \
 1   4   -->   1   4
    /             / \ 
   3             3   6
  

Challenge

Can you do it without recursion?

Notice

You can assume there is no duplicate values in this tree + node.

Code (Java):

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: The root of the binary search tree.
     * @param node: insert this node into the binary search tree
     * @return: The root of the new binary search tree.
     */
    public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if (root == null) {
            return node;
        }
        
        TreeNode p = root;
        TreeNode parent  = null;
        
        while (p != null) {
            if (p.val < node.val) {
                parent = p;
                p = p.right;
            } else {
                parent = p;
                p = p.left;
            }
        }
        
        if (parent.val < node.val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        
        return root;
    }
}

Lintcode 11. Search Range in Binary Search Tree

Given a binary search tree and a range [k1, k2], return node values within a given range in ascending order.

Example

Example 1:

Input：{5},6,10
Output：[]
        5
it will be serialized {5}
No number between 6 and 10

Example 2:

Input：{20,8,22,4,12},10,22
Output：[12,20,22]
Explanation：
        20
       /  \
      8   22
     / \
    4   12
it will be serialized {20,8,22,4,12}
[12,20,22] between 10 and 22

Code (Java):

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: param root: The root of the binary search tree
     * @param k1: An integer
     * @param k2: An integer
     * @return: return: Return all keys that k1<=key<=k2 in ascending order
     */
    public List<Integer> searchRange(TreeNode root, int k1, int k2) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        
        // stack stores all nodes greater or equal to k1
        //
        Stack<TreeNode> stack = new Stack<>();
        
        TreeNode p = root;
        
        while(p != null) {
            if (p.val >= k1) {
                stack.push(p);
                p = p.left;
            } else {
                p = p.right;
            }
        }
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.val <= k2) {
                ans.add(node.val);
            }
            
            findNext(node.right, stack);
        }
        
        return ans;
    }
    
    private void findNext(TreeNode p, Stack<TreeNode> stack) {
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
    }
}