Friday, April 24, 2020

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

Thursday, April 23, 2020

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

Monday, April 20, 2020

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

Monday, April 6, 2020

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

Wednesday, March 25, 2020

Lintcode 431: Connected Component in Undirected Graph

431. Connected Component in Undirected Graph

中文English
Find connected component in undirected graph.
Each node in the graph contains a label and a list of its neighbors.
(A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)
You need return a list of label set.

Example

Example 1:
Input: {1,2,4#2,1,4#3,5#4,1,2#5,3}
Output: [[1,2,4],[3,5]]
Explanation:

  1------2  3
   \     |  | 
    \    |  |
     \   |  |
      \  |  |
        4   5
Example 2:
Input: {1,2#2,1}
Output: [[1,2]]
Explanation:

  1--2

Notice

Nodes in a connected component should sort by label in ascending order. Different connected components can be in any order.
Code (Java):
/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */


public class Solution {
    /*
     * @param nodes: a array of Undirected graph node
     * @return: a connected set of a Undirected graph
     */
    public List<List<Integer>> connectedSet(List<UndirectedGraphNode> nodes) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (nodes == null || nodes.size() == 0) {
            return ans;
        }
        
        Map<UndirectedGraphNode, List<UndirectedGraphNode>> adjList = new HashMap<>();
        for (UndirectedGraphNode node : nodes) {
            adjList.put(node, node.neighbors);
        }
        
        Set<UndirectedGraphNode> visited = new HashSet<>();
        
        for (UndirectedGraphNode node : nodes) {
            if (!visited.contains(node)) {
                List<Integer> cc = bfs(adjList, node, visited);
                ans.add(cc);
            }
        }
        
        return ans;
    }
    
    private List<Integer> bfs(Map<UndirectedGraphNode, List<UndirectedGraphNode>> adjList, UndirectedGraphNode node, Set<UndirectedGraphNode> visited) {
        List<Integer> ans = new ArrayList<>();
        
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        
        queue.offer(node);
        visited.add(node);
        
        while (!queue.isEmpty()) {
            UndirectedGraphNode v = queue.poll();
            ans.add(v.label);
            
            for (UndirectedGraphNode neighbor : adjList.get(v)) {
                if (visited.contains(neighbor)) {
                    continue;
                }
                
                queue.offer(neighbor);
                visited.add(neighbor);
            }
        }
        
        Collections.sort(ans);
        
        return ans;
    }
}

Wednesday, July 17, 2019

Leetcode 1041. Robot Bounded In Circle

On an infinite plane, a robot initially stands at (0, 0) and faces north.  The robot can receive one of three instructions:
  • "G": go straight 1 unit;
  • "L": turn 90 degrees to the left;
  • "R": turn 90 degress to the right.
The robot performs the instructions given in order, and repeats them forever.
Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:
Input: "GGLLGG"
Output: true
Explanation: 
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
Example 2:
Input: "GG"
Output: false
Explanation: 
The robot moves north indefinitely.
Example 3:
Input: "GL"
Output: true
Explanation: 
The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

Note:
  1. 1 <= instructions.length <= 100
  2. instructions[i] is in {'G', 'L', 'R'}
Code (Java):
class Solution {
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int curX = 0;
    int curY = 0;
    int curDir = 0;    
    public boolean isRobotBounded(String instructions) {
        if (instructions == null || instructions.length() == 0) {
            return true;
        }
        

        for (int count = 0; count < 4; count++) {
            for (int i = 0; i < instructions.length(); i++) {
                char c = instructions.charAt(i);
                if (c == 'G') {
                    move();    
                } else {
                    turn(c);
                }
            }
        }
        
        return curX == 0 && curY == 0;
    }
    
    private void move() {
        curX += dirs[curDir][0];
        curY += dirs[curDir][1];
    }
    
    private void turn(char dir) {
        int dirVal = (dir == 'L' ? -1 : 1);
        curDir = (curDir + 4 + dirVal) % 4;
    }
}


Wednesday, June 19, 2019

Lintcode 555. Counting Bloom Filter

Description

中文English
Implement a counting bloom filter. Support the following method:
  1. add(string). Add a string into bloom filter.
  2. contains(string). Check a string whether exists in bloom filter.
  3. remove(string). Remove a string from bloom filter.

Example

Example1
Input:
CountingBloomFilter(3)
add("lint")
add("code")
contains("lint") 
remove("lint")
contains("lint") 

Output: 
[true,false]
Example2
Input:
CountingBloomFilter(3)
add("lint")
add("lint")
contains("lint")
remove("lint")
contains("lint")

Output: 
[true,true]

Code (java):
class HashFunction {
    private int size;
    private int base;
    public HashFunction(int size, int base) {
        this.size = size;
        this.base = base;
    }

    public int hash(String str) {
        int hashCode = 0;
        for (int i = 0; i < str.length(); i++) {
            hashCode = (int)(((long)hashCode * base + Integer.valueOf(str.charAt(i))) % size);
        }

        return hashCode;
    }
}

public class CountingBloomFilter {
    private List<HashFunction> hashFunctions;
    private int[] bloomFilter;
    /*
    * @param k: An integer
    **/
    public CountingBloomFilter(int k) {
        // do intialization if necessary
        hashFunctions = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            HashFunction func = new HashFunction(100000, 2 * i + 3);
            hashFunctions.add(func);
            bloomFilter = new int[100000];
        }
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            bloomFilter[hashCode] += 1;
        }
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void remove(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            bloomFilter[hashCode] -= 1;
        }
    }

    /*
     * @param word: A string
     * @return: True if contains word
     */
    public boolean contains(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            if (bloomFilter[hashCode] <= 0) {
                return false;
            }
        }

        return true;
    }
}

Lintcode 556. Standard Bloom Filter

Description

中文English
Implement a standard bloom filter. Support the following method:
  1. StandardBloomFilter(k),The constructor and you need to create k hash functions.
  2. add(string). add a string into bloom filter.
  3. contains(string). Check a string whether exists in bloom filter.

Example

Example1
Input:
CountingBloomFilter(3)
add("lint")
add("code")
contains("lint") 
remove("lint")
contains("lint") 

Output: 
[true,false]
Example2
Input:
CountingBloomFilter(3)
add("lint")
add("lint")
contains("lint")
remove("lint")
contains("lint")

Output: 
[true,false]
Code (Java):
class HashFunction {
    private int size;
    private int base;
    public HashFunction(int size, int base) {
        this.size = size;
        this.base = base;
    }

    public int hash(String str) {
        int hashCode = 0;
        for (int i = 0; i < str.length(); i++) {
            hashCode = ((hashCode * base) + Character.getNumericValue(str.charAt(i))) % size;
        }

        return hashCode;
    }
}

public class StandardBloomFilter {
    private BitSet bitSet;
    private int k;
    private List<HashFunction> hashFunctions;
    /*
    * @param k: An integer
    */public StandardBloomFilter(int k) {
        // do intialization if necessary
        this.k = k;
        hashFunctions = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            HashFunction func = new HashFunction(100000, 2 * i + 1);
            hashFunctions.add(func);
        }

        bitSet = new BitSet(100000);
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        for (int i = 0; i < k; i++) {
            int hashCode = hashFunctions.get(i).hash(word);
            bitSet.set(hashCode);
        }
    }

    /*
     * @param word: A string
     * @return: True if contains word
     */
    public boolean contains(String word) {
        // write your code here
        for (int i = 0 ; i < k; i++) {
            int hashCode = hashFunctions.get(i).hash(word);
            if (!bitSet.get(hashCode)) {
                return false;
            }
        }

        return true;
    }
}

Lintcode 566. GFS Client

Implement a simple client for GFS (Google File System, a distributed file system), it provides the following methods:
  1. read(filename). Read the file with given filename from GFS.
  2. write(filename, content). Write a file with given filename & content to GFS.
There are two private methods that already implemented in the base class:
  1. readChunk(filename, chunkIndex). Read a chunk from GFS.
  2. writeChunk(filename, chunkIndex, chunkData). Write a chunk to GFS.
To simplify this question, we can assume that the chunk size is chunkSize bytes. (In a real world system, it is 64M). The GFS Client's job is splitting a file into multiple chunks (if need) and save to the remote GFS server. chunkSize will be given in the constructor. You need to call these two private methods to implement read & write methods.

Example

GFSClient(5)
read("a.txt")
>> null
write("a.txt", "World")
>> You don't need to return anything, but you need to call writeChunk("a.txt", 0, "World") to write a 5 bytes chunk to GFS.
read("a.txt")
>> "World"
write("b.txt", "111112222233")
>> You need to save "11111" at chink 0, "22222" at chunk 1, "33" at chunk 2.
write("b.txt", "aaaaabbbbb")
read("b.txt")
>> "aaaaabbbbb"

Code (Java):
/* Definition of BaseGFSClient
 * class BaseGFSClient {
 *     private Map<String, String> chunk_list;
 *     public BaseGFSClient() {}
 *     public String readChunk(String filename, int chunkIndex) {
 *         // Read a chunk from GFS
 *     }
 *     public void writeChunk(String filename, int chunkIndex,
 *                            String content) {
 *         // Write a chunk to GFS
 *     }
 * }
 */



public class GFSClient extends BaseGFSClient {
    private int chunkSize;
    private Map<String, Integer> filenameToLastChunkIndexMap;
    /*
    * @param chunkSize: An integer
    */
public GFSClient(int chunkSize) {
        // do intialization if necessary
        this.chunkSize = chunkSize;
        filenameToLastChunkIndexMap = new HashMap<>();
    }

    /*
     * @param filename: a file name
     * @return: conetent of the file given from GFS
     */
    public String read(String filename) {
        if (!filenameToLastChunkIndexMap.containsKey(filename)) {
            return null;
        }
        // write your code here
        int lastChunkIndex = filenameToLastChunkIndexMap.get(filename);
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < lastChunkIndex; i++) {
            ans.append(readChunk(filename, i));
        }

        return ans.toString();
    }

    /*
     * @param filename: a file name
     * @param content: a string
     * @return: nothing
     */
    public void write(String filename, String content) {
        // write your code here
        int len = content.length();
        int chunkIndex = 0;
        for (int i = 0; i < len; i += chunkSize, chunkIndex++) {
            int end = Math.min(i + chunkSize, len);
            String chunkContent = content.substring(i, end);
            writeChunk(filename, chunkIndex, chunkContent);
        }

        filenameToLastChunkIndexMap.put(filename, chunkIndex);
    }
}

Lintcode 565. Heart Beat

Description

中文English
In the Master-Slave architecture, slave server will ping master in every k seconds to tell master server he is alive. If a master server didn't receive any ping request from a slave server in 2 * k seconds, the master will trigger an alarm (for example send an email) to administrator.
Let's mock the master server, you need to implement the following three methods:
  1. initialize(slaves_ip_list, k). salves_ip_list is a list of slaves' ip addresses. k is define above.
  2. ping(timestamp, slave_ip). This method will be called every time master received a ping request from one of the slave server. timestamp is the current timestamp in seconds. slave_ip is the ip address of the slave server who pinged master.
  3. getDiedSlaves(timestamp). This method will be called periodically (it's not guaranteed how long between two calls). timestamp is the current timestamp in seconds, and you need to return a list of slaves' ip addresses that died. Return an empty list if no died slaves found.
You can assume that when the master started, the timestamp is 0, and every method will be called with an global increasing timestamp.

Example

Example1
Input: 
initialize(["10.173.0.2", "10.173.0.3"], 10)
ping(1, "10.173.0.2")
getDiedSlaves(20)
getDiedSlaves(21)
ping(22, "10.173.0.2")
ping(23, "10.173.0.3")
getDiedSlaves(24)
getDiedSlaves(42)

Output: 
["10.173.0.3"]
["10.173.0.2", "10.173.0.3"]
[]
["10.173.0.2"]

Explanation:
initialize(["10.173.0.2", "10.173.0.3"], 10)
ping(1, "10.173.0.2")
getDiedSlaves(20)
>> ["10.173.0.3"]
getDiedSlaves(21)
>> ["10.173.0.2", "10.173.0.3"]
ping(22, "10.173.0.2")
ping(23, "10.173.0.3")
getDiedSlaves(24)
>> []
getDiedSlaves(42)
>> ["10.173.0.2"]
Code (Java)
public class HeartBeat {
    Map<String, Integer> ipToTimestampMap;
    int k;
    public HeartBeat() {
        // do intialization if necessary
        ipToTimestampMap = new HashMap<>();
    }

    /*
     * @param slaves_ip_list: a list of slaves'ip addresses
     * @param k: An integer
     * @return: nothing
     */
    public void initialize(List<String> slaves_ip_list, int k) {
        // write your code here
        this.k = k;
        for (String ip : slaves_ip_list) {
            ipToTimestampMap.put(ip, -1);
        }
    }

    /*
     * @param timestamp: current timestamp in seconds
     * @param slave_ip: the ip address of the slave server
     * @return: nothing
     */
    public void ping(int timestamp, String slave_ip) {
        // write your code here
        if (ipToTimestampMap.containsKey(slave_ip)) {
            ipToTimestampMap.put(slave_ip, timestamp);
        }
    }

    /*
     * @param timestamp: current timestamp in seconds
     * @return: a list of slaves'ip addresses that died
     */
    public List<String> getDiedSlaves(int timestamp) {
        // write your code here
        List<String> diedIps = new ArrayList<>();
        for (String ip : ipToTimestampMap.keySet()) {
            int lastPingTime = ipToTimestampMap.get(ip);
            if (timestamp - lastPingTime >= 2 * k) {
                diedIps.add(ip);
            }
        }

        return diedIps;
    }
}

Lintcode 1786. Pub Sub Pattern

Description

中文English
Pub/Sub pattern is a wide used pattern in system design. In this problem, you need to implement a pub/sub pattern to support user subscribes on a specific channel and get notification messages from subscribed channels.
There are 3 methods you need to implement:
  • subscribe(channel, user_id): Subscribe the given user to the given channel.
  • unsubscribe(channel, user_id): Unsubscribe the given user from the given channel.
  • publish(channel, message): You need to publish the message to the channel so that everyone subscribed on the channel will receive this message. Call PushNotification.notify(user_id, message) to push the message to the user.

Example

subscribe("group1",  1)
publish("group1", "hello")
>> user 1 received "Hello"
subscribe("group1", 2)
publish("group1", "thank you")
>> user 1 received "thank you"
>> user 2 received "thank you"
unsubscribe("group2", 3)
>> user 3 is not in group2, do nothing
unsubscribe("group1", 1)
publish("group1", "thank you very much")
>> user 2 received "thank you very much"
publish("group2", "are you ok?")
>> # you don't need to push this message to anyone
If there are more than 1 user subscribed on the same channel, it doesn't matter the order of time users receiving the message. It's ok if you push the message to user 2 before user 1.

Code (Java):
/* Definition of PushNotification
 * class PushNotification {
 *     public static void notify(int user_id, String the_message)
 *  };
 */
//
public class PubSubPattern {
    Map<String, Set<Integer>> channelTable;
    public PubSubPattern(){
     // Write your code here
     channelTable = new HashMap<>();
    }
    
    /**
     * @param channel: the channel's name
     * @param user_id: the user who subscribes the channel
     * @return: nothing
     */
    public void subscribe(String channel, int user_id) {
        // Write your code here
        Set<Integer> users = channelTable.getOrDefault(channel, new HashSet<>());
        users.add(user_id);
        channelTable.put(channel, users);
    }

    /**
     * @param channel: the channel's name
     * @param user_id: the user who unsubscribes the channel
     * @return: nothing
     */
    public void unsubscribe(String channel, int user_id) {
        // Write your code here
        if (channelTable.containsKey(channel)) {
            Set<Integer> users = channelTable.get(channel);
            users.remove(user_id);
        }
    }

    /**
     * @param channel: the channel's name
     * @param message: the message need to be delivered to the channel's subscribers
     * @return: nothing
     */
    public void publish(String channel, String message) {
        // Write your code here
        if (channelTable.containsKey(channel)) {
            Set<Integer> users = channelTable.get(channel);
            for (Integer user : users) {
                PushNotification.notify(user, message);
            }
        }
    }
}