I can confirm that changing the boilerplate code to this made all tests failing due to timeout pass.

Thanks!

Can also confirm that changing my (Java 8) boilerplate code to this made all tests that were failing due to timeout (Test cases 9 - 15) pass.

Thank you so much, and shame on HackerRank for providing bad boilerplate code!

I did this but still tests 10,12,13 fail due to timeout. Please help

my solution :

static List freqQuery(List queries) {

    HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
    List<Integer> retList = new ArrayList<Integer>();

    for(int i=0;i<queries.size();i++)
    {
        int op = queries.get(i)[0];
        int num = queries.get(i)[1];
        if(op==1)
        {
            if(!hash.containsKey(num))
                hash.put(num,1);
            else
                hash.put(num,hash.get(num)+1);
        }
        else
        if(op==2)
        {
            if(hash.containsKey(num))
            {
                if(hash.get(num)<=1)
                    hash.remove(num);
                else
                    hash.put(num,hash.get(num)-1);
            }

        }
        else
        if(op==3)
        {
            if(hash.containsValue(num)){
                retList.add(1);
            }
            else
                retList.add(0);

        }
    }

    return retList;
}

Thanks! Now tests 9-13 pass without "Terminated due to timeout" status with Java 8.

I agree with above comment.

I am getting compilation error in the main after changing my boilerplate code. Solution.java:63: error: ')' expected .map(Object::toString) ^

Solution.java:63: error: ';' expected .map(Object::toString) ^

Solution.java:63: error: not a statement .map(Object::toString) ^

Solution.java:63: error: ';' expected .map(Object::toString) ^

Solution.java:65: error: not a statement + "\n"); ^

Solution.java:65: error: ';' expected + "\n"); ^

That was very helpful. Thank you.

• Ramo

Good catch! I was hoping something like this was the case. I was pretty confident my implementation was O(1) for each of the query operations, but was still getting timeout errors for cases 9-13. After fixing the boilerplate code, all cases are passing. Thanks!

Hackerrank has so many issues... Thanks a ton! This made my test cases pass. My algorithm was linear and always used constant time access, so really this boiler plate code shouldn't matter if the tests are correct. I.E. they should be testing Big O not absolute time.

It's sad! I wasted hours trying to figure out why my tests were timing-out only to find out the bloddy boilerplate code as the culprit!

Very true. Saved further debugging time! I was wondering why its still failing instead my algorithm is quite efficient

I supposed, the result depends on server state. I have to rewrite output code and add inverse map to pass all tests.

Thank you. I didn't know why I had problems of timeout, but your change solved my problem. TY.

Thanks, the Java 8 harness is often joke tier but this one... I came to the discussions after measuring that the whole main method took 1600ms while my own code took 200ms for one of the failing cases.

Thanks, works for me!

Same for me. Solution is in O(n), this new boiler plate made me pass the tests immediately.

I was surprised that when I changed the boilerplate to use an array list presized to q, with elements that were array lists of size 2, I still couldn't beat the timeout. If anybody gets this to work with arraylist or list as the entries, I would be curious to see what they did in the boilerplate. Maybe above would work with compiled pattern but array list of array lists.... Maybe it's the time lost simply to allocate a wrapped integer instead of a primitive.

thank you. I was slowly getting pissed off but now everything passes.

Arrrrgh.... changed the function to take an int[], AND had it return an int[] (by counting the number of queries on input, and then passing that into the function) and am still timing out on 12 and 13. Stripped down my code so it now uses only a single non-primitive structure (one Map to keep track of the frequency of each number), and it's still not passing.

I'll have to come back to this one.

My solution was showing WA for test cases 9-13. Changing boiler plate code fixed it.

Thanks a lot @eduardocorral

Thank you! I was just coming to the discussion to complain how tests are timing out on my O(n) solution and it's not obvious how to optimize it to pass.

Yay, works great! Thanks @eduardocorral. Agreed, HackerRank should test their own code.

Thank you for this. Was there more optimizations that i should have made that could have passed? I went over all queries once and used 2 maps to count frequencies and then the number of occurances for a particular value.

confirm, thank you!

Thanks man:) I spent 2 hours trying to understand what else can be improved. Shame on hackerrank boilerplate.

I also confirm that changing the boilerplate code to this made all tests failing due to timeout pass. Thank you so much !

Thanks. Finally it's work for me.

Why changing to int[] make it faster? I changed the code and all the tests passed. I wonder why. Is it because intializing a list is slower than intializing an array? Or list.get() is slower than array[index]?

Test cases 10-13 were failing but after changing the boilerplate code to the above code, they passed. Thanks brother.!

Bless you. You code executes 2-3 times faster on my machine and I finally passed the tests

There are two more things have to be done before passing all test cases.

1. Use String.split() instead of pattern match.
2. Use 2D array instead of List<int[]> to store all queries.

public static void main(String[] args) throws IOException {
    try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))) {

        int q = Integer.parseInt(bufferedReader.readLine().trim());
        int[][] queries = new int[q][2];
        
        for (int i = 0; i < q; i++) {
            String[] qs = bufferedReader.readLine().split(" ");
            queries[i][0] = Integer.parseInt(qs[0]);
            queries[i][1] = Integer.parseInt(qs[1]);
        }

        List<Integer> ans = freqQuery(queries);
        try (BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")))) {
            bufferedWriter.write(
                    ans.stream()
                            .map(Object::toString)
                            .collect(joining("\n"))
                            + "\n");
        }
    }
}

Can you give me your code

For all those who were like me , trying to find solution for java.... just use the above one or fast IO (make sure u do the same justice with output also) with your own implementation........

OR

import java.io.; import java.util.; import static java.util.stream.Collectors.joining;

public class Solution { public static void main(String[] args) throws IOException {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter out = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    List<Integer> result = new ArrayList<>();
    int n = Integer.parseInt(in.readLine());
    HashMap<Long, Long> map = new HashMap<Long, Long>();
    HashMap<Long, Long> freq = new HashMap<Long, Long>();

    for (int i = 0; i < n; i++) {
        StringTokenizer s= new StringTokenizer(in.readLine());
        int a = Integer.parseInt(s.nextToken());
        final long b = Long.parseLong(s.nextToken());
        switch (a) {
            case 1:
                freq.computeIfPresent(map.get(b), (k, v) -> v == 1 ? freq.remove(map.get(b)) : v - 1);
                map.compute(b, (k, v) -> v == null ? 1 : v + 1);
                freq.compute(map.get(b), (k, v) -> v == null ? 1 : v + 1);
                break;
            case 2:
                freq.computeIfPresent(map.get(b), (k, v) -> v == 1 ? freq.remove(map.get(b)) : v - 1);
                map.computeIfPresent(b, (k, v) -> v == 1 ? map.remove(b) : v - 1);
                freq.compute(map.get(b), (k, v) -> v == null ? 1 : v + 1);
                break;
            case 3:
                result.add(freq.containsKey(b) ? 1 : 0);
                break;
        }
    }
    out.write(result.stream().map(Object::toString).collect(joining("\n")) + "\n");

    in.close();
    out.close();
}

}

Using Java 8 even with the change in the boiler plate my code timed out some test cases.

I switched to using Java 7 and all tests pass.

Thank you so much for this! I was beginning to pull my hair wondering why I was still getting timeouts after implementing a reverse HashMap to keep track of frequencies instead of calling values().contains()

Check my accepted c++ code here: https://www.hackerrank.com/challenges/frequency-queries/forum/comments/648137?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Thank you for pointing this out. Here is a c# version of boiler plate:

        static void Main(string[] args)
        {
                int q = Convert.ToInt32(Console.ReadLine().Trim());

                var queries = new int[q,2];

                for (int i = 0; i < q; i++)
                {
                    var nq = new int[2];
                    nq = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(queriesTemp => Convert.ToInt32(queriesTemp)).ToArray();
                    queries[i, 0] = nq[0];
                    queries[i, 1] = nq[1];
                }

                List<int> ans = freqQuery(queries);
                Console.WriteLine(String.Join("\n", ans));
        }

Why doesn't this code which runs in O(n) pass the test cases 10, 11, 12 and 13? It times out.

static List<Integer> freqQuery(List<int[]> queries) {
    List<Integer> result = new ArrayList<Integer>();
    HashMap<Integer, Integer> map = new HashMap<>();
    HashMap<Integer, Integer> freq = new HashMap<>();
    for (int[] q: queries) {
        System.out.println("\nIndex: " + _count ++);
        int x = q[0];
        int y = q[1];
        Integer count = map.getOrDefault(y, 0);
        Integer _freq = freq.getOrDefault(count, 0);            
        if (x == 1) {
            freq.put(count, _freq > 0 ? (_freq - 1): 0);
            freq.put(count + 1, freq.getOrDefault(count + 1, 0) + 1);
            map.put(y, count + 1);
        } else if (x == 2) {
            if (count != 0) {
                freq.put(count, _freq > 0 ? (_freq - 1): 0);
                freq.put(count - 1, freq.getOrDefault(count - 1, 0) + 1);
                map.put(y, count - 1);
            }
        } else if (x == 3) {
            result.add(freq.getOrDefault(y, 0) > 0 ? 1: 0);
        }
    }
    return result;
}

Thank you for calarifying this. I have spent a significant amount of time trying to come up with something better than O(n) . I have just changed the boilerplate code and have all test cases passing. My solution is O(n)

I can confirm that boilerplate in Java 8 is doing tests failling due to timeout. You can easily test it by submitting the code (without implementing the freqQuery method). Test 9 to 14 will fail due to timeout instead of wrong answer, like the others.

Thanks for the new boilerplate code!

Also, if someone still struggles with tests 12 and 13 due to timeout, use: List<Integer> result = new ArrayList<>(queries.size()); instead of List<Integer> result = new LinkedList<>();.

Of course we potentially allocate unnecessary memory in ArrayList (if queries contains other operations than operation 3), but this tric is to pass those tests. I.e. LinkedList will be better only with small amount of operations 3.

Thanks a bunch! I was lossing my mind trying to think of a sub linear solution. After first reading your comment I ran a submission with all my code commented out, still went over time.