回复: 20
跳转到指定楼层
上一主题 下一主题
收起左侧

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

   
全局:

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

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

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

x
不废话了,前因后果可以到前一篇  看。

⋯⋯好吧,多废话一句 :-p 觉得这篇文章有用的话,你可以做两件事给楼主一些正反馈:
  • 给代码所在 repo 加星 ()
  • 给这篇文章加米


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

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

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

followup1: 优化空间复杂度至 O(n)
followup2: 给定矩形里的三个点,判断是否存在遍历这三个点的路经
followup3: 给定矩形里的三个点,找到遍历这三个点的所有路径数量
followup4: 给定一个下界 (x == H),找到能经过给定下界的所有路径数量 (x >= H)
followup5: 起点和终点改成从左上到左下,每一步只能 ↓↘↙,求所有可能的路径数量
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
吧既然提到了,再多说一些好了。这篇贴子 () 里歪楼的点就在于用了 “见不得光” 这个词,这带有一种偷偷摸摸的暗示,但还真的没有什么偷偷摸摸的,结合场景来看好了。

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

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

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

评分

参与人数 66大米 +273 收起 理由
waynecy + 1 给你点个赞!
crayia + 1 good
Corolla17 + 1 给你点个赞!
jliu + 3 很有用的信息!
lemoncorn1123 + 1 很有用的信息!

查看全部评分


上一篇:领英店面
下一篇:蚂蚁金服电面
推荐
klepht 2018-10-21 13:49:40 | 只看该作者
全局:
请教一下楼主:
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 | 只看该作者
全局:
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 | 只看该作者
全局:
变斜体了,中间 \[i\] 忘记 escape 233
回复

使用道具 举报

🔗
kebugcheck 2018-5-30 07:42:31 | 只看该作者
全局:
楼主想问一下follow up2的test case,为什么(3, 3, [[1, 0], [2, 1], [1, 2]])这一组返回False? 这一组应该是可行的吧?

评分

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

查看全部评分

回复

使用道具 举报

🔗
blactangeri 2018-5-30 09:01:03 | 只看该作者
全局:
lz真的🐂🍺
回复

使用道具 举报

🔗
 楼主| jaychsu 2018-5-30 10:13:39 | 只看该作者
全局:
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]])

  1. """
  2. y 0 1 2
  3. x
  4. 0  S   E
  5. 1  A   C
  6. 2    B
  7. """
复制代码


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

评分

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

查看全部评分

回复

使用道具 举报

🔗
 楼主| jaychsu 2018-5-30 10:15:42 | 只看该作者
全局:

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

使用道具 举报

🔗
kebugcheck 2018-5-30 15:23:59 | 只看该作者
全局:

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

使用道具 举报

🔗
tommyttang 2018-5-31 07:37:28 | 只看该作者
全局:
谢谢楼主分享了!DP这个东西真的是虽然核心都是reduction,但每个人都有不同的approach,楼主写得很有启发性!

评分

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

查看全部评分

回复

使用道具 举报

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

本版积分规则

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