Scale a Distributed Randomized Multiset
Company: LinkedIn
Role: Software Engineer
Category: System Design
Difficulty: medium
Interview Round: Technical Screen
After designing the randomized multiset on a single machine, explain how you would scale it across multiple servers.
The distributed system should support the same logical operations:
- `insert(val)`
- `remove(val)`
- `getRandom()`
Discuss how requests are routed to the correct server, how data is partitioned, how to rebalance data when servers are added or removed, and how to implement `getRandom()` so that the returned element is globally random across all stored occurrences, not just within one shard.
Overview: This question evaluates expertise in designing scalable distributed data structures, focusing on competencies such as data partitioning, request routing, fault-tolerant rebalancing, and achieving globally uniform random sampling across shards.