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.
One which holds key value pair of number and its frequencies. And the other which holds key value pairs of a frequency and all the number having that particular frequency. Such as.
Great solution , I thought of the same idea , but I think in the second dictionary you don't need to keep track of the exact numbers for each frequency key since the question only asks about whether there is a number of a certain frequency or not so you can only keep the count of the numbers having a certain frequency key as the value for the second dictionary and update that count while inserting and deleting elements
I had a similar approach:
First dictionary (map) holds pairs of {number, frequency}.
Second dictionary holds pairs of {frequency, frequency's frequency}.
(Note that in the second map you don't really care which values have that frequency, just the number of values that have that frequency).
Same! The new boilerplate fixed 9, 11 but 10, 12, 13 still failing. I even tried taking OP's suggestion a step further and changed the boilerplate to int[q][2] (instead of just List<int[2]>) and still times out. Bummer.
I kept adjusting my code, and got my solution to O(n), where n = number of queries, and it still didn't pass test case 10 due to time out. Cut out a bunch of fat from the Boilerplate, and finally got it everything to pass with my solution. Here's what I ended up with for my boilerplate:
Thanks, Finally this worked for me. I used two maps one to track values and another to track frequencies. I don't know why hackerrack adds boiler plate code if it's so bad.
bufferedWriter.write(ans.stream().map(Object::toString)
.collect(joining("\n")) + "\n"); part of the boiler plate contains error
please help cant figure out
For me, setting the intitital capacity of the maps made the difference between the 1000000 query tests timing out vs. passing...
static List freqQuery(int[][] queries) {
int qs = queries.length;
// maps values and their frequencies
// setting the initial capacity to qs was key to not timing out
Map<Integer, Integer> map = new HashMap<>(qs);
// maps frequencies and number of values which have that frequency
// setting the initial capacity to qs was key to not timing out
Map<Integer, Integer> freqMap = new HashMap<>(qs);
Great suggestion. You are right.
No need of changing the boiler plate code.
But instead of setting the initial capacity using hash map, I used a linked hash map and that worked. Linked Hash Map doesn't have the added time complexity of resizing (i.e. everytime the length exceeds the default size)
Hashmap.containsValue is O(n) time complexity - more expensive than needed. In my solution, I use both a counter Hashmap to know how many times a specific number appears and a frequency Hashmap to count how many numbers appeared for a specific amount of times. Then, for op==3 I just check if frequency is greater than zero.
He is talking about map.containsValue NOT containsKey. So you basically have to iterate through the map to know whether desired value is present in the map or not. And that's O(n). where n is the number of keys present in the map.
From my experience, the getOrDefault() method is slower than the simple if-else get statements, and helped me get over the line for no fewer than 3 test cases.
Seems like python has a hard time switching from operations to printing. So placing everything in a list and then printing it works!
Nice job! Thanks for sharing!
Here is a shorter variant in Python3 that uses a frequency dictionary of sets rather than of ints. I was inspired by fromtheeast1's use of a frequency dictionary f, which prevents a timeout on the longer query lists. This success is due to a dict's or set's find-by-value time being O(1) average and O(n) worst, whereas a list's find-by-value time is O(n) average.
This isn't an issue with boiler plate. Your code is failing for cases where there is large amount of queries for op 3 that don't find a matching value.
containsValue is probably O(n) since the value list is not sorted.
Imagine your hash had >100k unique entries all with a frequency of one. Each query with op 3 would have to do 100k tests if the the value was two. This would be true even if every call to op 3 was testing for the same exact value each time!
That is going to be really really slow. Especially if you do all op 3 queries after all op 1 and op 2 queries. The hash table is not changing and we're passing the same values over and over and yet this code does O(n) look up every time.
If you want it to be fast you need a reverse look up of frequency value to list of operand.
You are iterating the map for finding whether the required frequency is present or not. Try maintaining the frequency to values map. So you won't have to iterate the map. see below code :-
static List freqQuery(List queries) {
List result = new ArrayList<>();
Map operationsMap = new HashMap();
Map<Integer, Set<Integer>> frequencyMap = new HashMap<>();
for (int[] query : queries) {
switch (query[0]) {
case 1:
Integer m = operationsMap.get(query[1]);
if (m == null) {
operationsMap.put(query[1], 1);
Set<Integer> sampleMap = frequencyMap.get(1);
if (sampleMap != null)
sampleMap.add(query[1]);
else
frequencyMap.put(1, new HashSet() {
{
add(query[1]);
}
});
} else {
operationsMap.put(query[1], ++m);
frequencyMap.get(m - 1).remove(query[1]);
Set<Integer> sampleMap = frequencyMap.get(m);
if (sampleMap != null)
sampleMap.add(query[1]);
else
frequencyMap.put(m, new HashSet() {
{
add(query[1]);
}
});
}
break;
case 2:
Integer n = operationsMap.get(query[1]);
if (n == null)
break;
else if (n == 1) {
operationsMap.remove(query[1]);
frequencyMap.get(1).remove(query[1]);
} else {
operationsMap.put(query[1], --n);
frequencyMap.get(n + 1).remove(query[1]);
Set<Integer> sampleMap = frequencyMap.get(n);
if (sampleMap != null)
sampleMap.add(query[1]);
else
frequencyMap.put(n, new HashSet() {
{
add(query[1]);
}
});
}
break;
case 3:
result.add((frequencyMap.get(query[1]) == null || frequencyMap.get(query[1]).isEmpty()) ? 0 : 1);
break;
}
}
This code may not perform well since hash.containsValue has a time complexity of O(n). Need to obtain the frequency in O(1) time. I used another map for frequency. This code has some functional issue. Trying to fix it.
so far I've got the following:
import java.io.;
import java.util.;
public class Solution2 {
// Complete the freqQuery function below.
static List<Integer> freqQuery(int[][] queries) {
Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
List<Integer> retList = new ArrayList<Integer>();
Map<Integer,Integer> frequency=new HashMap<Integer,Integer>();
int cnt=0;
for(int i=0;i<queries.length;i++)
{
int op = queries[i][0];
int num = queries[i][1];
cnt++;
if(op==1)
{
if(!hash.containsKey(num)) {
hash.put(num,1);
if(frequency.containsKey(1)){
frequency.put(1,frequency.get(1)+1);
} else {
frequency.put(1,1);
}
}
else {
frequency.put(hash.get(num),frequency.get(hash.get(num))-1);
hash.put(num,hash.get(num)+1);
if (frequency.containsKey(hash.get(num))){
frequency.put(hash.get(num),frequency.get(hash.get(num))+1);
} else {
frequency.put(hash.get(num),1);
}
}
}
else
if(op==2)
{
if(hash.containsKey(num))
{
if(hash.get(num)<=1) {
hash.remove(num);
if (frequency.get(1)==1)
frequency.remove(1);
else
frequency.put(1,frequency.get(1)-1);
}
else {
frequency.put(hash.get(num),frequency.get(hash.get(num))-1);
hash.put(num,hash.get(num)-1);
frequency.put(hash.get(num),frequency.get(hash.get(num))+1);
}
}
}
else
if(op==3)
{
if(frequency.containsKey(num) && frequency.get(num)>=1){
retList.add(1);
}
else
retList.add(0);
}
}
return retList;
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("c:\\temp\\aa.txt"));
int q = Integer.parseInt(bufferedReader.readLine().trim());
int[][] queries = new int[q][2];
for (int i = 0; i < q; i++) {
String[] queriesRowTempItems = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
queries[i][0]=Integer.parseInt(queriesRowTempItems[0]);
queries[i][1]=Integer.parseInt(queriesRowTempItems[1]);
}
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();
}
Good catch! I was hoping something like this was the case. I was pretty confident my implementation was O(1) for each of the query operations, but was still getting timeout errors for cases 9-13. After fixing the boilerplate code, all cases are passing. Thanks!
Hackerrank has so many issues... Thanks a ton! This made my test cases pass. My algorithm was linear and always used constant time access, so really this boiler plate code shouldn't matter if the tests are correct. I.E. they should be testing Big O not absolute time.
Thanks, the Java 8 harness is often joke tier but this one...
I came to the discussions after measuring that the whole main method took 1600ms while my own code took 200ms for one of the failing cases.
I was surprised that when I changed the boilerplate to use an array list presized to q, with elements that were array lists of size 2, I still couldn't beat the timeout. If anybody gets this to work with arraylist or list as the entries, I would be curious to see what they did in the boilerplate. Maybe above would work with compiled pattern but array list of array lists.... Maybe it's the time lost simply to allocate a wrapped integer instead of a primitive.
Arrrrgh.... changed the function to take an int[], AND had it return an int[] (by counting the number of queries on input, and then passing that into the function) and am still timing out on 12 and 13. Stripped down my code so it now uses only a single non-primitive structure (one Map to keep track of the frequency of each number), and it's still not passing.
Thank you! I was just coming to the discussion to complain how tests are timing out on my O(n) solution and it's not obvious how to optimize it to pass.
Thank you for this. Was there more optimizations that i should have made that could have passed? I went over all queries once and used 2 maps to count frequencies and then the number of occurances for a particular value.
Why changing to int[] make it faster? I changed the code and all the tests passed. I wonder why. Is it because intializing a list is slower than intializing an array? Or list.get() is slower than array[index]?
For all those who were like me , trying to find solution for java....
just use the above one or fast IO (make sure u do the same justice with output also) with your own implementation........
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
List<Integer> result = new ArrayList<>();
int n = Integer.parseInt(in.readLine());
HashMap<Long, Long> map = new HashMap<Long, Long>();
HashMap<Long, Long> freq = new HashMap<Long, Long>();
for (int i = 0; i < n; i++) {
StringTokenizer s= new StringTokenizer(in.readLine());
int a = Integer.parseInt(s.nextToken());
final long b = Long.parseLong(s.nextToken());
switch (a) {
case 1:
freq.computeIfPresent(map.get(b), (k, v) -> v == 1 ? freq.remove(map.get(b)) : v - 1);
map.compute(b, (k, v) -> v == null ? 1 : v + 1);
freq.compute(map.get(b), (k, v) -> v == null ? 1 : v + 1);
break;
case 2:
freq.computeIfPresent(map.get(b), (k, v) -> v == 1 ? freq.remove(map.get(b)) : v - 1);
map.computeIfPresent(b, (k, v) -> v == 1 ? map.remove(b) : v - 1);
freq.compute(map.get(b), (k, v) -> v == null ? 1 : v + 1);
break;
case 3:
result.add(freq.containsKey(b) ? 1 : 0);
break;
}
}
out.write(result.stream().map(Object::toString).collect(joining("\n")) + "\n");
in.close();
out.close();
}
Thanks, your input/output code was the key for me. I found that the official boilerplate and other ones provided both weren't passing for me, but this did the trick!
Thank you so much for this! I was beginning to pull my hair wondering why I was still getting timeouts after implementing a reverse HashMap to keep track of frequencies instead of calling values().contains()
Thank you for calarifying this. I have spent a significant amount of time trying to come up with something better than O(n) . I have just changed the boilerplate code and have all test cases passing. My solution is O(n)
I can confirm that boilerplate in Java 8 is doing tests failling due to timeout. You can easily test it by submitting the code (without implementing the freqQuery method). Test 9 to 14 will fail due to timeout instead of wrong answer, like the others.
Also, if someone still struggles with tests 12 and 13 due to timeout, use: List<Integer> result = new ArrayList<>(queries.size()); instead of List<Integer> result = new LinkedList<>();.
Of course we potentially allocate unnecessary memory in ArrayList (if queries contains other operations than operation 3), but this tric is to pass those tests. I.e. LinkedList will be better only with small amount of operations 3.
Thanks a bunch! I was lossing my mind trying to think of a sub linear solution. After first reading your comment I ran a submission with all my code commented out, still went over time.
Changing the boilerplate is unnecessary to avoid a timeout.
Rather you can keep two hashmaps where the keyset of one is the set of integers in the array and the keyset of the other is the set of frequencies with which integers appear in the array.
This allows you to perform all operations using keys rather than values, which is efficient enough that it doesn't timeout.
Frequency Queries
You are viewing a single comment's thread. Return to all comments →
For Java 7/8, change the boilerplate code to this
and note each query is now an
int[2]
instead of aList
. The method to implement is thenReduced the run time in inputs 9 and 13 from ~1.7s (
i7-4710MQ CPU @ 2.50GHz
) to ~0.8s, and all cases pass now.I can confirm that changing the boilerplate code to this made all tests failing due to timeout pass.
Thanks!
Thanks!
Solved it by creating two dictionaries.
One which holds key value pair of number and its frequencies. And the other which holds key value pairs of a frequency and all the number having that particular frequency. Such as.
Full python solution Hackerrank - Frequency Queries Solution
here is problem solution in Python java and C++ programming languages. https://programs.programmingoneonone.com/2021/03/hackerRank-frequency-queries-solution.html
I thought of it as well and was able to figure it out. I love hashtables!
Great solution , I thought of the same idea , but I think in the second dictionary you don't need to keep track of the exact numbers for each frequency key since the question only asks about whether there is a number of a certain frequency or not so you can only keep the count of the numbers having a certain frequency key as the value for the second dictionary and update that count while inserting and deleting elements
The second dict only has to keep track of how many numbers have that frequency, not the numbers themselves.
I had a similar approach: First dictionary (map) holds pairs of {number, frequency}. Second dictionary holds pairs of {frequency, frequency's frequency}. (Note that in the second map you don't really care which values have that frequency, just the number of values that have that frequency).
Java:
This is the working solution, I did the same in Java here.
weird, that's what I did, but I get some errors on the corner cases... need to check more..
That's exactly what I did but 5 testcases seem to be failing and I don't understand why. Any thoughts? Thanks!
here is problem solution in python java and c++ programming. https://programs.programmingoneonone.com/2021/03/hackerRank-frequency-queries-solution.html
Can also confirm that changing my (Java 8) boilerplate code to this made all tests that were failing due to timeout (Test cases 9 - 15) pass.
Thank you so much, and shame on HackerRank for providing bad boilerplate code!
Boilerplate is great :), makes you make sure code works. Hints: Input does not fit memory, there are requests for too hight frequencies.
Good hint, thanks :)
I did this but still tests 10,12,13 fail due to timeout. Please help
my solution :
static List freqQuery(List queries) {
Same! The new boilerplate fixed 9, 11 but 10, 12, 13 still failing. I even tried taking OP's suggestion a step further and changed the boilerplate to
int[q][2]
(instead of justList<int[2]>
) and still times out. Bummer.Changing to 2-D array worked for me
I kept adjusting my code, and got my solution to O(n), where n = number of queries, and it still didn't pass test case 10 due to time out. Cut out a bunch of fat from the Boilerplate, and finally got it everything to pass with my solution. Here's what I ended up with for my boilerplate:
Solution method does need to take in
int[][]
instead ofList<List<Integer>>
Thanks, Finally this worked for me. I used two maps one to track values and another to track frequencies. I don't know why hackerrack adds boiler plate code if it's so bad.
Didn't work for me!
Worked for me!
bufferedWriter.write(ans.stream().map(Object::toString) .collect(joining("\n")) + "\n"); part of the boiler plate contains error please help cant figure out
For me, setting the intitital capacity of the maps made the difference between the 1000000 query tests timing out vs. passing...
mine also passed all the test cases by just setting map size to number of queries and burn down boiling code to the array.
// Can someone please tell me why 5 testcases fail with this code vector freqQuery(vector> queries) { map store; vector result; long n=queries.size();
for(int i=0;i
} if(queries[i][0]==3) { int count=0;
} } return result; }
Great suggestion. You are right. No need of changing the boiler plate code. But instead of setting the initial capacity using hash map, I used a linked hash map and that worked. Linked Hash Map doesn't have the added time complexity of resizing (i.e. everytime the length exceeds the default size)
Hashmap.containsValue is O(n) time complexity - more expensive than needed. In my solution, I use both a counter Hashmap to know how many times a specific number appears and a frequency Hashmap to count how many numbers appeared for a specific amount of times. Then, for op==3 I just check if frequency is greater than zero.
All tests passed after changing the boilerplate.
Oh, like a histogram! Nice work! Maybe call that frequency variable 'histogram'. Will make much easier to read/understand.
Ultimate :)
Nice solution.
No it is O(1). It is basicallly calculating the hashcode!
He is talking about map.containsValue NOT containsKey. So you basically have to iterate through the map to know whether desired value is present in the map or not. And that's O(n). where n is the number of keys present in the map.
Can you please check my code, It's timing out for testcase 9, 10, 11, 12, 13. I have chnaged boilerplate code. Thanks in advance.
From my experience, the getOrDefault() method is slower than the simple if-else get statements, and helped me get over the line for no fewer than 3 test cases.
how you solve this error Sorry, we can't accept your submission. The custom input size should not exceed 50Kb.
This solution in Python, and it passed all test cases.
Seems like python has a hard time switching from operations to printing. So placing everything in a list and then printing it works! Nice job! Thanks for sharing!
Here is a shorter variant in Python3 that uses a frequency dictionary of sets rather than of ints. I was inspired by
fromtheeast1
's use of a frequency dictionaryf
, which prevents a timeout on the longer query lists. This success is due to a dict's or set's find-by-value time being O(1) average and O(n) worst, whereas a list's find-by-value time is O(n) average.Can you explain the use of d and f deictionaries and why increment f[d[key]] when command is 2.
Just a quick comment, in
You don't need to check for if d[key] > 0 , as it's already taken care of in the max(0, d[key] - 1) part
Can you explain the logic behind? Thank u.
awesome
only test case 11 not passed. i think problem in containsValue() method. please help..
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 abc {
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 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 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"); } } } }
Thanks for this :)
This solution works
Can you please explain your solution. Thank you
The following should be removed.
In the contstraints section it mentions that "z" is >= 1.
Also if 0 was possible you would be adding a 1 and then a 0 from your next statment.
For me didn't work failed in 4 cases
You are just a frikin beast bro :)
This isn't an issue with boiler plate. Your code is failing for cases where there is large amount of queries for op 3 that don't find a matching value.
containsValue is probably O(n) since the value list is not sorted.
Imagine your hash had >100k unique entries all with a frequency of one. Each query with op 3 would have to do 100k tests if the the value was two. This would be true even if every call to op 3 was testing for the same exact value each time!
That is going to be really really slow. Especially if you do all op 3 queries after all op 1 and op 2 queries. The hash table is not changing and we're passing the same values over and over and yet this code does O(n) look up every time.
If you want it to be fast you need a reverse look up of frequency value to list of operand.
This is what helped me.
Ended up having to add some extra operations to op 1 and 2 to maintain a second map of frequencies. But op 3 is now O(1), which was the bottleneck.
else if(op==3) { need to compare the count of a number.. Z not the actual number
You are iterating the map for finding whether the required frequency is present or not. Try maintaining the frequency to values map. So you won't have to iterate the map. see below code :-
return result; }
i also did same but my test case failed dur to time out
if(hash.get(num)<=1) hash.remove(num); else hash.put(num,hash.get(num)-1);
int op = queries.get(i).get(0); int num = queries.get(i).get(1);
Use
hash.put(num,hash.getOrDefault(num,0)+1); for creating a one liner frequency counter... Happy Coding ;-)
This code may not perform well since hash.containsValue has a time complexity of O(n). Need to obtain the frequency in O(1) time. I used another map for frequency. This code has some functional issue. Trying to fix it.
so far I've got the following:
import java.io.; import java.util.;
public class Solution2 {
}
instead of using containsKey and containsValue, try to use get and put operations. I got all test cases solved
Thanks! Now tests 9-13 pass without "Terminated due to timeout" status with Java 8.
include
using namespace std;
string ltrim(const string &); string rtrim(const string &); vector split(const string &);
// Complete the freqQuery function below. vector freqQuery(vector> queries) {
map m; map m1; vector v; for(int i=0;i
}
int main() { ofstream fout(getenv("OUTPUT_PATH"));
}
string ltrim(const string &str) { string s(str);
}
string rtrim(const string &str) { string s(str);
}
vector split(const string &str) { vector tokens;
}
bro, u can't pass any test cases. infact you haven't read the question.
vector freqQuery(vector> queries) {
vector v;
map m;
map m1;
for (int i = 0; i
} return v; }
Test case 10 got terminated due to timeout......
If you're getting a time out that means your algorithm can be improved. Try to come up with a solution that doesn't use loops at
Nice solution. All test cases passed.
very good solution,easy to understand
I agree with above comment.
I am getting compilation error in the main after changing my boilerplate code. Solution.java:63: error: ')' expected .map(Object::toString) ^
Solution.java:63: error: ';' expected .map(Object::toString) ^
Solution.java:63: error: not a statement .map(Object::toString) ^
Solution.java:63: error: ';' expected .map(Object::toString) ^
Solution.java:65: error: not a statement + "\n"); ^
Solution.java:65: error: ';' expected + "\n"); ^
Check for opening braces.
That was very helpful. Thank you.
Good catch! I was hoping something like this was the case. I was pretty confident my implementation was O(1) for each of the query operations, but was still getting timeout errors for cases 9-13. After fixing the boilerplate code, all cases are passing. Thanks!
Hackerrank has so many issues... Thanks a ton! This made my test cases pass. My algorithm was linear and always used constant time access, so really this boiler plate code shouldn't matter if the tests are correct. I.E. they should be testing Big O not absolute time.
It's sad! I wasted hours trying to figure out why my tests were timing-out only to find out the bloddy boilerplate code as the culprit!
Very true. Saved further debugging time! I was wondering why its still failing instead my algorithm is quite efficient
I supposed, the result depends on server state. I have to rewrite output code and add inverse map to pass all tests.
Thank you. I didn't know why I had problems of timeout, but your change solved my problem. TY.
Thanks, the Java 8 harness is often joke tier but this one... I came to the discussions after measuring that the whole main method took 1600ms while my own code took 200ms for one of the failing cases.
Thanks, works for me!
Same for me. Solution is in O(n), this new boiler plate made me pass the tests immediately.
I was surprised that when I changed the boilerplate to use an array list presized to q, with elements that were array lists of size 2, I still couldn't beat the timeout. If anybody gets this to work with arraylist or list as the entries, I would be curious to see what they did in the boilerplate. Maybe above would work with compiled pattern but array list of array lists.... Maybe it's the time lost simply to allocate a wrapped integer instead of a primitive.
thank you. I was slowly getting pissed off but now everything passes.
Arrrrgh.... changed the function to take an int[], AND had it return an int[] (by counting the number of queries on input, and then passing that into the function) and am still timing out on 12 and 13. Stripped down my code so it now uses only a single non-primitive structure (one Map to keep track of the frequency of each number), and it's still not passing.
I'll have to come back to this one.
My solution was showing WA for test cases 9-13. Changing boiler plate code fixed it.
Thanks a lot @eduardocorral
Thank you! I was just coming to the discussion to complain how tests are timing out on my O(n) solution and it's not obvious how to optimize it to pass.
Yay, works great! Thanks @eduardocorral. Agreed, HackerRank should test their own code.
Thank you for this. Was there more optimizations that i should have made that could have passed? I went over all queries once and used 2 maps to count frequencies and then the number of occurances for a particular value.
confirm, thank you!
Thanks man:) I spent 2 hours trying to understand what else can be improved. Shame on hackerrank boilerplate.
I also confirm that changing the boilerplate code to this made all tests failing due to timeout pass. Thank you so much !
Thanks. Finally it's work for me.
Why changing to int[] make it faster? I changed the code and all the tests passed. I wonder why. Is it because intializing a list is slower than intializing an array? Or list.get() is slower than array[index]?
Still test cases 10,11,12 could not pass.
Test cases 10-13 were failing but after changing the boilerplate code to the above code, they passed. Thanks brother.!
Bless you. You code executes 2-3 times faster on my machine and I finally passed the tests
There are two more things have to be done before passing all test cases.
String.split()
instead of pattern match.List<int[]>
to store all queries.I am still timingout on 9,10,11 with this boiler plate code.
Can you give me your code
For all those who were like me , trying to find solution for java.... just use the above one or fast IO (make sure u do the same justice with output also) with your own implementation........
OR
import java.io.; import java.util.; import static java.util.stream.Collectors.joining;
public class Solution { public static void main(String[] args) throws IOException {
}
Bro, thank you very much for the solution, since two days I'm trying for this, tried in hundreds of ways, but only yours suceeded. thanks a lot
Thanks, your input/output code was the key for me. I found that the official boilerplate and other ones provided both weren't passing for me, but this did the trick!
Thank you very much bro. i almost gave up on this, but saved me☺☺☺
Using Java 8 even with the change in the boiler plate my code timed out some test cases.
I switched to using Java 7 and all tests pass.
Thank you so much for this! I was beginning to pull my hair wondering why I was still getting timeouts after implementing a reverse HashMap to keep track of frequencies instead of calling values().contains()
Check my accepted c++ code here: https://www.hackerrank.com/challenges/frequency-queries/forum/comments/648137?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps
Thank you for pointing this out. Here is a c# version of boiler plate:
Why doesn't this code which runs in O(n) pass the test cases 10, 11, 12 and 13? It times out.
Thank you for calarifying this. I have spent a significant amount of time trying to come up with something better than O(n) . I have just changed the boilerplate code and have all test cases passing. My solution is O(n)
I can confirm that boilerplate in Java 8 is doing tests failling due to timeout. You can easily test it by submitting the code (without implementing the freqQuery method). Test 9 to 14 will fail due to timeout instead of wrong answer, like the others.
Thanks for the new boilerplate code!
Also, if someone still struggles with tests 12 and 13 due to timeout, use:
List<Integer> result = new ArrayList<>(queries.size());
instead ofList<Integer> result = new LinkedList<>();
.Of course we potentially allocate unnecessary memory in ArrayList (if queries contains other operations than operation
3
), but this tric is to pass those tests. I.e. LinkedList will be better only with small amount of operations3
.Thanks a bunch! I was lossing my mind trying to think of a sub linear solution. After first reading your comment I ran a submission with all my code commented out, still went over time.
how do we call the elements from the listqueries
I am getting an error in last part of the boiler plate that you have written from bufferedWriter.write thank you
If the frequency is greater than 10^5 then add 0 to the List, b/c the frequency of any number cannot exceed the value of 10^5.
Just Add the below condition, all the test cases will pass.
if(value > 100000) result.add(0);
else
result.add(arr[value] > 0 ? 1 : 0);
Works perfectly for 11th case. Thank you!
Hi, I have made the adjustment suggested but it still won't pass test case 11. Any suggestions?
Changing the boilerplate is unnecessary to avoid a timeout.
Rather you can keep two hashmaps where the keyset of one is the set of integers in the array and the keyset of the other is the set of frequencies with which integers appear in the array.
This allows you to perform all operations using keys rather than values, which is efficient enough that it doesn't timeout.
I don't know if the timeout restrictions have changed but my O(n) solution is passing without changing the boilerplate pretty quickly.