DSPACE(n) is a superset of DTIME(n) [1]. This means at best your algorithm matches the time complexity of this one. But this rule also applies to the case where n is known ahead of time and the data structure can be allocated all at once (best-case scenario). So your algorithm is almost guaranteed to be asymptotically worse than O(n).
Or in layman's terms: Allocating space takes time. Allocating n memory cells generally takes at least n units of time. In a scenario where you don't know the value of n (such as this) you have no choice but to grow your data structure gradually. Once you've used up all the currently allocated space, you need to allocate a bigger space somewhere else and copy the values over. And so on.
Difficult to say if it is better. You are going to be recalculating collisions as you dynamically create the map while checking at every iteration. What's worse is that if all your buckets are full, it will have to redistribute the entire map after making more buckets.
You can also use has instead of comparing the get.
And given this is JS, ECMA only requires the algorithm to be sub-linear on average, not constant.
So even just time complexity-wise, you would need to do a real performance test to claim that one way is better than the other. And of course, this solution has much better space complexity than yours.
I still do not see the point, as you are going to compare the users' solutions with your own code: rounding it up with a function just makes things more clean and readable.
No, I will not, as basically 99% of the katas here are done like that and there is a reason for it: we want to verify the user solution against a template :)
I've added the test case you suggested to the original Python version of this kata.
However, the JavaScript translation is broken in this matter, so I've added the test case but had to comment it out.
Unfortunately I'm not as good in JavaScript to fix the translation code. :(
This is BAD solution
DSPACE(n) is a superset of DTIME(n) [1]. This means at best your algorithm matches the time complexity of this one. But this rule also applies to the case where n is known ahead of time and the data structure can be allocated all at once (best-case scenario). So your algorithm is almost guaranteed to be asymptotically worse than O(n).
Or in layman's terms: Allocating space takes time. Allocating n memory cells generally takes at least n units of time. In a scenario where you don't know the value of n (such as this) you have no choice but to grow your data structure gradually. Once you've used up all the currently allocated space, you need to allocate a bigger space somewhere else and copy the values over. And so on.
Will do! I should have one together fairly shortly.
Difficult to say if it is better. You are going to be recalculating collisions as you dynamically create the map while checking at every iteration. What's worse is that if all your buckets are full, it will have to redistribute the entire map after making more buckets.
You can also use
hasinstead of comparing theget.And given this is JS, ECMA only requires the algorithm to be sub-linear on average, not constant.
So even just time complexity-wise, you would need to do a real performance test to claim that one way is better than the other. And of course, this solution has much better space complexity than yours.
Reference solution is incorrect, as pointed out by @konakona above:
It's been approved
Approved! Thank you for the translation!
Approved! Thank you for the translation!
I still do not see the point, as you are going to compare the users' solutions with your own code: rounding it up with a function just makes things more clean and readable.
No, I will not, as basically 99% of the katas here are done like that and there is a reason for it: we want to verify the user solution against a template :)
Oh, I see your point.
I've added the test case you suggested to the original Python version of this kata.
However, the JavaScript translation is broken in this matter, so I've added the test case but had to comment it out.
Unfortunately I'm not as good in JavaScript to fix the translation code. :(
But thanks for your kind contribution anyway!
In which aspect do you think this test is better than the others already present in the kata?