📣 4th of July限时特惠: VIP通行证立减$68
12
返回列表 发新帖
楼主: cccxfdj
跳转到指定楼层
上一主题 下一主题
收起左侧

Google MTV 10/30 new grad onsite interview

🔗
gorilazz 2015-10-31 16:36:33 | 只看该作者
全局:
marthew777 发表于 2015-10-31 15:52
多谢翻译代码,我的思路和你一样。。不过这样一想,面试的时候用python简直是cheating啊。。

我平时干活都是用的c++,为了刷题专门学的python
回复

使用道具 举报

🔗
returning 2015-11-1 12:48:44 | 只看该作者
全局:
清除掉所有的草最后回到原地,要求没有格子只visit一次吗,如果是,这是欧拉回路啊,先判断是否是欧拉回路,然后欧拉回路的解法是固定的。

补充内容 (2015-11-1 13:09):
sorry, 这是汉密尔顿图,不是欧拉,只能dfs算吧。。。。。够复杂的。
回复

使用道具 举报

🔗
 楼主| cccxfdj 2015-11-1 14:30:03 | 只看该作者
全局:
marthew777 发表于 2015-10-31 14:08
最后一题我刚写了一下,100多行代码。。不过这题蛮有意思的!!

其实这题模板是subsets类似, 不清楚要不要这么多行. 就是recursion后, 再打印出相反方向即可, 这样就表示回头了.
我当时面的时候一直在纠结怎么回头, 其实recursion 完直接打印相反方向就可以了...哎
回复

使用道具 举报

🔗
 楼主| cccxfdj 2015-11-2 06:58:28 | 只看该作者
全局:
feierqi 发表于 2015-11-2 04:24
问一下楼主第三题的binarysearch是怎么搞的,我刚才写了一下,只能loop到最后的k,然后开始找,如果按你说 ...

把每一次的A,B,C看成一个block
找到k使得我们可以从n的那个character所在的block开始搜索, 而不是从第一个block开始搜索, 这样就把running time缩短为O(log n)了.
回复

使用道具 举报

🔗
 楼主| cccxfdj 2015-11-2 07:09:46 | 只看该作者
全局:
feierqi 发表于 2015-11-2 07:01
额,我还是不是很明白,你是指ABC 是一个block, AABBCC是一个block这个意思吧,那么你找到第k个block, ...

3 * (2 ^ k - 1)就是求和公式
表示前k个block的char 总数
找到这个k之后
你就可以从i = 3 * (2 ^ k - 1) + 1开始, 直到i == n
回复

使用道具 举报

全局:
请问lz除草那题,是说每个草的位置只能遍历一遍还是所有的位置都只能遍历一遍,还是说没有要求啊?
回复

使用道具 举报

🔗
hj867955629 2015-11-5 01:59:12 | 只看该作者
全局:
cccxfdj 发表于 2015-11-2 07:09
3 * (2 ^ k - 1)就是求和公式
表示前k个block的char 总数
找到这个k之后

那直接让3*(2^k-1) = n,解出k就行了吧?感觉可以O(1)。。
回复

使用道具 举报

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

本版积分规则

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