Frequency Queries

24 Jan, 2019 Algorithms 0

Problem Statement
You are given queries. Each query is of the form two integers described below:
– $1 x$ : Insert x in your data structure.
– $2 y$ : Delete one occurence of y from your data structure, if present.
– $3 z$ : Check if any integer is present whose frequency is exactly $z$ . If yes, print 1 else 0.

The queries are given in the form of a 2-D array queries of size $q$ where queries[i][0] contains the operation, and queries[i][1] contains the data element. For example, you are given array $queries=\left[(1,1),(2,2),(3,2),(1,1),(1,1),(2,1),(3,2)\right]$ . The results of each operation are:

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

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: $\left[0,1\right]$ .

Function Description
Complete the freqQuery function. It must return an array of integers where each element is a $1$ if there is at least one element value with the queried number of occurrences in the current array, or $0$ 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 $q$ , the number of queries.
Each of the next $q$ lines contains two integers denoting the 2-d array $queries$ .

Constraints
* $1 \le q \le 10^6$
* $1 \le x,y,z \le 10^9$
* All $queries\left[i\right]\left[0\right] \in {1,2,3}$
* All $queries\left[i\right]\left[1\right] \le 10^9$

Output Format
Return an integer array consisting of all the outputs of queries of type $3$ .

Sample Input 0

1 5

1 6

3 2

1 10

1 6

2 5

3 2

Sample Output 0

0
1

Solution

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();
    }
}

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();

}

fizzbuzzer.com

Looking for good programming challenges?

Frequency Queries