Its my first round of interview at AJIO and the round was problem solving/data structures.
I have been given a single question for the complete round and expectation was to discuss and find an optimized approach and then write a production ready code.
The question is:
Q: Given 3 buckets as sorted arrays of same size denoting price of apparels, find all combinations to buy one and only one from each bucket for a fixed amount sum (the combination sum should exactly be equal to the sum given).
Input arr = [[34,67,98], [1,2,7], [9,90,1454]], sum = 44
output = [[34,1,9]]
For this example there is only one combination which sums to given sum.
I was able to come up with a approach having time complexity O(n^2) and space complexity as O(n). But interviewer asked me to decrease the time complexity more. I was not able to come up with an approach. Any leads on this would be appreciated.
My Solution:
[{34,1,9},..] function ([{34,67,98},{1,2,7},{9,90,1454}]){
vector<int> result;
unordered_map<int, int> mp;
int min_element = INT_MAX;
// filling out all the 3rd array elements in the map and getting out the min element
for(int i = 0; i < n ; i++){
if (mp.find(arr[2][i]) != mp.end()){
mp[arr[2][i]] += 1;
} else {
mp[arr[2][i]] = 1;
}
// finding min element
min_element = min(min_element, arr[2][i]);
}
// iterating loop on first and second array
for(int i = 0;i < n;i++){
if (arr[0][j] > x){
break;
}
for(int j = 0; j < n;j++){
// adding elements from both of the iterations
diff = x - (arr[0][i] + arr[1][j])
// checking the diff exists in map if yes adding combination in result list
if (mp.find(diff) != mp.end()){
result.append([arr[0][i], arr[1][j], diff]);
} else {
// if diff in less than min value, no more combinations can be found after that.
if(diff < min_element){
break;
}
}
}
}
return result;
}If you find discrepancies in this solution as well, please state that as well.