google 3.14实习面试

来分享一下面试经历，没有刷面经，现在非常后悔。。
今天两个电面，每个面试都只做了一题。。。两个面试官都是中国人。。

第一面题目：
longgest length of substring with at most k distinct characters. 没有思路，第一个思路是brute force扫一遍，然后以每个字符做起点求最长长度。我跟面试官说一定有更优的办

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

一份数据，每次收到数据的适合和queue的头比较时间。。。面试官好像蛮满意的，说不能再优化了。。

总体感觉第一面有点，给出这种思路的提示是不是要跪了。。。

第二面还行。。。

个人大致做了一下第一道题，攒人品。Debug了几次，感觉自己在处理细节的时候还是不是很强。对于处理如何记录一个字符出现这个问题上，其实不需要用Map，因为一共就26个字母，所以可以用数组。代码如下，这里我做了对大小写字母区别对待的处理

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];
                        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';
                                }
                               
                                if(tempArray[tempChar - tempIndex] > 0){
                                        tempArray[tempChar - tempIndex]++;
                                }else{
                                        tempArray[tempChar - tempIndex]++;
                                        size++;
                                        while(size>k){
                                                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;
                }
        }

做了一下第一题，个人感觉自己处理细节不是很好，所以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];
                        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';
                                }
                               
                                if(tempArray[tempChar - tempIndex] > 0){
                                        tempArray[tempChar - tempIndex]++;
                                }else{
                                        tempArray[tempChar - tempIndex]++;
                                        size++;
                                        while(size>k){
                                                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 12:47
感谢！
还没呢 焦虑的等待中
问recruiter说一般是一周到两周，但我估计会比较快吧，因为最近 ...

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

感谢！祝拿到offer！
不过不是很明白第二题问的是什么，get string print string为什么要用hashtable？

Sinkle 发表于 2016-3-16 05:11
感谢！祝拿到offer！
不过不是很明白第二题问的是什么，get string print string为什么要用hashtable？

其实是hashmap 你要记录他最后出现的时间

楼主收到通知了吗？一般面完多久有通知，这个点的话？。。祝楼主拿offer！

valleyvalley 发表于 2016-3-16 08:27
楼主收到通知了吗？一般面完多久有通知，这个点的话？。。祝楼主拿offer！

感谢！
还没呢 焦虑的等待中
问recruiter说一般是一周到两周，但我估计会比较快吧，因为最近面的人应该蛮少的。。
你也面了吗？ 怎么样

请问一下每十秒update hashtable的优化是什麽意思? 收到一个string再比对/更新该string的时间对每一笔不是O(1)时间複杂度吗?谢谢

mackygood 发表于 2016-3-16 13:34
请问一下每十秒update hashtable的优化是什麽意思? 收到一个string再比对/更新该string的时间对每一笔不是O ...

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

gzyeli123 发表于 2016-3-16 13:57
个人大致做了一下第一道题，攒人品。Debug了几次，感觉自己在处理细节的时候还是不是很强。对于处理如何记 ...

我觉得两个数组蛮麻烦的。。。而且代码不好看
要么用256的数组，要么用map。。
为了代码整洁 我宁愿牺牲点space或时间

然后开头的empty其实可以不用写

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