一亩三分地论坛

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

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

面筋热腾腾

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

2016(1-3月) 码农类 博士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
开始就问了问简历,然后问了. more info on 1point3acres.com
1。find the element in the rotated sorted array
用binary search解决
2。问时间的复杂度,答:log N
3。叫证明不可能有其它任何算法的时间复杂度优于log N

第三题根本没有任何头绪,纠缠了10几分钟,然后对方哥哥说:this is a difficult question,就结束了。
等挂了。

评分

1

查看全部评分

cx00001 发表于 2016-2-20 05:05:40 | 显示全部楼层
第三题的解释就是,因为n个数,最少用lgn位才能把他们表示出来,所以查找任何一个数,都不能低于lgn 的复杂度
回复 支持 2 反对 0

使用道具 举报

mickeyliu5 发表于 2016-1-22 09:54:01 | 显示全部楼层
第三题我上的算法课老师讲过,貌似任何sort方法的running time都不可能小于nlgn,这个应该类似,是用tree的结构证明的,上课就听的云里雾里的,面试出这个太坑了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-4 01:14:30 | 显示全部楼层
好于logn的时间复杂度的只有O(1)吧?这就不可能啊
回复 支持 反对

使用道具 举报

alitz 发表于 2016-2-24 01:06:58 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. 鍥磋鎴戜滑@1point 3 acres
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

alitz 发表于 2016-2-24 01:13:56 | 显示全部楼层
按错键发了条废帖……

第三题面MS时候问过,当时说一条sorted的array可以转成bst,然后search bst的Big O复杂度是由tree depth决定的,一个bst可以转成balanced bst,这个最小的depth就是log(N)

貌似他接受了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-5 13:16:54 | 显示全部楼层
cx00001 发表于 2016-2-20 05:05. 1point3acres.com/bbs
第三题的解释就是,因为n个数,最少用lgn位才能把他们表示出来,所以查找任何一个数,都不能低于lgn 的复杂 ...
-google 1point3acres
请问“最少用lgn位才能把他们表示出来”是什么意思?
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-25 10:10:52 | 显示全部楼层
假设有,然后sort可以比nlgn更好,这么说行么?
回复 支持 反对

使用道具 举报

xinxi531 发表于 2016-9-28 12:43:25 | 显示全部楼层
即使可以,他可能会继续问那为什么基于比较的sort算法最快只能是nlogn,感觉是个绕不开的话题。

楼上哪个从BST方面解释的说法个人感觉最靠谱。
回复 支持 反对

使用道具 举报

xinxi531 发表于 2016-9-28 12:43:43 | 显示全部楼层
tigercode 发表于 2016-9-25 10:10
假设有,然后sort可以比nlgn更好,这么说行么?

即使可以,他可能会继续问那为什么基于比较的sort算法最快只能是nlogn,感觉是个绕不开的话题。

楼上哪个从BST方面解释的说法个人感觉最靠谱。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 01:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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