A classic problem in applied-problem form.
Binary Search
The input is a log history. There are three types of logs: Info, Warn, and Error, and each log line starts with its own type — for example an Info log looks like "[Info] ...". The log history follows two patterns:
- Once an Error shows up, the service goes down, and every log after that is Error
- The log right before the first Error is always a Warn
The problem asks you to find the first Error that appears.
Binary search approach: search for the left boundary of the Error logs.
- If you hit Info or Warn, search to the right
- If you hit Error, search to the left
Graph BFS
This one is basically a follow-up to the previous problem, background-wise.
When a service crashes, all of its upstream services (the services that call it) crash along with it. The input is the dependency (call) relationships 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 is even given directly in adjacency-list format, so there's no preprocessing needed) — the service where the Error first started is the starting point, and you BFS or DFS this graph.
Graph DFS
Continuing the 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 easier to keep track of the path.
Discussion
Loading comments…