mishutka.gorelik
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I plugged it in into my unit tests that I've created to test my solution, and it seem to fail in half the cases.
I am sure that is due to some corner cases, because solution is similar to mine and uses rotate, shift or bubble down (whatever you want to call it).
I would like to know what is order of complexity of all of those solutions? To me they all look like O(N**2), am I missing something?
We iterate 1..N and on each iteration we potentially swapping N/2 elements, that IMHO gives O(n**2).
Comment hidden because of low score. Click to expand.
0
of 0 vote
I am no expert in c++ STL, but I would assume that inserting element into vector may have O(N) complexity. Am I missing something?
So iterate N times and possibly move N element each iteration, would it give us O(N**2)?
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Here is a silly solution. I don't think I got O(N), feels more like O(N**2). I am not posting utility class, just reorder function.
- mishutka.gorelik September 03, 2014