📣 VIP通行证夏日特惠 限时立减$68
楼主: Yunying
跳转到指定楼层
上一主题 下一主题
收起左侧

Google电面 08/25/2015

🔗
 楼主| 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的那些就自动没有了。
回复

使用道具 举报

全局:
flyaway25 发表于 2015-9-17 09:23
可以新建一个map,只把当前value大于1的那些减1加到新的map里面,然后再赋给原来的map,这样原来本身里面 ...

谢谢回复,这样可能会每次加一个数都开一个temp,空间不是就特别大?不过好像也没有什么别的方法了。。。

补充内容 (2015-9-17 09:35):
新的map,说错了
回复

使用道具 举报

🔗
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)
回复

使用道具 举报

🔗
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 ...

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
I believe your algorithm fails at this input case: [1, 2, 3, 1, 5, 6]
You would've kicked off 1 b ...

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

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

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

使用道具 举报

🔗
坐看云起 2015-9-22 07:13:18 | 只看该作者
全局:
遍历一次,保存一个长度为3的数组:
1. 如果数组中包括这个数,则概数count + 1
2. 如果数组中有空位,则放入概数,count置为1
3. 如果数组中有数字count为0,则替换概数,count置为1
4. 所有数字count减1

最后数组中剩下的数,就是candidate,每个统计一下就可以了

这个方法可以解决任意1/n的majority number
回复

使用道具 举报

🔗
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

這個example 最後會有5(count =1) 3(count=1) 1(count=0)  要怎麼做呢?

回复

使用道具 举报

🔗
坐看云起 2015-9-22 11:05:33 | 只看该作者
全局:
say543 发表于 2015-9-22 09:50
弱弱的问一下再检查一次是要再花o(n) ?

5 3 5 3 1 2

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

使用道具 举报

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

本版积分规则

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