4 ms·
Eh… You’re given `99999`. Increment it. A naive approach would turn this into `9999:`. Making this work is a bit complicated and involves memory reallocation i
by ninkendo 3y ago
Eh…
You’re given `99999`. Increment it. A naive approach would turn this into `9999:`. Making this work is a bit complicated and involves memory reallocation if you’re in a C-like language and you need to increase the length of the string in order to increment it. You’ll probably want a system where the caller passes a buffer of sufficient size to use for rewriting the string, in case you overflow. Make sure to have a way for the caller to pass the buffer length. You don’t want to allocate because that’s not the way it should be done in C, callers should generally allocate. You could use atoi, increment, and itoa to go back again, but that’s probably “cheating” from the perspective of a leetcode advocate, they likely want you to do this without the stdlib conversion functions.
There’s a bazillion reasons why this sucks as an interview question. There’s no way a correct answer is just something you’ll “get in 15 seconds”.
- jeffbee 3y agoWhether 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.
- ninkendo 3y agoI 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.
- jeffbee 3y agoFor 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.
- ninkendo 3y agoNo, 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.
- ericbarrett 3y agoYou could return the 0s with a carry flag.
- jeffbee 3y agoIt's still O(N) even if you don't need to copy the input, because you nonetheless visited every character in the string.
- ericbarrett 3y agoOh, I skimmed over the O(1) part. That baffled me for a moment, then I realized you were talking about the general case of a uniform random input where a carry for the 1s digit has probability 0.1, a carry for the 10s digit 0.01, etc., and all 9s is the pathological worst case, right? That's what I get for coming into the discussion sideways.
- Aurornis 3y agoIronically, you just answered the "difficult" interview question in a few lines of casual commenting. If you're not allowed to use atoi and itoa, it's still not all that difficult to do in C. Incrementing ASCII characters and handling carries is really trivial. I'd be kind of worried if I was hiring a C developer who didn't know the basic things you described above. I'm not sure why you think those are esoteric concepts that we shouldn't expect developers to know.
- suresk 3y agoYour last 2 sentences highlight the crux of it, I think - in the first sentence, you say "C developer" and in the second just "developers". This actually does seem like a great icebreaker-type question for a C developer. I'm less convinced every developer should be able to go into that level of detail if they are doing Javascript or Python or whatever. Ideally they'd be able to at least reason through some of this and demonstrate some understanding of some of this, but I'm not sure it is a great icebreaker question for all developer roles.
- crooked-v 3y agoJavascript doesn't even have ASCII - every string is UTF-16.
- ninkendo 3y agoI didn’t answer the interview question. The interview question would be to actually implement it. Something that was stated should be trivially done in 15 seconds. It would take me longer than that to explain why it’s not a trivial problem.