Space complexity for storing integers in Python 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?
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.