I appeared in Google's Online Challenge - Coding on 22nd August, 2020. It was conducted on HackerEarth.

Number of questions : 2
Difficulty level : medium-hard
Time : 60 minutes

Question 1.
Subsequence

This problem is similar to LCS expect here we need to find the length of Longest Common Subsequence between 2 arrays A and B, instead of strings.

So first, I tried to solve this problem using dynamic-programming as given below :

int min_number_of_elements_dp(int n, vector<int> &A, int m, vector<int> &B) {

	vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
	for(int i = n; i >= 0; i--) {
		for(int j = m; j >= 0; j--) {
			if(i == n || j == m)
				dp[i][j] = 0;
			else {
				if(A[i] == B[j])
					dp[i][j] = 1 + dp[i + 1][j + 1];
				else
					dp[i][j] = max(dp[i][j + 1], dp[i + 1][j]);
			}
		}
	}
	return n - dp[0][0];
}

Here dp[i][j] represents length of LCS between arrays A[i: ] and B[j: ].
Time and Space complexity : O(n^2).
This above solution was giving the Memory Limit Exceeded(MLE) error, though we can reduced the space complexity to O(n) as in each iteration we only need 2 rows of dp[][] table, but I think we still cannot reduced the time complexity from O(n^2) if we go with this approach.

So, after reducing the space complexity to linear it would still give the TLE error, as the constraints are strict and we have to solve this problem in less than O(n^2) time.

Better Approach: O(nlogn)
We can think this problem as finding the Longest Increasing Subsequence (LIS) in array B[ ].

Only consider elements of array B[] which are present in array A[], and map each element of array A[] to the index where it is located.
Then we can construct the LIS array subseq[ ] using binary-search which consists the indices in increasing order.
And finally the min-number of elements to be added in array B[] would be n - len(LIS).

int min_number_of_elements(int n, vector<int> &A, int m, vector<int> &B) {

	unordered_map<int, int> map;
	for(int i = 0; i < A.size(); i++) {
		map.insert({A[i], i});
	}

	vector<int> subseq;
	int l = 0, r = -1;
	for(int i = 0; i < m; i++) {
        // if element B[i] is in array A[]
		if(map.count(B[i])) { 
			int e = map[B[i]];
			
			while(l <= r) {
				int m = l + (r - l)/2;

				if(subseq[m] < e)
					l = m + 1;
				else
					r = m - 1;
			}
			if(r + 1 < subseq.size()) 
				subseq[r + 1] = e;    // found better element 'e' for pos r + 1
			else
				subseq.pb(e);         // extend the existing subseq

			l = 0, r = subseq.size() - 1;
		}
	}

	return n - subseq.size();
}

Question 2:
The Kth Maximum

We can solve the problem of finding XOR(i, j) using dp.
we can calculate XOR(i, j) as,
XOR[i][j] = XOR[i-1][j] ^ XOR[i][j-1] ^ XOR[i-1][j-1] ^ mat[i][j].

Explanation :
While calculating XOR[i-1][j] ^ XOR[i][j-1] in above expr, XOR[i-1][j-1] has been included twice thus cancels out each other(a ^ a = 0), so we have to xor XOR[i-1][j-1] one more time in expr, to get the correct value of XOR[i][j].

After this, we can find the Kth maximum element using sorting or using a min-heap of size k and than pick the smallest pair(i, j) for which XOR(i, j) is equal to Kth max-element.

void kth_max(int n, int m, vector<vector<int>> &mat, int k) {
	
	vector<vector<int>> XOR(n, vector<int>(m, 1));
	vector<int> vals;
	unordered_map<int, pair<int, int>> map;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			int a = i - 1 >= 0 ? XOR[i-1][j] : 0;
			int b = j - 1 >= 0 ? XOR[i][j-1] : 0;
			int c = (i - 1 >= 0 && j - 1 >= 0) ? XOR[i-1][j-1] : 0;
			XOR[i][j] = mat[i][j] ^ a ^ b ^ c;

			vals.pb(XOR[i][j]);
			if(!map.count(XOR[i][j])) 
				map.insert({XOR[i][j], {i, j}});
		}
	}

	sort(vals.begin(), vals.end());
	int kth_max_e = vals[n*m - k];

	// 1-based indexing
	cout << map[kth_max_e].first + 1 << " " << map[kth_max_e].second + 1 << "\n"; 
}

These were the questions that I got in my Google's OA.

I couldn't think of an O(nlogn) approach for the 1st problem in OA, and for the 2nd problem all hidden testcases passed but a few sample cases gave the Wrong Output and I couldn't fix the bug in my code, so I guess I totally bombed this OA.

Learnings :

1. Always code the solution keeping problem Constraints in mind.
2. Try to keep the logic simple n straight with concise code.