一亩三分地论坛

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

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

google onsite

[复制链接] |试试Instant~ |关注本帖
nickxiu 发表于 2014-3-11 07:05:04 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Other

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

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

x
电面传送门(感觉该合成一个的。。可惜当时写电面面经的时候没想到能到这边来。。):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
http://www.1point3acres.com/bbs/thread-84618-1-1.html
.1point3acres缃
一共四轮,俩亚裔俩烙印,中午吃饭也是烙印。口音都挺好,没神马障碍
[hide=10]
第一轮
先说了说简历上的project,然后做题
给一个set,里面是一堆pair,每个pair里是两个string,一个first,一个second,假设这堆pair能够构成一个树状结构,按照一定的格式打印这棵树
first-second关系类似paretnt-child关系
eg. From 1point 3acres bbs
set: (a, b) (b, c) (a, d) (d, e) (d, f) (d, g).鏈枃鍘熷垱鑷1point3acres璁哄潧
树状结构是root = a, root.left = b, root.right = d blah blah
打印结果:[space] 就是一个空格
a
[space]b
[space][space]c. from: 1point3acres.com/bbs
[space]d
[space][space]e
[space][space]f. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
[space][space]g

第二轮
pow(int x, int y)
1<=x<=9
1<=y<=99
想了半天发现数太大了int或者long都装不下,只能返回string
然后写了一个loop了y次的方法,然后说说时间复杂度,问有没有改进的,我开始觉得可能x不停平方可能快点,但是算了下貌似时间复杂度是一样的。。然后他说这就是为啥他一开始专门说了不要求效率,能写对就行。。难道真的是一样的。。. visit 1point3acres.com for more.
剩了点时间叫我定义一个priority queue的interface,假设别人实现代码后,我用啥test cases检验。. from: 1point3acres.com/bbs

午饭
和人聊着聊着他突然说如果你挂了6个月之后可以重新申。。我擦这是说明已经挂了么。。。

第三轮
给string a, string b,判断b里面是否存在子字符串是a的anagram。. from: 1point3acres.com/bbs
最开始写了个isAna(string a, string b)的函数,判断两个字符串是不是anagram。然后在主函数里移动window,调用isAna检查window里面的substring是不是anagram。然后问我有没有啥改进的,我想了半天觉得可以在isAna外面维持一个hashmap,每次移动window的时候加一个新字符减一个最后的字符,然后和目标字符串比较,但是时间复杂度还是没变。。十分郁闷的问他怎么搞,他说你这时间复杂度已经够低了。。改进的点是不要每次都在isAna里面建一个新的hashmap,并且不要每次pass一个substring给isAna,pass一个start point什么的就行。。。. from: 1point3acres.com/bbs
第二题是给一个int[] array, e.g {1,5,0,6}和一个int target,e.g. target = 21;
问是否存在某种分法把array分成几部分,每部分看成一个int,这几部分加起来等于target。e.g. {1,5}{0}{6},三部分加起来是21。{1,5}{0,6}也是21。target=25则false
没有写完整的程序,就说了说recursion怎么跑,每一步怎么传的参数
类似这样. From 1point 3acres bbs
rec(int[] array, int start, int target, int prev) {
for(i from start -> array.length) {
    /*
    get the number from start to this i
    */
    rec(array, i+1, target, sum of prev and number);
}
}-google 1point3acres
问了问时间复杂度貌似是exponential。。。然后问他我真不知道怎么改进他说没办法。。不是吧。。一副只是不想跟我多说的样子。。

第四轮
给一个整形数组,找离数组的平均值最近的数
写完后问如果该成一个可能随时加数进去的list,怎么找最近的数。分别说说怎么实现add(int)和findNearestAvg()。我想了想说大概用list或者用tree维持一个sorted list然后再二分查找,但是感觉不能同时保证add和find都是logN的。。然后他觉得是对的就下一题了。。
就是leetcode上面的maxPoint,但是返回的不是最多的穿过的点的数目,返回这条线

[\hide]


补充内容 (2014-4-6 14:28):
这个星期一收到口头通知说过了hc,星期五给了个暂定的package
(居然过了真意外。。。多谢大家的祝福)

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| nickxiu 发表于 2014-3-11 07:06:23 | 显示全部楼层
啊貌似没设置好分数呢。。智商硬伤了。。
回复 支持 反对

使用道具 举报

readman 发表于 2014-3-11 07:35:49 | 显示全部楼层
Scala?

第二题是给一个int[] array, e.g {1,5,0,6}和一个int target,e.g. target = 21; <----这题感觉是树吧? 为什么会是exp速度? 烙印没任何hint么?
回复 支持 反对

使用道具 举报

growingapple 发表于 2014-3-11 16:21:10 | 显示全部楼层
楼主有好消息了吗?祝楼主好运
回复 支持 反对

使用道具 举报

 楼主| nickxiu 发表于 2014-3-12 07:30:07 | 显示全部楼层

他说他也觉得是exp的。。就不了了之了
回复 支持 反对

使用道具 举报

doveonthewing 发表于 2014-3-12 08:21:58 | 显示全部楼层
nickxiu 发表于 2014-3-12 07:30
他说他也觉得是exp的。。就不了了之了

感觉就是exp的,有一些剪枝的优化,如果只要求一种解法,是不是可以尝试A*之类的搜索?
回复 支持 反对

使用道具 举报

lixiang.xjtu 发表于 2014-3-12 10:22:53 | 显示全部楼层
Dynamic Programming 搞定那个数组的题
回复 支持 反对

使用道具 举报

Lisepher 发表于 2014-3-14 10:43:11 | 显示全部楼层
楼主面的时候都是算法题吗?有没有OOP和System Design的题? 小弟下下周onsite
祝楼主好运!
回复 支持 反对

使用道具 举报

dimitrilyyl 发表于 2014-3-14 10:56:34 | 显示全部楼层
求问楼主选的是哪三个方向的职位?算法吗?
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-3-14 11:12:46 | 显示全部楼层
第一题是用有向图来做,时间复杂度是O(n), 这里n是表示pair的对数。需要O(n)的extra memory来做辅助的hashtable。
第二题,pow(int x, int y)用二进制,可能会好一点。O(logxlogy)的bit-operations。. 鍥磋鎴戜滑@1point 3 acres
第三题,好像leetcode的原题。
第四题,思考中,应该有一个O(n)的算法。求指点
回复 支持 反对

使用道具 举报

 楼主| nickxiu 发表于 2014-3-14 11:40:06 | 显示全部楼层
Lisepher 发表于 2014-3-14 10:43 . 1point3acres.com/bbs
楼主面的时候都是算法题吗?有没有OOP和System Design的题? 小弟下下周onsite. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
祝楼主好运!

题都在上面了,能和design有关的估计就上面说的哪个interface的东西了。。其他的全是算法 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
祝你好运~
回复 支持 反对

使用道具 举报

 楼主| nickxiu 发表于 2014-3-14 11:41:55 | 显示全部楼层
dimitrilyyl 发表于 2014-3-14 10:56
求问楼主选的是哪三个方向的职位?算法吗?

当时给我的貌似就general developer, tester, site reliability engineer这三个吧,也没说算法不算法啥的。我选了前后俩,也不知道面的是哪个,估计是developer吧
回复 支持 反对

使用道具 举报

 楼主| nickxiu 发表于 2014-3-14 11:45:42 | 显示全部楼层
averillzheng 发表于 2014-3-14 11:12
第一题是用有向图来做,时间复杂度是O(n), 这里n是表示pair的对数。需要O(n)的extra memory来做辅助的hash ...

恩我第一题跟你一样的做法,只是当时傻逼了绕了好久才搞懂题意。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
第四题我当时也觉得就是一dp,但是发现貌似不对。。然后就到现在还没想出更好的办法了。。
回复 支持 反对

使用道具 举报

dimitrilyyl 发表于 2014-3-14 11:50:18 | 显示全部楼层
nickxiu 发表于 2014-3-14 11:41
当时给我的貌似就general developer, tester, site reliability engineer这三个吧,也没说算法不算法啥的 ...

好像我表述的有点问题,后面还有选3个最熟悉的领域好像有Advanced Algorithms,Database Internal,Networking之类的,不知道这个选择对面试有没有影响
回复 支持 反对

使用道具 举报

 楼主| nickxiu 发表于 2014-3-14 13:50:46 | 显示全部楼层
dimitrilyyl 发表于 2014-3-14 11:50
好像我表述的有点问题,后面还有选3个最熟悉的领域好像有Advanced Algorithms,Database Internal,Netwo ...

我选的networking, distributed system, adv algo,但是貌似前两个基本上没问到。。
回复 支持 反对

使用道具 举报

MackeyZheng 发表于 2014-3-14 17:08:40 | 显示全部楼层
赞一个!
回复 支持 反对

使用道具 举报

kang1415926 发表于 2014-3-17 23:01:26 | 显示全部楼层
祝楼主好运!
回复 支持 反对

使用道具 举报

猫咪老师 发表于 2014-3-22 21:26:41 | 显示全部楼层
楼主有消息了木?他家电话还是邮件通知尼?
回复 支持 反对

使用道具 举报

 楼主| nickxiu 发表于 2014-3-23 03:55:22 | 显示全部楼层
猫咪老师 发表于 2014-3-22 21:26
楼主有消息了木?他家电话还是邮件通知尼?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
还完全木有音信啊。。也不敢催。。
回复 支持 反对

使用道具 举报

猫咪老师 发表于 2014-3-23 05:20:38 | 显示全部楼层
nickxiu 发表于 2014-3-23 03:55
还完全木有音信啊。。也不敢催。。

没有消息就是好消息啊....我比你面的还晚一天,12号,好忐忑
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 00:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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