Minimum XOR for queries

I was asked the following question in an interview.

Given an array $$A$$ with $$n$$ integers and an array $$B$$ with $$m$$ integers. For each integer $$b \in B$$ return and integer $$a \in A$$ such that $$a \otimes b$$ is minimum, where $$x\otimes y$$ for to integers $$x$$ and $$y$$ is the bitwise xor operation of $$x$$ and $$y$$.

For example:

Input:

A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]


Output

[6, 9, 6, 9]


Because when 4 is XORed with any element in A minimum value will occur when A[I] = 6

4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5


Here is my brute force solution in python.

def get_min_xor(A, B):

ans = []

for val_b in B:
min_xor = val_b ^ A[0]

for val_a in A:
min_xor = min(min_xor, val_b ^ val_a)
# print("{} ^ {} = {}".format(val_b, val_a, val_b ^ val_a))

ans.append(min_xor ^ val_b)

return ans


Any ideas on how this could be solved in sub O(MxN) time complexity?

I had the following idea in mind. I would sort the array A in O(NlogN) time then for each element in B. I would try to find it's place in the array A using binary search.Let's say B[X] would fit at ith position in A then I would check the min XOR of B[X] ^ A[i-1] and B[X] ^ A[i+1]. But this approach won't work in all the cases. For example the following input

A = [1,2,3]
B = [2, 5, 8]


Output:

[2, 1, 1]


Here is the trie based solution

class trie(object):

def convert_number(self, number):
return format(number, '#032b')

binary_number = self.convert_number(number)

for bit in binary_number:

if bit not in cur_dict:
cur_dict[bit] = {}
cur_dict = cur_dict[bit]

cur_dict[number] = True

def search(self, number):

binary_number = self.convert_number(number)

for bit in binary_number:
if bit not in cur_dict:
if bit == "1":
cur_dict = cur_dict["0"]
else:
cur_dict = cur_dict["1"]
else:
cur_dict = cur_dict[bit]

return list(cur_dict.keys())[0]

def get_min_xor_with_trie(A,B):

number_trie = trie()

for val in A:

ans = []

for val in B:
ans.append(number_trie.search(val))

return ans


Using Trie Data Structure, you can solve this problem in $$O(m + n)$$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values).
Let say we know that all integers in $$A$$ are 32-bit values. Use the following steps:
• Insert all values in $$A$$ into the tree in $$O(32 \times m) = O(m)$$
• For each value in $$B$$, traverse the tree from the leftmost bit. If a bit doesn't match with child of a middle node, continue the traverse using the existing child until you reach a leaf. Traversing finishes in $$O(32 \times n) = O(n)$$
Which in total, the complexity is $$O(m + n)$$.