= 27d567bc2d48d9f40e9ccc20ea370b15)
datadataeverywhere comments on Quixey Engineering Screening Questions - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (22)
O(log n) stack size is allowed (since normal loop would also take O(log n) just to write down n), but you need to keep each stack frame constant size, not O(log(n)), since otherwise you get O(log^2 n) total space complexity.
I had thought the solution was very simple before you pointed this out. With some difficulty I improved my solution to O(log(log(n)) * log(n)), and it took quite a bit more time for me to get completely constant sized stack frames.
I suspect most people initially come up with the O(log^2(n)) solution and jump next to the O(log(n)) solution without getting stuck in the middle there, but I'm curious if this gave you any problems.