CareerCup

Maybe you could combine a hash table with a custom data structure that is backed by an array. The hash table would have an index into the array.

AddServer:
insert value at end of array: O(1)
insert value and array index in hash table: O(1)

RemoveServer:
get array index from hash table, delete entry from hash table: O(1)
replace array entry with last array value: O(1)
update array index in corresponding hash table entry: O(1)

ReturnRandomServer:
access array by index using random mod array size: O(1)

Not sure they would accept the amortized O(1) costs of the hash table though.

This puppy is an interesting one. Thanks for posting. I do not have an answer...but I am hoping my thought process can generate a response with an answer :-)

O(1) add and remove is possible with a hash OR a double linked list. It is the return random server that is the problem.

I thought about probabilistic structures like skip lists and blook filter, could not get a guaranteed O(1). I thought about a bitmap of remaining servers...not O(1).

Would welcome a tip from somebody else :-) Thanks in advance.

Hi smallchallenges,

Can you explain how this addresses the RandomServer part? You note cuckoo hashing supports constant time lookup, delete and amotized inserts, but stated earlier that O(1) add and delete are already possible. So how does cuckoo hashing help with the Random server part? Thanks for clarifying :)