一亩三分地论坛

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

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

Google 店面一 09/252015

[复制链接] |试试Instant~ |关注本帖
aiweiwei 发表于 2015-9-25 22:51:46 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 网上海投 - HR筛选 技术电面 |Otherfresh grad应届毕业生

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

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

x
发一个google新鲜的电面题目:. 鍥磋鎴戜滑@1point 3 acres
总共45分钟,我申请的是new graduate的职位,就是普通的sde
然后电话来,还是先聊了一下简历,大致寒暄后,才开始进入问题
因为我平时用python,google也是用python,还问了几个python的问题。
1. python的initiator怎么写. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2. 扯了一下python c++ Jave的比较,差异,优缺,python特别的是white space consuming,因为indent的缘故。而且不想c++和java是machine language,java还要被编译的时候转化成binary code,c++也是需要编译成机器可识别的。python不需要编译。。。。。虽然我知道大家都都知道,但是我还是老实的报一下面试全部过程,趁着现在记忆比较清晰。
3.上题目,面试官说,那你懂sorting吗,我说懂,然后面试官来题目了:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
一个array,里面的number没有sort好,你有什么快速的方法sort呢?
然后我就说那一般比较快的是quick sort,merge sort
然后面试官要求我口述merge sort方法原理,没有真的写
4.然后来真的写的题目了,一个array,要找第k个大的element,怎么找呢
一开始我没有想到quicksort,还yy了半天说sort后找出来,面试官明显不满意,因为复杂度是NlogN了,面试官说有更好的方法吗. Waral 鍗氬鏈夋洿澶氭枃绔,
才忽然想到quick sort原理的pivot,然后leetcode也有原题的,然后就是O(N)就算完了。然后google doc上写完
.鐣欏璁哄潧-涓浜-涓夊垎鍦
反正总体我就店面了这一题,因为之前寒暄啊聊简历啊聊python啊聊sort啊,我就使劲说的那种,而且面试官感觉也不shy的那种,也跟我说啊说的。所以导致时间只够写了一题的code。哎,感觉要挂。最近找工作,也认识了版上一位朋友,相互鼓励中,就不那么孤独了,也bless其他朋友。

PS: 我积分太低了,导致很多面经贴子都看不到,各位好心人走过路过求加分,本来我code就差了,又因为积分低看不到面经,人生就简直不能悲剧更多了。

如果有小伙伴想一起讨论面试找工作经验互相支持鼓励的,也可以私信我。

Bless everyone!!


补充内容 (2015-10-14 04:36):
拿到on site啦,虽然还没有定具体什么时候on site,但是很兴奋来更新一下

评分

8

查看全部评分

本帖被以下淘专辑推荐:

leixiang5 发表于 2015-9-25 23:51:55 | 显示全部楼层
leixiang5 发表于 2015-9-25 23:43
谢谢楼主分享。祝你拿到onsite。。
. visit 1point3acres.com for more.
java的code是转换成byte code...jvm然后interrupt 这些byte code来运行。。
原来python不需要compiler啊?。长知识了。。
quicksort来找k个大的。。不是O(n^2)吗?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
欢迎楼主加我微信。我把我微信发给你了。。
再次保佑楼主拿到onsite..
回复 支持 0 反对 1

使用道具 举报

leixiang5 发表于 2015-9-26 00:32:32 | 显示全部楼层
penenda 发表于 2015-9-26 00:24
quicksort的原理找第K大只需要o(N). quicksort选取一个元素之后把大的放一边,小的放另外一边。如果单纯 ...

"This is an optimization over method 1 if QuickSort is used as a sorting algorithm in first step. In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.".1point3acres缃

Geek里的解释。。比如说你pick 1st element as your pivot..然后array是sorted。。然后要你找k=n..那不是n^2吗
回复 支持 1 反对 0

使用道具 举报

leixiang5 发表于 2015-9-25 23:43:47 | 显示全部楼层
谢谢楼主分享。祝你拿到onsite。。
回复 支持 反对

使用道具 举报

penenda 发表于 2015-9-26 00:24:27 | 显示全部楼层
leixiang5 发表于 2015-9-25 23:51
java的code是转换成byte code...jvm然后interrupt 这些byte code来运行。。
原来python不需要compiler啊 ...

quicksort的原理找第K大只需要o(N). quicksort选取一个元素之后把大的放一边,小的放另外一边。如果单纯只找第K大的,只要排出比他小的(在这个元素左边的)规模为K-1的时候就可以了。
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-9-26 00:38:07 | 显示全部楼层
python 确实是interpretor, 但本质还是会compile(不然机器怎么能懂呢?)这里涉及JIT编译知识,略复杂过
大多数我们使用的python都是CPython, 也就是python底层使用C的编译器,我们还可以选择Jython,顾名思义-JAVA底层编译支持(JIT)

python其实唯一优势就是语法sugar,对用户更加友好,除此以外不如C/Java,特别是在多线程领域(GIL大法舍我起谁). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

K element - 方法1. sort,直观方便, 方法2, MinHeap/MaxHeap, 效率会高点, 方法3, quickSort(partition) 效率再高点


回复 支持 反对

使用道具 举报

peach=。= 发表于 2015-9-26 00:45:55 | 显示全部楼层
楼主答的很好啊!我觉得有希望!
交流的很好,后面引导着也说出了正解,很好啊!
回复 支持 反对

使用道具 举报

mouse77 发表于 2015-9-26 04:13:24 | 显示全部楼层
非常感谢分享
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-9-26 08:18:26 | 显示全部楼层
看楼主的描述答的挺好的呀, 只是聊天开心说的时间多了一点, 做题时间少了一点, 不能成为被挂的理由吧?~楼主乐观点哈
回复 支持 反对

使用道具 举报

 楼主| aiweiwei 发表于 2015-9-26 10:13:29 | 显示全部楼层
yjfox 发表于 2015-9-26 00:38. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
python 确实是interpretor, 但本质还是会compile(不然机器怎么能懂呢?)这里涉及JIT编译知识,略复杂过
...

多谢大神指点。对,我当时也跟面试官说,我自己yy觉得python应该还是compile的,感觉像是在run的时候现去compile的,不然为什么python比c++和java慢呢,总有个时间守恒的定律吧,不能无原有慢吧。然后牛逼的面试官就开始跟我讲了,但是那会儿我状态有点不好,也有几个词听不懂,就没有真正搞懂,但反正结论大致还是python不用compile,但是为啥python慢面试官跟我讲了我还是没懂。。。

请问大神你说的minheap/maxheap那个方法是啥呢?
回复 支持 反对

使用道具 举报

 楼主| aiweiwei 发表于 2015-9-26 10:13:54 | 显示全部楼层
leixiang5 发表于 2015-9-26 00:32
. Waral 鍗氬鏈夋洿澶氭枃绔,"This is an optimization over method 1 if QuickSort is used as a sorting algorithm in first step.  ...

就感觉最差的情况是n2
回复 支持 反对

使用道具 举报

penenda 发表于 2015-9-26 10:22:16 | 显示全部楼层
leixiang5 发表于 2015-9-26 00:32
"This is an optimization over method 1 if QuickSort is used as a sorting algorithm in first step.  ...

最坏确实到n^2. 对于一般情况可以O(n)解决。。
回复 支持 反对

使用道具 举报

wade123 发表于 2015-9-26 10:32:36 | 显示全部楼层
找第k大的应该是用quick select吧,记得复杂度O(N)
回复 支持 反对

使用道具 举报

mikegrup 发表于 2015-9-26 10:48:19 | 显示全部楼层
谢谢楼主!~~G的模式果然没套路可言,每个人都不一样
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-9-26 21:44:50 | 显示全部楼层
mikegrup 发表于 2015-9-26 10:48
谢谢楼主!~~G的模式果然没套路可言,每个人都不一样

我问了下我的面试官。。每个software engineer可以当面试官。。题目又是他们自己出。。所以就会让每个人面试的经历不同。。所以g面试还要带点运气。。
回复 支持 反对

使用道具 举报

 楼主| aiweiwei 发表于 2015-9-26 21:49:12 | 显示全部楼层
leixiang5 发表于 2015-9-26 21:44
我问了下我的面试官。。每个software engineer可以当面试官。。题目又是他们自己出。。所以就会让每个人 ...

酱紫 请问你面试经验是啥,求分享
回复 支持 反对

使用道具 举报

xnature 发表于 2015-9-26 22:26:14 | 显示全部楼层
leixiang5 发表于 2015-9-26 00:32
"This is an optimization over method 1 if QuickSort is used as a sorting algorithm in first step.  ...

O(n)是average,worst case是O(n^2)。

快排worst case也是O(n^2)啊
回复 支持 反对

使用道具 举报

xnature 发表于 2015-9-26 22:42:55 | 显示全部楼层
Python最大的特点是duck-typing!
回复 支持 反对

使用道具 举报

charles92 发表于 2015-9-28 22:10:05 | 显示全部楼层
aiweiwei 发表于 2015-9-26 10:13
多谢大神指点。对,我当时也跟面试官说,我自己yy觉得python应该还是compile的,感觉像是在run的时候现去 ...

假设你要找 k-th max value in array A.
Keep 一个 min-heap,存储目前为止遇到的 k 个最大的数。
从头到尾遍历一遍 A:
当 heap size < k 的时候, insert into min-heap;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
当 heap size == k 的时候,比较当前值和 min-heap 的 head ,如果当前值较小就忽略,反之 pop heap then insert 当前值。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
循环结束后 pop heap 就是 k-th max 。

Running time:
min-heap insert / pop : O(log k) worst/average case
所以 overall 是 O(n log k) worst/average case

和 Quickselect (就是LZ提到的方法)相比, min-heap 法 worst case 更快,但 average case 稍稍逊色。关键看 worst case 是否有要求了。
回复 支持 反对

使用道具 举报

theocrasy 发表于 2015-10-18 08:50:47 | 显示全部楼层
楼主 原来google是接受用python面试的?? 我学长在google里工作 他和我说:你刷题最后不要python 因为我们用c++和java的多,你面试用python我会很不爽。。。。

搞得我不敢用python呢。。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 12:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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