Frequency Queries
Problem Statement
You are given queries. Each query is of the form two integers described below:
– : Insert x in your data structure.
– : Delete one occurence of y from your data structure, if present.
– : Check if any integer is present whose frequency is exactly
. If yes, print 1 else 0.
The queries are given in the form of a 2-D array queries
of size where
queries[i][0]
contains the operation, and queries[i][1]
contains the data element. For example, you are given array . The results of each operation are:
1 2 3 4 5 6 7 8 9 |
Operation Array Output (1,1) [1] (2,2) [1] (3,2) 0 (1,1) [1,1] (1,1) [1,1,1] (2,1) [1,1] (3,2) 1 |
Return an array with the output: .
Function Description
Complete the freqQuery
function. It must return an array of integers where each element is a if there is at least one element value with the queried number of occurrences in the current array, or
if there is not.
freqQuery
has the following parameter(s):
- queries: a 2-d array of integers
Input Format
The first line contains of an integer , the number of queries.
Each of the next lines contains two integers denoting the 2-d array
.
Constraints
*
*
* All
* All
Output Format
Return an integer array consisting of all the outputs of queries of type .
Sample Input 0
1 2 3 4 5 6 7 8 9 10 |
8 1 5 1 6 3 2 1 10 1 10 1 6 2 5 3 2 |
Sample Output 0
1 2 3 |
0 1 |
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution { static List<Integer> freqQuery(List<Integer[]> queries) { List<Integer> ans = new ArrayList<>(); final int INSERT = 1; final int REMOVE = 2; final int QUERY = 3; Map<Integer, Integer> value2count = new HashMap<>(); Map<Integer, Integer> count2countOccurance = new HashMap<>(); for (Integer[] q: queries) { int type = q[0]; int value = q[1]; if (type == INSERT) { if (value2count.containsKey(value)) { int oldCount = value2count.get(value); int newCount = oldCount + 1; value2count.put(value, newCount); count2countOccurance.put(oldCount, count2countOccurance.get(oldCount) - 1); if (!count2countOccurance.containsKey(newCount)) { count2countOccurance.put(newCount, 0); } count2countOccurance.put(newCount, count2countOccurance.get(newCount) + 1); } else { value2count.put(value, 1); if (!count2countOccurance.containsKey(1)) { count2countOccurance.put(1, 0); } count2countOccurance.put(1, count2countOccurance.get(1) + 1); } } else if (type == REMOVE) { if (value2count.containsKey(value)) { int oldCount = value2count.get(value); int newCount = Math.max(oldCount - 1, 0); value2count.put(value, newCount); count2countOccurance.put(oldCount, count2countOccurance.get(oldCount) - 1); if (!count2countOccurance.containsKey(newCount)) { count2countOccurance.put(newCount, 0); } count2countOccurance.put(newCount, count2countOccurance.get(newCount) + 1); } } else if (type == QUERY) { if (count2countOccurance.containsKey(value) && count2countOccurance.get(value) > 0) { ans.add(1); } else { ans.add(0); } } } return ans; } public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int q = Integer.parseInt(bufferedReader.readLine().trim()); List<Integer[]> queries = new ArrayList<>(); for (int i = 0; i < q; i++) { String[] queriesRowTempItems = bufferedReader.readLine().replaceAll("\\s+$", "").split(" "); Integer[] queriesRowItems = new Integer[2]; queriesRowItems[0] = Integer.parseInt(queriesRowTempItems[0]); queriesRowItems[1] = Integer.parseInt(queriesRowTempItems[1]); queries.add(queriesRowItems); } List<Integer> ans = freqQuery(queries); for (int i = 0; i < ans.size(); i++) { bufferedWriter.write(String.valueOf(ans.get(i))); if (i != ans.size() - 1) { bufferedWriter.write("\n"); } } bufferedWriter.newLine(); bufferedReader.close(); bufferedWriter.close(); } } |