6 ms·
>But the hashmap guy might accidentally say it's O(N) memory (common mistake for frequency maps) Wait why is it O(1) memory for the frequency map? As you keep
by krackers 11y ago
>But the hashmap guy might accidentally say it's O(N) memory (common mistake for frequency maps)
Wait why is it O(1) memory for the frequency map? As you keep adding elements doesn't the hashmap have to resize to prevent too many hash collisions?
> finding if an unsorted list of numbers is an arithmetic series with just O(1) memory
Is the strategy to solve this to first find the common difference `d` with one pass through the array (by finding the largest and smallest) and then sweeping through one more time xor-ing each element a[i] with a[i] + d and checking if the result is equal to the (minimum) xor (maximum + d)?
- cyphar 11y ago> >But the hashmap guy might accidentally say it's O(N) memory (common mistake for frequency maps) > Wait why is it O(1) memory for the frequency map? As you keep adding elements doesn't the hashmap have to resize to prevent too many hash collisions? Presumably because you'll have a constant number of keys (I'm not sure what the exact problem he's referring to is).
- krackers 11y agoThe problem was to find the only non duplicate number in a list. I'm not sure how you would have a constant number of keys. I mean I guess if you consider a worst-case hash table with bucket for each integer you would have 2^32 keys (which is technically O(1) space since the size remains fixed regardless of list length). But using Big-O in this case is clearly disingenuous since the space allocated is far, far more than the one for xor solution.
- eranation 11y agoMy 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 :)
- krackers 11y agoAh that makes sense. 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?