Set with constant-time insert, delete and get random
Design a set with add, remove and get_random, all in average O(1); get_random returns each element with equal probability. Handle empty-set and missing-element cases. Follow-up: how would you make it safe for concurrent use (one lock for the set versus finer-grained locking)?
GoogleTechnical phone screenNo answer yet. Write the first one; the best answer gets endorsed.