Round 1's interview and timeline are covered in a separate link, so I won't repeat that here.
The interviewer described the question verbally: Amazon has a ton of services, and there are dependencies between them. When we take some of those services offline, figure out which other services end up affected.
Clarifying questions: always, always do this first — get the conditions of the problem completely nailed down before anything else. I asked the interviewer for an example. He wasn't prepared for that and ended up drawing a diagram on the spot. Once I had the example, I confirmed this was a topological sort problem.
- Could the input be invalid, e.g. contain a cycle? -> No, the input is guaranteed to be valid.
- Can I define my own input format? -> Yes. I defined the input as a hashmap where the key is a service name and the value is the list of services that depend on it.
Before writing any code: you have to talk through your approach out loud first. Amazon's coding environment doesn't actually run your code, so if you just start typing without explaining your reasoning and the interviewer doesn't buy into your code, you're basically done for. So walk through the plan before you write anything.
My approach:
- Count the in-degree of every service.
- Push every service with in-degree 0 into a queue.
- Initialize a set of affected services, seeded with the services that were shut down.
- Process the queue by popping from the front each time.
- Look at the list of services that depend on the current one. If the current service is in the affected set, add each dependent service to the set as well. Also decrement the dependent service's in-degree, and if it hits 0, push it into the queue.
- When the queue is empty, return the affected-services set.
Discussion
Loading comments…