亚麻OA 2021

2021年1月亚麻OA。
给定四种商品和预算求组合数。

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

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

楼主这种dp写法会超时吗 knapsack

1. public int getNumberOfOptions(int[] priceOfJeans, int[] priceOfShoes,
   
2.                                   int[] priceOfSkirts, int[] priceOfTops, int dollars) {
   
3.         //dp[i][j] represents the # of options for buying items from 0 to i with j dollars
   
4.         //
   
5.        // induction rule: dp[i][j] += dp[i - 1][j - priceOfI] for each priceOfI if j - priceOfI >= 0
   
6.         //base case: dp[i][0] = 0, dp[0][j] depends on how many priceOfItem0 is <= j
   
7.         //time: O(4 * dollars * len of price array)
   
8. 
   
9.         int[][] dp = new int[4][dollars + 1];
   
10.         for (int i = 0; i < 4; i++) {
    
11.             for (int j = 0; j <= dollars; j++) {
    
12.                 if (j == 0) {
    
13.                     dp[i][j] = 0;
    
14.                 }
    
15.                 else if (i == 0) {
    
16.                     for (int price: priceOfJeans){
    
17.                         if (price <= j) {
    
18.                             dp[i][j]++;
    
19.                         }
    
20.                     }
    
21.                 }
    
22.                 else if (i == 1) {
    
23.                     induction(dp, priceOfShoes, i, j);
    
24.                 }
    
25.                 else if (i == 2) {
    
26.                     induction(dp, priceOfSkirts, i, j);
    
27.                 }
    
28.                 else if (i == 3) {
    
29.                     induction(dp, priceOfTops, i, j);
    
30.                 }
    
31.             }
    
32.         }
    
33.         return dp[3][dollars];
    
34. 
    
35. 
    
36.     }
    
37.     private void induction(int[][] dp, int[] prices, int i, int j) {
    
38.         for (int price: prices) {
    
39.             if (j - price >= 0) {
    
40.                 dp[i][j] += dp[i - 1][j - price];
    
41.             }
    
42.         }
    
43.     }

复制代码

论坛匿名用户 发表于 2021-2-1 13:45
这个倒是有一点点可能？  能不能详细说一下你得mem是存什么？  就是key是什么，value是什么？  我当时没 ...

最basic的key 用 index + “，” + budget。 value用count。不过一般这种可以用dp iterative or dfs
+ memo的都可以用2d array来 represent。
我觉得要是纯dfs time complexity应该是b ^ n * (maxLen)
b = budget
n = 4 because given 4 array or given n array
maxLen = Max of size for 4 array

memo reduced to - b * n * maxLen

根据coin是s^n -> s*n
And
1335 Min job schedule dfs后就是n*n*d

你觉得呢？

bydstand 发表于 2021-2-12 07:02
budget的复杂度是10 ** 9

那也还是得走一遍吧？可能像很多题网上的都需要mod下10 ^ 9 + 7. 因为worst case 只要combination里有低于budget就要loop一边。别的有什么办法？楼主最开始的log 的我觉得不feasible。 因为是在建于把其他3个array lock position在binary search最后一个。那其实每一个数都需要lock住其他三个。

我怎么觉得这个题目是背包问题DP解决呢

o彩蝶寻梦o 发表于 2021-1-25 14:13
我怎么觉得这个题目是背包问题DP解决呢

DP会超时。 如果可能，稍微提供下具体思路得DP解法？  我用得两个物品价值得组合数，三个物品和价值得组合数，四个物品对应价值得组合数。  他得price range太大了，会TLE

只有这一题吗？

szhudl 发表于 2021-1-28 18:12
只有这一题吗？

第二题比较简单我没贴，大概是一个排序数连续得最长得数组。

DFS + Memo coin problem
Time: 4 * N where N = Max len of 4 array (reduced from brute force of N * 4 without memo)
Space: S where S = size of memo keys and dfs recursion stack

iterative DP 一时想不出来需要可能第二个for loop int coin改成这层的int【】。

是不是有两个题啊，多谢

dorothyzheng112 发表于 2021-1-30 08:40
楼主这种dp写法会超时吗 knapsack[mw_shl_code=java,true]public int getNumberOfOptions(int[] priceOfJea ...

感觉你的解法应该不会TLE，正在拜读

dorothyzheng112 发表于 2021-1-30 08:40
楼主这种dp写法会超时吗 knapsack[mw_shl_code=java,true]public int getNumberOfOptions(int[] priceOfJea ...

这个超时倒是小事，问题你内存就爆了啊。  dollor得取值范围是1 - 10 ^ 9。  你申请得有点多了。