Buttercola: April 2020

Friday, April 24, 2020

Lintcode 793. Intersection of Arrays

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].

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;
    }
}

Thursday, April 23, 2020

Lintcode 550. Top K Frequent Words II

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);
        }
    }
}

Monday, April 20, 2020

Lintcode 960. First Unique Number in Data Stream II

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]

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;
    }
}

Monday, April 6, 2020

Lintcode Insert Node in a 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

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

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;
        }
    }
}

Friday, April 24, 2020

Lintcode 793. Intersection of Arrays

Example

Notice

Thursday, April 23, 2020

Lintcode 550. Top K Frequent Words II

Example

Notice

Monday, April 20, 2020

Lintcode 960. First Unique Number in Data Stream II

Example

Notice

Monday, April 6, 2020

Lintcode Insert Node in a Binary Search Tree

Example

Challenge

Notice

Lintcode 11. Search Range in Binary Search Tree

Example