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.
Nice way to use Counter, I didn't know you can use it like that. But I tested it with 1000000 queries against defaultdict and defaultdict is around 15-20% faster. I guess both of them using a lot of memory but as a dictionaries and hashmaps problem it's not so important here.
Interesting. Do you know why defaultdict is faster. From what I understand, defaultdict is very similar to Counter except that if we call a missing key, the defaultdict will include that key in its key set while Counter does not, which means defaultdict cost more operations and thus cost more time? (I'm a total newbie to computer science so excuse me for my naive question
Actually I'm not sure why but I tested dictionary types a few times in competitions to save a few secs and defaultdict had been always fastest. Weird thing is your use of counter is same with defaultdict but according to python.org it's same with Dict. Here is one of the test links I found, some others says speed difference is bigger.
Nice work.
In my code taste I would just suggest extracting command and value for less square brackets => better readability
and simplify result else f.e. like:
This is the shortest way (as per my knowledge).
However, there is an error.
when [q[0] == 2], before doing cnt[freq[q[1]]]-=1, you should check if cnt[freq[q[1]]] > 0. Otherwise, you might make it negative.
Very clever solution. One minor change (which is optional, actually). The first instance of "cnt[freq[q[1]]]-=1" (within "if q[0]==1:") should only be done if cnt[freq[q[1]]] >0.
Hi Naomi, great solution! i understand the method is called double hashing. I tried solving the problem with single hash but faced timeout issues in several cases. could you explain why double hashing resolves the issue?
"if n in dic.values()" can start to take too much time if you are doing it too often. Try to store frequencies somewhere instead of searching through your array of values everytime you get a q==3.
Hi, one dict is to keep track of the frequency of each elements (key: element, value: frequency). The other keeps track of frequency of the frequency (key: frequency, value: number of elements that has that frequency). Hope it helps!
Hi, do you notice that each time, the query starts with 3, it has to count occ_dict all over again? In my code, when the query starts with 3, it just has to search for it, none additional counting is required
So I rewrote your solution with some comments to try and figure out your logic. Can you check to see if I've understood it?
def freqQuery(queries):
arr = dict() # val:count of said values
freq = dict() #number of counts, ie 1:numbers that appear only
out = []
for (oper, val) in queries:
if (oper == 1):
#insertion
if not(val in arr):
arr[val] = 0 #if value isn't in arr dict, then add value to dict and give it a 0 bc we can't assign a 1 just yet
if not(arr[val] in freq):
freq[arr[val]] = 1 #if freq dictionary doesn't already have arr[val]'s number, then we automatically assign by 1
freq[arr[val]] -= 1 #subtracting arr[val]'s number by one because it's always kept at 1
arr[val] += 1 #adding 1 to arr[val]
if not(arr[val] in freq):
freq[arr[val]] = 0 #if arr[val]'s cnt isn't in freq, then we assign it 0
freq[arr[val]] += 1 #otherwise we increase it by 1
if (oper == 2) and (val in arr):
#deletion
freq[arr[val]] -= 1 #same as above, we subtract 1 from it to keep it at 1
arr[val] -= 1
freq[arr[val]] += 1 #same as above, we add 1 from it to keept it at one
if arr[val] <= 0:
arr.pop(val)
if (oper == 3) and (val in freq):
out.append(int(freq[val]>0))
elif(oper == 3):
out.append(0)
return out
Frequency Queries
You are viewing a single comment's thread. Return to all comments →
My Python solution. Let me know if there's a shorter way:
Nice way to use Counter, I didn't know you can use it like that. But I tested it with 1000000 queries against defaultdict and defaultdict is around 15-20% faster. I guess both of them using a lot of memory but as a dictionaries and hashmaps problem it's not so important here.
Interesting. Do you know why defaultdict is faster. From what I understand, defaultdict is very similar to Counter except that if we call a missing key, the defaultdict will include that key in its key set while Counter does not, which means defaultdict cost more operations and thus cost more time? (I'm a total newbie to computer science so excuse me for my naive question
Actually I'm not sure why but I tested dictionary types a few times in competitions to save a few secs and defaultdict had been always fastest. Weird thing is your use of counter is same with defaultdict but according to python.org it's same with Dict. Here is one of the test links I found, some others says speed difference is bigger.
https://gist.github.com/dpifke/2244911
Thanks tieros!
Very clever! I had trouble looking up if a particular frequency existed without timing out; this is (in my opinion) a very elegant solution!
Thank you My first time sharing a solution (as well as earning compliments from it)
nice work!
i ended up with something almost identical, though i used defaultdicts with sets
results.append(int(freqs[value] > 0))
Great job! I'm gonna remember the double hash trick for the future!
Nice work. In my code taste I would just suggest extracting command and value for less square brackets => better readability and simplify result else f.e. like:
Looks exactly like my solution.
Why do you do
and
before and after actions 1 and 2? Why do they not cancel out?
Because freq[value] changes between 1st and 2nd call. So it decreases and increases freq for different entries.
correct!
This approach does not work in python 3 because action is interpreted as the index of the query, and not the first number in the array.
brillainat
This is the shortest way (as per my knowledge). However, there is an error. when [q[0] == 2], before doing cnt[freq[q[1]]]-=1, you should check if cnt[freq[q[1]]] > 0. Otherwise, you might make it negative.
Actually my logic is same, test cases 7,8 and 11 are failing
my wrong answer also failing in 7, 8 and 11 i got correct answer after i found that i forgot to skip delete query if the number total is zero
Very clever solution. One minor change (which is optional, actually). The first instance of "cnt[freq[q[1]]]-=1" (within "if q[0]==1:") should only be done if cnt[freq[q[1]]] >0.
Hi Naomi, great solution! i understand the method is called double hashing. I tried solving the problem with single hash but faced timeout issues in several cases. could you explain why double hashing resolves the issue?
gettings tle in 10,12,13. any suggestions?
"if n in dic.values()" can start to take too much time if you are doing it too often. Try to store frequencies somewhere instead of searching through your array of values everytime you get a q==3.
I did what you said (when q==3, i used a list to store all the frequencies), however, still time out.
can you explain the question why you need to use two dictionaries
Hi, one dict is to keep track of the frequency of each elements (key: element, value: frequency). The other keeps track of frequency of the frequency (key: frequency, value: number of elements that has that frequency). Hope it helps!
much needed this explaination! thanks helped alot
My question is why is this better than using a defaultdict and a Counter? my solution is as follows:
Any help would be appreciated, thanks!
Hi, do you notice that each time, the query starts with 3, it has to count
occ_dictall over again? In my code, when the query starts with 3, it just has to search for it, none additional counting is requiredBest solution ever, concise and great use of Counters
Not shorter but this is a passable solution without the use of Counter from Collections:
So I rewrote your solution with some comments to try and figure out your logic. Can you check to see if I've understood it?