Implement a SessionManager class that distributes sessions across 3 servers (e.g., s1, s2, s3) while maintaining load balance. The class must support two methods: (1) start_session(session_id: str) -> None — assigns the given session to the server currently holding the fewest sessions, but silently rejects duplicate session IDs that have already been registered; (2) get_allocation() -> Dict[str, Set[str]] — returns a mapping of each server to its set of assigned session IDs. At all times, the difference in session count between any two servers must not exceed 1 (e.g., [8, 8, 8] or [8, 8, 7] are valid; [9, 8, 7] is not). Candidates are also expected to write their own test cases covering normal operation and edge cases.
What happens if the same session ID is submitted twice concurrently in a multi-threaded environment?
What edge cases did you choose to test and why?
How would you handle removing a session (end_session)?
| Approach | Notes |
|---|---|
| Round-robin assignment | Simple O(1) assignment but does not handle session removal or dynamic imbalance; fails if sessions can be removed or if server counts can diverge. |
| Sorted list / linear scan | Correct but O(n) per insertion instead of O(log n); impractical at scale. |
Common mistakes: Missing the duplicate session ID edge case — not tracking which session IDs have already been registered, allowing the same ID to be assigned multiple times.
Interviewer hints: The balance constraint is explicit: the session count gap between any two servers must not exceed 1 (e.g., [8,8,8] or [8,8,7] valid; [9,8,7] invalid).
What passers do: Used a min-heap storing (num_of_sessions, server_id) so that start_session always pulls the server with the fewest sessions in O(log n) time, then pushes it back after incrementing.; Maintained a separate set of already-registered session IDs to silently reject duplicate start_session calls.; Wrote their own test cases covering both normal operation and the duplicate session ID edge case.
Send them this page. It is free to read, no account needed.
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 15 Palantir questions, refreshed monthly from new candidate reports.