一亩三分地论坛

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

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

7/20 google面经

[复制链接] |试试Instant~ |关注本帖
pengpengche 发表于 2016-7-24 06:53:30 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
7/20号面的google,感觉估计跪了第一轮是个中国阿姐,问的是经典题目3a3b decompress,我开始刷面经的时候觉得这题很简单,就没做,结果就跪在这轮,当时我写了版代码,有bug,处理不了20a这种情况,然后当时我就比较蒙,试了几个方法也没做出来。后来还是有bug,估计是脑袋还没醒吧。。。当时就觉得跪定了。
.1point3acres缃第二轮是个中国大哥带一个中国shadow,给我类似一个set<string> 里面类似于iaaaan,annnnb,addddb,这种字符串,iaaaan可以表示为i4n,然后传入一个字符串判断是否set中存在大于一个缩写和传入缩写相同,follow up是如果set里每个string都有最短缩写形式,但这种形式不能出现两次,否则就要换种形式出现,比如本来annnnb可以表示为6但是addddb也可以表示为6,所以6就不能用了,annnb得表示为an3b,adddb得表示为ad3b,输入一个string,判断这个string的最短缩写。我当时用dfs解决的,感觉面试官本来也没想明白正确解法,也说不出来什么,让我给了几个testcases.鏈枃鍘熷垱鑷1point3acres璁哄潧
第三轮是个烙印,给我一个字符串ecec。。。,和一个k值,让我找出包含k个不同值的最长字符串,hashmap加two pointer。follow up:问我如果有大写,怎么判断,我感觉他是胡问的,可能当时没准备后续题,然后我说lower一下不就行了,他说不然 more space, 我给了个解法,完事,还剩十分钟,聊了会天,他走了
第四轮白人妹子,让我找出是否存在n/4的popular element,binary search 解决,然后一道ood,说一个house只知道他的邻居,然后传一本书,传回来后所有这个区域的house名字都在书上,我说bfs,dfs都行,然后给个boolean避免回传,他说如果只能传书呢,当时我说什么我也忘了,大概就是加判断,不传回父节点,他说一个house并不知道是谁传给他的,我说那干脆,把书传回去后,删除重复名字,他说名字不是唯一的,最后我说那就价格判断,收到过书的就不再收了,他表示可以,让我写一下,我写出来,她考虑了五分钟,我感觉她就是在蹭时间,后来他上去花了个循环,说这种情况你说的无法解决,我一看还真是,最后我有想了个判断,大概就是如果邻居值和父节点一样,那就跳到下一个邻居值,具体情况也想不起来了,她表示ok了,让我问了几个问题,我简单问了问。她就把我送出去了
我总体感觉后三轮都还行,第一轮我真是醉了,可能太紧张的原因,回来特别懊悔,感觉跪在个白痴题上,当时她一直跟我说话,我紧张加着急,当时就钻牛角尖了,我估计我这种情况,offer是没戏了,只能move on 了. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


补充内容 (2016-7-24 22:17):
顺便求内推啊,大家知道最近谁还招new grad么

评分

3

查看全部评分

randrand1 发表于 2016-7-24 07:27:24 | 显示全部楼层
第一题这样写可以吗?

bool isDigit(char x) {. 1point3acres.com/bbs
    return x >= '0' && x <= '9';
}

string decompress(string str) {
    string ret;
    for(int i=0; i<str.size(); ++i) {
        if (!isDigit(str[i])) {
            ret.push_back(str[i]);
            continue;
        }
        int j = i;
        while(j<str.size() && isDigit(str[j])) {
            ++j;
        }
        int count = stoi(str.substr(i,  j-i));
        for(int k=0; k<count; ++k) ret.push_back(str[j]);
        i = j;
    }
    return ret;. 1point 3acres 璁哄潧
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

zxcnn 发表于 2016-7-24 07:34:11 | 显示全部楼层
送HC了没?送了应该就有戏吧
回复 支持 反对

使用道具 举报

 楼主| pengpengche 发表于 2016-7-24 10:18:56 | 显示全部楼层
zxcnn 发表于 2016-7-24 07:34
送HC了没?送了应该就有戏吧

不知道呢,周四才面完,怎么也得等到周一才知道吧
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-7-24 12:21:35 | 显示全部楼层
话说第三题能不能用DP?
然后楼主的hashmap加双指针能不能再详细点说一下?
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-24 13:07:24 | 显示全部楼层
第四题的ood题目神马不懂? 感觉就是traversal 然后加一个visited array ? 楼主能在说说考点吗?
回复 支持 反对

使用道具 举报

zhaoweigg 发表于 2016-7-24 13:11:54 | 显示全部楼层
csushin1992 发表于 2016-7-24 12:21
话说第三题能不能用DP?
然后楼主的hashmap加双指针能不能再详细点说一下?

lc 原题: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
回复 支持 反对

使用道具 举报

 楼主| pengpengche 发表于 2016-7-24 22:14:03 | 显示全部楼层
say543 发表于 2016-7-24 13:07. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第四题的ood题目神马不懂? 感觉就是traversal 然后加一个visited array ? 楼主能在说说考点吗?

我感觉他是临时想的,因为我前面不是答了一题了,感觉没考点,就是他想起来什么就让我解决,visited肯定不能加,他说传递的参数只能是一本书,不能传数组
回复 支持 反对

使用道具 举报

 楼主| pengpengche 发表于 2016-7-24 22:14:52 | 显示全部楼层
csushin1992 发表于 2016-7-24 12:21
话说第三题能不能用DP?
然后楼主的hashmap加双指针能不能再详细点说一下?

他让返回最长数组,不是长度,dp不行,就是下面哥们分享的链接那一题
回复 支持 反对

使用道具 举报

 楼主| pengpengche 发表于 2016-7-24 22:16:22 | 显示全部楼层
randrand1 发表于 2016-7-24 07:27
第一题这样写可以吗?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
bool isDigit(char x) {
. Waral 鍗氬鏈夋洿澶氭枃绔,
应该可以吧,当时我太紧张了,大脑一片空白。。。
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-24 22:46:47 | 显示全部楼层
第一题好多变种啊...具体问你的是什么/..还有你运气真不错 好多中国人面你
回复 支持 反对

使用道具 举报

Peripatetic 发表于 2016-7-25 09:44:04 | 显示全部楼层
lz第四轮找n/4popular element怎么binary search?我只知道linear time的解法。
回复 支持 反对

使用道具 举报

sansi 发表于 2016-7-25 12:20:38 | 显示全部楼层
楼主你第四轮的题和店面的题不是同一道题么。你没有主动告诉面试官,这样可能不太好。你面的什么题其实他们都有记录的。
回复 支持 反对

使用道具 举报

 楼主| pengpengche 发表于 2016-7-25 22:24:10 | 显示全部楼层
sansi 发表于 2016-7-25 12:20
楼主你第四轮的题和店面的题不是同一道题么。你没有主动告诉面试官,这样可能不太好。你面的什么题其实他们 ...

主动告诉了,他还是让我写了一下,所以五分钟写完,他给我加了个ood。。。。所以我觉得自己好倒霉
回复 支持 反对

使用道具 举报

 楼主| pengpengche 发表于 2016-7-25 22:25:33 | 显示全部楼层
readman 发表于 2016-7-24 22:46
第一题好多变种啊...具体问你的是什么/..还有你运气真不错 好多中国人面你

我感觉我运气其实不错,但是第一轮不知道怎么搞的,google是我第一个onsite的第一轮,可能当时比较蒙吧,下面我看过好多次这道题,当时就觉得太简单了,就不想了。。。。
回复 支持 反对

使用道具 举报

 楼主| pengpengche 发表于 2016-7-25 22:26:32 | 显示全部楼层
Peripatetic 发表于 2016-7-25 09:44
lz第四轮找n/4popular element怎么binary search?我只知道linear time的解法。
. visit 1point3acres.com for more.
可以看我之前电面的帖子,里面有解释
回复 支持 反对

使用道具 举报

 楼主| pengpengche 发表于 2016-7-25 22:27:01 | 显示全部楼层
Peripatetic 发表于 2016-7-25 09:44
lz第四轮找n/4popular element怎么binary search?我只知道linear time的解法。

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴可以看我之前电面的帖子,里面有解释
回复 支持 反对

使用道具 举报

Peripatetic 发表于 2016-7-26 10:37:45 | 显示全部楼层
pengpengche 发表于 2016-7-25 22:27
可以看我之前电面的帖子,里面有解释

谢谢,我不知道数组要是有序的。要是无序的话只能线性时间了。
回复 支持 反对

使用道具 举报

zhaoweigg 发表于 2016-7-26 13:33:11 | 显示全部楼层
pengpengche 发表于 2016-7-25 22:26
可以看我之前电面的帖子,里面有解释

但是这个验证起来worst case 其实也是O(n)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 22:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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