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