How should I practice Balanced Session Manager?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Palantir phone screen problems in FastPrep.

Is Balanced Session Manager associated with Palantir?

FastPrep tags this as a Palantir phone screen coding practice problem when the problem catalog has that company and stage context.

Balanced Session Manager

Palantir● MediumNEW GRADPHONE SCREEN

Problem statement

Source note: The report gives a detailed practice spec for a session manager that keeps every server's load within one session of the others, with start, end and snapshot operations and a fast-update goal. The author says this practice version extends the original interview task, which had session starts and balancing only, by adding ending sessions and the speed goal. The source accepts any balanced allocation. These practice choices make answers checkable: a new session goes to the server with the fewest sessions, the earliest one on ties; when an end leaves a gap of two, the newest session on the earliest most-loaded server moves, where a session that arrived by a move counts as the newest on its new server; the operations come as a list and each snapshot gives one row per server with its session IDs sorted; IDs use lowercase letters and digits; and the size limits. The judged core task matches the source at about 85%.

You manage active sessions on a fixed list of servers, servers. Each active session adds a load of 1 to the server it is on. After every operation, the most-loaded server may have at most one more session than the least-loaded server. For example, loads [3, 3, 2] and [1, 0, 0] are balanced, but [3, 3, 1] is not. To keep this rule, an existing session may be moved to another server.

Process operations in order. Each operation is one of these:

["start", sessionId]: start a session. If sessionId is already active, do nothing. Otherwise, place it on the server with the fewest sessions. If several servers tie, use the one that comes first in servers.
["end", sessionId]: end the session and remove it from its server. If sessionId is not active, do nothing. If the server that lost the session now has two fewer sessions than the most-loaded server, move one session to it. Take the session from the most-loaded server that comes first in servers, and move the session that was placed on that server most recently, whether it arrived by a start or by an earlier move. An ended ID may be started again later as a new session.
["allocation"]: take a snapshot of where every active session is.

For each ["allocation"] operation, add one row per server to the answer, in the order of servers. A row starts with the server ID, followed by the IDs of that server's sessions in lexicographic order. A server with no sessions gives a row with only its ID. Return all rows in order.

One move is always enough: ending a session lowers one load by 1, so at most one server ends up two below the maximum.

Performance

Let S be the number of servers. Try to make each start and end take O(log S) time without scanning every server or every session. Taking a snapshot may take O(S + A) time, where A is the number of active sessions. Say which of your bounds are worst-case, average-case, or amortized, and whether your memory use grows with the number of past operations. The tests are small enough that scanning every server also passes, so this goal is for your design and complexity analysis.

Function

balanceSessions(servers: String[], operations: String[][]) → String[][]

Examples

Example 1

servers = ["s1","s2","s3"]operations = [["start","a"],["start","b"],["start","c"],["start","d"],["start","e"],["allocation"],["start","a"],["allocation"],["end","c"],["allocation"]]return = [["s1","a","d"],["s2","b","e"],["s3","c"],["s1","a","d"],["s2","b","e"],["s3","c"],["s1","a"],["s2","b","e"],["s3","d"]]

Each start goes to the server with the fewest sessions, ties going to the earliest server: a to s1, b to s2, c to s3, d to s1, and e to s2. The first snapshot shows loads [2, 2, 1].

Starting a again does nothing because it is already active, so the second snapshot is the same.

Ending c leaves s3 empty while s1 and s2 hold 2 sessions. The earliest most-loaded server is s1, and its most recently placed session is d, so d moves to s3. The last snapshot shows loads [1, 2, 1].

Example 2

servers = ["s1"]operations = [["end","x"],["allocation"],["start","x"],["allocation"],["end","x"],["allocation"],["start","x"],["allocation"]]return = [["s1"],["s1","x"],["s1"],["s1","x"]]

Ending x before it starts does nothing. After that, x starts, ends, and starts again on the only server. Each snapshot is one row for s1.

Example 3

servers = ["x","y"]operations = [["start","p"],["start","q"],["start","r"],["end","q"],["allocation"],["end","r"],["allocation"]]return = [["x","p"],["y","r"],["x","p"],["y"]]

Sessions p and r go to x and q goes to y. Ending q leaves y empty while x holds 2, so the newest session on x, r, moves to y.

Ending r then removes it from y, its current server. Loads [1, 0] are balanced, so nothing moves.

Constraints

1 <= servers.length <= 100
Server IDs are unique. Each has 1 to 10 characters, all lowercase letters or digits.
1 <= operations.length <= 1000
Each operations[i] is ["start", sessionId], ["end", sessionId], or ["allocation"].
Each sessionId has 1 to 10 characters, all lowercase letters or digits.
At most 10 operations are ["allocation"].