📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 18
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

2021(10-12月) MachineLearningEng 博士 全职@google - 网上海投 - 技术电面  | 😐 Neutral 😣 Hard | Fail | 在职跳槽

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

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

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

刚面完,感觉基本挂了,这题没见过。面试的时候觉得肯定是用DP, 但是那个transition 方程就是想不出来。
  • Given a distance list(kilos), kilos= [1,1,10,30,20,40], and starting capacity
    您好!
    本帖隐藏的内容需要积分高于 188 才可浏览
    您当前积分为 0。
    使用VIP即刻解锁阅读权限或查看其他获取积分的方式
    游客,您好!
    本帖隐藏的内容需要积分高于 188 才可浏览
    您当前积分为 0。
    VIP即刻解锁阅读权限 或 查看其他获取积分的方式
    Unlock interview details and practice with AI
    Popular Interview Questions from Top Companies
    >

    这是我后来自己做的,不知道是不是最优解,请大牛指点。代码写的很乱,基本思想就是 dp[ii][j] = max(dp[i+1][j-1] + kilos[j], dp[i-1][j-1]).[i]
    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>
    复制代码
    [/i]

评分

参与人数 3大米 +6 收起 理由
葡萄的奶茶 + 4
Pasión + 1 很有用的信息!
madrid + 1 很有用的信息!

查看全部评分


上一篇:FB VO 至少我一点没觉得他家最近的bar降了
下一篇:罗盘卡拉特店面过经
推荐
lllxin37 2021-9-19 09:44:13 | 只看该作者
全局:
DFS => cache => top-down DP => bottom-up DP => 优化memory的 bottom-up DP 是比较可行的思路

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

使用道具 举报

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

使用道具 举报

推荐
lllxin37 2021-9-29 02:05:47 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
zn88358800 2021-9-18 15:34:40 | 只看该作者
全局:
大概写了一下
  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 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
24790955 2021-9-18 20:43:03 | 只看该作者
全局:
请教下题目细节, 看半天没有理解题目, 我们是要求可以走的最远距离吗? 限制是天数吗? 没有找到限制条件...
回复

使用道具 举报

🔗
 楼主| wenlongdaxia 2021-9-19 00:09:21 | 只看该作者
全局:
24790955 发表于 2021-9-18 05:43
请教下题目细节, 看半天没有理解题目, 我们是要求可以走的最远距离吗? 限制是天数吗? 没有找到限制条件...

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

使用道具 举报

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

使用道具 举报

全局:
zn88358800 发表于 2021-9-18 00:34
大概写了一下感觉跟加油站的题很像 不同的是 每一天要看上一天的 k-1 和 k+1
https://leetcode.com/playg ...

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

使用道具 举报

🔗
24790955 2021-9-19 09:28:40 | 只看该作者
全局:
本帖最后由 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))
复制代码

复制代码
回复

使用道具 举报

🔗
苏浅 2021-9-19 15:17:30 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

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

本版积分规则

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