一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1481|回复: 16
收起左侧

google 3.14实习面试

[复制链接] |试试Instant~ |关注本帖
ScottShao 发表于 2016-3-15 11:53:27 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
来分享一下面试经历,没有刷面经,现在非常后悔。。. from: 1point3acres.com/bbs
今天两个电面,每个面试都只做了一题。。。两个面试官都是中国人。。

第一面题目:
longgest length of substring with at most k distinct characters. 没有思路,第一个思路是brute force扫一遍,然后以每个字符做起点求最长长度。我跟面试官说一定有更优的办法。。想到了用hashmap。。但是存的value想错了。。纠结了一会儿。面试官给了提示。。存最后出现的index就行。。。。等于直接给了答案。。。。lz是不是跪了。。。。然后开始coding。。code倒是没有bug。。。.1point3acres缃
对了,中间讲第二个思路的时候,面试官有点听不懂。。说我们还是讲中文吧。。。。。。。感觉好虚第一面。。

第二面:
一个function接受string data,如果前十秒内没有出现的话,就把string打印出来。。
第一个思路是用hash table 存。。被指出几个小bug。。然后我们开始优化。 说如果有million集的数据怎么办。。我说每十秒update hashtable。。. more info on 1point3acres.com
接着优化。。要遍历hashtable 时间复杂度太高。。然后我说用queue再存一份数据,每次收到数据的适合和queue的头比较时间。。。面试官好像蛮满意的,说不能再优化了。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
总体感觉第一面有点,给出这种思路的提示是不是要跪了。。。

第二面还行。。。

评分

1

查看全部评分

Sinkle 发表于 2016-3-16 05:11:14 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
感谢!祝拿到offer!
不过不是很明白第二题问的是什么,get string print string为什么要用hashtable?
回复 支持 反对

使用道具 举报

 楼主| ScottShao 发表于 2016-3-16 05:48:04 | 显示全部楼层
关注一亩三分地微博:
Warald
Sinkle 发表于 2016-3-16 05:11-google 1point3acres
感谢!祝拿到offer!
不过不是很明白第二题问的是什么,get string print string为什么要用hashtable?
. From 1point 3acres bbs
其实是hashmap 你要记录他最后出现的时间
回复 支持 反对

使用道具 举报

valleyvalley 发表于 2016-3-16 08:27:20 | 显示全部楼层
楼主收到通知了吗?一般面完多久有通知,这个点的话?。。祝楼主拿offer!
回复 支持 反对

使用道具 举报

 楼主| ScottShao 发表于 2016-3-16 12:47:24 | 显示全部楼层
valleyvalley 发表于 2016-3-16 08:27
楼主收到通知了吗?一般面完多久有通知,这个点的话?。。祝楼主拿offer!

感谢!
还没呢 焦虑的等待中
问recruiter说一般是一周到两周,但我估计会比较快吧,因为最近面的人应该蛮少的。。
你也面了吗? 怎么样.1point3acres缃
回复 支持 反对

使用道具 举报

mackygood 发表于 2016-3-16 13:34:13 | 显示全部楼层
请问一下每十秒update hashtable的优化是什麽意思? 收到一个string再比对/更新该string的时间对每一笔不是O(1)时间複杂度吗?谢谢
回复 支持 反对

使用道具 举报

gzyeli123 发表于 2016-3-16 13:57:12 | 显示全部楼层
个人大致做了一下第一道题,攒人品。Debug了几次,感觉自己在处理细节的时候还是不是很强。对于处理如何记录一个字符出现这个问题上,其实不需要用Map,因为一共就26个字母,所以可以用数组。代码如下,这里我做了对大小写字母区别对待的处理

public int logestSubStringKDistinct(String s, int k){
                if(s!=null && !s.isEmpty()){
                        int start = 0;. From 1point 3acres bbs
                        int maxLength = 0;
                        int size = 0;
                        int[] lower = new int[26];. more info on 1point3acres.com
                        int[] upper = new int[26];
                        for(int i=0; i<s.length(); i++){
                                char tempChar = s.charAt(i);
                                int[] tempArray;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                char tempIndex;
                                if(tempChar<='z'&&tempChar>='a'){
                                        tempArray = lower;
                                        tempIndex = 'a';.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                }else{
                                        tempArray = upper;
                                        tempIndex = 'A';. visit 1point3acres.com for more.
                                }
                                . 1point 3acres 璁哄潧
                                if(tempArray[tempChar - tempIndex] > 0){
                                        tempArray[tempChar - tempIndex]++;
                                }else{
                                        tempArray[tempChar - tempIndex]++;
                                        size++;
                                        while(size>k){. from: 1point3acres.com/bbs
                                                char tempStart = s.charAt(start);
                                                start++;. visit 1point3acres.com for more.
                                                if(tempStart>='a'&&tempStart<='z'){
                                                        tempArray = lower;
                                                        tempIndex = 'a';
                                                }else{
                                                        tempArray = upper;
                                                        tempIndex = 'A';. 鍥磋鎴戜滑@1point 3 acres
                                                }
                                                if(tempArray[tempStart - tempIndex]>0){-google 1point3acres
                                                        tempArray[tempStart - tempIndex]--;
                                                        if(tempArray[tempStart - tempIndex]==0){
                                                                size--;
                                                        }
                                                }
                                        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                }
                                maxLength = Math.max(maxLength, i-start+1);
                        }
                       
                        return maxLength;. 1point 3acres 璁哄潧
                }else{. 1point 3acres 璁哄潧
                        return 0;
                }
        }


回复 支持 反对

使用道具 举报

gzyeli123 发表于 2016-3-16 13:59:31 | 显示全部楼层
做了一下第一题,个人感觉自己处理细节不是很好,所以debug了好几次。用数组来记录字符就可以免去Map的麻烦,以及可以节省时间。这里做了对大小写区别对待的处理。代码如下:

public int logestSubStringKDistinct(String s, int k){
                if(s!=null && !s.isEmpty()){
                        int start = 0;
                        int maxLength = 0;
                        int size = 0;
                        int[] lower = new int[26];. from: 1point3acres.com/bbs
                        int[] upper = new int[26];
                        for(int i=0; i<s.length(); i++){
. Waral 鍗氬鏈夋洿澶氭枃绔,                                char tempChar = s.charAt(i);
                                int[] tempArray;
                                char tempIndex;
                                if(tempChar<='z'&&tempChar>='a'){
                                        tempArray = lower;
                                        tempIndex = 'a';
                                }else{
                                        tempArray = upper;
                                        tempIndex = 'A';
                                }
                                . more info on 1point3acres.com
                                if(tempArray[tempChar - tempIndex] > 0){
                                        tempArray[tempChar - tempIndex]++;
                                }else{
                                        tempArray[tempChar - tempIndex]++;
                                        size++;
                                        while(size>k){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                                char tempStart = s.charAt(start);
                                                start++;
                                                if(tempStart>='a'&&tempStart<='z'){
                                                        tempArray = lower;
                                                        tempIndex = 'a';
                                                }else{
                                                        tempArray = upper;
                                                        tempIndex = 'A';
                                                }
                                                if(tempArray[tempStart - tempIndex]>0){
                                                        tempArray[tempStart - tempIndex]--;
                                                        if(tempArray[tempStart - tempIndex]==0){
                                                                size--;
                                                        }
                                                }
                                        }
                                }
                                maxLength = Math.max(maxLength, i-start+1);
                        }
                       
                        return maxLength;
                }else{
                        return 0;
                }
        }
回复 支持 反对

使用道具 举报

 楼主| ScottShao 发表于 2016-3-16 22:25:46 | 显示全部楼层
mackygood 发表于 2016-3-16 13:34. 1point 3acres 璁哄潧
请问一下每十秒update hashtable的优化是什麽意思? 收到一个string再比对/更新该string的时间对每一笔不是O ...

因为我们只需要过去十秒的数据 如果不更新hashtable的话 这个表的数据会很大 而且会存着之前的无用数据 所以我想每十秒更新一下hashtable 去除无用的数据。
回复 支持 反对

使用道具 举报

 楼主| ScottShao 发表于 2016-3-16 22:28:12 | 显示全部楼层
gzyeli123 发表于 2016-3-16 13:57
. 鍥磋鎴戜滑@1point 3 acres个人大致做了一下第一道题,攒人品。Debug了几次,感觉自己在处理细节的时候还是不是很强。对于处理如何记 ...
. From 1point 3acres bbs
我觉得两个数组蛮麻烦的。。。而且代码不好看
要么用256的数组,要么用map。。
为了代码整洁 我宁愿牺牲点space或时间
.鏈枃鍘熷垱鑷1point3acres璁哄潧
然后开头的empty其实可以不用写

还有我觉得这种方法可能不是最优 试试记录每个字符最后出现的index
回复 支持 反对

使用道具 举报

valleyvalley 发表于 2016-3-16 23:25:53 | 显示全部楼层
ScottShao 发表于 2016-3-16 12:47
感谢!
还没呢 焦虑的等待中 . 1point 3acres 璁哄潧
问recruiter说一般是一周到两周,但我估计会比较快吧,因为最近 ...

恩恩,昨天刚刚面的,也是在焦虑的等消息,第一面还好,是个国人小哥,很nice,第二面应该是个白人小哥,hin冷漠,基本不说话,我说我的思路他一直表示听不懂,就一直我说啊说啊,他一直不懂不懂。。。而且只面了一题。。唉。。听说google是看两个面试的average?我也不知道。。。保佑保佑
回复 支持 反对

使用道具 举报

 楼主| ScottShao 发表于 2016-3-16 23:59:42 | 显示全部楼层
valleyvalley 发表于 2016-3-16 23:25. from: 1point3acres.com/bbs
恩恩,昨天刚刚面的,也是在焦虑的等消息,第一面还好,是个国人小哥,很nice,第二面应该是个白人小哥, ...

我也碰到国人小哥 小哥一直笑笑 很和蔼的样子 而且很给提示。。 我也有一面非常一般
你面的是实习吗
回复 支持 反对

使用道具 举报

valleyvalley 发表于 2016-3-17 00:21:09 | 显示全部楼层
ScottShao 发表于 2016-3-16 23:59. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我也碰到国人小哥 小哥一直笑笑 很和蔼的样子 而且很给提示。。 我也有一面非常一般
你面的是实习吗

对的,国人小哥对国人比较好。。我是面实习,听说即使过了也没坑了。。但是不管怎样还是想能过了先。。你呢?
回复 支持 反对

使用道具 举报

 楼主| ScottShao 发表于 2016-3-17 00:22:16 | 显示全部楼层
valleyvalley 发表于 2016-3-17 00:21
对的,国人小哥对国人比较好。。我是面实习,听说即使过了也没坑了。。但是不管怎样还是想能过了先。。你 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我也是实习啊。。
已经没坑了吗
我听说还有一点点坑啊。。。
回复 支持 反对

使用道具 举报

valleyvalley 发表于 2016-3-17 01:18:06 | 显示全部楼层
ScottShao 发表于 2016-3-17 00:22-google 1point3acres
我也是实习啊。。
已经没坑了吗
我听说还有一点点坑啊。。。

听大家的说法各不相同,大概是还有很少的坑,但是pool里还有很多的人。。所以概率比较小吧。。
回复 支持 反对

使用道具 举报

 楼主| ScottShao 发表于 2016-3-17 07:00:57 | 显示全部楼层
valleyvalley 发表于 2016-3-17 01:18. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
听大家的说法各不相同,大概是还有很少的坑,但是pool里还有很多的人。。所以概率比较小吧。。

嗯哼 能不能加个联系方式 有消息通知一下?
回复 支持 反对

使用道具 举报

valleyvalley 发表于 2016-3-17 09:16:22 | 显示全部楼层
ScottShao 发表于 2016-3-17 07:00
嗯哼 能不能加个联系方式 有消息通知一下?
.1point3acres缃
好的,不过我刚刚试了一下,我好像新人权限太低,不能发消息你,要不你发消息给我你的qq或者微信或者别的?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-4-30 20:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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