一亩三分地论坛

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

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

Google 10/8 电面

[复制链接] |试试Instant~ |关注本帖
小柯西 发表于 2015-10-16 09:05:00 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
10月8号下午面的,背靠背2轮,3个工作日后收到邮件说进入host match。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

自己运气比较好,碰到的都是常规题。

第一轮是个国人大哥,Search Infrastructure组,是我比较感兴趣的组,后来还聊了会,感觉很不错。
上来给了个warmup,给两个字符串,知道其中一个字符串多出一个字母,除此之外与另一个字符串完全相同,求找出那个多出的字符串。
follow up, 如果这两个字符各自shuffle,如何找出那个多出来的字符。要求给2种解法,一个是排序,一个用hashmap,时间换空间,空间换时间。
follow up,能不能用 constant space解决。

全都要写code。整个过程交流很顺畅,国人大哥也很满意,结束的时候给我的反馈让我觉得有戏。.鏈枃鍘熷垱鑷1point3acres璁哄潧

第二轮来了个白人小哥,Youtube的。. 1point3acres.com/bbs
第一道题是判断两个给定的数组是否互为permutation。同样要求给两种解法,时间换空间,空间换时间。
第二道题,longest path in binary tree。path可以起止与任意一个节点。
过程也比较愉快,最后还讨论了下youtube的watch next功能,算是有说有笑地结束。

现在就等match了。

发上来造福大家,希望能帮自己攒攒人品!!!

评分

6

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 小柯西 发表于 2015-10-17 05:10:38 | 显示全部楼层
czxttkl 发表于 2015-10-16 20:43
第一轮的“能不能用 constant space解决“ 怎么做呀 LZ

用xor操作做的,这题其实是leetcode single number的变体
回复 支持 2 反对 0

使用道具 举报

caffery24 发表于 2015-10-23 11:12:57 | 显示全部楼层
snowwolf 发表于 2015-10-23 11:10. 1point3acres.com/bbs
public char findExtraChar (String a, String b) {
        char sum=0;
        for (int i=0;i

就是其实xor所有的,剩下的就是了吧
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2015-10-16 10:22:15 | 显示全部楼层
楼主在哪边面的?
回复 支持 反对

使用道具 举报

 楼主| 小柯西 发表于 2015-10-16 11:28:26 | 显示全部楼层
say543 发表于 2015-10-16 10:22
楼主在哪边面的?

我是电面啊
回复 支持 反对

使用道具 举报

czxttkl 发表于 2015-10-16 20:43:38 | 显示全部楼层
第一轮的“能不能用 constant space解决“ 怎么做呀 LZ
回复 支持 反对

使用道具 举报

slaink 发表于 2015-10-16 22:24:38 | 显示全部楼层
czxttkl 发表于 2015-10-16 20:43
第一轮的“能不能用 constant space解决“ 怎么做呀 LZ

ASCII range是constant,所以bucket是constant space?
回复 支持 反对

使用道具 举报

slaink 发表于 2015-10-17 06:13:10 | 显示全部楼层
小柯西 发表于 2015-10-17 05:10
用xor操作做的,这题其实是leetcode single number的变体

能具体说一下吗?比如 "a" 与 "aa" 两个字符串

补充内容 (2015-10-17 06:28):. Waral 鍗氬鏈夋洿澶氭枃绔,
明白了,唯一的那个不同的是在两个字符串内出现次数为奇数的。
回复 支持 反对

使用道具 举报

TGGOGO 发表于 2015-10-17 06:47:00 | 显示全部楼层
"要求给2种解法,一个是排序,一个用hashmap,时间换空间,空间换时间“ 是什么意思?如果排序的话时间是O(nlogn), space: O(n)。如果用hashmap,时间是O(n), space: O(n)。不知道我这么理解对吗?
回复 支持 反对

使用道具 举报

 楼主| 小柯西 发表于 2015-10-17 08:41:20 | 显示全部楼层
TGGOGO 发表于 2015-10-17 06:47
"要求给2种解法,一个是排序,一个用hashmap,时间换空间,空间换时间“ 是什么意思?如果排序的话时间是O( ...

对的,其实我当时给出两种解法的时候我特别说明了,python sorted字符串以后会生成一个新的数组,其实换也没达到换空间的目的,但是其他语言中如果string是mutable的,那就可以认为没用额外空间
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-18 09:34:11 | 显示全部楼层
求问第二轮第二题longest path是什么意思?节点最多么?还是和最大?
回复 支持 反对

使用道具 举报

xuweineo 发表于 2015-10-20 04:05:19 | 显示全部楼层
顶一顶小柯西
回复 支持 反对

使用道具 举报

 楼主| 小柯西 发表于 2015-10-20 06:24:12 | 显示全部楼层

被顶得好舒服~~
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-10-20 13:24:45 | 显示全部楼层
楼主是New Grad吗?不用onsite就host match了?还是说host match之后onsite?
回复 支持 反对

使用道具 举报

 楼主| 小柯西 发表于 2015-10-20 13:29:59 | 显示全部楼层
snowwolf 发表于 2015-10-20 13:24
楼主是New Grad吗?不用onsite就host match了?还是说host match之后onsite?

我面的是实习的。。
回复 支持 反对

使用道具 举报

JoeWest 发表于 2015-10-21 03:49:58 | 显示全部楼层
恭喜楼主了~
有个问题,第二轮的第一题和第一轮问题本质是一样的吧?都可以用sort和hashmap解决?
先谢过了~
回复 支持 反对

使用道具 举报

caffery24 发表于 2015-10-21 04:04:00 | 显示全部楼层
第一问constant求思路。。。
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-10-23 10:41:02 | 显示全部楼层
请问 longest path in binary tree 是必定叶子节点 到 叶子节点 而且经过 root 吧 🍃
回复 支持 反对

使用道具 举报

 楼主| 小柯西 发表于 2015-10-23 11:05:20 | 显示全部楼层
mmliu 发表于 2015-10-23 10:41
请问 longest path in binary tree 是必定叶子节点 到 叶子节点 而且经过 root 吧 🍃

可以其实于任意一点,未必经过root
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-10-23 11:10:52 | 显示全部楼层
caffery24 发表于 2015-10-21 04:04
第一问constant求思路。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
public char findExtraChar (String a, String b) {
        char sum=0;
. From 1point 3acres bbs        for (int i=0;i<Math.max(a.length(),b.length());i++) {
                char c1,c2;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                c1 = (i<a.length())?a.charAt(i):0;
                c2 = (i<b.length())?b.charAt(i):0;
                sum += c1-c2;
        }
        return (sum>0)?sum:-sum;
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 07:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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