Amazon OA 面经

今天做了亚麻的OA，第一道题网上也有，但是没有明确的解法：A customer wants to buy a pair of jeans, a pair of shoes, a skirt, and a top but has a limited budget in dollars. Given different pricing options for each product, determine how many options our customer has to buy 1 of each product. You cannot spend more money than the budgeted amount.
Example
priceOfJeans = [2, 3]
priceOfShoes = [4]
priceOfSkirts = [2, 3]
pric

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

izes of the four price arrays

我做了两个解法，第一个是用DFS，然后二维数组 memoization： visited[dollars][4], dollars是customer手里的钱。可是这样有bad allocation的错误。估计是dollars可以很大导致了space limit exceeded。

后来又参考了 454. 4Sum II， 可是因为这个是小于等于dollars都可以，所以不能达到O(n^2)，会超时。

所以大家知不知道这道题的正确解法？

谢谢

ThetaSigma14 发表于 2021-5-4 06:27
可不可以precomute所有组合 然后再loop through呢
def possible_combinations2(items, budget):
    all_ ...

这样不行吧，会超时

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

用DP做可以吗？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

yunliang2014 发表于 2021-5-4 09:20
用DP做可以吗？

public static int getNumberOfOptions(int[] a, int[] b, int[] c, int[] d, int k) {
...

和 DFS一样， k会很大，这样超过空间要求

想问下楼主第二题是什么？已加米，多谢

hakunamatatal 发表于 2021-5-5 05:12
想问下楼主第二题是什么？已加米，多谢

|*|***|*****|**|

| 之间contain *

*的个数是东西的数量。给一个range，问里面有contain 多少个东西

lilianFJB 发表于 2021-5-5 05:18
|*|***|*****|**|

| 之间contain *

好的，多谢楼主。祝面试顺利~

另外还想问下，我看你标了状态，已经有update了么？好快啊