4 ms·
Do you allow linear space?
by plonh 11y ago
Do you allow linear space?
- deleted 11y ago[deleted]
- eveningcoffee 11y agoNope. Constant space. But there is a catch that is very likely not obvious here. All the numbers in the array are (were) unique (and the zero was not present).
- msoad 11y agoYou didn't say all the array includes all numbers with no repeats ect ect...
- eveningcoffee 11y agoThis is also case with the job interviews. Some information is actually missing/not obvious and interviewers may actually evaluate your reaction to this situation because this would also model (to some degree) a real life situation. So I added the missing bits (and fixed typos). You have an array size of n of integers from 1 to n, that is not sorted. There are no duplicate numbers in this array. One of the numbers got changed to 0. Given the array after the change return the changed number in linear time and constant space. Assume the same array but two of the numbers got changed to 0. Given an array after the change return the changed numbers in linear time and constant space. The first part of this problem should be simple. The second part is more tricky.
- Schwolop 11y agoFWIW I've had this same question in an interview years ago in Australia. Don't recall seeing the second part (which is more interesting, mathematically), but it just goes to show how many questions end up re-used by different companies as their employees travel.