Buttercola: June 2019

Wednesday, June 19, 2019

Lintcode 555. Counting Bloom Filter

Description

中文English

Implement a counting bloom filter. Support the following method:

add(string). Add a string into bloom filter.
contains(string). Check a string whether exists in bloom filter.
remove(string). Remove a string from bloom filter.

Have you met this question in a real interview?

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:

StandardBloomFilter(k),The constructor and you need to create k hash functions.
add(string). add a string into bloom filter.
contains(string). Check a string whether exists in bloom filter.

Have you met this question in a real interview?

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

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

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:

initialize(slaves_ip_list, k). salves_ip_list is a list of slaves' ip addresses. k is define above.
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.
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.

Have you met this question in a real interview?

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.

Have you met this question in a real interview?

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

Tuesday, June 18, 2019

Lintcode 525. Mini Uber

Description

中文English

Support two basic uber features:

Drivers report their locations.
Rider request a uber, return a matched driver.

When rider request a uber, match a closest available driver with him, then mark the driver not available.

When next time this matched driver report his location, return with the rider's information.

You can implement it with the following instructions:

report(driver_id, lat, lng)
- return null if no matched rider.
- return matched trip information.
request(rider_id, lat, lng)
1. create a trip with rider's information.
2. find a closest driver, mark this driver not available.
3. fill driver_id into this trip.
4. return trip

This is the definition of Trip in Java:

public class Trip {
    public int id; // trip's id, primary key
    public int driver_id, rider_id; // foreign key
    public double lat, lng; // pick up location
}

Have you met this question in a real interview?

Example

Example 1:

Input:
  report(1, 36.1344, 77.5672) 
  report(2, 45.1344, 76.5672) 
  request(2, 39.1344, 76.5672) 
  report(1, 38.1344, 75.5672) 
  report(2, 45.1344, 76.5672) 
Output:
  null
  null
  Trip(rider_id: 2, driver_id: 1, lat: 39.1344, lng: 76.5672)
  Trip(rider_id: 2, driver_id: 1, lat: 39.1344, lng: 76.5672)
  null

Example 2:

Input:
  report(1, 36.1344, 77.5672)
  report(2, 45.1344, 76.5672)
  request(2, 39.1344, 76.5672)
  request(3, 78.1344, 134.5672)
Output:
  null
  null
  LOG(INFO): Trip(rider_id: 2, driver_id: 1, lat: 39.1344, lng: 76.5672)
  LOG(INFO): Trip(rider_id: 3, driver_id: 2, lat: 78.1344, lng: 134.5672)

Code (Java):

/**
 * Definition of Trip:
 * public class Trip {
 *     public int id; // trip's id, primary key
 *     public int driver_id, rider_id; // foreign key
 *     public double lat, lng; // pick up location
 *     public Trip(int rider_id, double lat, double lng);
 * }
 * Definition of Helper
 * class Helper {
 *     public static double get_distance(double lat1, double lng1,
                                         double lat2, double lng2) {
 *         // return distance between (lat1, lng1) and (lat2, lng2)
 *     }
 * };
 */
 
class Location {
    double lat;
    double lng;
    public Location(double lat, double lng) {
        this.lat = lat;
        this.lng = lng;
    }
}
public class MiniUber {
    private Map<Integer, Trip> tripTable;
    private Map<Integer, Location> locTable;
 
    public MiniUber() {
        // initialize your data structure here.
        tripTable = new HashMap<>();
        locTable = new HashMap<>();
    }
 
    // @param driver_id an integer
    // @param lat, lng driver's location
    // return matched trip information if there have matched rider or null
    public Trip report(int driver_id, double lat, double lng) {
        // if trip table contains driver_id, return it
        if (tripTable.containsKey(driver_id)) {
            return tripTable.get(driver_id);
        }
         
        Location loc = new Location(lat, lng);
         
        // report loc to location table
        locTable.put(driver_id, loc);
         
        return null;
    }
 
    // @param rider_id an integer
    // @param lat, lng rider's location
    // return a trip
    public Trip request(int rider_id, double lat, double lng) {
        // Write your code here
        Trip trip = new Trip(rider_id, lat, lng);
 
        double minDist = Integer.MAX_VALUE;
        int matchedDriver = -1;
        // find the cloeset driver
        for (Integer driver_id : locTable.keySet()) {
            Location loc = locTable.get(driver_id);
            double dist = Helper.get_distance(lat, lng, loc.lat, loc.lng);
            if (dist < minDist) {
                minDist = dist;
                matchedDriver = driver_id;
            }
        }
 
        if (matchedDriver != -1) {
            locTable.remove(matchedDriver);
        }
 
        trip.driver_id = matchedDriver;
        tripTable.put(matchedDriver, trip);
 
        return trip;
    }
}

Note:
For rider reports its location. It should first check the driver in the trip table. If yes, just return it first.

Lintcode 530. Geohash II

Example

Example1

Input: "wx4g0s"`
Output: lat = 39.92706299 and lng = 116.39465332

Example2

Input: "w"
Output: lat = 22.50000000 and lng = 112.50000000

Code (Java):

public class GeoHash {
    /*
     * @param geohash: geohash a base32 string
     * @return: latitude and longitude a location coordinate pair
     */
    public double[] decode(String geohash) {
        // step1: get binary code
        //
        String binaryGeoHash = getBinaryGeoHash(geohash);
 
        // step 2: get binary representation of the long and latitude
        String[] binaryLongLati = getBinaryLongAndLati(binaryGeoHash);
 
        double longtitude = getLocation(binaryLongLati[0], -180, 180);
        double latitude = getLocation(binaryLongLati[1], -90, 90);
 
        double[] ans = new double[2];
        ans[0] = latitude;
        ans[1] = longtitude;
 
        return ans;
    }
 
    private double getLocation(String code, double start, double end) {
        double mid = start + (end - start) / 2;
        for (int i = 0; i < code.length(); i++) {
            if (code.charAt(i) == '0') {
                end = mid;
            } else {
                start = mid;
            }
 
            mid = start + (end - start) / 2;
        }
 
        return mid;
    }
 
    private String[] getBinaryLongAndLati(String binaryGeoHash) {
        String[] ans = new String[2];
        StringBuilder longtitude = new StringBuilder();
        StringBuilder latitude = new StringBuilder();
 
        for (int i = 0; i < binaryGeoHash.length(); i += 2) {
            longtitude.append(binaryGeoHash.charAt(i));
            if (i + 1 < binaryGeoHash.length()) {
                latitude.append(binaryGeoHash.charAt(i + 1));
            }
        }
 
        ans[0] = longtitude.toString();
        ans[1] = latitude.toString();
 
        return ans;
    }
 
    private String getBinaryGeoHash(String geohash) {
        String dict = "0123456789bcdefghjkmnpqrstuvwxyz";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < geohash.length(); i++) {
            int base32 = dict.indexOf(geohash.charAt(i));
            sb.append(toBase2(base32));
        }
 
        return sb.toString();
    }
 
    private String toBase2(int num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            sb.insert(0, num % 2);
            num /= 2;
        }
         
        // pad with zeros
        while (sb.length() < 5) {
            sb.insert(0, '0');
        }
 
        return sb.toString();
    }
}

Lintcode 529. Geohash

Notice

1 <= precision <=12

Code (Java):

public class GeoHash {
    /*
     * @param latitude: one of a location coordinate pair 
     * @param longitude: one of a location coordinate pair 
     * @param precision: an integer between 1 to 12
     * @return: a base32 string
     */
    public String encode(double latitude, double longitude, int precision) {
        // write your code here
        int len = (precision * 5) % 2 == 0 ? precision * 5 / 2 : precision * 5 / 2 + 1;
        String latStr = generateCode(latitude, -90, 90, len);
        String longStr = generateCode(longitude, -180, 180, len);
         
        String geoHashCode = getGeoHash(latStr, longStr);
        StringBuilder finalCode = new StringBuilder();
 
        String dict = "0123456789bcdefghjkmnpqrstuvwxyz";
 
        for (int i = 0; i <= geoHashCode.length() - 5; i += 5) {
            int num = 0;
            for (int j = i; j < i + 5; j++) {
                num = num * 2 + Character.getNumericValue(geoHashCode.charAt(j));
            }
 
            finalCode.append(dict.charAt(num));
        }
 
        return finalCode.toString();
    }
 
    private String generateCode(double loc, double start, double end, int len) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            double mid = start + (end - start) / 2;
            if (loc <= mid) {
                sb.append('0');
                end = mid;
            } else {
                sb.append('1');
                start = mid;
            }
        }
 
        return sb.toString();
    }
 
    private String getGeoHash(String latitude, String longtitude) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < longtitude.length(); i++) {
            sb.append(longtitude.charAt(i));
            sb.append(latitude.charAt(i));
        }
 
        return sb.toString();
    }
}

Thursday, June 13, 2019

lintcode 232. Tiny Url

Example

Example 1:

Input: shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
Output: "http://www.lintcode.com/faq/?id=10"
Explanation: 
  When longToShort() called, you can return any short url.
  For example, "http://tiny.url/abcdef".
  And "http://tiny.url/ABCDEF" is ok as well.

Example 2:

Input:
  shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
  shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
Output:
  "http://www.lintcode.com/faq/?id=10"
  "http://www.lintcode.com/faq/?id=10"

Code (Java):

public class TinyUrl {
    private GlobalCounter counter;
    private Map<Integer, String> idToLongURL;
    private Map<String, Integer> longURLToId;
    private String dict = "0123456789" + "abcdefghijklmnopqrstuvwxyz" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 
    public TinyUrl() {
        counter = new GlobalCounter();
        idToLongURL = new HashMap<>();
        longURLToId = new HashMap<>();
    }
 
    public String longToShort(String url) {
        // write your code here
        // find if the short url already exists
        if (longURLToId.containsKey(url)) {
            int id = longURLToId.get(url);
            return idToShortURL(id);
        }
         
        int id = counter.getNext();
        String shortURL = idToShortURL(id);
         
        idToLongURL.put(id, url);
        longURLToId.put(url, id);
         
        return shortURL;
    }
 
    /*
     * @param url: a short url starts with http://tiny.url/
     * @return: a long url
     */
    public String shortToLong(String url) {
        // write your code here
        int id = shortURLToId(url);
         
        return idToLongURL.get(id);
    }
     
     
    private String idToShortURL(int id) {
        StringBuilder sb = new StringBuilder();
        while (id > 0) {
            sb.insert(0, dict.charAt(id % 62));
            id /= 62;
        }
 
        while (sb.length() < 6) {
            sb.insert(0, '0');
        }
         
        String shortURL = "http://tiny.url/" + sb.toString();
         
        return shortURL;
    }
     
    private int shortURLToId(String shortURL) {
        int id = 0;
        shortURL = shortURL.substring(shortURL.length() - 6);
        for (int i = 0; i < shortURL.length(); i++) {
            id = id * 62 + base62(shortURL.charAt(i));
        }
         
        return id;
    }
     
    private int base62(char c) {
        if (c >= '0' && c <= '9') {
            return c - '0';
        } else if (c >= 'a' && c <= 'z') {
            return c - 'a' + 10;
        } else if (c >= 'A' && c <= 'Z') {
            return c - 'A' + 36;
        }
         
        return 0;
    }
}
 
class GlobalCounter {
    private int counter;
    public GlobalCounter() {
        counter = 1;
    }
 
    public int getNext() {
        int next = counter;
        counter += 1;
        return next;
    }
}

Thursday, June 6, 2019

Lintcode 520 Consistent Hashing II

Description

中文English

在 Consistent Hashing I 中我们介绍了一个比较简单的一致性哈希算法，这个简单的版本有两个缺陷：

增加一台机器之后，数据全部从其中一台机器过来，这一台机器的读负载过大，对正常的服务会造成影响。
当增加到3台机器的时候，每台服务器的负载量不均衡，为1:1:2。

为了解决这个问题，引入了 micro-shards 的概念，一个更好的算法是这样：

将 360° 的区间分得更细。从 0~359 变为一个 0 ~ n-1 的区间，将这个区间首尾相接，连成一个圆。
当加入一台新的机器的时候，随机选择在圆周中撒 k 个点，代表这台机器的 k 个 micro-shards。
每个数据在圆周上也对应一个点，这个点通过一个 hash function 来计算。
一个数据该属于哪台机器负责管理，是按照该数据对应的圆周上的点在圆上顺时针碰到的第一个 micro-shard 点所属的机器来决定。

n 和 k在真实的 NoSQL 数据库中一般是 2^64 和 1000。

请实现这种引入了 micro-shard 的 consistent hashing 的方法。主要实现如下的三个函数：

create(int n, int k)
addMachine(int machine_id) // add a new machine, return a list of shard ids.
getMachineIdByHashCode(int hashcode) // return machine id

当 n 为 2^64 时，在这个区间内随机基本不会出现重复。
但是为了方便测试您程序的正确性，n 在数据中可能会比较小，所以你必须保证你生成的 k 个随机数不会出现重复。
LintCode并不会判断你addMachine的返回结果的正确性（因为是随机数），只会根据您返回的addMachine的结果判断你getMachineIdByHashCode结果的正确性。

Have you met this question in a real interview?

Example

样例 1:

输入:
  create(100, 3)
  addMachine(1)
  getMachineIdByHashCode(4)
  addMachine(2)
  getMachineIdByHashCode(61)
  getMachineIdByHashCode(91)
输出: 
  [77,83,86]
  1
  [15,35,93]
  1
  2

样例 2:

输入: 
  create(10, 5)
  addMachine(1)
  getMachineIdByHashCode(4)
  addMachine(2)
  getMachineIdByHashCode(0)
  getMachineIdByHashCode(1)
  getMachineIdByHashCode(2)
  getMachineIdByHashCode(3)
  getMachineIdByHashCode(4)
  getMachineIdByHashCode(5)
输出: 
  [2,3,5,6,7]
  1
  [0,1,4,8,9]
  2
  2
  1
  1
  2
  1

Code (Java):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 public class Solution {
    /*
     * @param n: a positive integer
     * @param k: a positive integer
     * @return: a Solution object
    */
    private int n;
    private int k;
    private TreeMap<Integer, Integer> virtualToPhysicalMap;
     
    public static Solution create(int n, int k) {
        Solution sol = new Solution();
         
        // Write your code here
        sol.n = n;
        sol.k = k;
        sol.virtualToPhysicalMap = new TreeMap<>();
         
        return sol;
    }
 
    /*
     * @param machine_id: An integer
     * @return: a list of shard ids
     */
    public List<Integer> addMachine(int machine_id) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            int virtualNode = getVirtualNode();
            virtualToPhysicalMap.put(virtualNode, machine_id);
            System.out.println(virtualNode + " " + machine_id);
            ans.add(virtualNode);
        }
         
        return ans;
    }
 
    /*
     * @param hashcode: An integer
     * @return: A machine id
     */
    public int getMachineIdByHashCode(int hashcode) {
        // write your code here
        Map.Entry<Integer, Integer> entry = virtualToPhysicalMap.ceilingEntry(hashcode);
         
        return entry == null ? virtualToPhysicalMap.firstEntry().getValue() : entry.getValue();
         
    }
     
    private int getVirtualNode() {
        Random rand = new Random();
        int node = rand.nextInt(n);
        while (virtualToPhysicalMap.containsKey(node)) {
            node = rand.nextInt(n);
        }
         
        return node;
    }
}

Buttercola

Wednesday, June 19, 2019

Lintcode 555. Counting Bloom Filter

Description

Example

Lintcode 556. Standard Bloom Filter

Description

Example

Lintcode 566. GFS Client

Lintcode 565. Heart Beat

Description

Example

Lintcode 1786. Pub Sub Pattern

Description

Example

Tuesday, June 18, 2019

Lintcode 525. Mini Uber

Description

Example

Lintcode 530. Geohash II

Lintcode 529. Geohash

Thursday, June 13, 2019

lintcode 232. Tiny Url

Thursday, June 6, 2019

Lintcode 520 Consistent Hashing II

Description

Example