Pergunta de entrevista da empresa Uber
Why do you choose Uber?
input a list of array [[1, 2, 3], [1], [1, 2]] return the list of array, each array is a combination of one element in each array.
[[1, 1, 1], [1, 1, 2], [2, 1, 1], [2, 1, 2], [3, 1, 1], [3, 1, 2]]
Followup: each array in the input list is an iterator, which can only be looped once.
Respostas da entrevista
>>> import itertools
>>> input = [[1, 2, 3], [1], [1, 2]]
>>> print [each for each in itertools.product(*input)]
const combinations = (m) => {
let res = [];
backtrack(m, 0, [], res);
return res;
};
const backtrack = (m, s, curr, res) => {
if (m.length === curr.length) {
res.push(curr.slice());
return res;
}
for (let i = s; i < m.length; i++) {
let row = m[i];
for (let el of row) {
curr.push(el);
backtrack(m, i + 1, curr, res);
curr.pop();
}
}
};
console.log(combinations([[1],[2,3,4],[5]]));
console.log(combinations([[1,2],[3,4]]));
console.log(combinations([[1, 2, 3], [1], [1, 2]]));