Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 249
Good morning! Here's your coding interview problem for today.

This problem was asked by Salesforce.

Given an array of integers, find the maximum XOR of any two elements.

Pull request:
Day249
Resolves #514 

Patch:
diff --git a/README.md b/README.md
index 2a243fd..12d5343 100644
--- a/README.md
+++ b/README.md
@@ -260,3 +260,4 @@ problems from
 * [Day 246](https://github.com/vaskoz/dailycodingproblem-go/issues/508)
 * [Day 247](https://github.com/vaskoz/dailycodingproblem-go/issues/510)
 * [Day 248](https://github.com/vaskoz/dailycodingproblem-go/issues/512)
+* [Day 249](https://github.com/vaskoz/dailycodingproblem-go/issues/514)
diff --git a/day249/problem.go b/day249/problem.go
new file mode 100644
index 0000000..e9b2051
--- /dev/null
+++ b/day249/problem.go
@@ -0,0 +1,88 @@
+package day249
+
+// MaxXorPairBrute find the maximum XOR of any two elements.
+// Runs in O(N^2) time and O(1) space.
+func MaxXorPairBrute(nums []int64) int64 {
+	max := int64(-1 << 63)
+	for i := 0; i < len(nums)-1; i++ {
+		for j := i + 1; j < len(nums); j++ {
+			if result := nums[i] ^ nums[j]; result > max {
+				max = result
+			}
+		}
+	}
+	return max
+}
+
+// MaxXorPairSort find the maximum XOR of any two elements.
+// Runs in O(N log N) time and O(N) space.
+func MaxXorPairSort(nums []int64) int64 {
+	copied := make([]int64, len(nums))
+	copy(copied, nums)
+	max := int64(-1 << 63)
+	for i := 1; i < len(nums); i++ {
+		if result := nums[i] ^ nums[i-1]; result > max {
+			max = result
+		}
+	}
+	return max
+}
+
+// BitTrie is a trie for binary data.
+type BitTrie struct {
+	Value int64
+	Next  [2]*BitTrie
+}
+
+// Insert a key in the BitTrie.
+func (bt *BitTrie) Insert(key int64) {
+	cur := bt
+	for i := 63; i >= 0; i-- {
+		var bit int
+		if key&(1<<uint(i)) != 0 {
+			bit = 1
+		}
+		if cur.Next[bit] == nil {
+			cur.Next[bit] = &BitTrie{}
+		}
+		cur = cur.Next[bit]
+	}
+	cur.Value = key
+}
+
+// HighestXorValue returns the highest xor-ed result of a
+// value that already exists in the tree.
+func (bt *BitTrie) HighestXorValue(key int64) int64 {
+	cur := bt
+	for i := 63; i >= 0; i-- {
+		var bit int
+		if key&(1<<uint(i)) == 0 {
+			if i != 63 {
+				bit = 1
+			}
+		} else {
+			if i == 63 {
+				bit = 1
+			}
+		}
+		if cur.Next[bit] == nil {
+			bit = 1 - bit
+		}
+		cur = cur.Next[bit]
+	}
+	return key ^ cur.Value
+}
+
+// MaxXorPairLinear runs in O(N) time and O(N) space for a trie.
+func MaxXorPairLinear(nums []int64) int64 {
+	max := int64(-1 << 63)
+	bt := &BitTrie{}
+	bt.Insert(nums[0])
+	for i := 1; i < len(nums); i++ {
+		if result := bt.HighestXorValue(nums[i]); result > max {
+			max = result
+		}
+		bt.Insert(nums[i])
+	}
+	return max
+}


Test patch:
diff --git a/day249/problem_test.go b/day249/problem_test.go
new file mode 100644
index 0000000..b609515
--- /dev/null
+++ b/day249/problem_test.go
@@ -0,0 +1,62 @@
+package day249
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	nums   []int64
+	maxXor int64
+}{
+	{[]int64{30, -20, 10, 100, 3300, 1001}, 3853},
+	{[]int64{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}, 15},
+}
+
+func TestMaxXorPairLinear(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxXorPairLinear(tc.nums); result != tc.maxXor {
+			t.Errorf("Expected %v, got %v", tc.maxXor, result)
+		}
+	}
+}
+
+func BenchmarkMaxXorPairLinear(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxXorPairLinear(tc.nums)
+		}
+	}
+}
+func TestMaxXorPairSort(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxXorPairSort(tc.nums); result != tc.maxXor {
+			t.Errorf("Expected %v, got %v", tc.maxXor, result)
+		}
+	}
+}
+
+func BenchmarkMaxXorPairSort(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxXorPairSort(tc.nums)
+		}
+	}
+}
+
+func TestMaxXorPairBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxXorPairBrute(tc.nums); result != tc.maxXor {
+			t.Errorf("Expected %v, got %v", tc.maxXor, result)
+		}
+	}
+}
+
+func BenchmarkMaxXorPairBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxXorPairBrute(tc.nums)
+		}
+	}
+}