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.
  1. Frequency Queries
  2. Discussions

Frequency Queries

Sort 583 Discussions, By:

votes

  • eduardocorral + 0 comments

    For Java 7/8, change the boilerplate code to this

    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<int[]> queries = new ArrayList<>(q);
      Pattern p  = Pattern.compile("^(\\d+)\\s+(\\d+)\\s*$");
      for (int i = 0; i < q; i++) {
        int[] query = new int[2];
        Matcher m = p.matcher(bufferedReader.readLine());
        if (m.matches()) {
          query[0] = Integer.parseInt(m.group(1));
          query[1] = Integer.parseInt(m.group(2));
          queries.add(query);
        }
      }
      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");
      }
    }
  }

    and note each query is now an int[2] instead of a List. The method to implement is then

    static List<Integer> freqQuery(List<int[]> queries) {

    Reduced the run time in inputs 9 and 13 from ~1.7s (i7-4710MQ CPU @ 2.50GHz) to ~0.8s, and all cases pass now.

  • naomi_nguyen7 + 0 comments

    My Python solution. Let me know if there's a shorter way:

    `def freqQuery(queries):

    freq = Counter()

cnt = Counter()

arr = []

for q in queries:
    if q[0]==1:
        cnt[freq[q[1]]]-=1
        freq[q[1]]+=1
        cnt[freq[q[1]]]+=1

    elif q[0]==2:
        if freq[q[1]]>0:
            cnt[freq[q[1]]]-=1
            freq[q[1]]-=1
            cnt[freq[q[1]]]+=1

    else:
        if cnt[q[1]]>0:
            arr.append(1)
        else:
            arr.append(0)

return arr`

  • ivanduka + 0 comments

    JavaScript solution (passes all tests):

    const func = arr => {
  const result = [];
  const hash = {};
  const freq = [];

  for (let i = 0; i < arr.length; i += 1) {
    const [action, value] = arr[i];
    const initValue = hash[value] || 0;

    if (action === 1) {
      hash[value] = initValue + 1;

      freq[initValue] = (freq[initValue] || 0) - 1;
      freq[initValue + 1] = (freq[initValue + 1] || 0) + 1;
    }

    if (action === 2 && initValue > 0) {
      hash[value] = initValue - 1;

      freq[initValue - 1] += 1;
      freq[initValue] -= 1;
    }

    if (action === 3) result.push(freq[value] > 0 ? 1 : 0);
  }

  return result;
};

    The idea is that we count 3 things: 1. Creating a dictionary with all added/removed values as keys and number of elements as values 2. Updating a frequency table 3. Result that we return in the end

    Obvious solution would be to keep only the dictionary. However, then in case 3 every time we need to traverse the whole dictionary to check if there is a key with value that equals the search value;

    It works fine on the initial tests but fails on the main set of tests because traversal of the whole dictionary is expensive.

    OK, then we need to keep an extra list of frequencies. I used a simple array where the index is the number of occurencies, for example [0,2,3] means that there are 2 values which occur twice and 3 values that occur 3 times (dictionary in this case would be something like: {12: 2, 14: 3}

    This way in case 3 I need only to check freq[number of occurencies]

  • codersanjeev + 0 comments

    Used the simple idea that search in keys of map takes O(1) time and search in values of map takes O(n) time.

    first map will store <element, frequency> second map will store <frequency, frequencyCount>

    #include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int nq;
    cin>>nq;
    
    // first will contain <element, frequency> pairs
    map<int,int> first;
    // second will contain <frequency, frequencyCount> pairs
    map<int,int> second;

    for(int i=0; i<nq; i++){
        
        int a, b;
        
        cin >>a >>b;
        
        if(a == 1) {
            // Insert b into first map.
            // Update the frequencies in second map.
            int elem = first[b];    // ele = current frequency of element b.
            
            if(elem > 0) {
                // b was already present.
                second[elem]--;
            }

            // Add b 
            // increase frequency of b
            first[b]++;
            
            // Update the count of new frequency in second map
            second[first[b]]++;
        }

        else if(a == 2) {
            // Remove b
            int temp = first[b];    // temp = current frequency of element b
            if(temp > 0){
                // b is present
                second[temp]--; // Update frequency count
                first[b]--;     // decrease element frequency
                second[first[b]]++; // Update frequency count
            }
        }
        else {
            // check for the b frequency of any element
            int res = second[b];
            if(res > 0) {
                cout<<1<<endl;
            }
            else {
                cout<<0<<endl;
            }
        }
    }
    return 0;
}

  • apps_yoon + 0 comments

    Is anyone else having timeout issues for test cases 9-13 for Swift? Even with the two hashmap solution.

Load more conversations