一亩三分地论坛

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

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

Google onsite 面筋失败经验

[复制链接] |试试Instant~ |关注本帖
totolin 发表于 2015-7-17 10:35:13 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
Onsite interview
1.
[ 0 2 1
  1 0 1
0 是障碍物,2是食物,1是可走的路径。 要求着到可以走到所有食物一次最短的点。 我用bfs做出来,最后的时候他说我有个case没考虑到,就是没有最佳路径的时候怎么办。 其他的都没问题。2. given a infinite stream of real number, 随时找median. 我说用 2 heaps, 但是他说infinite的数字要infinite的空间怎么办。然后我就说2heap应该也可以,就是保证一定size把多余的扔掉。我又挣扎说了一些其他方法,都不大行。 最后他说你用2heap做做吧,我大概做了出来,然后他就给我看了个case说这个方法什么时候会失败。 他最后说其实实际应用中2heap可以用,只要n够大就行。感觉这个面试比较惨。     
3. given a probability = [.5 .1 .2 .2], label = [A B C D], write a data structure that generates the label based on the prob. 我说先找cumulative probability[.5, .6, .8 1], 然后弄个0~1之间的random数字比较过去找它的位置就好。他就说有没有更快的方法。 其实他想叫我用binary search,但是我一直以为是不是有什么O(1)的解法,浪费了一些时间后才发现原来他想要binary search, 最后弄出来了。
4. first is summary missing range problem. [0 1 2 45 99] output “3-44,46-98”。 做了出来但是做法没有最优,我说可以改,他就说我相信你可以改就下一题了。second is given a dict of words [aba, cbc], find the letter to letter probability. b->a 50%, b->c 50%. 这个做的还可以,有一个小bug
5. hamming distance between a and b, a, b < 2^64. 这题很快就做了出来。就是把a^b>>i &1  64 次。 然后他就说要想办法speed up,说给我64G的ram。我想了很久最后说可以搞个2^8的字典,然后把a^b分8段比就好。 他就说为什么用8, 然后就问我2^8的字典要用多少空间. 我没记空间大小的那些知识,所以不会做...几经提示后结论是可以用2^32的字典要4G空间,这样比两次就好。他最后又问说如果你用这个方法,但是ram只有2g,那会发生什么情况。 我就说那会有error吧。他就说什么error。我说不出来。他就说“you clearly have never used win 95 swap space”. 然后差不多就结束了。我觉的最后这个哥么应该给我差评了。

总结失败经验:
1. 应该多考虑corner case, 总是写完被人问有什么case会有问题
2. 尽量一次算法最优,像什么能用binary search的时候就不要用O(N)的
3. 一些cs基础的东西要懂,什么swap space的。转行不容易啊。。

.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-3-9 12:27):
第一题就是leetcode 317. Shortest Distance from All Buildings.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第2题是 295. Find Median from Data Stream 变种。你先把基本的做出来然后讨论一下无限数据该怎么办。我现在觉得应该是要用到reservoir sampling.

评分

3

查看全部评分

本帖被以下淘专辑推荐:

returning 发表于 2015-10-12 03:33:46 | 显示全部楼层
say543 发表于 2015-10-12 02:21
弱弱的问一下既然是求median(中位数) 为什么会有因为size 而漏掉的情况呢?还是讨论的是求mean(平均数)?

题目不是说万一数目很大怎么办?如果heap不能维护,那肯定就要估计了,对吧,一旦估计就可能漏掉一些,除非开始的估计很准确。
回复 支持 1 反对 0

使用道具 举报

 楼主| totolin 发表于 2015-7-18 06:00:11 | 显示全部楼层
UmassJin 发表于 2015-7-17 23:25. 1point3acres.com/bbs
感谢楼主分享!patpat~ 请问楼主第二道题目如果用two heaps的话,面试官指出是什么case,没有办法通过呢?

这题的奇葩点是说有无限的数字,所以heap的size要有上限n。 但是当你有上限的时候,一个一直递增的数列就会給你问题, 因为会有可能把你的median給扔掉。 . from: 1point3acres.com/bbs
第一题历遍每个食物,然后算这个食物到每个点的距离。把每个食物到不同点的距离加起来,最低的就是answer。
回复 支持 1 反对 0

使用道具 举报

547690781 发表于 2015-7-17 11:16:40 | 显示全部楼层
for problem 4, is the original array sorted?
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2015-7-17 12:00:54 | 显示全部楼层
pat pat, 楼主是什么转行?
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-17 12:19:21 | 显示全部楼层
you clearly have never used win 95 swap space
我擦, swap space都考......
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-17 12:26:24 | 显示全部楼层
given a dict of words [aba, cbc], find the letter to letter probability 求楼主解法
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-7-17 12:44:05 | 显示全部楼层
第三题的binary search是指对cumulative array search?
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-7-17 12:47:10 | 显示全部楼层
what is the 'letter to letter probability'? Is it the probabllity that two letter A and B shown up on the same word in this dictionary?
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-7-17 12:47:16 | 显示全部楼层
what is the 'letter to letter probability'? Is it the probabllity that two letter A and B shown up on the same word in this dictionary?
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-7-17 12:48:03 | 显示全部楼层
是不是用类似reverse index 的方法
回复 支持 反对

使用道具 举报

 楼主| totolin 发表于 2015-7-17 20:49:14 | 显示全部楼层
我从数学转行。第4题是sorted。 letter of probability的题目是这样, 做一个27x27的matrix, 26 个代表字母,最后一个代表开始或者结束,然后你每个字母走过去找它出现的次数,最后除一下row sum求概率就好。比如 [aba, acb],a之后出现b的机率是50%, 出现c的几率是50%。 b之后出现a的机率是50%,b最为结尾的几率是50%。 a作为开头的机率是2/3, a最为结尾的机率是1/3。

补充内容 (2015-7-18 05:50):
说错了, a-b的机率是1/3, a-c的机率是1/3, a-end的机率是1/3.
回复 支持 反对

使用道具 举报

 楼主| totolin 发表于 2015-7-17 20:51:25 | 显示全部楼层
wugoat 发表于 2015-7-17 12:44
第三题的binary search是指对cumulative array search?

是的。cumulative array 本来就是sorted的所以应该用binary search, 我没有一下就反应出来。
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-7-17 21:33:21 | 显示全部楼层
求解:
1. 第一题没有最佳路径,是指没有食物吗?

2, 第四题,第1个有没有小于O(n)的解法?
回复 支持 反对

使用道具 举报

 楼主| totolin 发表于 2015-7-17 21:51:42 来自手机 | 显示全部楼层
第一要考虑食物被隔开的情况,事先要讨论好怎么处理而不是事后被指出。题41最优是o(n).我遍了个o(n2)的
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-17 23:25:32 | 显示全部楼层
感谢楼主分享!patpat~ 请问楼主第二道题目如果用two heaps的话,面试官指出是什么case,没有办法通过呢?
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-17 23:27:12 | 显示全部楼层
另外第一题的解法是遍历所有的点,除了食物和障碍物,然后算出每个点到每个食物的距离吗?感觉这么做复杂度好高
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-7-18 00:40:13 | 显示全部楼层
第5 题,字典是什么方法呢?麻烦楼主再解释一下
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-7-18 01:14:11 | 显示全部楼层
totolin 发表于 2015-7-17 20:49
我从数学转行。第4题是sorted。 letter of probability的题目是这样, 做一个27x27的matrix, 26 个代表字 ...

多谢解释,a之后出现b的概率50%, 怎么算得
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-18 01:22:27 | 显示全部楼层
totolin 发表于 2015-7-17 20:49
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 我从数学转行。第4题是sorted。 letter of probability的题目是这样, 做一个27x27的matrix, 26 个代表字 ...

请问这题原题是什么? 就是题目怎么叙述的
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-7-18 01:59:58 | 显示全部楼层
36 楼大哥用位算法做比较阳春白雪一点,店面的时候不一定一下能想起来,我这边有个比较下里巴人的法,大家看看成不成。
代码中假设题目里字典中的词字母可以使用多次1)把目标词抽象成set(如果只能一次则抽象成map: Character, Integer)
2)把词典有短到长排列
3)遍历词典,一旦发现匹配马上返回,因为余下的都比当下的长,没必要再看
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

public class ShortestDict {
    public static void main(String[] args) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        String[] words = new String[]{"so99ort", "so1rt", "skype", "so11rt", "apppples"};

        System.out.println( new ShortestDict().getShortest("SR 456 T", words) );

    }
    public String getShortest( String s , String[] words){
            if ( s == null || s.equals("") || words == null ) {
                    return null;. visit 1point3acres.com for more.
            }
            s = s.toLowerCase();
            Comparator< String > lenC = new Comparator < String >( ){
                    public int compare(String s1, String s2 ) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                            return s1.length() - s2.length();
                    }
            };
            Arrays.sort(words, lenC);
            Set< Character > set = new HashSet< Character >();
            for ( int i = 0; i < s.length() ; ++i ) {
                    if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
                            set.add(s.charAt(i));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            }
            for ( String w : words ) {
                    w = w.toLowerCase();.鏈枃鍘熷垱鑷1point3acres璁哄潧
                    Set< Character > tmp = new HashSet<Character>(set);
                    for ( int i = 0; i < w.length(); ++i ) {
                            tmp.remove( w.charAt(i) );
                            if ( tmp.isEmpty() ) {. more info on 1point3acres.com
                                    return w;
                            }
                    }. 鍥磋鎴戜滑@1point 3 acres
            }
            return null;
    }
}
大家看看对不对

回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-7-18 02:01:26 | 显示全部楼层
发错楼了。大家无视我。。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 12:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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