一亩三分地论坛

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

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

Google-Intern-电面

[复制链接] |试试Instant~ |关注本帖
hanyu 发表于 2016-1-26 05:08:44 | 显示全部楼层 |阅读模式

() @ - -  |

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

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

x
一. 国妹
1. 找到一个array中出现超过两次的数。    我:hashmap. from: 1point3acres.com/bbs
    follow up:空间要求O(1).                    我:暴力O(n^2) or Sort
2. shuffle,但要求是每个元素的下标不能和原来的index一样
    我,每次生成一个possiblePos的数组,然后摇号。

二. 不知哪国哥(有点口音,只要是通话质量很差)
1. 一个int stream,输出每windowSize的avarage。如1,2,3,4,window:2,out:1,0.5, 1.5, 2.5, 3.5
   我:存windowsize的数字和上一个平均数。
2. 和第一题类似,算window里出现频率最多的那个数。(没写代码). 1point3acres.com/bbs
   我:堆,按照频率排的大根堆。再来个hash:从元素指向堆中节点,方便更新堆。再存windowsize的数字。

不知结果会如何......

补充内容 (2016-1-26 05:54):
2.1的out不应该有1,0.5是(0+1)/2得到的

补充内容 (2016-1-26 05:58):
2.2 解法说的详细一些:1. 一个大小为windowsize的大根堆,每个node存两个值,一个是value数值,另一个是该数出现了几次. 2. 一个hashmap,从value map的heap的node,方便更新. 3. 大小为windowsize的vector, 记录数。

补充内容 (2016-1-26 06:00):
2.2:当window向后滑一步,需要:1.把滑出的数的value的出现次数--。2.滑入的数的次数++,如果没出现过,就heap里加一个新的节点。3.调整heap,map,vector,并输出堆顶。

补充内容 (2016-1-27 00:56):
对于最后一题堆不好操作的问题,maplain建议使用平衡二叉树,在c++里就是map~

补充内容 (2016-2-13 03:05):
进pool了

评分

2

查看全部评分

本帖被以下淘专辑推荐:

虾米酱 发表于 2016-1-26 05:25:59 | 显示全部楼层
最后一题可以用分布式计算么,感觉好像设计题
回复 支持 反对

使用道具 举报

 楼主| hanyu 发表于 2016-1-26 05:42:31 | 显示全部楼层
虾米酱 发表于 2016-1-26 05:25
最后一题可以用分布式计算么,感觉好像设计题

你说的太高端了.....我不懂
回复 支持 反对

使用道具 举报

atwoodwang0918 发表于 2016-1-26 05:51:50 | 显示全部楼层
请问楼主二面第一题 为什么一开始会输出1和0.5呢??然后第二题能详细说说做法么?非常感谢!!祝offer!!
回复 支持 反对

使用道具 举报

neal1st 发表于 2016-1-26 05:53:37 | 显示全部楼层
LZ应该妥了。
什么是possiblePos的数组,怎么摇号啊。
回复 支持 反对

使用道具 举报

 楼主| hanyu 发表于 2016-1-26 05:54:18 | 显示全部楼层
atwoodwang0918 发表于 2016-1-26 05:51
请问楼主二面第一题 为什么一开始会输出1和0.5呢??然后第二题能详细说说做法么?非常感谢!!祝offer!!

对不起,我错了,没有1。0.5是(1+0)/2。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二题看我补充内容吧。
Thanks。
回复 支持 反对

使用道具 举报

xiaobao9 发表于 2016-1-26 06:36:12 | 显示全部楼层
问下楼主,2.2中,heep怎样支持删除一个非堆顶 node?C++的priority_queue应该不支持删除一个非堆顶node,也不支持访问一个非堆顶t的node。Java就不知道了
回复 支持 反对

使用道具 举报

 楼主| hanyu 发表于 2016-1-26 08:59:47 | 显示全部楼层
xiaobao9 发表于 2016-1-26 06:36
问下楼主,2.2中,heep怎样支持删除一个非堆顶 node?C++的priority_queue应该不支持删除一个非堆顶node, ...

对,当时就慌了~都准备自己写堆了~他说:不用写代码.....
回复 支持 反对

使用道具 举报

刘小盒子 发表于 2016-1-26 10:28:17 | 显示全部楼层
感谢楼主分享,应该是妥了,祝offer~~~
回复 支持 反对

使用道具 举报

 楼主| hanyu 发表于 2016-1-26 10:32:19 | 显示全部楼层
刘小盒子 发表于 2016-1-26 10:28
感谢楼主分享,应该是妥了,祝offer~~~

多谢大盒子芋头
回复 支持 反对

使用道具 举报

 楼主| hanyu 发表于 2016-1-26 12:28:21 | 显示全部楼层
neal1st 发表于 2016-1-26 05:53
LZ应该妥了。
什么是possiblePos的数组,怎么摇号啊。

就是现在还有哪些位置没有放元素进去,把他们放进一个数组,摇一个这个数组长度范围内的随机数,然后取相应坐标的数。当然,与原位置相同的坐标不应该在这个数组中。
回复 支持 反对

使用道具 举报

maplain 发表于 2016-1-26 23:10:25 | 显示全部楼层
hanyu 发表于 2016-1-26 08:59.1point3acres缃
对,当时就慌了~都准备自己写堆了~他说:不用写代码.....

对于堆,是没办法删除非顶点node的,因而堆是没办法处理这种情况吧?要用平衡树,以数字出现的次数作为key值,然后各种操作,查找,插入,删除都是logn。
回复 支持 反对

使用道具 举报

 楼主| hanyu 发表于 2016-1-27 00:55:56 | 显示全部楼层
maplain 发表于 2016-1-26 23:10
对于堆,是没办法删除非顶点node的,因而堆是没办法处理这种情况吧?要用平衡树,以数字出现的次数作为ke ...
.1point3acres缃
我认为你说的非常有道理诶~多谢多谢~
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-1-27 02:33:07 | 显示全部楼层
shuffle这个是什么意思,找到一些数之后随机选?
回复 支持 反对

使用道具 举报

 楼主| hanyu 发表于 2016-1-27 04:07:55 | 显示全部楼层
mchzh 发表于 2016-1-27 02:33
shuffle这个是什么意思,找到一些数之后随机选?

就是洗牌
回复 支持 反对

使用道具 举报

yixianpig 发表于 2016-1-27 04:42:02 | 显示全部楼层
maplain 发表于 2016-1-26 23:10. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
对于堆,是没办法删除非顶点node的,因而堆是没办法处理这种情况吧?要用平衡树,以数字出现的次数作为ke ...

请问这样是每个window都要生成一个平衡树吗?感觉自己没理解到正确解法T.T  可以具体解释下吗
回复 支持 反对

使用道具 举报

maplain 发表于 2016-1-27 05:09:05 | 显示全部楼层
yixianpig 发表于 2016-1-27 04:42
请问这样是每个window都要生成一个平衡树吗?感觉自己没理解到正确解法T.T  可以具体解释下吗
. 鍥磋鎴戜滑@1point 3 acres
不是。原来楼主说维护一个大根堆,每次返回堆顶。现在维护一个平衡树,然后每次返回最大值(出现次数),相当于查找操作(查找最大键值),窗口移动,有的数据进来,有的出去相当于插入和删除。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 11:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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