在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3562|回复: 16
收起左侧

Google-Intern-电面

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

() @ - -   | |

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

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

x
一. 国妹
1. 找到一个array中出现超过两次的数。    我:hashmap
    follow up:空间要求O(1).                    我:暴力O(n^2) or Sort
2. shuffle,但要求是每个元素的下标不能和原来的index一样. more info on 1point3acres
    我,每次生成一个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里出现频率最多的那个数。(没写代码)
   我:堆,按照频率排的大根堆。再来个hash:从元素指向堆中节点,方便更新堆。再存windowsize的数字。

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

补充内容 (2016-1-26 05:54):
2.1的out不应该有1,0.5是(0+1)/2得到的. Waral 博客有更多文章,
. more info on 1point3acres
补充内容 (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):. more info on 1point3acres
2.2:当window向后滑一步,需要:1.把滑出的数的value的出现次数--。2.滑入的数的次数++,如果没出现过,就heap里加一个新的节点。3.调整heap,map,vector,并输出堆顶。

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

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

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

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

使用道具 举报

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!!
.1point3acres网
对不起,我错了,没有1。0.5是(1+0)/2。
第二题看我补充内容吧。
.本文原创自1point3acres论坛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, ...

对,当时就慌了~都准备自己写堆了~他说:不用写代码.....
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

刘小盒子 发表于 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应该妥了。
. 围观我们@1point 3 acres什么是possiblePos的数组,怎么摇号啊。
.留学论坛-一亩-三分地
就是现在还有哪些位置没有放元素进去,把他们放进一个数组,摇一个这个数组长度范围内的随机数,然后取相应坐标的数。当然,与原位置相同的坐标不应该在这个数组中。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| hanyu 发表于 2016-1-27 00:55:56 | 显示全部楼层
maplain 发表于 2016-1-26 23:10
对于堆,是没办法删除非顶点node的,因而堆是没办法处理这种情况吧?要用平衡树,以数字出现的次数作为ke ...

我认为你说的非常有道理诶~多谢多谢~
回复 支持 反对

使用道具 举报

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  可以具体解释下吗
来源一亩.三分地论坛.
不是。原来楼主说维护一个大根堆,每次返回堆顶。现在维护一个平衡树,然后每次返回最大值(出现次数),相当于查找操作(查找最大键值),窗口移动,有的数据进来,有的出去相当于插入和删除。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 11:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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