CareerCup

import java.util.HashMap;

public class Party {

	private HashMap<Integer, String> indexToHostMap= null;
	private HashMap<String, Integer> hostToIndexMap= null;
	private int count;
	
	public Party() {

		count = 0;
		indexToHostMap = new HashMap<Integer, String>();
		hostToIndexMap = new HashMap<String, Integer>();
	}

	//Time Complexity is O(1)
	void addHost(String host) {

		indexToHostMap.put(count, host);
		hostToIndexMap.put(host, count); // host is unique
		count++;
	}

	//Time Complexity is O(1)	
	void removeHost(String host) {

		int index = hostToIndexMap.get(host); // get index

		indexToHostMap.remove(index); //remove index
		hostToIndexMap.remove(host);  //remove host

		if(count-1 == index) {
			// last element removed, no re-ordering required
			count--;
			return;
		}

		// Move last index element to removed index 
		String lastHost = indexToHostMap.get(count-1);
		indexToHostMap.remove(count-1);
		
		indexToHostMap.put(index, lastHost);
		hostToIndexMap.put(lastHost, index);
		count--;

	}

	//Time Complexity is O(1)
	public String getHost() {

		int random = (int) Math.random();
		random = random%count;
		return indexToHostMap.get(random);
	}

}

Use set to store hostnames.
in getHost() method use iterator object & return iterator.next()

calling addHost & removeHost methods, will be less frequent.
calling getHost() will be frequent as with every request come to LB, it will call getHost

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class LoadBalancer {

public static void main(String[] args) {
LB lb = new LB();

lb.addHost("a");
lb.addHost("b");
lb.addHost("c");
lb.addHost("d");
lb.addHost("e");
lb.addHost("f");

System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());

lb.removeHost("d");

System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
System.out.println(lb.getHost());
}
}

class LB {
private Set<String> ips;
private Iterator<String> iterator;

public LB() {
ips = new HashSet<String>();
iterator = ips.iterator();
}

public void addHost(String ip) {
ips.add(ip);
}

public void removeHost(String ip) {
ips.remove(ip);
iterator = ips.iterator();
}

public String getHost() {
if(!iterator.hasNext()) {
iterator = ips.iterator();
}
return iterator.next();
}
}