- Frequency Queries
- Discussions
Frequency Queries
Frequency Queries
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 aList
. The method to implement is thenstatic 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`
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; }
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]
nico_dubus + 0 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"); } } } }
Sort 621 Discussions, By:
Please Login in order to post a comment