= 27d567bc2d48d9f40e9ccc20ea370b15)
RichardKennaway 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)
For practical problems -- and you are looking to hire practical people -- asymptotic performance is only relevant up to the size of problem that could be encountered in practice. #2 is putting up a sequence of n alerts: n must be small enough to consider as an atom, i.e. it takes unit space and arithmetic takes unit time. 32 bits is plenty, even if a computer is going to run automated tests of the code. 64, if 32 just seems too small for an integer variable these days, but no more.
When you say O(log n) for #2, you're presumably talking about space? Time is trivially O(n).
Talking about space. My point is just that the practical man can send me an O(log n) solution and explain why it's not worse than the iterative solution. Either you say ints are constant space, and then so is the stack size (at O(log 32)), or you say the iterative solution is O(log n) for unbound n.