Maximum XOR of Two Numbers in an Array Interview Question for Amazon

## Maximum XOR of Two Numbers in an Array

This problem asks us to find the maximum result of XORing two numbers within a given integer array.  We're given the constraints that 0 <= i <= j < n, where n is the length of the array.

### 1. Brute Force Solution

The most straightforward approach is to iterate through all possible pairs of numbers in the array and calculate their XOR, keeping track of the maximum XOR value found so far.

```python
def find_maximum_xor_brute_force(nums):
    max_xor = 0
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            max_xor = max(max_xor, nums[i] ^ nums[j])
    return max_xor

Example:

nums = [3, 10, 5, 25, 2, 8]
result = find_maximum_xor_brute_force(nums) # Output: 28 (5 ^ 25)

2. Optimal Solution using Trie

We can optimize this solution using a Trie data structure. The idea is to build a Trie where each bit of each number in the array is represented as a node in the Trie. Then, for each number, we traverse the Trie to find the number that maximizes the XOR value.

class TrieNode:
    def __init__(self):
        self.children = [None, None]  # 0 and 1

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):  # Iterate from MSB to LSB
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def find_max_xor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opposite_bit = 1 - bit
            if node.children[opposite_bit]:
                max_xor |= (1 << i) # set the i-th bit to 1
                node = node.children[opposite_bit]
            else:
                node = node.children[bit]
        return max_xor

def find_maximum_xor(nums):
    trie = Trie()
    for num in nums:
        trie.insert(num)

    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.find_max_xor(num))
    return max_xor

Example:

nums = [3, 10, 5, 25, 2, 8]
result = find_maximum_xor(nums) # Output: 28

Explanation:

Trie Construction: We insert each number into the Trie, representing its binary representation.
Finding Max XOR: For each number in nums, we traverse the Trie, trying to find a number that has the opposite bits as much as possible. This is because XORing opposite bits results in 1, which contributes to a larger XOR value.

3. Big(O) Run-time Analysis

Brute Force: O(n^2), where n is the number of elements in the nums array, due to the nested loops.
Trie: O(n), where n is the number of elements in the nums array. We iterate through each number once to insert into the Trie (O(1) to insert each number since the bit string length is fixed at 32), and then we iterate through each number again to find_max_xor, which takes O(1) as well since we are iterating at most 32 bits each time to traverse the trie.

4. Big(O) Space Usage Analysis

Brute Force: O(1), because it doesn't use any extra data structures.
Trie: O(n), where n is the number of elements in the nums array. In the worst-case scenario, where all numbers are distinct, the Trie will store each number's binary representation. The depth of trie is fixed at 32, but the number of nodes grows linearly with the input n.

5. Edge Cases and How to Handle Them

Empty Array: If the input array nums is empty, return 0.
Single Element Array: If the input array nums contains only one element, return 0.
All Elements are Zero: If all elements in nums are zero, return 0.
Negative Numbers: The problem statement specifies non-negative integers, but if negative numbers were allowed, we'd need to account for the sign bit in the Trie construction.

def find_maximum_xor_handling_edge_cases(nums):
    if not nums or len(nums) <= 1:
        return 0
    
    trie = Trie()
    for num in nums:
        trie.insert(num)

    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.find_max_xor(num))
    return max_xor

These edge cases are handled implicitly by the Trie solution because we iterate through all possible pairs of numbers, and handle empty/single element cases with an initial check.