JacVlD
BAN USER- 0of 0 votes
AnswersImplement rotate function for forward-only iterators.
- JacVlD in United States
Clarification: with O(1) additional memory. Rotate semantics should be that of std::rotate.
I personally know a O(n*log(n)) solution which takes O(log(n)) extra memory, and I assume it should be possible to reduce memory costs to O(1).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer
Splendid! I saw something similar in STL implementation, though it was much less clear and I couldn't understand most part. Just for the other people who come to this topic, here is the proof of linear complexity: it's easy to notice, that each time you advance the iterators, you are in fact decreasing the length of the list on next recursion call by one, thus you do no more than O(n) advancements.
- JacVlD August 01, 2012My O(n log n) solution is based on reverse. You can implement reverse using simple divide-and-conquer: first reverse left part, then right part, and then simply swap them. In fact if n is a power of two, you can even implement this without any recursion, making it use O(1) space, however I don't know how to make this algorithm work in O(1) space in general case
- JacVlD August 01, 2012
Due to the fact that in many implementations of reverse algorithm these cases are actually different, we need these tests just to cover all execution paths.
- JacVlD June 27, 2013