Amazon On-Site Interview

  • Given a list of items that has two attributes: one is the id of current item and the other one is the cost of the item. You need to find out all the combinations(at least 2 items) whose total cost is less than or equal to an input value maxCost.

Sample:

  • items: [(1, $20), (2, $30), (3, $50), (4, $40)]
  • maxCost: $100
  • return: [[1, 2, 3], [2, 3], [1, 3], [3, 4], [1, 2, 4], [2, 4], [1, 4], [1, 2]]

Solution(You can use DP as well):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(vector<item>& items, vector<int>& path, vector<vector<int>>& res, int maxCost, int start) {
if (items[start].cost <= maxCost) {
path.push_back(items[start]);
if (path.size() >= 2) res.push_back(path);
if (start != items.size() - 1) dfs(items, path, res, maxCost - items[start], start + 1);
path.pop_bakc();
}
if (start != items.size() - 1) dfs(items, path, res, maxCost, start + 1);
}
vector<vector<int>> getPickCombs(vector<item> items, int maxCost) {
int n = items.size();
if (n == 0) return {{}};
vector<vector<int>> res;
vectro<int> path;
dfs(items, path, res, maxCost, 0);
return items;
}
  • Given a map that maps an product(product ID) to its images. Since there are some images are being mapped by multiple products, the product information might be wrong. You need to de-duplicate these products who have the same images and remain only one lowest alphabet order ID.

Sample:

  • Maps:
1
2
3
A ---> {img1, img2},
B ---> {img2, img3},
C ---> {img3, img4}
  • Returns: [A], as A has the same image with B and B also has a same image with C. Based on description, we have to remove B, C.
  • Given a word like “apple” and an map that has one character to one character map indicating available character replacement. You need to return all possible string after replacing some character(at least one) in given word.

Sample:

  • word: “apple”
  • Maps:
1
2
a ---> @
e ---> 3
  • Returns: [@pple, @ppl3, appl3, @pple]