Processing inputs and report success or error

Question

I have a program that gets requests (an array of strings of size n) from different domains (each input value is called as a domain) for each second i.

Within 5 seconds for a given domain the program should accept at most 2 successful requests.

Also at most 5 successful requests in 30 seconds.

For each request the program should return either "success" if accepted or "error" if not accepted.

Example:

n = 9, requests = ["xyz", "abc", "xyz", "pqr", "abc", "xyz", "xyz", "abc", "xyz"]


Result = 
["success", "success", "success", "success", "success", "success", "error", "success", "success"]

Explanation:

domain xyz occurs at indices = [0,2,5,6,8]
domain abc = [1,4,7]
domain pqr = [3]

If we pick index 6, if we pick 5 seconds range there are 2 successful requests at 2 and 5, so we get an error response at index 6. Remaining cases we get success response.

Constraints

n range is 1 to 10^4
input string contains lowercase English letters.

Here is what I tried:

public static List<String> solve(List<String> requests) {
    List<String> result = new ArrayList<>();
    Map<String, List<Integer>> map = new HashMap<>();

    int n = requests.size();
    for(int i=0; i<n; i++) {
        String s = requests.get(i);
        int time = i;
        
        // remove items older than 30 seconds
        while(!map.getOrDefault(s, new ArrayList<>()).isEmpty() && time - map.get(s).get(0) >= 30) {
            map.get(s).remove(0);
        }
        
        // remove items older than 5 seconds
        while(!map.getOrDefault(s, new ArrayList<>()).isEmpty() && time - map.get(s).get(0) >= 5) {
            map.get(s).remove(0);
        }
        
        //check if we have 2 successful requests for given domain
        if(map.getOrDefault(s, new ArrayList<>()).size() >= 2) {
            map.get(s).remove(0);
            result.add("error");
        } else {
            result.add("success");
            map.computeIfAbsent(s, k-> new ArrayList<>()).add(time);
        }   
    }
    return result;
}

When I tried to solve it my program fails saying wrong output for many test cases. What is the correct approach to solve this problem.

Answer 1

You don't check anything after first while loop, in fact you could just skip it and get the same result, it is doing absolutely nothing that the next while isn't doing anyway. The second while loop leads to discarding all values not in a 5s range, so it is impossible to check the 30s condition.

Fixed code (also using LinkedList instead of ArrayList where it is used like a Queue which would shift all elements in the ArrayList every time you remove the head).

public static List<String> solve(List<String> requests) {
    List<String> result = new ArrayList<>(requests.size()); // you know capacity
    Map<String, LinkedList<Integer>> map = new HashMap<>();

    int n = requests.size();
    for(int = 0; i < n; i++) {
        String s = requests.get(i);
        int time = i;
        // remove items older than 30 seconds only
        // no unnecessary list creations
        while(map.containsKey(s) && !map.get(s).isEmpty()) && time - map.get(s).getFirst() >= 30) {
            map.get(s).removeFirst();
        }
        // add element, you also need it in error case for next iteration
        map.computeIfAbsent(s, k-> new LinkedList<>()).add(time);
        // check both conditions now
        // the 2nd part is the general way to test if more than x elements in y time
        int m = map.get(s).size();
        if (m > 5 || m > 2 && time - map.get(s).get(m - 3) < 5) {
            result.add("error");
        } else {
            result.add("success");
        }   
    }
    return result;
}