MathWorks EDG Online Coding Assessment Interview Experience

Problem Statement The goal is to find the length of the longest subsequence in an array such that the bitwise XOR of any two adjacent elements in the subsequence equals a specific target value, $k

Problem Statement The goal is to find the length of the longest subsequence in an array such that the bitwise XOR of any two adjacent elements in the subsequence equals a specific target value, $k$.

Observation The condition $a_i \oplus a_{i+1} = k$ implies a direct relationship between adjacent elements. For any current value $x$ in the subsequence, the immediately preceding value must be $x \oplus k$. This effectively forms pairs or chains of alternating values.

Solution Approach This problem can be solved using Dynamic Programming with a hash map. Let dp[val] represent the maximum length of a valid subsequence ending with the value val. As we iterate through the array: 1. For the current number num, identify the required previous value: partner = num ^ k. 2. The length of the subsequence ending at num becomes 1 + dp[partner] (if the partner has not appeared yet, dp[partner] is 0). 3. Update the maximum length found so far.

C++ Implementation

cpp #include <iostream> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; int longestXORSubsequence(const vector<int>& arr, int k) { unordered_map<int, int> dp; int maxLength = 0; // Initialize to 0 to handle empty arrays for (int num : arr) { int partner = num ^ k; // Extend the sequence ending at 'partner' dp[num] = 1 + dp[partner]; maxLength = max(maxLength, dp[num]); }

**return** maxLength; } int main() { int n, k; if (cin >> n >> k) { vector<int> arr(n); for (int& x : arr) cin >> x; cout << longestXORSubsequence(arr, k) << endl; }

**return** 0; }