Uber Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
One of the most efficient solutions to the above problem could be to use an
1. unordered set in c++.
2. push all the array elements into it.
3. now, one by one pick the elements from the array and calculate the difference between the total sum and the array element and find for the result in the set, if found push the set into the vector, and repeat this step till all the array elements have been processed and then, finally return the vector, which will be you final solution.
Thanks
Probably not as compact and elegant as the solutions above, but it does it job.
const getSequences = (list, sum, sequences={}, curSequence=[], index=0) => {
for (; index < list.length; index++) {
const seqSum = curSequence.reduce((s, value) => {
return s + value;
}, 0);
if (seqSum + list[index] > sum) {
continue;
}
if (seqSum + list[index] == sum) {
const matchSeq = [...curSequence, list[index]];
const hashCode = matchSeq.reduce((s, value) => {
return s + ',' + value;
}, '');
if (!(hashCode in sequences)) {
sequences[hashCode] = matchSeq;
}
continue;
}
const newSequences = getSequences(list, sum, sequences, [...curSequence, list[index]], index+1);
for (let [hashCode, sequence] of Object.entries(newSequences)) {
sequences[hashCode] = sequence;
}
}
return sequences;
};
Probably not as compact and elegant as the solutions above, but it does it job.
const getSequences = (list, sum, sequences={}, curSequence=[], index=0) => {
for (; index < list.length; index++) {
const seqSum = curSequence.reduce((s, value) => {
return s + value;
}, 0);
if (seqSum + list[index] > sum) {
continue;
}
if (seqSum + list[index] == sum) {
const matchSeq = [...curSequence, list[index]];
const hashCode = matchSeq.reduce((s, value) => {
return s + ',' + value;
}, '');
if (!(hashCode in sequences)) {
sequences[hashCode] = matchSeq;
}
continue;
}
const newSequences = getSequences(list, sum, sequences, [...curSequence, list[index]], index+1);
for (let [hashCode, sequence] of Object.entries(newSequences)) {
sequences[hashCode] = sequence;
}
}
return sequences;
};
- Anonymous May 14, 2019