I just finished the first coding round at Cresta, so here is a report. The role is Senior Software Engineer. After the recruiter call there are two coding rounds, one hour each, and this one was the problem solving round.
The question: you are given a dict where the key is an agent and the value is that agent's active periods. Each period is [start, end, chats], and both start and end are inclusive. The load at any time t is the sum of chats over all periods that contain t. Find the maximum load, and one time at which that maximum load occurs.
Here is how I thought about it: sweep line. First flatten the dict into intervals, then for each interval add chats at start and subtract chats at end+1, since end is inclusive. Sort the change points, sweep through once, and keep track of the current load and the maximum.
changes = sorted map from time to load change
for each [start, end, load]:
changes[start] += load
changes[end + 1] -= load
currentLoad = 0
maximumLoad = 0
bestTime = none
for each (time, change) in changes in ascending order:
currentLoad += change
if currentLoad > maximumLoad:
maximumLoad = currentLoad
bestTime = time
return maximumLoad and bestTime
Two things to watch out for: end is inclusive, so the subtraction goes at end+1; and the comparison is strictly greater than, so on a tie you keep the earliest time.
I don't have the result yet, I'll update once I do.
Discussion
Loading comments…