查看: 11544|回复: 20
收起左侧

从 Unique Paths 的 Follow-ups 看动态规划的遍历和优化

    |只看干货 |美国面经, 码农类general, 面试经验, google

分享帖子到朋友圈
本楼: 👍   100% (7)
 
 
0% (0)   👎
全局: 👍   98% (534)
 
 
1% (8)    👎

2018(1-3月) 码农类General 本科 其他@Google - Other - 其他  | Other | 在职跳槽

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

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

x
不废话了,前因后果可以到前一篇 扫地机器人,Robot API、实现及总结 看。

⋯⋯好吧,多废话一句 :-p 觉得这篇文章有用的话,你可以做两件事给楼主一些正反馈:


Unique Paths 是我入门动态规划的第一题,后来做面经做完这些 Follow-ups 才感觉自己真正懂了动态规划,特别是遍历顺序和空间优化。这篇文章总结 Unique Paths 的 Follow-ups,题目如下,从 地里的面经/glassdoor 搜集来之后,我又重新理了一遍语序。

给定一个矩形的宽和长,求所有可能的路径数量

Rules:
1. 从左上角走到右上角
2. 要求每一步只能向正右、右上或右下走,即 →↗↘

followup1: 优化空间复杂度至 O(n)
followup2: 给定矩形里的三个点,判断是否存在遍历这三个点的路经
followup3: 给定矩形里的三个点,找到遍历这三个点的所有路径数量
followup4: 给定一个下界 (x == H),找到能经过给定下界的所有路径数量 (x >= H)
followup5: 起点和终点改成从左上到左下,每一步只能 ↓↘↙,求所有可能的路径数量

在往下看之前:


从左上角走到右上角,要求每一步只能向正右、右上或右下走,即 →↗↘


followup1: 优化空间复杂度至 O(n)
  • 代码:L51-L86, https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L51-L86
  • 可以把 dp[m][n] 简化成 dp[m],但是如果直接往 dp[x] 上加,会挂。挂的原因是 dp 需要加上 dp[i + 1] 和 dp[i - 1],但是当到下一格的时候 dp[x] (x == i + 1),dp[x] 需要往回加 dp,而 dp 已经事先加过 dp[x] 了,所以 dp[x] 又会加一次自己原来的值,所以出错
  • 解法就是在进每个格子之后,先用个变量保存 dp[x] 的值,然后再 modify dp[x],等到下一格 dp[x + 1] 要往回加的时候,就去加这个临时变量
  • 也可以用滚动数组弄成 dp[m][2]


followup2: 给定矩形里的三个点,判断是否存在遍历这三个点的路经



懒癌发作,越到后面越懒得打,希望我 “见不得光” 的代码能给需要的人一点帮助 233

好吧既然提到了,再多说一些好了。这篇贴子 (http://www.1point3acres.com/bbs/thread-421347-1-1.html) 里歪楼的点就在于用了 “见不得光” 这个词,这带有一种偷偷摸摸的暗示,但还真的没有什么偷偷摸摸的,结合场景来看好了。

面试官喜欢的套路各种各样,有的不喜欢废话,多废话一句就是扣分项,有的希望你多说,少说了就是难相处,有的希望你多用 build-in 方法,说是考察你对语言的熟悉程度,有的希望你能自己实现 build-in 方法,不自己实现就是扣分项。

所以才说面试一定要沟通,而且很大程度靠运气,事前真是猜不透,在这种不确定的情况,希望能把握确定的东西是人性。以致于去面试当然希望能碰到自己熟悉的东西,熟悉的东西才能放心换着套路玩,于是形成刷题这种风气吧。

如果被问有没有做过题,不用见不得光,但你得知道,如果是程序以外的问题,你可以不用回答非黑即白的答案。

评分

参与人数 66大米 +273 收起 理由
waynecy + 1 给你点个赞!
crayia + 1 good
Corolla17 + 1 给你点个赞!
jliu + 3 很有用的信息!
lemoncorn1123 + 1 很有用的信息!
wocaole + 2 忍不住给你点个赞,面经很有用了。
aini97886 + 2 欢迎分享你知道的情况,会给更多积分奖励!
Eric0009 + 3 给你点个赞!

查看全部评分


上一篇:领英店面
下一篇:蚂蚁金服电面
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
请教一下楼主:
https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L168
这里的i在什么时候会大于等于k呢?

评分

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

查看全部评分

回复

使用道具 举报

 楼主| jaychsu 2018-5-31 07:15:06 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (534)
 
 
1% (8)    👎
kebugcheck 发表于 2018-5-30 15:23
啊我理解错题意了,我以为可以从这三个点中任意一个点出发,其实还是从左上角走到右上角,但要经过三个点 ...

私底下练习的时候,多误会题意是好事,代表你能多发现其他可能的变种题,和其他 edge case,也许你可以试一下如果题目变成你说的这样,你该怎么解呀。但是如果在面试中,千万记得,coding 前先 go through 几个你想的 example,确保你的理解是题目预期的,也能帮助你发现 edge case。

希望对你有帮助,祝顺利:)

评分

参与人数 1大米 +3 收起 理由
kebugcheck + 3 楼主人太好啦!很有帮助!谢谢!

查看全部评分

回复

使用道具 举报

 楼主| jaychsu 2018-5-9 12:33:36 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (534)
 
 
1% (8)    👎
变斜体了,中间 \[i\] 忘记 escape 233
回复

使用道具 举报

头像被屏蔽
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (16)
 
 
5% (1)    👎
楼主想问一下follow up2的test case,为什么(3, 3, [[1, 0], [2, 1], [1, 2]])这一组返回False? 这一组应该是可行的吧?

评分

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

查看全部评分

回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (137)
 
 
4% (6)    👎
lz真的🐂🍺
回复

使用道具 举报

 楼主| jaychsu 2018-5-30 10:13:39 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (534)
 
 
1% (8)    👎
kebugcheck 发表于 2018-5-30 07:42
楼主想问一下follow up2的test case,为什么(3, 3, [[1, 0], [2, 1], [1, 2]])这一组返回False? 这一组应 ...
(3, 3, [[1, 0], [2, 1], [1, 2]])


[Python] 纯文本查看 复制代码
"""
 y 0 1 2
x
0  S   E
1  A   C
2    B
"""


从 S 走不到 A,从 C 也走不到 E 呀。不过因为跑的测试都是小规模的,大规模没测过,如果有发现 fail 的 case 一定要让我知道:)

评分

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

查看全部评分

回复

使用道具 举报

 楼主| jaychsu 2018-5-30 10:15:42 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (534)
 
 
1% (8)    👎

虽然看不懂,我就当称赞啦,多谢~
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (16)
 
 
5% (1)    👎

啊我理解错题意了,我以为可以从这三个点中任意一个点出发,其实还是从左上角走到右上角,但要经过三个点对吧?所以path一共是要经过5个点,要计算四次斜率对吧?很谢谢楼主!我不太懂python代码没看太懂!
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (10)
 
 
0% (0)    👎
谢谢楼主分享了!DP这个东西真的是虽然核心都是reduction,但每个人都有不同的approach,楼主写得很有启发性!

评分

参与人数 1大米 +5 收起 理由
jaychsu + 5 是的,主要还是思路。很高兴你喜欢

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

X 关闭
>
快速回复 返回顶部 返回列表