3 kyu
How many are smaller than me II?
1,224 of 2,715joh_pot
Loading description...
Algorithms
Performance
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
This comment has been hidden.
sortedcontainers is a 3rd party library & is not available on Codewars.
You'll need to implement the functionality yourself.
Go Translation
I've checked the multithreading code for this one,and still got the timeout error! Any suggestion for optimizing that better?
Multithreading will not help when you use inefficient algorithm, because multithreading can make your code only two- or four- or eight- times faster or so, and this will not help if your algorithm is 1000 times too slow for large arrays.
You most probably need to think of a better idea. But it's difficult to give any specific hints without knowing what is your current approach.
OP solved it, closing
This comment has been hidden.
Big sized tests are generally over
100 000. Some languages specify their size in the description, some don't.Your solution is too slow. This is not the 7kyu version of the kata.
This kata is kyu 2 for sure
Maybe, maybe not. Maybe it depends on the language as well.
But it's 3kyu now, and after 8 years reranking is probably not gonna happen.
Closing.
I'm a 100% sure I made a solution that's not O(n^2). I've tried it on my machine with a test case of list of 120K random numbers ranging from -1000 to 1000. The solution took about 14 seconds, and with the normal solution (from the standard kata, which is O(n^2)) it took more than 2 minutes.
This kata is surely hard, I'll try to make it...
I hope that isn't 14 seconds for a single test. There are 100 performance tests ( at least in JS, can't see Python ).
everything was passed on the test, however when i attempt the code the results "STDERR Execution Timed Out (12000 ms)". and on the large_random_test was turned orange when there's no error on it.
Execution timed outis an error. You did not pass everything on the test; there were more tests your solution did not have time for.This comment has been hidden.
This comment has been hidden.
If by "hacked" you mean a solution will fail on a perverse case, this is not an issue. It's hard enough to pass average cases.
Closing.
This comment has been hidden.
Not a kata suggestion. See https://docs.codewars.com/training/troubleshooting#post-discourse.
This comment has been hidden.
This kata is 3 kyu for a reason.
Your code needs to be optimised. The fact you can't do that is not a fault of the kata.
I think I'm passing 66 (out of 100?) long tests before timing out with my current code after refactoring multiple times for greater optimization, but at this point I'm at a loss. I feel very close to getting in under the timeout threshold but I'm not sure where I can squeeze more efficiency. Any hints?
This comment has been hidden.
Timed OutPassed: 67Failed: ?Exit Code: 1 Test Results: Log [4, 3, 2, 1, 0] [1, 1, 0] Fixed tests Initial_tests (7 of 7 Assertions) Completed in 0.59ms Random tests Small_random_tests (50 of 50 Assertions) Medium_random_tests (10 of 10 Assertions) Large_random_tests STDERR Execution Timed Out (12000 ms) Why did my code time out? Our servers are configured to only allow a certain amount of time for your code to execute. In rare cases the server may be taking on too much work and simply wasn't able to run your code efficiently enough. Most of the time though this issue is caused by inefficient algorithms. If you see this error multiple times you should try to optimize your code further.
Your code is too slow for this problem. You need to optimize your approach.
Not a kata issue.
This comment has been hidden.
spoiler flag, please...
Sorry, thanks for catching my mistake. I will remember to use the spoiler flag in the future when my comment is about my solution.
This comment has been hidden.
When I saw "Execution Timed Out (12000 ms)" I thought there was some quite heavy preformance requirements that my ocde did not met;
But I have compared it with one of the accepeted solution (the starting with
class Tree): on my PC my solution is 1.5x faster!I'm wondering if a more critical time limit on codewars server has now made this probleam unfeasible…
Well I just solved it in the Java version, so I can confirm it is still posible. However I can't confirm for any other languages
Seems like you didn't benchmark with big enough inputs. On my machine your current solution runs in 7.9 seconds on one of the large tests (65535 elements) while the top voted solution executes the very same input in 0.5 seconds.
Most time is likely spent while prepending elements to
countsbecause this copies over the whole list again and again making your algorithm O(n²).Good news is that this can easily be fixed and your solution will work.
@Madjosz
Thank you for the hint! You were right, I used a bigger array so the execution time is around 5s, and profiled my code: the
counts = [total_counts[val]] + countsline was responsible of 95% of the CPU time.So yes: changing it so it does a modification (not a creation) worked :-)
How many bigsized tests are there in java version? I passed seven bigsized before timeout and I am thinking how close I am. Or is it better to try totally new algorithm?
Java has 100 bigSized tests, each with an array of 80000 - 100000 elements. You definitely need a better approach than your O(n²) solution.
It seems it has been reported but hasn't been resolved.
The test timedout even all tests passed.
This means your code returned the correct for all the inputs it had the time to perform, but it fails at somepoint because it is too slow, or there is some bug helping him from finishing. Please refer to the documentation: https://docs.codewars.com/training/troubleshooting
I close the issue since it is not a kata issue (= a proved flaw in the kata).
This comment has been hidden.
No idea, but this is not a kata issue (= a flaw in the kata), maybe a question?
My JavaScript solution has a time complexity of 2 * O(n log n), so effectively O(n log n). On my laptop it's finishing 100000 element arrays in around 118ms when reporting it with console.time. I am getting through around 70 large tests at this time complexity, should O(n log n) be a passing solution?
Update
I refactored my solution and brought down the time complexity down to just a single O (n log n) algorithm.
I cannot express enough how satifying it feels to finally complete this. This challenge provoked me to take an online course on data structures and algorithms. I have learned so much since I first attempted this challenge and stuck with it until I learned the proper data structure needed to complete it.
In the end I was clocking around 12ms for a 100000 element array on my local machine. Tho the real accomplishment was what I learned in the journey to get there.
Cheers and thanks for a great challenge!
My solution is literally passing all random tests (50 small, 10 medium, 2 large) and still getting a timeout. How is that possible?
I'm pretty sure it means you've passed these tests so far but got a timeout before you passed the next one
Something's not right here, my code just got passed in the test but I'm getting a time out prompt every time I submitting it
your solution is not supposed to pass, so no problem (on the other hand, it may happen that it passes from time to time, but...).
Closing,
Cheers
But how can this be the case if all cases were solved?
This comment has been hidden.
Hello.
I had a strange situation
I got an information as below, and still got timed out. When I checked the console output, I treated 100 arrays of around 90000 elements each.
Test Passed
Completed in 11670ms
Completed in 11686ms
Completed in 11689ms
STDERR
Execution Timed Out (12000 ms)
Why did my code time out? Our servers are configured to only allow a certain amount of time for your code to execute. In rare cases the server may be taking on too much work and simply wasn't able to run your code efficiently enough. Most of the time though this issue is caused by inefficient algorithms. If you see this error multiple times you should try to optimize your code further.
This is a performance kata. Your code is too slow. Not a kata issue, closing.
Hello.
How many large random tests am I supposed to compute?
When I print the size of the input arrays I get a time out at about 72nd to 80th input array of about 90000 elements each.
Update.
I know, there are 100 large tests.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Nice kata. I am very satisfied with mine solution.
I can pass 5 of 6 large test. I can only see one place to further optimazie my code. I thnink my time complexity is something like O(n + n*(1/2n)), Pice of code that i want to optimize is in coment below with a spoiler.
This comment has been hidden.
How to make soft enters in coments?
not sure what you're asking about... I guess it's one of those two:
Let's say i have an algorithm that gives me the right array with time complexity of O(nlog(n)), more precise nlog(n)+2n. Maybe i can just optimize some instruction here and there, change the while statement with for...but i only pass the first 5 large test. Is there any hint about mathematical properties that i should care about? because i cannot think an algorithm more optimized than that, there must be some tricks, maybe with the structure/composition of the original array...pls help!
I'd look up test driven development. Two different data structures can perform the given operation, one may take a lot longer though given the task and requirements to fulfill your test. One data structure can provide the operation instantaneously, while the other has to go through the process which may take longer. Such an example is a hash table in python(I would google this if you haven't learned this already). The mathematics portion you asked for a hint about seems to be to be an advanced understanding of math, but the exact keyword to help you look up and understand, that I do not know. This is what I can tell you with my current knowledge, it may not be the whole picture and entirely accurate, but the idea should be similiar.
Your code might not actually be
O(n log n). If you only manage the first 5 large tests, I really doubt it is.Post your code, maybe we can say something. If your code really is
O(n log n), it would have to be horribly inefficient to fail so soon, and you would probably be able to optimise it yourself ( maybe not enough, but usefully, at least ).There is only 6 large test
This comment has been hidden.
Your code is too slow. It's
O(n²); you need better than that. This isn't 3kyu for nothing.My algorithm does a 20k array in 0.45 seconds. Why is it still slow?
Because its runtime scales with the square of the number of elements. Doing something
400 000 000times can still be fast ( CPUs run at GHZ speeds ). Now feed it a million elements. A million squared is1 000 000 000 000. That will take ( too much ) time.You'll need something that scales better. Tests use arguments up to
100 000long ( in JS, but I guess Python will do similar ).Is multithreading the solution ?
No.
Multithreading reduces your runtime by a constant factor ( the number of threads ); you probably need to go from
O(n²)toO(n log n).In python, even if I am not printing anything it runs out of time with a tree search algorithm. Worked in Java with minimal time
The blank attempt is already consuming 5 seconds alone
Still possible after getting rid of method calling (no recursion)
Maybe a performance tag?
it is there as of now
This comment has been hidden.
Disregard
Well, it is
3kyu.. if you solved it, you'd get massive points :DThis comment has been hidden.
Yes.
Exactly
O(n log n)actually. ( Unless P == NP, thenO(n)may be possible. )This comment has been hidden.
When I tried to get a long list to work on my device, I got an error Max Buffer Size Reached (1.5 MiB)
My language is python
Are you printing something in your code?
Not kata's issue; it already trims down output of very hard outputs. If your code prints too much to stdout this will happen.
maybe you are printing somthing
In Python, an incorrect answer for the large random tests will cause "Max buffer size reached" from printing. A custom assertion message should probably be used instead.
.
This comment has been hidden.
say the language or run the blank solution to see
Probably 100. ( That's JS. Your language seems to be Java; I can't see it there, but 100 is fairly standard on here. )
Thanks guys. I already cracked this Kata. Btw I noticed someone down-voted my original question...Why..? :(
I have done with it in at least 3 ways, but I still got time out. I always stop at the time of testing large random test. So I want ask some helps here. Could you please show me your hands?
Timing out for python with the optimal solution too
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
also tried returning a number like 1 and same execution timeout
that was because there were too much data to print to the console. Handled
There is something wrong with tests in JavaScript. Trivial (and obviously wrong) code timed out. It shouldn't pass any test, but it must not time out.
that was because there were too much data to print to the console. Handled
Rust translation ready for review
Auto-approved after lapsed grace period.
This comment has been hidden.
Hi, you didn't implement what you said you did.
___ ___ ___-> you did the first two words, but your solution is nowhere near having the third word.Okay let me give it a trial agin. Thanks.
This comment has been hidden.
I am passing all the tests, but still getting time error :/ seems strange.
Random tests Small_random_tests (50 of 50 Assertions) Medium_random_tests (10 of 10 Assertions) Large_random_tests (4 of 4 Assertions)
there are more than 4 large random tests, which is why your solution is timing out
Just one question, is it feasable in python?
yep, it very much is. you just haven't found the solution yet
patience, young padawan
This comment has been hidden.
?
wdym
I always get timeout, using numpy and list comprehension
it means your solution is too slow
it can definitely be done in python,45 people have done it ;)
I already have 3 different working solutions, but all of them are too slow (timing out).... kill me please :D
it's blue for a reason ;)
python: "optimized" O(N²) solutions are passing. That shouldn't happen, afaik.
ideas:
Can you give me a link(s) to such solution(s) so I can try to make adjustment?
the current top solution (as said in a message below)
and this one too: https://www.codewars.com/kata/reviews/629de4bb4ca7eb0001aff116/groups/62a50aadb392770001824a56
The problem is the reference solution (and yours) last 11 seconds to pass all the current tests. Am I missing something? I don't know what I could do, the tests are significatively reduced compared with JS. I asked for a careful review for this reason (I should have been more explicit).
the ref solution generally pass in 9-10s, you might have got out of luck.
First question would be to decide if those solution should or not pass. If they shouldn't, then we can start thinking about fixing the tests. So, what's your opinion?
Obviously the point of this kata is to disable O(N^2) solutions.
check discord, I'm not sure it's faisable, actually
handled
bruh
the following test should be added in all languages (this case doesn't appear in any fixed test):
btw, the "small" batch of random tests in python use too long inputs. That batch should be limited to arrays of 20 elements at most.
.
This comment has been hidden.
approved
see issue above (the top one) plz. I'm not entirely sure, so it's opened to discussion, but imo, the current top solution in python shouldn't pass.
This comment has been hidden.
This comment has been hidden.
Just give me a hint. Is there any special mathematical-type solution?
How can I deal with large random tests? (JavaScript)
Write something better than
O(n²).This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
The basic implementation of that is enough to pass the kata, but... you have to avoid performances overhead in your implementation otherwise you may not pass the tests. So "keep it simple/stupid", but hunt for useless operations.
My Segment Tree solution(javascript) is not fast enough, pls give me some tips.
I used binary search and it's not fast enough...can someone please give me some tips on how to improve? Should I try interpolation search? Maximum amount of test cases I can pass is 160 (100 medium size + 6 initial tests + 54 large size) I am using Java by the way.
Hi, I am running an O(log(n)) algorithm inside a loop, if i am not wrong the resulting time complexity should be O(nlog(n))
var smaller = function(nums) { first helper function here O(nlog(n))) loop{ second helper function here O(log(n)) } }
if so why am i getting execution timed out(12000 ms) issue. for the small random tests (100 of 100 Assertions) tests were completed in 70ms i could pass only 4 of 4 (large random tests) any advice would be appreciated
I'm a bit confused about this kata. I always get Execution Timed Out (12000 ms) but it's weird because when I check the tests I get 'Small random tests (100 of 100 Assertions)' in 'Completed in 102ms' I don't know if my algorithm is not fast enought or there's a issue with the tests.
Javascript version
The timed executions published only consider the execution time of your solution.
The overall timeout includes that in addition to all the other code that goes into setting up the tests.
For random input, the test setup includes running a base solution to see what the answer should be.
So for every instance your solution is run against random input, another base solution is also run and that time is not reported.
Solving this kata requires a very well optimised solution.
This comment has been hidden.
There are 100 big tests! So you did half the job. Bon courrage
Good unique kata
This comment has been hidden.
Same question. I passed 61 big tests and still "Execution Timed Out (16000 ms)" Java
java, 2. XD
Python language is not available?
Nope.
It is.
This comment has been hidden.
'Means your structure must be wrong somewhere. Note that you don't need that version. The regular/simpler one is enough.
EDIT: isn't there a builtin in java about that? or at least something you can build on?
This comment has been hidden.
I made it finally!!! <3
Had somebody made it in Java?
Because I already have an O(n log n) algorithm and the output still been "Execution Timed Out (16000 ms)"
Just tell me yes or no...to change of lenguage or to try harder :)
I'm getting the same error.
im getting the same
I think maybe not all n log n's are equal. I have a solution that is technically n log n, but very often doesn't need the log n part.
I wrote two solutions both of them have this exit code problem but the output is proper. any tip or suggestion is welcomed.
Hi,
Not a suggestion, a question ;)
I guess the exit code is related to time out? you need a more efficient approach (anything slower than O(n log n) won't pass)
cheers
This solution is exactly the same solution as the reference solution, even the comments are the same. This must be a very big coincidence ...
Only //what? is added to not get a copy solution.
More equal solutions ...
This one and this one.
Another one:
This one and this one.
that's called copycats. can you give the links to the users profiles?
https://www.codewars.com/users/PeterZwegat
reported
you cant understand that this kata goes with extremly bigger test cases?, they are different
Very cool kata! Super satisfied once solved. It's one of the rare katas I've seen that forces using a better data structure.
Thank you author!
This comment has been hidden.
smaller([5, 4, 3, 2, 1]) === [4, 3, 2, 1, 0] 5 is bigger than all elements to the right of it. There are 4 elements to the right, so write 4 to the result array. 4 is bigger than all elements to the right of it. There are 3 elements to the right, so write 3 to the result array. etc.
smaller([1, 2, 0]) === [1, 1, 0] 1 is bigger than only one element to the right of it. So write 1 to the result array. 2 is bigger than one element to the right of it. So write 1 to the result array. There are no elements bigger than 0 to the right of it. So write 0 to the result array.
Java translation is ready for review.
The Instructions should contain the information about time complexity. I can only guess that quadratic solutions are not acceptable, imo that should be said at the beginning
There is a
performancetag, and some languages show test sizing ( all languages should do this ).My solution passes 193 tests and then times out. Just how many more are out there??
Okay, I've tried about 30 more times and finally all the tests passed and my solution got accepted. But it left me with... mixed feelings.
It would really, really help if you mentioned with which language you're having this problem. Help us help you!
Closing.
Hi! Sorry, I thought you could view my solution. The language is JavaScript.
The second description example is wrong, should be an array and instead it is 3 numbers
I didn't understand the instructions, Can some one explain further?
For every item in the left, you should return how many numbers on the right are smaller So:
There's an easy greedy solution that involves complexity similar to O(n * n), so the proposed tests would pass, but final tests will not due to timeout. I'm trying to figure out how to make this O(n) :D
Good luck!
I don't think it can be done in O(n) (but maybe I'm wrong about that)
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Please read the earlier comments in this thread. You will see that you are not the only one having problems to solve this kata. Simply looping through the list is too slow. Try to search for articles about datastructures that can sort or search arrays very efficiently and you will find what you need.
Cheers.
Random tests are way too big. I've done 7 different approaches to the answer in Javascript, two in ruby, and three in crystal, and all of them pass the first 106 tests, then they time-out on the random tests. It'd be nice if you could remove them or make them shorter, because at this point I'm not sure algorithm efficiency is a problem.
that's on purpose. You need a better algorithm approach (without that requirement, this wouldn't be a blue kata)
literally just solved the kata, did some research on faster more effecient algorithms, shorter code apparently doesn't always mean it compiles faster.
This comment has been hidden.
same
There must be smaller tests too, otherwise it's impossible to debug the solution.
Added small tests too.
Is there some way to remove my solution? It is not my solution, I copied it from the solutions on the easy cata just to see if it would pass (attempt only, not submit) it but I did not thought it was gonna get submitted.
PHP translation is ready. Please, review and approve
This comment has been hidden.
There is an obvious way of two cycles, but it has n^2 difficulty. Give me a hint how to reduce the diffuculty, please.
It might be nice to get some moderate size random tests (maybe array size 25 or so), since there are many cases which might pass the static tests but fail random due to logical errors, not timeouts. As it is, it's almost impossible to actually debug in the test suite without just writing my own random tests.
This puzzle is throwing me a bit, any hints?
This comment has been hidden.
No, you have the correct complexity. Perhaps tweak your solution a bit and reduce overhead?
Ruby translation submitted
please see above issue
Is it really possible to solve this kata in <12s? I thought my algorithm was quite effective, but apparently not 😅 as it times out...
Tried running
smaller = x => nulland it takes 6+ seconds to execute, so there's like ~6 sec to execute the algorithm on all the test cases.Help?
This comment has been hidden.
That's not unfortunately, that's by design. Try the easy version.
I am also getting timeout on O(n log n)
This comment has been hidden.
This comment has been hidden.
this is a hard one for me... I humbly ask: any advice?
This comment has been hidden.
Never mind, i finally got it right, calling
new ...at every iteration slowed my code down..
Seeing how many times same questions are being asked again and again, posting a conclusion:
would be more useful to update the description with that, actually. Maybe in your translation? ;)
Questions will still be asked, as people don't read the spec. So it's better to have this one here. :smiling_imp: Might edit spec later, as translation has nothing to do with spec clarification.
Coffeescript translation
It was rejected.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Sadly I find this kata near imposible without more hints :(
not an issue.......................
(damn, I clicked too fast for my browser, about the flag...)
Wow. Just wow. My initial attempt didn't even passed first random test, so after some good thought and optimisation I've managed to beat it, even passed 2 random tests before timeout, but got stuck on third. Then, out of curiosity I've tried to run random test with dummy function, just to know how much tests are there, was pretty sure third would be the last one, but just in case... So after I've picked up my jaw from chair, and seeing that just test code was eating about 8 seconds from 12, I was pretty sure that test case is bugged, glad I've checked discussions. Now I slowly realise the amount of optimisation required, the whole approach must be wrong, though got a hint from post down here - accesing object properties is slow, hmm... Got to think now...
This comment has been hidden.
⌐■_■No.This comment has been hidden.
Hi everyone again! Thanks a lot for help with this issue, I found that I had a very stupid error in implementation (no idea how it passed sample tests :)).
Now I wonder - is it OK that I have "Array is too large to print out - Expected: 'true', instead got: 'false'" messages? (I'm definatelly not trying to print anything - I run empty function - maybe it's some issue with test? Should I ignore it and continue coding?) And the second question to people who passed this kata - is it OK that when a try to run empty function it takes 7-8seconds or it's caused somehow by that messages about array size?
Internal solution runs for around 6 seconds, so your aim is to be at least as fast as it.
If your answer is correct, you get
true, otherwise you getfalse.Hi alanolmo
@Voile is correct about the internal implementation. The
Array is too large to print out - Expected: 'true', instead got: 'false'just means that your solution is incorrect for that test case and unfortunately due to the large arrays, I can't print out the test array so that you can see what values were used in that test. It has nothing to do with whether you are printing out anything or not.Thanks for explanation!
hmm.. i have two algorithms, one takes about 1380ms and the other only 80ms.. but the random tests still fail. I think it would be much better to give feedback in the random tests and tell which testcase failed. With the current test suite it is very unhelpful to figure out what is missing/wrong with the solution. (Unless this is not even about the performance but about writing a new testsuite to debug the code?)
In addition it would be nice to give a hint in the description what is actually the problem to solve (performance) and give clear boundaries for the maximum execution time.
Execution time is 12 seconds (global CW limit).
Also, you seem to mix up the purpose of validity tests and performance tests :)
The issue with the test suite is now fixed (see issue written by alanolmo).
I just mean that it would be helpful to know at the beginning, that it is about the complexity of the algorithm ;-)
This comment has been hidden.
This comment has been hidden.
I'm getting the same thing.
I copy & pasted my solution out to a html file to test it in Firefox (which I end up doing a lot when I'm stuck). Turns out I can break my solution by feeding it really long arrays (9k+) which some of the other commenters here mentioned were in the random tests, I get
too much recursion.Well, so much for that idea. :/
That's because the random tests has this:
Putting an empty string in Test blocks is a bad bad bad idea, because it eats all the
console.logoutputs.Hi Voile
Why would an empty string make any difference as opposed to some text message for that test block when it comes to eating the outputs?
I don't know, it's a well-known issue of CW's JS test framework. So the common suggestion is to at least put something non-empty as the descrption string.
I have added some text to the
itblock. Thanks for bringing this to my attention, I had no idea about this issue.This comment has been hidden.
this is not an issue with the kata.
That's the point, O(n^2) is not a fast enough algorithm for this kata.
Otherwise why'd you think this is 3kyu? :P
I'm not talking about O(N^2). its obviuous that it wont do. The thing is that in example i given the complexity is actually O(N). If the problem can be solved with less than linear complexity, it worth to put this as a note into description.
It's not.
You're looping through your histogram every loop, which, in general, will have O(n) entries (since duplicates are rare), so your algorithm is not O(n), but O(n^2).
in a loop of N iterations I have a loop with 3 iterations, since 3 is constant it yields O(N). It's not O(N^2). The snippet above is not a real solution and histogram is a constant dummy object I used to test various approaches to store arrays and look how it will affect performance.
Just to be clear: this dummy code, that doesn't do anything useful at all and has complexity of O(N), can't pass tests due to timeouts. I assume that it has something to do with lags on codewars in general...
If you're trying to get the keys of an object and looping through them for every array element that's going to be slow, because getting the keys of an object is slow. If you change the above to
It finishes in 8.5 seconds. This is a language feature, not a kata feature or algorithmic feature.
Also, in the end, this approach is still O(n^2), so I think you might as well drop this approach at once and think of a better algorithm :)
This comment has been hidden.
Well, it shows why one shouldn't do too much performance tuning in JS, it's somewhat magical! :P
But yeah, if a correct approach is used the total runtime (including the 6 seconds spent by the test code itself) should be less than 10-11 seconds.
The description should be more specific of what this kata asks for. Statements should be added such as:
The kata test cases have 100 random tests with arrays with between 80k-100k elements in them. A simple solution might take hours to finish the tests, but this kata requires them to be done in less than 12 seconds. The fastest solutions take around 10 seconds to finish.
Specfically explaining what the kata requires, rather than just calling it "a hard version" would allow users to make an informed decision on whether or not to attempt to solve it.
It probably depends a little bit on language, but generally you need a fast
O(n log n)solution.O(n²)definitely won't cut it.People who would understand that specification understand a
3 kyuranking and aperformancetag.Closing.
This comment has been hidden.
This comment has been hidden.
Your tests don't complete in time! Please refactor your "random test" suite.
10 people have completed this kata. We all had the same tests. You cant console log a 100k element array. Make sure you can pass the example test cases and then figure out how to deal with it when it scales.
I completed this kata. If it helps, analyze your algorithm. You need something faster than O(n^2).
I use something faster than O(N^2) but it does not pass. How much time does your solution take to complete?
Reference solution inside the tests completes 100 random tests in around 6 seconds. If you implement something similar, it's on the edge of the 12 second limit.
This comment has been hidden.
Hi The test cases are fine, they are all good. They timeout because they are very stringent and huge.
If the tests time out they are anything but fine! Even a simple function like the following doesn't complete in the alotted 12 seconds...
So anyone trying the kata can't even debug the tests.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Hi, I flagged your comment as "spoiler". Don't worry if you cannot see it anymore, people who have already solve this kata can and will be able to answer to you.
BTW : never post solutions or part of solutions without using the spoiler flag.
Cheers
Hi rscharfer
You are right, your test case is a bit small. The kata test cases have a 100 random tests with arrays between 80k-100k elements in it. Thanks for taking time out to do the kata!
Thanks @Blind4Basics
Great. Ok, thank you.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
...Okay, so I somehow broke the kata accidentally by first trying to return
arr.lengthfor the random test cases because I wanted to see their sizes. See my solution. In fact, returning anything related to arr works:arr,arr[0],arr[100], ...Something is definitely broken but I can't figure out where, probably related to the
Function.prototype.toStringoverride. It's pretty weird, and probably bad because it causes arrays to not behave like how it is typically at all.Thanks Voile! There was a massive issue. It is recitified now. Thanks for reporting this, really appreciate it.
Oh... perhaps it was my mistake yesterday, haven't seen every detail and so perhaps i was a litle bit too quick (after looking the valid and invalid solutions everything seems ok so i looked for some other older katas)? Hope you haven't too much trouble solving this issue! PS: Just saw the code should be quicker than before (more invalid solutions), so later on i will look again...
I just changed your testcases a little bit and approved the kata (average was 3kyu), as expected many solutions got invalid. It's older than one year and it really was (is;-)) a great kata. So hope it's ok for you?
Excellent smile67! You are a legend for getting the test cases to what it was! Thanks mate, appreciate it.
Don't know why you haven't changed your tests - i enjoyed this kata very much and i remember it was really difficult at my beginning here. Took me some different tries and discussions with myjinxin;-)!
...deleted (cw error)
I didn't bother changing the tests because some users passed the kata even if they timed out, which made me think it was pointless because Codewars had the issue.
The following line of code in the (hidden) preloaded section is causing some weird behavior:
Effectively it is preventing the use of typed arrays for some reason that I do not comprehend. Really it shouldn't do that, so I filed an issue against Codewars itself as well. See https://github.com/Codewars/codewars.com/issues/279.
In the meantime, I suggest working around the issue, perhaps by changing it to return an empty string:
Thanks, updated to your suggestion.
This comment has been hidden.
Ok, have it (realized my first point and solved it) - so no help is needed;-) Very nice kata, thanks and three points for you;-)!
PS: Process took 5099ms to completeWell done mate! Kudos for persisting till you got it. That is a really good trait to have.
Thanks, very kind;-)! Perhaps next time again...:-)?!
This comment has been hidden.
Arrays have lengths between 30k and 50k. They are huge.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
PS: Very nice kata, really hard i think (or i'm blind for a quick solution - the first (but very short) one breaks after ~ 50 random tests);-)! 10$ for reducing to 40 random tests:-)?!
This comment has been hidden.
This comment has been hidden.
How many random tests are there? my solution only pass 6 basic + 16 random ...
100 random tests.
A difficult problem ， I did it... Vote 3Kyu for you
I think you got lucky my friend. That solution shouldn't have passed. Test cases have changed. Thanks for showing a flaw in my tests tho.
I give up, unless I'm similar to your solution, you can always add your data until I can't pass ， isn't it?
Not really. Arrays should have had a minimum of 30k elements and my tests generated between 10 and 30k which is not correct. That is why your solution could pass.
This comment has been hidden.
I've test for your code 5 times , It can pass 34-38 random test in 6000ms
This comment has been hidden.
Am i wrong - your solution only passed the tests here before testcases changed (so you have no solution yet)? You are right, sometimes 34-38 in 6 s, and sometimes up to 50, but 50 was max., did some tries. It was only a first short test and idea to get a feeling for the time and problem (took me 10 minutes to do it on my tablet, and the idea generally was correct - but surely not quick enough). I will look at this problem next days once again, but not yet - i'm very busy this week... There are different possibilities (or better ideas;-)) for a next try.
Once again, I've solved this Kata (if he doesn't add the test data), your code search section has been fast enough, but it's a waste of time in other places.
Ok sorry, now i have it - it's early in the morning and my brain isn't working;-)...
I just solved three Kata(about sudoku validator), with almost the same solution, so funny... http://www.codewars.com/kata/540afbe2dc9f615d5e000425 http://www.codewars.com/kata/529bf0e9bdf7657179000008 http://www.codewars.com/kata/did-i-finish-my-sudoku/
Looked at it, seems easy - two of them with 4kyu (high rating for easy problem?) - thanks for the links, next time...;-)!
Are you an American? In that case, I head down to the bottom of your feet, a distance of the earth (a little joke). It's the afternoon in my country(China).
No... Germany... day beginns 08:34.. i think you are 6-8 hours later... (sometimes i went on holiday near by your country;-))
So... no time, but solved them;-)... Nearly same solution for all three katas. Thanks for your hint, was nice to do... solved between meeting and meal;-). And your solutions... as always very short and well done (i'm often only solving without thinking and typing on tablet screen);-)...
At first, I'm not a professional in javascript, but I tried several ways and was't able to pass the random tests. What a pitty! May someone cangive me a hint on which way I should concentrate:
Array.mapandArray.filterAs you can see, I'm a little desperated...
Little typo in the tag section
peformance-->performance.Futhermore, I would add a sentence to the description saying that this kata is exactly the same like your first kata, but there are more complex tests which concentrate on performance issues.
both points seem to have been addressed: there is a
performancetag and a link to the easier kata