Re:Getting a job at Apple without going to college or doing ...
by ninkendo on Thursday August 17, 2023 @02:32PM
(#37166048)
I don’t see how you can increment `9999` in O(1) if the string length is considered the size of the input. You have to rewrite the string with zeroes, which is O(n) of the size of the string.
Re:Getting a job at Apple without going to college or doing ...
by jeffbee on Thursday August 17, 2023 @02:48PM
(#37166246)
For that case, which is the worst case, yes. And the amortized average complexity is O(1) because that case is unlikely.
Are you starting to see why this is a good icebreaker? It has all kinds of discussion potential.
Re:Getting a job at Apple without going to college or doing ...
by ninkendo on Thursday August 17, 2023 @11:32PM
(#37171142)
No, not when the goal is to actually implement it. You implied in your comment that if I wasn’t someone who could implement this in 15 seconds, I’m not a good candidate in your mind. It would take me longer to explain why it’s not trivial.
Re:Getting a job at Apple without going to college or doing ...
by ericbarrett on Thursday August 17, 2023 @07:40PM
(#37169779)
You could return the 0s with a carry flag.
Re:Getting a job at Apple without going to college or doing ...
by jeffbee on Thursday August 17, 2023 @08:34PM
(#37170156)
It's still O(N) even if you don't need to copy the input, because you nonetheless visited every character in the string.
Re:Getting a job at Apple without going to college or doing ...
by ericbarrett on Friday August 18, 2023 @05:34AM
(#37173243)
Oh, I skimmed over the O(1) part. I'm baffled then. How do you calculate an N-rune string without O(N)?
An O(1) in-place solution with a sane API exists in C++ and the form of it is also a handy indicator of whether candidate who proposes solving this in C++ is familiar with more recent standards or not.