Requirements
- Implement the supplied session-manager class.
- Support
start_session(session_id: str) -> Noneto assign a new session to a server. - Support
get_allocation()to return a dictionary mapping server IDs to sets of session IDs. - Keep the difference between any two servers' session counts at most one.
- A session ID that has already started must not be added again.
- Write tests covering ordinary allocation and edge cases, including duplicate session IDs.
Examples
For three servers [s1, s2, s3], valid balanced session-count distributions include [8, 8, 8] and [8, 8, 7].
Notes
- The full phone screen lasts 60 minutes; approximately 15 minutes are spent on a résumé project and 40 minutes on coding.
- The project discussion emphasizes methodology and decision-making rather than only technical implementation.
- Server initialization, allocation tie-breaking, and behavior with no servers are unspecified; clarify these before coding.
Solution approach
- For a fixed nonempty server set that starts empty, keep a set of all assigned session IDs and a server-to-session-set mapping. Check the global set before allocating, so a duplicate does not change any count.
- Choose a least-loaded server for each new ID. If counts initially differ by at most one, incrementing a minimum preserves that invariant. A scan is a simple O(S) choice per insertion for S servers.
- A min-heap of (count, stable tie-break key, server ID) reduces the selection and update to O(log S) per new session for S >= 2, with expected O(1) hash-set lookup. Keep one heap entry per server. Storage is O(S + N) for N unique sessions.
- Decide whether get_allocation returns a snapshot. A defensive copy costs O(S + N) and prevents callers from mutating the manager through the returned sets. This is an implementation choice to clarify, not an additional interview requirement.
Preparation
- In 20 minutes, implement the two methods for a fixed nonempty server list and verify that every distinct session appears on exactly one server.
- In 10 minutes, add tests for duplicate IDs, uneven totals, an empty allocation, and the agreed no-server behavior; assert the count difference after every insertion.