一亩三分地论坛

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

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

Google电面 08/25/2015

[复制链接] |试试Instant~ |关注本帖
Yunying 发表于 2015-9-17 07:19:26 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
几周之前的电面了,刚刚在同学的指引下到地里>_< 这两天趴在地里看面经,突然想起来应该把自己的也写下来。(本科new grad, Software Engineer Full Time)
内推投的,内推后一天就收到HR回复。

电面就一轮一个问题:Find the popular number in the array. Popular means it appeas > 1/4 size of the array。

拿到题目直接抬手就暴力解法,5分钟写完。然后接下来40分钟小哥都在孜孜不倦地指引我找一个Better的解法。反正最后唠嗑了40分钟我还没把better solution的解法代码写出来,只是终于理解了小哥的意思(。。。) . visit 1point3acres.com for more.

挂了电话觉得肯定跪了,结果1周后HR喊我去onsite>V<

(然而过了两周了HR问了我available的时间后就杳无音讯了还没把onsite的时间发给我啊!抓狂中【打滚T^T)

本帖被以下淘专辑推荐:

坐看云起 发表于 2015-9-22 07:13:18 | 显示全部楼层
遍历一次,保存一个长度为3的数组:
1. 如果数组中包括这个数,则概数count + 1
2. 如果数组中有空位,则放入概数,count置为1
3. 如果数组中有数字count为0,则替换概数,count置为1. 1point3acres.com/bbs
4. 所有数字count减1

最后数组中剩下的数,就是candidate,每个统计一下就可以了
. 1point3acres.com/bbs
这个方法可以解决任意1/n的majority number
回复 支持 3 反对 0

使用道具 举报

jiebour 发表于 2015-9-17 09:42:28 | 显示全部楼层
Yunying 发表于 2015-9-17 09:04
呃面试小哥给的答案是每次查1/4size的头和尾。比如一共有30个element你就查array[0]和array[7]。如果它们一 ...

直接遍历一遍,全部扔进hashmap里,然后遍历hashmap一遍,出答案。时间复杂度O(N)
回复 支持 1 反对 0

使用道具 举报

mint0715 发表于 2015-9-17 07:30:22 | 显示全部楼层
每次扔掉四个不同的element,直到最后剩下的就是popular.
因为popular的数量超过1/4,所以无论怎么扔,popular都不会被扔完。

开一个大小为3的hashmap,记录目前为止出现频率最高的三个元素->他们的频率。
读入下一个元素,如果在map里,对应频率+1,否则三个元素各-1.一旦某个元素频率<0。说明他的数量被人超越了,就把它踢掉,换那个超越他的进map。
最后留在map里的,就是要求的元素。
回复 支持 反对

使用道具 举报

pyemma 发表于 2015-9-17 07:56:23 | 显示全部楼层
mint0715 发表于 2015-9-16 15:30
每次扔掉四个不同的element,直到最后剩下的就是popular.
因为popular的数量超过1/4,所以无论怎么扔,pop ...

好巧妙的方法,这个方法可以推广到k个情况吧
回复 支持 反对

使用道具 举报

weixc1234 发表于 2015-9-17 08:34:45 | 显示全部楼层
better solution是Moore Voting吧,跟leetcode上majority element的题目类似的。.1point3acres缃
-google 1point3acres
https://en.wikipedia.org/wiki/Bo ... rity_vote_algorithm. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-9-17 08:46:39 | 显示全部楼层
mint0715 发表于 2015-9-17 07:30. more info on 1point3acres.com
每次扔掉四个不同的element,直到最后剩下的就是popular.
因为popular的数量超过1/4,所以无论怎么扔,pop ...

map里面留下的知识potential的结果,你还需要再验证一次是否满足majority的条件。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-17 08:52:50 | 显示全部楼层
flyaway25 发表于 2015-9-17 08:46. more info on 1point3acres.com
map里面留下的知识potential的结果,你还需要再验证一次是否满足majority的条件。
. more info on 1point3acres.com
对!比如 1 2 3 4 1 2 3 4 1 2 3 4 4 5 5
回复 支持 反对

使用道具 举报

 楼主| Yunying 发表于 2015-9-17 09:04:06 | 显示全部楼层
呃面试小哥给的答案是每次查1/4size的头和尾。比如一共有30个element你就查array[0]和array[7]。如果它们一样那这个值就是popular了,如果不一样那binary search找和末尾那个值相同的index最小的值,然后这样查过去……complexity就是nlogn
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-9-17 09:07:18 | 显示全部楼层
Yunying 发表于 2015-9-17 09:04
呃面试小哥给的答案是每次查1/4size的头和尾。比如一共有30个element你就查array[0]和array[7]。如果它们一 ...

这个解法需要先排序吧 摩尔投票算法反正是线性时间
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-17 09:09:27 | 显示全部楼层
flyaway25 发表于 2015-9-17 08:46.1point3acres缃
map里面留下的知识potential的结果,你还需要再验证一次是否满足majority的条件。

嗯嗯,没错,我有个疑问,就是如果不一样,就是要把hashmap所有key的value值都减1,这个一边遍历一边修改的code是什么?好像用iterator只能有iter.remove(),请问怎么修改呢?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-17 09:17:45 | 显示全部楼层
onsite加油啦
回复 支持 反对

使用道具 举报

 楼主| Yunying 发表于 2015-9-17 09:21:29 | 显示全部楼层
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
谢谢~~~^_^
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-9-17 09:23:02 | 显示全部楼层
宝贝忆彼岸 发表于 2015-9-17 09:09
嗯嗯,没错,我有个疑问,就是如果不一样,就是要把hashmap所有key的value值都减1,这个一边遍历一边修改 ...

可以新建一个map,只把当前value大于1的那些减1加到新的map里面,然后再赋给原来的map,这样原来本身里面是1的那些就自动没有了。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-17 09:35:29 | 显示全部楼层
flyaway25 发表于 2015-9-17 09:23. visit 1point3acres.com for more.
可以新建一个map,只把当前value大于1的那些减1加到新的map里面,然后再赋给原来的map,这样原来本身里面 ...

谢谢回复,这样可能会每次加一个数都开一个temp,空间不是就特别大?不过好像也没有什么别的方法了。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2015-9-17 09:35):-google 1point3acres
新的map,说错了
回复 支持 反对

使用道具 举报

mint0715 发表于 2015-9-17 11:21:24 | 显示全部楼层
jiebour 发表于 2015-9-17 08:52
对!比如 1 2 3 4 1 2 3 4 1 2 3 4 4 5 5

对对。。。

顺带一说,这个是O(N)时间O(1)空间的做法。。。

不限空间的话,还是直接hash统计一下找最大。。
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-18 07:37:38 | 显示全部楼层
mint0715 发表于 2015-9-17 07:30
每次扔掉四个不同的element,直到最后剩下的就是popular.
因为popular的数量超过1/4,所以无论怎么扔,pop ...
. visit 1point3acres.com for more.
I believe your algorithm fails at this input case: [1, 2, 3, 1, 5, 6]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
You would've kicked off 1 by the end, but it IS a popular element.
I think adding 3 when the element occurs can fix it.
回复 支持 反对

使用道具 举报

mint0715 发表于 2015-9-18 13:26:13 | 显示全部楼层
snklee 发表于 2015-9-18 07:37. 1point3acres.com/bbs
I believe your algorithm fails at this input case: [1, 2, 3, 1, 5, 6]
You would've kicked off 1 b ...

srry,细节有误。. visit 1point3acres.com for more.
当遇到新的元素x时:
1.如果x在列表里,对应frequence+1-google 1point3acres
2.如果x不在列表里,检查列表里当前是否有frequence == 0的元素y,用x->0取代y->0。

最后检查列表里剩下的三个元素,是否满足总count>1/4。

补充内容 (2015-9-18 13:27):
3.如果x不在列表里,且列表里所有元素的frequence都不为0,那么列表里所有元素的frequence-1。
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-22 09:50:59 | 显示全部楼层
坐看云起 发表于 2015-9-22 07:13
遍历一次,保存一个长度为3的数组:
1. 如果数组中包括这个数,则概数count + 1
2. 如果数组中有空位,则 ...

弱弱的问一下再检查一次是要再花o(n) ?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

5 3 5 3 1 2
. From 1point 3acres bbs
這個example 最後會有5(count =1) 3(count=1) 1(count=0)  要怎麼做呢? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-22 11:05:33 | 显示全部楼层
say543 发表于 2015-9-22 09:50
弱弱的问一下再检查一次是要再花o(n) ?. From 1point 3acres bbs

5 3 5 3 1 2

这个过程是O(k)的,此处k==3,因为数组长度取决于要找的目标所占比例,所以这道题可以当作是常量时间
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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