Difference of Arrays
EasyWrite a function diff(arrA, arrB) that accepts two arrays and returns a new array that contains all values that are not contained in both input arrays. The order of numbers in the result array does not matter.
Examples
Pythona = [1, 2, 3, 4] b = [3, 4, 5, 6] diff(a, b) # => [1, 2, 5, 6]
Note: we don't care if numbers are out of order or repeated; for example, these two arrays are equivalent since they are re-arrangements of the same values:
Pythona = [1, 2, 1] b = [2, 1, 2] diff(a, b) # => []
Questions like this are usually used to test your knowledge of different data structures and reason about their space and time tradeoffs. You may be asked to implement one version and then asked to improve it under a time or space constraint.
It's always a good idea to begin by discussing the 'brute force' solution, and then inquire about time and space constraints. This will also give you a moment to consider the problem from different angles.
The brute force solution to this problem is to iterate through each array and check for the presence of every item in the other array. Notice that there's a lot of repeated operations with this approach because it requires looping over each array to check for every item, which results in an O(n^2) runtime.
We can solve the problem much more efficiently by using two hash tables (or sets). We create a hash for each array. Then we loop over each value in the hash and check if the opposite hash contains that value. The final solution looks almost indistinguishable from the brute force version, but since the lookup time of a hash is constant, our runtime performance is reduced to O(n), which is huge improvement.
Another way to solve this problem is to think about it in mathematical terms. Ultimately, we're being asked to find the symmetric difference (or XOR) of two sets of numbers. Most languages have built-in support for sets, and we can leverage this to simplify our solution a lot! Here's how we could use Python's set arithmetic to solve the question in one line: