Summary
I encountered a dynamic programming problem involving XOR subsequences during my Mathworks EDG interview, and this post details the problem and my C++ solution.
Full Experience
During my interview for the Engineering Development Group (EDG) at Mathworks, I was presented with a challenging coding problem. The core of the problem required me to identify the longest subsequence from a given array where, for any two consecutive elements a and b in the subsequence, their bitwise XOR operation (a ^ b) resulted in a specific target value k. My approach involved recognizing the pattern implied by the XOR condition and applying dynamic programming. I realized that if a ^ b = k, then a ^ k = b. This insight allowed me to efficiently determine the required preceding element for any number in the subsequence. I used a hash map to store the maximum length of subsequences ending at each number, allowing for quick lookups when extending subsequences.
Interview Questions (1)
Given an array of integers arr and a target integer k, find the length of the longest subsequence such that for any two consecutive elements a and b in the subsequence, a ^ b = k.
Observation from the problem: "From the question we can observe that.. So, the subsequence is nothing but alternate values.. So, we need to find the pairs of them.. So, Suppose we are at a value x, then ending at x, max length of subsequence can be defined as 1 + dp[x ^ target] ;"