DSA interview question

Maximum XOR With an Element From an Array (Restricted by Upper Bound)

Hard · Data structures · Topics: trie, bit manipulation, offline queries

The problem

You're building a secure key-derivation service for a distributed systems team. Each query gives you a target value xi and a constraint mi — you need to find the maximum XOR of xi with any value from nums that is less than or equal to mi. If no such value exists (all elements in nums exceed mi), return -1 for that query. This mirrors LeetCode 1707 ("Maximum XOR With an Element From Array") — a classic offline queries + Trie problem.

(Note: the original LeetCode version constrains by an upper bound mi, not a range [li, ri] — that range-restricted version is a different, harder problem requiring persistent tries or merge-sort-tree-of-tries. I'll solve the standard upper-bound version here and call out the range variant as a follow-up.)

Example: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]] → for query [3,1] (xi=3, mi=1), valid elements are {0,1}, max XOR with 3 is 3^0=3 or 3^1=2, so answer = 3.

Function signature

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries);
// queries[i] = {xi, mi}

Test cases

`nums`	`queries`	Output	Explanation
`[0,1,2,3,4]`	`[[3,1],[1,3],[5,6]]`	`[3,3,7]`	Query 1: elements ≤1 → {0,1}; max(3^0,3^1)=3. Query 3: all elements ≤6, max XOR with 5 is 5^2=7
`[5,2,4,6,6,3]`	`[[12,4],[8,1],[6,3]]`	`[15,-1,5]`	Query 2: elements ≤1 → none exist → -1
`[1]`	`[[1,0]]`	`[-1]`	No elements ≤ 0 exist
`[0]`	`[[0,0]]`	`[0]`	Single match, 0^0=0
`[1,2,3]`	`[[0,3]]`	`[3]`	All elements valid, max XOR with 0 is just the max value present (3)

How interviewers phrase it

"For each query (xi, mi), find the max XOR of xi with any element in nums that's <= mi. Return -1 if none qualify."
This is LeetCode 1707. The "range [li, ri]" framing you mentioned is actually a harder variant — be ready to clarify which version is being asked, since the standard offline-Trie technique only works cleanly for the upper-bound version.
Interviewers may first ask "max XOR of two numbers in an array" (LeetCode 421, no queries) as a warm-up before this query-based extension.

Clarifying questions to ask

Is the constraint per query an upper bound mi (element ≤ mi), or an index range [li, ri] (elements between specific array positions)? This fundamentally changes the approach:
- Upper bound (mi): solvable with offline queries sorted by mi + incremental Trie insertion — O((n+q) * log(max_val)).
- Index range ([li, ri]): requires persistent Trie (a Trie snapshot at each prefix index, allowing you to query "Trie state at index r minus Trie state at index l-1") — significantly more complex, O((n+q) * log(max_val)) but with much higher constant factor and implementation complexity.
Can queries be processed offline (i.e., do I know all queries upfront, or must I answer them online/one-at-a-time as they arrive)? (Offline sorting is the standard trick for the upper-bound version.)
What's the maximum value in nums / queries? (Determines how many bits the Trie needs — typically 30 bits for values up to 1e9, or fewer if specified.)
Should I assume nums and query values are non-negative integers?

Follow-ups to expect

"Why sort both nums and queries — what does that buy you?"
"Walk through how the Trie is used to find max XOR efficiently, bit by bit."
"What if the problem ACTUALLY wants index range [li, ri] instead of a value upper bound — how would you adapt?"
"What's the complexity if you did this naively without a Trie — comparing every query against every valid element?"
"Can you solve 'Maximum XOR of two elements in an array' (no queries) using the same Trie technique?"
"How would memory usage scale with a Trie here, and how would you optimize it?"

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