Codegoda 2021

Jul 18, 2021 3 min read

1.

2.

3.

4.

5.

6. Which microservice failed?

Given the services (nodes in the graph) that alert, the task is to identify which services is the root cause of the failure. A failure is a root cause only when there are no other dependencies which also fail.

graph TD;
  A-->B;
  A-->C;
  B-->D;
  C-->E;
  E-->D;
  C-->F;

Input (alerts):

1 E 
3 A C E 
2 A D 
3 D E F

Example output:

1 E 
1 E 
1 D 
2 D F

Explanation

The input graph (omitted) is the one shown in the diagram above. The input has 4 alerts.

In the first case, only service E has an alert. Thus, E is the root cause.

In the second alert case, services A, C and E have alerts. Since A depends on C and C depends on E, we don’t consider them the root cause. E has no dependency and has an alert. Thus, E is the root cause.

In the third case, services A and D have alerts. Since A depends on D through C, B and E, we still consider that the failure on service D might have caused a failure on service A even if the alerts on services C, B and E did not fire. Thus, D is the root cause.

In the fourth case, services D, E and F have alerts. E depends on D, so E is not the root cause. D and F do not depend on any services which failed, so they both are the root causes.

Solution 1

This is probably not an optimal solution, but it came first when I tried. The idea is to construct a reverse graph and find all the descendants. In this case, the time complexity would be $O(A(E + V))$ where $A$ is the number of alerts and $V$ and $E$ is the number of vertices and edges in the graph respectively.

void dfs(
  const int root,
  const int start,
  const vector<vector<int>>& adj, // Adjacency list of the reversed graph
  vector<bool>& visited,
  unordered_map<int, bool>& root_causes
)
{
  if (root != start) {
    auto it = root_causes.find(root);
    if (it != root_causes.end()) {
      root_causes.erase(it);
    }
  }
  visited[root] = true;
  for (const auto n : adj[root]) {
    if (!visited[n]) {
      dfs(n, start, adj, visited, root_causes);
    }
  }
}

void solve(
  const vector<vector<int>>& adj, // Adjacency list of the reversed graph
  unordered_map<int, bool> services_with_alert,
  const vector<string>& service_names
)
{
  unordered_map<int, bool> root_causes = services_with_alert;
  for (const auto p : services_with_alert) {
    size_t num_services = service_names.size();
    vector<bool> visited(num_services, false);
    dfs(p.first, p.first, adj, visited, root_causes);
  }
  // print out solution
  cout << root_causes.size();
  for (const auto p : root_causes) {
    cout << " " << service_names[p.first];
  }
  cout << endl;
}

7.

8.

9.


Notes

  • I couldn’t seem to find restrictions on sharing or posting questions in the terms (https://codegoda.io/terms-and-conditions/). But if I read it wrong, Dear Agoda, please let me know if it is against the terms.
C++

Related