[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

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

Google面经 已挂

[复制链接] |试试Instant~ |关注本帖
lvlingsheng 发表于 2016-4-20 11:31:59 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Fail | fresh grad应届毕业生

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

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

x
上周三面试的,今天接到电话说已经挂了。

Google的面试给我留下了很好的印象,因为做的比较规范,最后反馈也都是电话告知结果,非常正规的感觉。

我当时面试的时候运气不错,是一个美国小哥,题目也蛮简单的。第一题是给两个string,其中一个string比另外一个多了个字母,返回这个字母。

第一题就用了最简单的比较,比较每一个字母(按照顺序就可以了),注意一下边界条件,最后一个的边界条件。

Follow up是如果字母顺序打乱了怎么找。我先说了HashMap,要写的时候想起来另外一个方法,就是把所有的ASICII加起来,减一下,得到的就是多出来的那个。 我就直接说了这个,然后写了这个。写完之后小哥问了一下时间空间复杂度,然后说你已经把本来要提升的东西做了、

然后给了个第三题,是说如果说要实现一个数据结构,要有insert(), delete(),medium(),mode()方法,怎么写。

这题感觉是我最后被拒的原因,因为我感觉我没正确理解他的意思。因为这里你用LinkedList()也好,ArrayList()也好,总会有一个时间复杂度会很高,后面结束的时候想想可能是想让我比较每种结构的优缺点。

我当时是写了一个Arraylist的,他问如果找中位数怎么办,是不是会time complexity很高,然后我说每个结构都会有缺点,是个trade off。

最后时间也不够,因为是额外加的,草草结束了这题。


其实答完感觉还可以,不过最后还是挂了。. Waral 博客有更多文章,
.本文原创自1point3acres论坛
Move on了,不过HR还是很nice,今天电话告知我挂了之后问我要不要点学习资料,还发了学习资料,然后说8到12个月以后再见。 整体对google的招聘印象很好

评分

2

查看全部评分

duduhaha 发表于 2016-4-20 12:16:59 | 显示全部楼层
mode()是干啥的?

第三题用TreeMap就行了吧
回复 支持 反对

使用道具 举报

Dream_Hunter 发表于 2016-4-20 12:27:22 | 显示全部楼层
duduhaha 发表于 2016-4-20 12:16
mode()是干啥的?
.本文原创自1point3acres论坛
第三题用TreeMap就行了吧

mode是求众数。也就是出现次数最多的数。这样需要返回所有的可能的mode嘛?
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-20 13:55:56 | 显示全部楼层
第一个题用异或做可以么,相加还是会溢出的吧,如果string很大的话
回复 支持 反对

使用道具 举报

 楼主| lvlingsheng 发表于 2016-4-20 13:57:31 | 显示全部楼层
mingzhou1987 发表于 2016-4-20 13:55-google 1point3acres
第一个题用异或做可以么,相加还是会溢出的吧,如果string很大的话

异或应该也可以的
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-20 14:42:14 | 显示全部楼层
第一题两个string相同字符对应的index也一样吗?
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-20 14:42:41 | 显示全部楼层
请问 找mode element 有什么efficient的方法么
回复 支持 反对

使用道具 举报

 楼主| lvlingsheng 发表于 2016-4-20 14:43:13 | 显示全部楼层
caiqi8877 发表于 2016-4-20 14:42
第一题两个string相同字符对应的index也一样吗?

没错的
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| lvlingsheng 发表于 2016-4-20 14:43:57 | 显示全部楼层
adiggo 发表于 2016-4-20 14:42
请问 找mode element 有什么efficient的方法么

这里我觉得不管用什么数据结构,总会有问题的,要不就是mode差,要不就是insert差,要不就是找中位数差,应该是想让你讲trade off吧
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-22 06:59:24 | 显示全部楼层
我觉得第二题可能面试官想考的是BST + Max Heap. 每个node里面加一个count就可以了,这样找中数,平均数都是O(1)  insert和delete是lgN
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-22 07:17:58 | 显示全部楼层
hidden_track 发表于 2016-4-22 06:59. 1point 3acres 论坛
我觉得第二题可能面试官想考的是BST + Max Heap. 每个node里面加一个count就可以了,这样找中数,平均数都 ...

两个priority queue可以很容易的找到medium,但是加上count之后,好像也得挨个挨个看哪个node是众数?可以写一下代码参考一下吗?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-22 09:30:22 | 显示全部楼层
hidden_track 发表于 2016-4-22 06:59
我觉得第二题可能面试官想考的是BST + Max Heap. 每个node里面加一个count就可以了,这样找中数,平均数都 ...

我觉得你的想法应该是对的,所有操作时间都是lgN,只不过BST的delete相对比较不好写呀。

补充内容 (2016-4-22 10:25):
仔细一想,最大堆也不好写,insert和delete分别该对最大堆做什么?求教
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-22 10:01:33 | 显示全部楼层
yueliu2366 发表于 2016-4-22 09:30. 留学申请论坛-一亩三分地
我觉得你的想法应该是对的,所有操作时间都是lgN,只不过BST的delete相对比较不好写呀。

要我面,直接打开普林斯顿老头的代码开抄。。。。。。思想不难就是写起来麻烦点
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-22 10:38:21 | 显示全部楼层
yueliu2366 发表于 2016-4-22 09:30
我觉得你的想法应该是对的,所有操作时间都是lgN,只不过BST的delete相对比较不好写呀。

补充内容 (2016- ...

堆的话insert. delete确实比较麻烦....但我觉得面试官看思路吧....实在不行就先写个BST的版本,然后O(n)的时间找mode。。最后在提下用heap可以优化到O(1)
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-4-23 04:09:53 | 显示全部楼层
hidden_track 发表于 2016-4-22 06:59
我觉得第二题可能面试官想考的是BST + Max Heap. 每个node里面加一个count就可以了,这样找中数,平均数都 ...
.本文原创自1point3acres论坛
找的不是平均数, 是medium, 用tree的话, 不能O(1)吧?
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-4-23 04:11:49 | 显示全部楼层
Mark6 发表于 2016-4-22 07:17-google 1point3acres
两个priority queue可以很容易的找到medium,但是加上count之后,好像也得挨个挨个看哪个node是众数?可 ...

不需要挨个看找众数, 只需要保存当前众数的count, 每次加入一个新的值的时候,比较count和众数的count, 并更新

补充内容 (2016-4-23 04:12):
不过需要用另外的数据结构保存每个数的Count
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-23 04:27:56 | 显示全部楼层
众数的部分搞一个HashMap<Integer, Integer> num----count;
再搞一个HashMap<Integer, HashSet<Integer>> count----num;. more info on 1point3acres
两个凑一块维护.

中位数的话,一个MinHeap, 一个MaxHeap. 维护size差小于1...
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-23 05:03:05 | 显示全部楼层
hyj143 发表于 2016-4-23 04:11
不需要挨个看找众数, 只需要保存当前众数的count, 每次加入一个新的值的时候,比较count和众数的count ...

有道理!那在delete的时候也得更新,那如果到时delete到了当前的众数的节点,也就是当前众数不再是众数了,那还得挨个扫描剩下的所有的节点? 来源一亩.三分地论坛.

如果另外用一个heap 按每个数的count建堆怎么样?用来找众数。 来源一亩.三分地论坛.
然后另外两个heap 按每个数自身的大小建堆,用来找medium。。
回复 支持 反对

使用道具 举报

helloc93 发表于 2016-4-23 05:56:29 | 显示全部楼层
楼主可以分享下学习资料吗?google一直是dream,准备申他家全职
chhoward93@gmail.com
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-4-23 06:21:30 | 显示全部楼层
Mark6 发表于 2016-4-23 05:03
有道理!那在delete的时候也得更新,那如果到时delete到了当前的众数的节点,也就是当前众数不再是众数了 ...

对, 应该就是这样, 每次的操作都是Logn
我觉得从时间复杂度上来说, 这个应该很有优势了。 不顾占用空间有点大
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-25 02:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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