Katkat
Back

Find when failures started in log stream

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to identify the first occurrence of a specific condition in a sorted boolean stream using a modified binary search approach.

Problem Statement

You are monitoring a distributed system that logs health status checks in real-time. Each log entry is either True (system is healthy) or False (system has failed). The system logs are stored as a continuous stream where all True entries precede all False entries (i.e., the stream looks like [True, True, ..., True, False, False, ..., False]).

Given an interface is_healthy(index) that returns a boolean representing the health status at a specific index, find the index of the first False entry. If the system has never failed, return -1.

Because the stream is massive, you must optimize for the number of calls to is_healthy.

Constraints

  • The stream size N is unknown.
  • 0 <= index < N.
  • Minimize the number of calls to is_healthy.

Examples

Example 1:

  • Input: [True, True, False, False]
  • Output: 2
  • Explanation: The first False occurs at index 2.

Example 2:

  • Input: [True, True, True]
  • Output: -1
  • Explanation: No failure was found.

Edge Cases

  • The stream is entirely True.
  • The stream is entirely False.
  • The stream has only one entry.

Hints

Hint 1

Since the total number of entries is unknown, you first need to find an upper bound for the index of the first failure.

Hint 2

Use exponential backoff (checking indices 1, 2, 4, 8, ...) to find a range that contains the first `False` in O(log N) time.

Hint 3

Once you have an upper bound, perform a standard binary search within the determined range to find the first index where `is_healthy` returns `False`.

Follow-up questions

  • What is the time complexity of your solution in terms of the index `k` of the first failure?
  • How would your approach change if the stream was distributed across multiple machines?
  • What if the stream was not perfectly sorted, but instead contained occasional 'flapping' or noise (e.g., a few `False` values appearing before the true failure onset)?