We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Frequency Queries
  2. Discussions

Frequency Queries

  • nico_dubus + 3 comments

    I was timing out on a few of the test cases, even using two hashmaps. I tried the optimization of boilerplate code proposed here, and was still timing out on 10 which, to be fair, has a million operations. So to really turbocharge it, you can pass a BufferedReader to your freqQuery function, and rather than pass in an int array[q][2], undertake your operations as you read them line by line, so you only do a single pass.

    My code - if there's another optimization I missed, please feel free to point it out to me. 

    import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Solution {

    // Complete the freqQuery function below.
    static List<Integer> freqQuery (BufferedReader bufferedReader, int q)throws IOException {

        HashMap<Integer, Integer> valuesToCounts = new HashMap<>();
        HashMap<Integer, Set<Integer>> countsToValues = new HashMap<>();
        ArrayList<Integer> results = new ArrayList<>(); 
        int size = q;
           
        for (int i = 0; i < q; i++) {
            String[] query = bufferedReader.readLine().split(" ");
            int operation = Integer.parseInt(query[0]);
            int number = Integer.parseInt(query[1]);

            int oldCount = valuesToCounts.getOrDefault(number, 0); 
            int newCount; 

            if (operation == 1) {
                newCount = oldCount + 1; 
                valuesToCounts.put(number, newCount);
                
                if (countsToValues.containsKey(oldCount)) {
                    countsToValues.get(oldCount).remove(number);
                }
                countsToValues.putIfAbsent(newCount, new HashSet<>());
                countsToValues.get(newCount).add(number);
            }

            if (operation == 2) {
                newCount = (oldCount > 1) ? oldCount - 1 : 0;
                valuesToCounts.put(number, newCount);

                if (countsToValues.containsKey(oldCount)) {
                    countsToValues.get(oldCount).remove(number);
                }

                countsToValues.putIfAbsent(newCount, new HashSet<>());
                countsToValues.get(newCount).add(number);
            }

            if (operation == 3) {
                if (number > size) results.add(0);
                else {
                    results.add((number == 0 || countsToValues.getOrDefault(number, Collections.emptySet()).size() > 0) ? 1 : 0);
                }
            }
        }

        return results; 
    }

    public static void main(String[] args) throws IOException {
        try (BufferedReader bufferedReader = new BufferedReader(
                    new InputStreamReader(System.in))) {
            
            int q = Integer.parseInt(bufferedReader.readLine().trim());

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

      Yep that did it. Dang that was annoying. Thanks for the help ;)

    • dianadoctor1995 + 0 comments
      [deleted]
    • SupaTroopa + 1 comment

      This fixed timeout on 9-12 for me, on Java 8. The other suggestions to change the boilerplate by passing in[][] did not, but this worked.

      Can someone explain why though? Is there a memory constraint problem with passing in the 2D array instead of the bufferedReader, consequentially slowing the program down? Not too sure what's the difference.

      • dianadoctor1995 + 0 comments

        The thing with the 2D array is that you read all the inputs first to build the array and then you process them again one-by-one. This solution will process the current input upon reading it which is relatively faster since you don't have to go through the array again.