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):
    head = {}

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

    def add(self, number):
        cur_dict = self.head

        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):
        cur_dict = self.head

        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:
        number_trie.add(val)

    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: 


Create an empty trie. Every node of trie may contains at most two children
for 0 and 1 bits.
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)$.