You can use recursive calls to implement this with the same asymptotic space requirements as a simple loop, the trick is algorithmic, not in smuggling in a disguised loop (and is really no trick, once you look at what kind of data running recursion can store at what cost). I think it’s a great question.
Except that the question explicitly disallows any recursion that would produce an O(n) or even O(log n) stack size, and asks you to assume that the compiler won’t perform tail call optimization. I don’t think you can do it with O(1) stack depth and no tail calls.
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.
Oh, in that case I see the solution (though I won’t post a spoiler here). I was assuming that n was a regular Javascript variable, not a bignum or a float large enough to introduce precision issues, so that the normal solution would only use O(1) memory. That part of the question really ought to be clarified; Javascript normally doesn’t even support bignums.
Talking about asymptotic performance characteristics only makes sense when the domain of a problem is infinite, so to me it was clear that the problem should be analyzed as if ints are variable size.
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.
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.
You can use recursive calls to implement this with the same asymptotic space requirements as a simple loop, the trick is algorithmic, not in smuggling in a disguised loop (and is really no trick, once you look at what kind of data running recursion can store at what cost). I think it’s a great question.
Except that the question explicitly disallows any recursion that would produce an O(n) or even O(log n) stack size, and asks you to assume that the compiler won’t perform tail call optimization. I don’t think you can do it with O(1) stack depth and no tail calls.
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.
Oh, in that case I see the solution (though I won’t post a spoiler here). I was assuming that n was a regular Javascript variable, not a bignum or a float large enough to introduce precision issues, so that the normal solution would only use O(1) memory. That part of the question really ought to be clarified; Javascript normally doesn’t even support bignums.
Talking about asymptotic performance characteristics only makes sense when the domain of a problem is infinite, so to me it was clear that the problem should be analyzed as if ints are variable size.
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.
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.