Spotting an Error Spike

Hard Sliding window 2 parts 262 lines View on GitHub ↗

Question

Topic: Sliding window / Hashing · Difficulty: Medium → Hard

Log lines arrive in time order as timestamp,merchantId,statusCode,count. Alert when a merchant’s errors spike. Output alerts sorted by timestamp, then merchant, then status code.

Part 1: threshold alert

For each (merchant, non-200 status), if the errors in the last 30 seconds add up to at least 5, emit one TRIGGER (only the first time).

Part 2: compare against successes

Also require the failures to be significant next to successful traffic: alert only if failures ≥ 5 and failures × 100 > successes (200s) in the same window. Every new log line re-checks every failure code that merchant has seen.

Part 3: trigger and resolve

An alert can now clear. Emit TRIGGER when the condition becomes true and RESOLVE when it stops being true, so the same alert can fire again later.

Approach: per key, a time-ordered list of (timestamp, count); sum backwards while inside the 30s window. Part 3 keeps a set of active alerts to detect state changes.

SpottingAnErrorSpike.java 81 lines GitHub ↗

/**
 * Problem: Spotting an Error Spike
 * Difficulty: Hard
 * Topic: Sliding window
 * Question: Alert when a merchant has 5+ errors in 30s, then relative to successes, then with TRIGGER/RESOLVE events. Full statement in README.md.
 */
package dsa.question6;

import java.util.*;

public class SpottingAnErrorSpike {

    HashMap<String, Alert> alertGenerated;
    HashMap<String, List<Pair>> timestampOfAlert;
    int alertThreshold = 5;

    public void processAlert(long timeStamp, String merchantId, int statusCode, int count) {
        if(statusCode == 200) {
            return;
        }

        String key = merchantId + "-" + statusCode;
        if(alertGenerated.containsKey(key)) {
            return;
        }

        //add
        timestampOfAlert.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timeStamp, count));
        List<Pair> alerts = timestampOfAlert.get(key);
        int threshold = 0;
        long timelimit = timeStamp - 30;
        for(int i = alerts.size() - 1; i>=0 ;i-- ) {
            if(alerts.get(i).timestamp > timelimit) {
                threshold += alerts.get(i).count;
            }else{
                break;
            }
        }
        if(alertThreshold <= threshold) {
            Alert alert = new Alert(timeStamp, merchantId, statusCode, "TRIGGER");
            alertGenerated.put(key, alert);
        }

        return;

    }

    public List<Alert> spotSpikeAlert(String[] alertLog) {

        alertGenerated = new LinkedHashMap<>();
        timestampOfAlert = new HashMap<>();

        for(int i=0 ;i<alertLog.length; i++) {
            String[] log = alertLog[i].split(",");
            long timestamp = Long.valueOf(log[0].trim());
            String merchant = log[1].trim();
            int statusCode = Integer.valueOf(log[2].trim());
            int count = Integer.valueOf(log[3].trim());

            processAlert(timestamp, merchant, statusCode, count);
        }

        List<Alert> ans = new ArrayList<>();
        alertGenerated.forEach((key, value) -> {
            ans.add(value);
        });

        ans.sort(
                Comparator.comparingLong((Alert a) -> a.timestamp)
                        .thenComparing(a -> a.merchant)
                        .thenComparingInt(a -> a.statusCode)
        );

        return ans;
    }

    public class Pair{
        long timestamp;
        int count;
        public Pair(long timestamp, int count) {
            this.timestamp = timestamp;
            this.count = count;
        }
    }

    public class Alert {

        long timestamp;
        String event;
        String merchant;
        int statusCode;

        public Alert(long timestamp, String merchant, int statusCode, String event) {
            this.timestamp = timestamp;
            this.merchant = merchant;
            this.statusCode = statusCode;
            this.event = event;
        }
    }
}

SpottingErrorSpikePart2.java 91 lines GitHub ↗

package dsa.question6;

import java.util.*;

public class SpottingErrorSpikePart2 {

    HashMap<String, Alert> alertGenerated;
    HashMap<String, List<Pair>> timestampOfAlert;
    int alertThreshold = 5;
    HashMap<String, Set<Integer>> failureCodes = new HashMap<>();

    public void processAlert(long timeStamp, String merchantId, int statusCode, int count) {
        String key = merchantId + "-" + statusCode;
        timestampOfAlert.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timeStamp, count));
        if (statusCode != 200) {
            failureCodes.computeIfAbsent(merchantId, k -> new HashSet<>()).add(statusCode);
        }
        for (int code : failureCodes.getOrDefault(merchantId, Collections.emptySet())) {
            check(timeStamp, merchantId, code);
        }
    }

    private void check(long timeStamp, String merchantId, int statusCode) {
        String key = merchantId + "-" + statusCode;
        if (alertGenerated.containsKey(key)) {
            return;
        }

        List<Pair> alerts = timestampOfAlert.get(key);
        long fails = 0, success = 0;
        long timelimit = timeStamp - 30;
        for (int i = alerts.size() - 1; i >= 0; i--) {
            if (alerts.get(i).timestamp > timelimit) {
                fails += alerts.get(i).count;
            } else {
                break;
            }
        }

        String successkey = merchantId + "-" + 200;
        if (timestampOfAlert.containsKey(successkey)) {
            List<Pair> successLog = timestampOfAlert.get(successkey);
            for (int i = successLog.size() - 1; i >= 0; i--) {
                if (successLog.get(i).timestamp > timelimit) {
                    success += successLog.get(i).count;
                } else {
                    break;
                }
            }
        }

        if (alertThreshold <= fails && fails * 100 > success) {
            Alert alert = new Alert(timeStamp, merchantId, statusCode, "TRIGGER");
            alertGenerated.put(key, alert);
        }
    }

    public List<Alert> spotSpikeAlert(String[] alertLog) {

        alertGenerated = new LinkedHashMap<>();
        timestampOfAlert = new HashMap<>();

        for(int i=0 ;i<alertLog.length; i++) {
            String[] log = alertLog[i].split(",");
            long timestamp = Long.valueOf(log[0].trim());
            String merchant = log[1].trim();
            int statusCode = Integer.valueOf(log[2].trim());
            int count = Integer.valueOf(log[3].trim());

            processAlert(timestamp, merchant, statusCode, count);
        }

        List<Alert> ans = new ArrayList<>();
        alertGenerated.forEach((key, value) -> {
            ans.add(value);
        });

        ans.sort(
                Comparator.comparingLong((Alert a) -> a.timestamp)
                        .thenComparing(a -> a.merchant)
                        .thenComparingInt(a -> a.statusCode)
        );

        return ans;
    }

    public class Pair{
        long timestamp;
        int count;
        public Pair(long timestamp, int count) {
            this.timestamp = timestamp;
            this.count = count;
        }
    }

    public class Alert {

        long timestamp;
        String event;
        String merchant;
        int statusCode;

        public Alert(long timestamp, String merchant, int statusCode, String event) {
            this.timestamp = timestamp;
            this.merchant = merchant;
            this.statusCode = statusCode;
            this.event = event;
        }
    }
}

SpottingErrorSpikePart3.java 90 lines GitHub ↗

package dsa.question6;

import java.util.*;

public class SpottingErrorSpikePart3 {

    HashSet<String> active = new HashSet<>();
    List<Alert> events = new ArrayList<>();
    HashMap<String, List<Pair>> timestampOfAlert = new HashMap<>();
    HashMap<String, Set<Integer>> failureCodes = new HashMap<>();
    int alertThreshold = 5;

    public void processAlert(long timeStamp, String merchantId, int statusCode, int count) {
        String key = merchantId + "-" + statusCode;
        timestampOfAlert.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timeStamp, count));
        if (statusCode != 200) {
            failureCodes.computeIfAbsent(merchantId, k -> new HashSet<>()).add(statusCode);
        }
        for (int code : failureCodes.getOrDefault(merchantId, Collections.emptySet())) {
            check(timeStamp, merchantId, code);
        }
    }

    private void check(long timeStamp, String merchantId, int statusCode) {
        String key = merchantId + "-" + statusCode;

        List<Pair> alerts = timestampOfAlert.get(key);
        long fails = 0, success = 0;
        long timelimit = timeStamp - 30;
        for (int i = alerts.size() - 1; i >= 0; i--) {
            if (alerts.get(i).timestamp > timelimit) {
                fails += alerts.get(i).count;
            } else {
                break;
            }
        }

        String successkey = merchantId + "-" + 200;
        if (timestampOfAlert.containsKey(successkey)) {
            List<Pair> successLog = timestampOfAlert.get(successkey);
            for (int i = successLog.size() - 1; i >= 0; i--) {
                if (successLog.get(i).timestamp > timelimit) {
                    success += successLog.get(i).count;
                } else {
                    break;
                }
            }
        }

        boolean meets = alertThreshold <= fails && fails * 100 > success;
        if (meets && !active.contains(key)) {
            active.add(key);
            events.add(new Alert(timeStamp, merchantId, statusCode, "TRIGGER"));
        } else if (!meets && active.contains(key)) {
            active.remove(key);
            events.add(new Alert(timeStamp, merchantId, statusCode, "RESOLVE"));
        }
    }

    public List<Alert> spotSpikeAlert(String[] alertLog) {

        active = new HashSet<>();
        events = new ArrayList<>();
        timestampOfAlert = new HashMap<>();

        for(int i=0 ;i<alertLog.length; i++) {
            String[] log = alertLog[i].split(",");
            long timestamp = Long.valueOf(log[0].trim());
            String merchant = log[1].trim();
            int statusCode = Integer.valueOf(log[2].trim());
            int count = Integer.valueOf(log[3].trim());

            processAlert(timestamp, merchant, statusCode, count);
        }


        events.sort(
                Comparator.comparingLong((Alert a) -> a.timestamp)
                        .thenComparing(a -> a.merchant)
                        .thenComparingInt(a -> a.statusCode)
        );

        return events;
    }

    public class Pair{
        long timestamp;
        int count;
        public Pair(long timestamp, int count) {
            this.timestamp = timestamp;
            this.count = count;
        }
    }

    public class Alert {

        long timestamp;
        String event;
        String merchant;
        int statusCode;

        public Alert(long timestamp, String merchant, int statusCode, String event) {
            this.timestamp = timestamp;
            this.merchant = merchant;
            this.statusCode = statusCode;
            this.event = event;
        }
    }
}