一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 429|回复: 0
收起左侧

Google 电面面经

[复制链接] |试试Instant~ |关注本帖
phil 发表于 2016-4-9 03:09:50 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚刚结束的谷歌电面,题是做出来了,就是心里没底。

题目很简单, merge k sorted list. leetcode原题。拿到题目的那一瞬间发现烙印哥哥还是不错的。做题之前象征性的问问之前的经历,还没说完就直接码题。

因为之前做过好几遍,就开码了。楼主选的c++。
. Waral 鍗氬鏈夋洿澶氭枃绔,
第一种方法就是merge vector中的 前两个lists,生成新的list.然后放到原来的包含Lists的vector的末尾,删除前两个。 循环知道vector.size 为1为止。
.1point3acres缃
码到一半被叫停。 说这方法太慢,有没有更快的。

楼主心里一咯噔。 想来想去来个merge sort吧,就是每次都merge vector的前半段lists 和 后半段 lists.   每一次操作, vector的size都会减半。 楼主自以为这是加快了速度。. 1point3acres.com/bbs

可是又是码到一半被叫停, 说每一次的结果新生成的list长度会增加,复杂度不是O(nlogn)。. visit 1point3acres.com for more.

后来才想到可以用堆来做,这样的复杂度是最小的, 为O(所有list node 的数量)。

相当于一道题用不同的方法码了三次。 最后烙印听上去还是很高兴的, 谈笑风生了一会。

吸取的教训就是每一道题都要用最优解来做。

都说电面至少要两道题以上才能move on。 我这也可以说是命悬一线了。

不管怎样都过去了, 继续move on.

求onsite 求米。





评分

1

查看全部评分

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 21:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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