Round 1
Questions:
Problem 1 - Hard
Given an array of size n. Find number of unique triplets xors that can be generated with elements from the array. For a triplet i <= j <= k.
1 <= n <= 2 * 10 ^ 5
Example:
[9,10,11]
Output - 4
8 - 9 ^ 10 ^ 11
9 - 9 ^ 10 ^ 10
10 - 9 ^ 9 ^ 10
11 - 9 ^ 9 ^ 11
It can be proved that no unique xors apart from this can be generated with any combination of triplet.
Candidate's Approach:
Candidate's Approach
I did solve the problem but with O(n ^ 2) by precomputing xor pairs. Then doing xor of pair with array elements. As I was not able to find an optimal approach.
10/14 test cases passed; others failed due to TLE.
Interviewer's Feedback
No feedback provided.
Problem 2 - Hard
Given an integer k and m. Find number positive integers less than or equal to k having sum of their digits divisible by integer m.
Inputs:
1 <= k <= 10 ^ 15
1 <= m <= 300
Example:
k = 30, m = 4
Answer is 6.
Candidate's Approach:
Candidate's Approach
I was able to solve this after a lot of trials using digit DP.
Interviewer's Feedback
No feedback provided.
Problem 3 - Hard
Given 2 arrays: the first consists of the price of stocks at the current stage, and the second with prices of them in the future. You will also be given an integer savings.
Return the maximum number of profit that can be achieved with the savings amount.
Example:
Savings - 250
current - [157, 78, 200, 97, 45]
future - [170, 180, 234, 86, 78]
Answer is:
- 157, 78
- 170, 180
- 115
- 78, 97, 45
- 180, 86, 78
- 124
- 78, 45
- 180, 78
- 135
So maximum achievable profit is 135.
Candidate's Approach:
Candidate's Approach
Variation of fractional knapsack. Instead of adding the entire profit, I added future[i] - current[i] to the answer. I was able to solve this problem.
Interviewer's Feedback
No feedback provided.
What are my chances of getting shortlisted for machine coding round?