6
$\begingroup$

So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point.

The question that the interviewee was trying to solve was -

Array 1 has all unique integers.
Array 2 has the same integers as array 1, except one integer missing.
The code has to find that missing integer.

The interviewee suggested we can just subtract the sum of the second array from that of the first array and that'd give us the missing integer, and since these are just sums (integers), they'd take O(1) space. But the interviewer then said it's not actually constant since a sufficiently large sum can take more space than a smaller sum.

While that is true, and I double-checked it, via -

In [1]: import sys

In [2]: sys.getsizeof(90)
Out[2]: 24

In [3]: sys.getsizeof(9000000000000000000000000000000000)
Out[3]: 40

what complexity is it then?

Is saying constant space complexity for these algorithms wrong then?

$\endgroup$
  • 1
    $\begingroup$ Do it without the arbitrarily large sums. Initialize a var to 0 and use a shared index to walk along both arrays. At each iteration, add the value from the longer array to the var, and subtract the value from the shorter array. Upon adding the final number from the longer array, var should have the value of the missing number. (you may still get arbitrarily large values in var in the worst-case scenario, like for instance if the longer array is sorted in descending order and the shorter one is sorted ascending) $\endgroup$ – aroth Nov 11 '19 at 7:22
  • 1
    $\begingroup$ @aroth better yet, use XOR. Interleaved addition and subtraction can still lead to quadratically large temporary values. Alternatively, advance one array if the sum is negative and one if it's positive - but that's harder to code, and breaks for negative members $\endgroup$ – John Dvorak Nov 11 '19 at 18:30
6
$\begingroup$

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the space complexity is $O(\log N + \log M)$, where $N$ is the number of integers in input and $M$ is maximum value in input. However note that normally we don't measure space complexity in bits: if we did, then the space complexity of most linear time algorithms, like DFS and BFS would have an extra $O(\log n)$ factor.

In my opinion, there is no single right answer when talking about space complexities like this in an informal setting like job interview. However you should keep in mind that having a single right answer is not the goal of job interviews.

$\endgroup$
  • $\begingroup$ Sure, there's no single right answer, but there are plenty wrong ones :) Saying "this is an integer, therefore its space complexity is O(1)" is wrong because in practice O(1) holds only while integers are limited in range. $\endgroup$ – IMil Nov 11 '19 at 4:02
  • $\begingroup$ @IMil But, in the context of a job interview, as distinct from the asymptotic context of complexity theory, the integers usually are limited in range. If you're building, say, Google Maps, you're dealing with navigation on a spheroid about 12700km in diameter, so any distance you need to consider is less than a 32-bit number of metres. $\endgroup$ – David Richerby Nov 11 '19 at 8:37
  • 2
    $\begingroup$ @DavidRicherby: Having built something very similar, I can testify that software engineers are very happy that the earth's circumference is approximately 2^32 centimeters. It's almost as if the centimeter is derived from the earth's circumference. $\endgroup$ – MSalters Nov 11 '19 at 13:59
  • $\begingroup$ I'll note that if you perform the addition and subtraction one at a time in an accumulator (switching between the "add" and "subtract" list any time one of the operations will overflow), your accumulator's size will be O(1) to the maximum storage size of any one integer in the two lists. Specifically, 1 extra bit is both necessary and sufficient to guarantee that you'll always be able to operate on at least one of the two lists. $\endgroup$ – Brian Nov 11 '19 at 15:31
  • $\begingroup$ Thinking about it more carefully, there may be pathological cases requiring 1-2 extra bits due to weird issues involving boundary conditions (e.g., the representable integer number line is not symmetric around 0 since "number of odds represented" + "number of evens represents" + 1 (for zero) is an even number. $\endgroup$ – Brian Nov 11 '19 at 15:38
3
$\begingroup$

Resource usage always depends on your model of computation. If you're in a situation where integers can grow arbitrarily large then, yes, you need to take that into account.

One way of doing this is by assuming that integer variables take an amount of space that depends on the value stored. Another way is to use something like the word RAM model, which more or less assumes that integer variables are big enough to hold whatever numbers come up in the instances you care about. Another is to explicitly assume that whatever size of integer variable you fix is big enough. What solutions might be appropriate depends on what you're doing.

$\endgroup$
1
$\begingroup$

No, breaking the algorithm by increasing n (the amount of numbers) makes this 100% not working in constant space.

To the question nobody asked:

You could easily modify the algorithm to get the space to be constant. (Only the solution given in the interview has this problem. The "best" solution does not have this problem.)

Basically the size of the sum should not be a problem either. Assuming that each number can be stored in constant space of b bits you could easily modify the algorithm to use less space by doing this:

  1. calculating the sum for each list/array mod $2^b$ ($r_1$ and $r_2$, with $r_1 ≥ r_2$)
    • if $r_1 = r_2$ -> either the result is $0$ or the input is broken
  2. getting the difference ($d = r_1 - r_2$)

Thanks to a possible overflow caused by the number missing:

  1. calculate the inverted result $d' = 2^b - d = r_2 - r_1 + 2^b$ (mod $2^b$)
  2. search for both numbers $d$ and $d'$ in both lists - the one found exactly once is the result

If space was limited (for any reason) this would be an option. It comes at a price: looping again over the input - which might not be possible if the data comes from a server and you do not have the storage to save it.

So almost constant space that only scales with size of the input - I would ignore it in this case because the size of numbers is often ignored. (-> 2 ints and 2 bools). For doubling the steps in the loops. (And 2*O(n) = O(n).)

Example:

  • b = 3 -> mod 8
  • list1 = 3,5,7 -> 15 (mod 8) = 7
  • list2 = 3,5 -> 8 (mod 8) = 0
  • d = 7 - 0 = 7
  • d' = 0 - 7 + 8 = 1

Example 2:

  • b = 3 -> mod 8
  • list1 = 1,3,5,7 = 16 (mod 8) = 0
  • list2 = 1,3,5 = 9 (mod 8) = 1
  • d = 1 - 0 = 1
  • d' = 0 - 1 + 8 = 7

For both: So either 7 or 1 should be exactly once in the 2 lists. Here 7 is both times the result and the 1 can be found only in amounts that are even.

(Writing a function to flip a bit when you find a given number while looping over those 2 lists should be easy.)


Optimization:

By using the length of the 2 arrays and comparing them you could easily get some information about which value ($d$ or $d'$) is not important. Calculate sum(longer array) - sum(shorter array) and you will have the number.

-> Single loop over both "arrays" in parallel and $2$ numbers of space would be the best case scenario. (And this would even work with some data stream that can't be repeated for some reason.)

In case you cannot use both arrays in parallel you would need one extra number ($≥2$ bits). Then you would add $1$ for each number in array1 and substract $1$ for each number in array2. The result is either $1$ or $-1$ which gives you information which list is longer. (Other results: something is wrong.)


As spitemaster suggested: Using XOR can be used to improve this even more. His idea reduces the amount of work a bit on older machines (or slower machines you can buy today - like µC) and allows you to save about 50% of the RAM (or 66% of the registers) needed above.

(If you implement the algorithm in hardware this would be really interesting, because XOR is much smaller/faster than an adder.)

The algorithm would simply run over both arrays using XOR on all values. The result is a mix of all numbers that appear 1 + 2*k times. So if there is only one such number you have the number.

$\endgroup$
  • $\begingroup$ How is that the best algorithm? Wouldn't the 'best' algorithm for this problem (narrowly defined) be taking the XOR of each element in both lists, which would leave you with the single missing number? That's constant in size and very fast. $\endgroup$ – Spitemaster Nov 11 '19 at 13:48
  • $\begingroup$ True. In that case you could even simply run over both arrays at once. The result would be the last value calculated. (-> Faster operation (on old machines), a few calculations less and you could cut the needed memory to <50%.) But it would be still "minor optimisation" (O(n) stays O(n)). The idea is of course a bit better. $\endgroup$ – MurksVomOrk Nov 11 '19 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.