📣 4th of July限时特惠: VIP通行证立减$68
跳转到指定楼层
上一主题 下一主题
收起左侧

给Google onsite面经添砖加瓦

 
🔗
 楼主| 猫头鹰也是猫 2016-11-12 06:52:00 | 只看该作者
全局:
代号9527 发表于 2016-11-11 23:42
恭喜大神,请问过完hc就是offer吗还是要先team match?

谢谢!今年new grad都是先offer再match的!
回复

使用道具 举报

🔗
 楼主| 猫头鹰也是猫 2016-11-12 06:55:43 | 只看该作者
全局:
chaosMonkey 发表于 2016-11-11 19:11
g家的问题都是这么难吗?

同意楼上观点。而且我的面试官都会或多或少地帮我往正确的思路上指引,所以乍一看觉得难的题最后也都能做出来,回想也没那么可怕。
回复

使用道具 举报

🔗
jokebill 2016-11-14 13:00:37 | 只看该作者
全局:
做lz第二轮第二题,才发现python的yield真是好用

  1. def derived_gen(gen):
  2.   while True:
  3.     n = gen.next()
  4.     val = gen.next()
  5.     for i in xrange(n):
  6.       yield val

  7. for n in derived_gen(iter([2, 3, 0, 5, 3, 2, 1, 8]))
  8.   print n
  9.       
复制代码
回复

使用道具 举报

🔗
luofeidream 2016-11-24 08:16:26 | 只看该作者
全局:
zzgzzm 发表于 2016-10-24 14:37
第四轮 药片题:药瓶中每一个状态是由w(整片个数), h(半片个数)以及到达该状态的概率p唯一决定的。这 ...

这种方法占用的空间开销太大了吧?
回复

使用道具 举报

🔗
zzgzzm 2016-11-24 11:32:39 | 只看该作者
全局:
luofeidream 发表于 2016-11-24 08:16
这种方法占用的空间开销太大了吧?

的确是。。。对于level order traversal的办法,level k就有组合数C(k,k/2)个nodes,而这个数是远远大于O(2^(k/2))量级的,所以时间空间代价都远远大于O(2^(k/2))  (k=198天)。其实我在写level order traversal的办法时也觉得这是只是理论上的推导,因为大量细小的概率乘机载求和那么在实现时精度早就没有了。

我在想除非这个就应该当个纯数学题来解,感觉和二项式系数有关系,但也没看出具体的线索。其实在第198天时的状态无非就是(1,0)或(0,2),但它们各自的概率是什么以及有没有对称性似乎都很难讲。我目前还没有想出explicit的数学表达式结果(关键是转移概率总是随时间动态变化的)。
回复

使用道具 举报

🔗
zhshr 2016-11-24 14:39:14 | 只看该作者
全局:
妈呀这论坛发代码怎么这么丑。。发GIST了。。。。
两种O(n^2)的算法。。第一种是维护两天的状态和到达状态的概率。
这种方式的空间复杂度是O(N),因为只有两个数组prevDay和currDay,而且也不涉及浮点运算精度问题。时间复杂度是O(MN),因为需要循环N天,每次循环都要遍历数组。

第二种算法就是上面说的dfs+memorization,按照我的思路,dfs()应该有两个参数,就是当前的两种药片数,返回值是从这个state到目标target的概率。这样可以把概率memorization起来。

抛砖引玉。。。何况可能连砖都不是。。轻拍





补充内容 (2016-11-24 15:41):
恩写多了。。还是涉及浮点运算问题的。。。

评分

参与人数 2大米 +10 收起 理由
hreat + 5 很有用的信息!
UUOlidd + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
fightinus 2016-11-24 15:07:35 | 只看该作者
全局:
jfree811 发表于 2016-10-15 20:43
话说google面试的时候能和中国面试官说中文吗?之前看别人写的帖子有提到直接中文交流。

这个看面试官吧,他要是跟你讲中文面,你就回中文,他要是说英文,你就英文对他~见机行事
回复

使用道具 举报

🔗
yxgoogle2016 2017-1-15 04:18:27 | 只看该作者
全局:
剧院的订座系统 怎么做的呀
回复

使用道具 举报

🔗
stormcat 2017-4-10 12:03:03 | 只看该作者
全局:
感谢你的分享。有所启发受益了。谢谢
回复

使用道具 举报

🔗
zling 2017-4-12 14:41:07 | 只看该作者
全局:
恭喜楼主啊~~~ 谢谢分享
回复

使用道具 举报

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

本版积分规则

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