123
返回列表 发新帖
楼主: tommy1122337
跳转到指定楼层
上一主题 下一主题
收起左侧

Google Onsite

🔗
linjin 2016-11-26 14:46:33 | 只看该作者
全局:
zzgzzm 发表于 2016-11-14 07:21
第二题:用DFS是不是这个意思. 当用DFS迭代时同时要传当前的方向,然后若在同一方向的位置无障碍物时就只沿 ...

每个点有四个方向。简单的把visited过的点设成1是不够的。 比如点A从方向0进入, 在dfs中有可能要从方向1进入。
回复

使用道具 举报

🔗
zzgzzm 2016-11-26 14:59:20 | 只看该作者
全局:
sunnyroom 发表于 2016-11-26 11:49
能解释一下概率是怎么计算的吗?
碰见概率就蒙蔽

用数学来说比较清楚:
设硬币X(i)=1的概率为p(i), X(i)=0的概率为1-p(i)。 用E(n,k)表示前n个X(i)中恰好k个X(i)=1的事件,那么求P(E(n,k))实际上就是用全概公式来DP求解。
因为显然事件X(n)=1与X(n)=0是互斥的,所以
P(E(n,k)) = P(E(n,k) and X(n)=1) + P(E(n,k) and X(n)=0)
= P(X(n)=1)*P(E(n,k) with condition X(n)=1) + P(X(n)=0)*P(E(n,k) with condition X(n)=0)
= p(n)*P(E(n-1,k-1)) + (1-p(n))*P(E(n-1,k))
其中p(n)给定已知,这样DP的转移方程就有了。关键是要注意到事件“E(n,k) with condition X(n)=1” 就是 E(n-1,k-1) 以及 “E(n,k) with condition X(n)=0”就是E(n-1,k)。
还有条件概率定义就是对任意事件A, B有:P(A with condition B) = P(A and B)/P(B).

补充内容 (2016-11-26 15:03):
全概公式:P(E) = P(A)*P(E with condition A) + (1-P(A))*P(E with condition not A), 其中E, A为任意事件。
回复

使用道具 举报

🔗
zzgzzm 2016-11-26 15:16:11 | 只看该作者
全局:
linjin 发表于 2016-11-26 14:46
每个点有四个方向。简单的把visited过的点设成1是不够的。 比如点A从方向0进入, 在dfs中有可能要从方向1 ...

感谢指正,你说的没错。若某个cell是在十字交叉路口的话有可能需要经过2次,但方向不同(sliding path的特性)。我第一次遗漏了这一点,需要分别记录某个cell是否横向和纵向走过。我在另一个面经中看到同样的题(sliding maze),同时要求找拐弯最少的路径。我写了个逻辑更简单BFS的,每次只将拐弯的cell入队(只visit一次),直行中的cell不必入队,我觉得只有拐点cell重要应该是sliding maze问题的关键了。
http://www.1point3acres.com/bbs/ ... 038&ptid=211354
回复

使用道具 举报

🔗
luofeidream 2016-11-27 02:21:36 | 只看该作者
全局:
zzgzzm 发表于 2016-11-14 05:20
第三轮:LZ已经写了recusive的,这和DP差不多了:时间O(nk),空间O(k)

第8行似乎写错了,应该是cur[0] = prev[0] * (1 - c[nn - 1])吧
回复

使用道具 举报

🔗
sunnyroom 2016-11-27 03:34:29 | 只看该作者
全局:
zzgzzm 发表于 2016-11-26 14:59
用数学来说比较清楚:
设硬币X(i)=1的概率为p(i), X(i)=0的概率为1-p(i)。 用E(n,k)表示前n个X(i)中恰好 ...

多谢多谢。
回复

使用道具 举报

🔗
zzgzzm 2016-11-27 04:28:50 | 只看该作者
全局:
luofeidream 发表于 2016-11-27 02:21
第8行似乎写错了,应该是cur[0] = prev[0] * (1 - c[nn - 1])吧

感谢指正。
回复

使用道具 举报

🔗
kevindx1120 2016-11-27 04:42:08 | 只看该作者
全局:
yhatl 发表于 2016-11-13 11:33
lz已经说了不会了 莫装逼
装逼遭雷劈

这位兄台,我没有装比啊.就题论题啊.
回复

使用道具 举报

🔗
sunnyroom 2016-12-17 12:18:44 | 只看该作者
全局:
kevindx1120 发表于 2016-11-13 00:28
第三题,在你的recursive 解法里,你不是已经给出了递归关系式,为什么说不会bottum up 的递归. 
第四题 ...

Dijkstra面试中写不出来的。DFS全部遍历一遍得了
回复

使用道具 举报

🔗
Longfeng 2016-12-29 15:56:54 | 只看该作者
全局:
请问楼主在哪栋楼面的?
回复

使用道具 举报

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

本版积分规则

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