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

热乎乎的Google Onsite面经

🔗
refurbish 2015-4-6 16:27:48 | 只看该作者
全局:
Arthur2012 发表于 2015-4-6 08:54
lz的第二面第三题是石子归并问题,如果给出O(n^3)的解法不知道可不可以。

看了lz描述,半天没看懂题意,到你这里豁然开朗
回复

使用道具 举报

🔗
refurbish 2015-4-6 17:22:53 | 只看该作者
全局:
第四题太坑了,后台预处理,那啥问题都能线型了,还搞毛啊。楼主也真够冒险的,他们面试官其实能看到之前人出的题目的,后面系统里好像也能查,要是写到comment里。。。
回复

使用道具 举报

🔗
狂暴CNM地 2015-4-6 23:21:57 | 只看该作者
全局:
Arthur2012 发表于 2015-4-6 08:54
lz的第二面第三题是石子归并问题,如果给出O(n^3)的解法不知道可不可以。

石子归并?  这个题感觉就是算法导论上  Matrix multiplication的变种吧   递归指数级  DP的话n^3
回复

使用道具 举报

🔗
Arthur2012 2015-4-6 23:33:06 | 只看该作者
全局:
狂暴CNM地 发表于 2015-4-6 23:21
石子归并?  这个题感觉就是算法导论上  Matrix multiplication的变种吧   递归指数级  DP的话n^3

恩恩,矩阵连乘的变种,DP可以优化到n^2
http://blog.csdn.net/acdreamers/article/details/18039073
回复

使用道具 举报

🔗
fishyuze 2015-4-7 03:06:24 | 只看该作者
全局:
对给定的点反过来向上uphill做BFS,然后一个map记录矩阵上每个点被访问了几次。然后再来个for loop检查矩阵上被所有给定的点访问过的最高点。time complexity O(n).

反向bfs复杂度似乎没法降吧 应该还是O(kn)的吧 k是给的destination个数 n是矩阵所有点的个数?
回复

使用道具 举报

🔗
 楼主| coolis 2015-4-7 03:49:55 | 只看该作者
全局:
fishyuze 发表于 2015-4-7 03:06
反向bfs复杂度似乎没法降吧 应该还是O(kn)的吧 k是给的destination个数 n是矩阵所有点的个数?

恩,还是O(kn)
回复

使用道具 举报

无效楼层,该帖已经被删除
无效楼层,该帖已经被删除
🔗
fishyuze 2015-4-7 05:29:56 | 只看该作者
全局:
面试官说sort是个好方法,但有没有更好一点的,我一听,这是要linear时间啊,


弄个counting sort是线性的 否则难优化了吧 似乎可以规约到排序 然后证明基于比较的方法不可能更优了?
回复

使用道具 举报

🔗
 楼主| coolis 2015-4-7 11:31:35 | 只看该作者
全局:
fishyuze 发表于 2015-4-7 05:29
弄个counting sort是线性的 否则难优化了吧 似乎可以规约到排序 然后证明基于比较的方法不可能更优了?

counting sort的N不能太大,但是这里是任意array。我没有想出什么更好的算法,所以只能从后台预处理的角度去做了,不知道有没有大神有更牛的算法。
回复

使用道具 举报

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

本版积分规则

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