搜索
体验新版
<
一亩三分地»论坛 › 海外求职 › 海外面经 › 从 Unique Paths 的 Follow-ups 看动态规划的遍历和优化
123下一页
返回列表 发新帖
回复: 20
跳转到指定楼层
上一主题 下一主题
收起左侧

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

   
海外面经 码农类general 面试经验 google
🔗
jaychsu | 只看该作者 | 🔍更多面试经验 |倒序浏览
全局：

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 楼主人太好啦！很有帮助！谢谢！

查看全部评分

Coderust: Hacking the Coding Interview
回复

使用道具 举报

推荐
 楼主| 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 | 只看该作者
全局：
blactangeri 发表于 2018-5-30 09:01
lz真的🐂🍺

虽然看不懂，我就当称赞啦，多谢～
回复

使用道具 举报

🔗
kebugcheck 2018-5-30 15:23:59 | 只看该作者
全局：
jaychsu 发表于 2018-5-30 02:13
...

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

使用道具 举报

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

评分

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

查看全部评分

回复

使用道具 举报

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

本版积分规则

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