My bad, I meant for a variant of the question that uses chars and not numbers. With numbers the hashmap will be still constant memory just like you said, but it's a big constant (2^32) - but still O(1) memory. This is because the input is of ints, and it can only be one of ~2^32 numbers for either values or keys. And since we only count the number, we don't need a map, we can just use a set (a map with boolean value true if the element is in the set) we add to the set and remove when we see the element again, the only element left is our non duplicate item. But the max we can have is sizeof(int)/2-1 duplicate numbers + 1 non duplicate, so memory can't be more than a constant.
In the char variant, the worst case number of keys in your hashmap is the total number of chars in Unicode. You can't have more than that no matter how big is the input.
So both cases are a very, very big constant, but still a constant.
Time complexity however is theoretically unbounded as you can have any size of input, but again, this is limited to the max size of an array, so TECHNICALLY the time complexity is an integer in Java at most 2^32 as well.
But I would not risk saying that in an interview, O(1) memory will pass, saying O(1) time because the size will never be longer the the max array length sounds more risky.
if it's an int though, it's an O(1) and O(1) memory if you really want to be technical. So are all interview questions involving an array of integers I guess :)
And what was the intended solution for finding if an unsorted list of numbers is an arithmetic series in constant memory? You say it's the same xor trick, but I don't see how it's applicable. Do you xor all the values with all the values shifted over by the common difference?
"arithmetic series" and "unsorted list" are mutually exclusive statements. Unless you mean something like "the sorted version is an arithmetic series".
In the char variant, the worst case number of keys in your hashmap is the total number of chars in Unicode. You can't have more than that no matter how big is the input.
So both cases are a very, very big constant, but still a constant.
Time complexity however is theoretically unbounded as you can have any size of input, but again, this is limited to the max size of an array, so TECHNICALLY the time complexity is an integer in Java at most 2^32 as well.
But I would not risk saying that in an interview, O(1) memory will pass, saying O(1) time because the size will never be longer the the max array length sounds more risky.
if it's an int though, it's an O(1) and O(1) memory if you really want to be technical. So are all interview questions involving an array of integers I guess :)