DSA interview question

Maximum XOR of Two Numbers in an Array

Hard · Data structures · Topics: trie, bit manipulation

The problem

You're building a hash bucket distribution checker for a distributed cache system. To minimize collisions, your team wants to verify the maximum possible XOR between any two cache key identifiers in a given batch — a high max-XOR value is a good signal of well-distributed bits across the bucket space. Given an integer array nums, find the maximum result of nums[i] XOR nums[j] for any valid i != j.

Example: nums = [3,10,5,25,2,8] → maximum XOR is 5 XOR 25 = 28.

Function signature

int findMaximumXOR(vector<int>& nums);

Test cases

Input `nums`	Output	Explanation
`[3,10,5,25,2,8]`	`28`	`5 (00101) XOR 25 (11001) = 28 (11100)`
`[0]`	`0`	Only one element — no valid pair, conventionally returns 0
`[2,4]`	`6`	`2 (010) XOR 4 (100) = 6 (110)`
`[8,10,2]`	`10`	`8 (1000) XOR 2 (0010) = 10 (1010)`
`[14,70,53,83,49,91,36,80,92,51,66,70]`	`127`	Larger test case from LeetCode's examples
`[0,0]`	`0`	Identical elements XOR to 0
`[1,2,3]`	`3`	`1 XOR 2 = 3`, the maximum among all pairs

How interviewers phrase it

"Given an array of integers, find the maximum XOR of any two elements."
"What's the best way to pick two numbers from this array to maximize their bitwise XOR?"
This is LeetCode 421 — often the warm-up version before the query-based extension (LeetCode 1707, "Maximum XOR With an Element From Array," which you covered earlier) — interviewers frequently chain these two together in the same session.

Clarifying questions to ask

Can i == j (i.e., can I XOR an element with itself)? (Typically no — needs i != j, though XOR-ing identical values just gives 0 anyway, so it rarely changes the answer, but still good to confirm logically.)
What's the range of values in nums? (Determines how many bits the Trie needs to consider — e.g., up to 2^31 - 1 needs 31 bits.)
Can nums contain duplicates or negative numbers? (Standard LeetCode version assumes non-negative; clarify if negatives are in scope, since bitwise XOR semantics with two's complement negatives need extra care.)
What should be returned for a single-element or empty array? (Convention: 0, since no valid pair exists — confirm with interviewer.)

Follow-ups to expect

"What's the brute force approach, and why is it insufficient?"
"Walk through why the Trie approach is O(n * bitLength) instead of O(n²).
"Can you solve this without a Trie, using a hash-set-based bit-by-bit greedy approach instead?"
"How does this relate to the query-based version you solved earlier (Max XOR With an Element From Array)?"
"What if you needed the actual PAIR (i, j) achieving the max XOR, not just the value?"
"How would you extend this to find the maximum XOR of THREE numbers, not two?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview