A classic problem in application-question form.
Binary Search
The input is a log history. There are three kinds of logs: Info, Warn, and Error, and each log starts with its own type — for example, an Info-type log looks like "[Info] ...". The log history follows two patterns:
- Once an Error shows up, the service is down, and every log after that is also Error.
- The first Error is always preceded by a Warn.
The question asks you to find the first Error that appears.
Binary search approach: search for the left boundary of the Error logs.
- On Info or Warn, search right.
- On Error, search left.
The graph BFS question was basically a follow-up to the previous one, using the same setup.
When a service crashes, all of its upstream services (the ones that call it) crash along with it. The input is the dependency (call) relationship between services, plus the service where the Error first started, and the output is all the services that will eventually Error (order doesn't matter).
The dependency relationships between services define a graph, with services as nodes and dependencies as edges (the input might even come directly in adjacency-list format, so there's no preprocessing needed). The service where the Error first started is the starting node — BFS or DFS this graph.
Graph DFS
As a further follow-up: output the longest Error call chain, i.e. the longest traversal path starting from the service where the Error first started. DFS makes it easy to maintain the path.
Discussion
Loading comments…