Find first error and propagate failures
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given a chronological log history where each entry is a string prefixed with one of [Info], [Warn], or [Error]. Two invariants hold:
(
1) once the first [Error] appears, all subsequent entries are [Error];
(
2) the entry immediately before the first [Error] is [Warn]. Task 1 (Binary Search): Return the 0-based index of the first [Error] using O(log n) comparisons; explain the decision rule at mid and prove correctness and time/space complexity. Follow-up 1 (Graph BFS/DFS): You are also given a directed service call graph where an edge A -> B means service A calls (depends on) service B, and a single service s that first starts erroring. If failures propagate upstream (when B fails, every caller of B eventually fails), output the set of all services that will end up in error; design an algorithm using BFS or DFS, specify input/output formats (e.g., adjacency list), and describe how you handle cycles or repeated visits. Follow-up 2 (Graph DFS for longest chain): On the same graph and start service s, output one of the longest error propagation chains starting at s (a longest simple path starting from s). Use DFS to maintain the current path and best-so-far path; describe how you avoid revisiting nodes, and analyze complexity and assumptions needed for tractability.
Quick Answer: This question evaluates proficiency with algorithmic invariants and search techniques, specifically binary search on ordered logs, graph traversal (BFS/DFS) for reachability and longest-path reasoning, cycle handling, and formal analysis of correctness and time/space complexity within the Coding & Algorithms domain.
You are given: (A) a chronological list of log entries where each string begins with one of "[Info]", "[Warn]", or "[Error]"; (B) a directed service call graph as edges (u, v) meaning service u calls/depends on service v; and (C) a service s that first starts erroring. In the logs, two invariants hold: once the first "[Error]" appears, every following entry is "[Error]"; the entry immediately before the first "[Error]" is "[Warn]". Implement a function that returns a tuple of three results: (1) the 0-based index of the first "[Error]" using O(log n) comparisons; if no error exists, return -1; (2) the set of all services that will end up in error when failures propagate upstream (if B fails, all services that call B eventually fail), returned as a lexicographically sorted list; (3) one of the longest error propagation chains starting at s in the upstream direction (a longest simple path in the reverse graph), returned as a list of services starting at s. If multiple longest chains exist, return the lexicographically smallest sequence. Assume the call graph is a DAG for part (3).
Constraints
- 2 <= len(logs) <= 200000
- Each log entry starts with exactly one of: "[Info]", "[Warn]", "[Error]"
- Monotonic logs: once the first "[Error]" appears, all subsequent entries are "[Error]"
- The entry immediately before the first "[Error]" is "[Warn]" (thus, the first error index >= 1) unless no error exists
- 0 <= number of services <= 100000; 0 <= number of edges <= 200000
- Edges (u, v) mean u depends on v; failure propagates from v to u
- Service names are non-empty ASCII strings and uniquely identify services
- For part (3), the call graph is a DAG (thus the reverse graph is also acyclic)
- Return the failing services as a lexicographically sorted list; for longest chains, break ties by lexicographically smallest sequence
Hints
- For the first error index, the predicate "logs[i] starts with '[Error]'" is monotone; use binary search to find the lowest i with predicate true.
- Build the reverse graph (for edge u->v, add v->u) and run BFS/DFS from s to find all upstream callers that fail.
- For the longest chain on a DAG, use DFS with memoization to compute the longest path length from each node; to break ties, pick the next node with the smallest name among those achieving the same length, then reconstruct the path from s.