查看: 2028|回复: 16
收起左侧

狗狗新鲜电话面试新题+题解?求加米

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (57)
 
 
1% (1)    👎

2021(10-12月) MachineLearningEng 博士 全职@Google - 网上海投 - 技术电面  | Fail/Rej | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 wenlongdaxia 于 2021-9-17 23:30 编辑

刚面完,感觉基本挂了,这题没见过。面试的时候觉得肯定是用DP, 但是那个transition 方程就是想不出来。
  • Given a distance list(kilos), kilos= [1,1,10,30,20,40], and starting capacity k=1, you want to get the maximum distance following this rule: if you don't work on day i (you rest), you will gain 1 more capacity, otherwise, you will consume 1 capacity and gain the distance. If you have 0 capacity at the end of one day, you can not move, which means
    您好!
    本帖隐藏的内容需要积分高于 188 才可浏览
    您当前积分为 0。
    使用VIP即刻解锁阅读权限或查看其他获取积分的方式
    游客,您好!
    本帖隐藏的内容需要积分高于 188 才可浏览
    您当前积分为 0。
    VIP即刻解锁阅读权限查看其他获取积分的方式
    >

    这是我后来自己做的,不知道是不是最优解,请大牛指点。代码写的很乱,基本思想就是 dp[ii][j] = max(dp[i+1][j-1] + kilos[j], dp[i-1][j-1]).
    1. <div><i>                     def maximum_kilos(kilos, k):
    2. </i></div><div><i>  n = len(kilos)
    3. </i></div><div><i>  dp = [[None]*n for i in range(n+k+1)]
    4. </i></div><div><i>  # initialize the first column
    5. </i></div><div><i>  dp[k][0] = 0
    6. </i></div><div><i>  dp[k-1][0] = kilos[0]
    7. </i></div><div><i>  for j in range(1, n):
    8. </i></div><div><i>    for i in range(n+k-1,-1,-1):
    9. </i></div><div><i>      # print(i,j)
    10. </i></div><div><i>      if i==0:
    11. </i></div><div><i>        if dp[i+1][j-1] is not None:
    12. </i></div><div><i>          dp[i][j] = dp[i+1][j-1]+ kilos[j]
    13. </i></div><div><i>      else:
    14. </i></div><div><i>        if dp[i-1][j-1] is None and dp[i][j-1] is None and dp[i+1][j-1] is None:
    15. </i></div><div><i>          pass
    16. </i></div><div><i>        elif dp[i+1][j-1] is None and dp[i][j-1] is None:
    17. </i></div><div><i>          dp[i][j] = dp[i-1][j-1]
    18. </i></div><div><i>        elif dp[i-1][j-1] is None and dp[i][j-1] is None:
    19. </i></div><div><i>          dp[i][j] = dp[i+1][j-1] + kilos[j]
    20. </i></div><div><i>        elif dp[i+1][j-1] is None and dp[i][j-1] is not None:
    21. </i></div><div><i>          dp[i][j] = dp[i-1][j-1]
    22. </i></div><div><i>        elif dp[i-1][j-1] is None and dp[i][j-1] is not None:
    23. </i></div><div><i>          dp[i][j] = dp[i+1][j-1]+ kilos[j]
    24. </i></div><div><i>        else:
    25. </i></div><div><i>          dp[i][j] = max(dp[i+1][j-1]+kilos[j], dp[i-1][j-1])
    26. </i></div><div><i>  print('dp after operation: {}'.format(dp))
    27. </i></div><div><i>  res= max([ dp[i][n-1] for i in range(k+n) if dp[i][n-1] is not None])
    28. </i></div><div><i>  return res
    29. </i></div><div><i>kilos=[0,0,20,30,40,50]
    30. </i></div><div><i>k=1
    31. </i></div><div><i>res = maximum_kilos(kilos,k)</i></div>
    复制代码

评分

参与人数 2大米 +2 收起 理由
Pasión + 1 很有用的信息!
madrid + 1 很有用的信息!

查看全部评分


上一篇:FB VO 至少我一点没觉得他家最近的bar降了
下一篇:罗盘卡拉特店面过经
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   95% (2084)
 
 
4% (93)    👎
DFS => cache => top-down DP => bottom-up DP => 优化memory的 bottom-up DP 是比较可行的思路

没有必要直接最后一步做起。DP关键的是中间状态怎么表示,这道题的话是dp[i][k], 每天有2种选择。和上面帖子说的差不多。因为i +1 只会有 i访问到,所以memory usage可以降维度
回复

使用道具 举报

本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (20)
 
 
0% (0)    👎
Dp的题目button up不好想可以用recursion top down。

你每天都有两种选择,干活,不干活。
假设用rec(i, k)表示考虑第i天,并且有k个能量

如果i越界,base case返回
如果k=0只能休息,rec(i, k) = rec(i+1, k+1)

其他情况取两个选择的最大值
干活:rec(i+1, k-1) + kilo
不干活 rec(i+1, k+1)


写出recursion之后你会发现有重复计算的情况,可以依据i和k做cache。其实就是一个2D 的dp。

是背包问题的变种
回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   95% (2084)
 
 
4% (93)    👎
jinmu 发表于 2021-9-28 10:53
求教一下DFS+memo和top-down DP的核心区别是什么?

没有本质区别。不过要注意的是如果dfs + memo ==> bottom-up DP的话,要比较注意的是dp状态和状态转化方程。所以需要的话尽量在dfs + memo的时候定义好 clear 的DP 状态转化
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (58)
 
 
1% (1)    👎
大概写了一下
  1. def maxDistances(kilos, k):
  2.     m = k+len(kilos)
  3.     res = 0
  4.     dp = [[0 for i in range(m)] for j in range(len(kilos))]
  5.     dp[0][k-1] = kilos[0]
  6.     for i in range(1, len(kilos)):
  7.         for j in range(k+i+1):
  8.             if k < j:
  9.                 continue
  10.             if j == 0:
  11.                 dp[i][j] = dp[i-1][j+1]+kilos[i]
  12.             elif j == i+k:
  13.                 dp[i][j] = dp[i-1][j-1]
  14.             else:
  15.                 dp[i][j] = max(dp[i][j], dp[i-1][j-1], dp[i-1][j+1]+kilos[i])
  16.             res = max(res, dp[i][j])
  17.     for r in dp:
  18.         print(r)
  19.     return res

  20. kilos = [1,1,10,20,30,20,40]
  21. print(maxDistances(kilos, 1))
复制代码
感觉跟加油站的题很像 不同的是 每一天要看上一天的 k-1 和 k+1
https://leetcode.com/playground/PsYavY8H

评分

参与人数 1大米 +1 收起 理由
苏浅 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (50)
 
 
3% (2)    👎
请教下题目细节, 看半天没有理解题目, 我们是要求可以走的最远距离吗? 限制是天数吗? 没有找到限制条件...
回复

使用道具 举报

 楼主| wenlongdaxia 2021-9-19 00:09:21 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (57)
 
 
1% (1)    👎
24790955 发表于 2021-9-18 05:43
请教下题目细节, 看半天没有理解题目, 我们是要求可以走的最远距离吗? 限制是天数吗? 没有找到限制条件...

是的,就是要求最远距离,限制条件就是当你在某一天结束的时候,只有0 capacity,你只能选择休息来获得capacity.
回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   82% (5791)
 
 
17% (1201)    👎
本帖最后由 biomedicineman 于 2021-9-18 15:45 编辑

DFS + memo。
这里DFS的逻辑很简单,每天无非就两种选择。真实面试中或许这么写更现实?
memo后本质就是2D DP
  1.     static int max = 0;
  2.     static Integer[][] map;
  3.     public static int methoddfs(int[] kilos) {
  4.         int n = kilos.length;
  5.         map = new Integer[n + 1][n + 2]; // capacity starts from 1
  6.         dfs(kilos, 0, 1, 0);
  7.         return max;
  8.     }
  9.    
  10.     // dfs 记录每天开始的状态
  11.     private static void dfs(int[] kilos, int idx, int capacity, int dis) {     
  12.         // memo
  13.         if (map[idx][capacity] != null && map[idx][capacity] > dis) return;
  14.         map[idx][capacity] = dis;
  15.         
  16.         // stop
  17.         if (idx == kilos.length) {
  18.             max = Math.max(max, dis);
  19.             return;
  20.         }

  21.         // rest at idx
  22.         dfs(kilos, idx + 1, capacity + 1, dis);
  23.         // move
  24.         if (capacity > 0) {
  25.             dfs(kilos, idx + 1, capacity - 1, dis + kilos[idx]);
  26.         }
  27.     }
复制代码

补充内容 (2021-09-20 02:20 +8:00):
又写了下DP版本的
```
public static int method(int[] kilos) {
        int n = kilos.length;
        // dp[day][capacity], and dp is distance at the end of day.
        int[][] dp = new int[n][n + 1];

        // Initilize dp
        for (int i = 0; i < n; i++)
            Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0][2] = 0; // rest on day1
        dp[0][0] = kilos[0]; // move on day1
      
       //  for dp[j], if rest: dp[i - 1][j -1]  move: dp[i - 1][j + 1] + kilos
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= n; j++) {
                int move = (j == n) ? Integer.MIN_VALUE : dp[i - 1][j + 1] + kilos;
                int rest = (j == 0) ? Integer.MIN_VALUE : dp[i - 1][j - 1];
                dp[j] = Math.max(move, rest);
            }
        }
        
        int maxRes = 0;
        for (int j = 0; j <= n; j++) { //capacity
            maxRes = Math.max(maxRes, dp[n - 1][j]);
        }
        return maxRes;
    }
```
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   82% (5791)
 
 
17% (1201)    👎
zn88358800 发表于 2021-9-18 00:34
大概写了一下感觉跟加油站的题很像 不同的是 每一天要看上一天的 k-1 和 k+1
https://leetcode.com/playg ...

请教你说的加油站的题,具体是哪题?感觉有很多加油站的题。。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (50)
 
 
3% (2)    👎
本帖最后由 24790955 于 2021-9-19 09:33 编辑

做决策拿最优解的问题, 一般我倾向于用递归+memoization, 转移只用想状态随决策怎么变就行了, 再考虑下basecase,  贴上个人的参考代码:
  1. from functools import cache
  2. def max_distance(kilos: List[int], start_cap: int = 1) -> int:
  3.         @cache
  4.         def max_dist_sub(day_i: int, cap: int) -> int:
  5.                 if day_i == len(kilos):
  6.                         return 0
  7.                 if cap > 0:
  8.                         move_on = max_dist_sub(day_i+1, cap-1) + kilos[day_i]
  9.                 else:
  10.                         move_on = 0
  11.                 charge = max_dist_sub(day_i+1, cap+1)
  12.                 return max(charge, move_on)
  13.         return max_dist_sub(0, start_cap)
  14. if __name__ == '__main__':
  15.     kilos = [1,1,30,20,40]
  16.     start_cap = 1
  17.     print(max_distance(kilos, start_cap))
复制代码

复制代码
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (275)
 
 
6% (19)    👎
zn88358800 发表于 2021-9-18 00:34
大概写了一下感觉跟加油站的题很像 不同的是 每一天要看上一天的 k-1 和 k+1
https://leetcode.com/playg ...

楼主,这个 dp[j] = max(dp[j], dp[i-1][j-1], dp[i-1][j+1]+kilos), 为什么max 里面有个 dp[j]?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表