It's the courier question that's already up on the forum, and the forum write-up was already very detailed! But there's one thing it left out: the same dasher can take multiple orders at the same time.
When I was practicing beforehand I hadn't considered that case, and I hadn't seen it mentioned on the forum either, so when the third, concurrent follow-up came out, I had to think about it for a bit. Without the case of one dasher taking multiple orders, the solution is just (time, +1/-1) events. With multiple orders per dasher, it becomes (dasherId, time, +1/-1), plus an extra map for de-duplication — if you find that this dasher has already been counted as +1, you don't add it again.
Because the solution I wrote on the spot failed one test (I thought about it for a few days — it turns out it's that when sorting, you need to handle ties specially: -1 should come before +1. Python handles that automatically for (time, +1/-1), but it does not automatically handle ties for (dasherId, time, +1/-1). That's where it went wrong. Putting dasherId last fixes it automatically.)
There were still 5-8 minutes left, but the interviewer wouldn't let me keep debugging. I figured I'd definitely failed the KPI round, but 4 business days later they told me I'd passed.
Discussion
Loading comments…