Implement a load balancer for web servers. It provide the following functionality:

1. Add a new server to the cluster = > add(server_id) .
2. Remove a bad server from the cluster = > remove(server_id) .
3. Pick a server in the cluster randomly with equal probability = > pick() .

Have you met this question in a real interview?

Yes

Example

At beginning, the cluster is empty =>{}.

add(1)
add(2)
add(3)
pick()

>
>
 1         // the return value is random, it can be either 1, 2, or 3.
pick()

>
>
 2
pick()

>
>
 1
pick()

>
>
 3
remove(1)
pick()

>
>
 2
pick()

>
>
 3
pick()

>
>
 3

class LoadBalancer {
public:
    LoadBalancer() {
        // Initialize your data structure here.
    }

    // @param server_id add a new server to the cluster 
    // @return void
    void add(int server_id) {
        // Write your code here
        int m = ids.size();
        hash[server_id] = m;
        ids.push_back(server_id);
    }

    // @param server_id server_id remove a bad server from the cluster
    // @return void
    void remove(int server_id) {
        // Write your code here
        int index = hash[server_id];
        ids[index] = ids.back();
        hash[ids.back()] = index;
        ids.pop_back();
        hash.erase(server_id);
    }

    // @return pick a server in the cluster randomly with equal probability
    int pick() {
        // Write your code here
        int index = rand() %  ids.size();
        return ids[index];
    }

private:
    map<int, int> hash;
    vector<int> ids;
};