News for hackers. Stuff that matters.
Re:Getting a job at Apple without going to college or doing ... by jeffbee on Thursday August 17, 2023 @02:24PM (#37165939)
Whether this should be done in-place or not is a completely valid direction in which to take the discussion and would be a "pass" from me. Also a "pass" would be `return itoa(atoi(input)+1))` with relevant caveats.

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.

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)?