Tower Research's Streaming Failure Detector

Tower Research likes streaming data-structure problems that have to run forever without leaking. This failure detector watches an infinite log stream and alerts on three failures inside a window, then the interviewer pushes on memory and scale. Here is the full question, Java for each part, and a detailed rubric.

The question

Part 1 · Per-user sliding window

Keep a deque of recent failure timestamps per user. On a failure, append and evict anything older than the window; on a success, clear the user. Alert when the window holds at least the threshold.

import java.util.*;

class FailureDetector {
    private final int threshold; private final long window;
    private final Map<String, Deque<Long>> failures = new HashMap<>();

    FailureDetector(int threshold, long window) { this.threshold = threshold; this.window = window; }

    boolean process(long ts, String user, String event) {
        if (!event.equals("failure")) { failures.remove(user); return false; }   // success resets streak

        Deque<Long> dq = failures.computeIfAbsent(user, k -> new ArrayDeque<>());
        dq.addLast(ts);
        while (!dq.isEmpty() && ts - dq.peekFirst() > window) dq.pollFirst();     // evict stale
        return dq.size() >= threshold && (dq.peekLast() - dq.peekFirst() <= window);
    }
}

Part 2 · Bound the memory

Two leaks hide here. A single user's deque should never exceed the threshold, and users that stop failing should not linger forever. Cap the deque, drop empty entries, and sweep idle users.

    boolean process(long ts, String user, String event) {
        if (!event.equals("failure")) { failures.remove(user); return false; }

        Deque<Long> dq = failures.computeIfAbsent(user, k -> new ArrayDeque<>());
        dq.addLast(ts);
        while (!dq.isEmpty() && ts - dq.peekFirst() > window) dq.pollFirst();
        if (dq.size() > threshold) dq.pollFirst();        // never store more than we need
        if (dq.isEmpty()) failures.remove(user);          // drop emptied users
        return dq.size() >= threshold && (dq.peekLast() - dq.peekFirst() <= window);
    }

    // Periodic sweep: forget users whose newest failure has aged out of the window.
    void evictIdle(long now) {
        failures.entrySet().removeIf(e -> now - e.getValue().peekLast() > window);
    }

Per-user memory is now O(threshold), a tiny constant, and total memory is bounded by the number of recently active users rather than everyone ever seen.

Part 3 · Scale to many users

The state is partitioned cleanly by user, so it shards. Hash each user to one of N workers and every event for that user lands on the same worker, which keeps its stream ordered and its window correct without cross-worker coordination.

How Tower Research scores it

Tower Research interview FAQ