google面经# JobHunting - 待字闺中
I*c
1 楼
1. 老白
求一个数的因子 比如24 因子是 2，3，4，6，8，12
这道题是最可惜的，一开始太紧张，有点懵，没有直接想到可以把24化成几个素数来求
解。而是用了一个递归的办法，写到一半才想到可以用别的办法，而且代码还有一个
bug，就是2，3的因子数是空集，如果输入是 n = 6的话，如何处理。写完递归以后，
老白又让写了化成素数的解法。然后老白问n＝32 和 n=35两种情况下，哪个计算量会
少一点
2. 烙印
给定两个字符串 abczde abcde ，他们的差别在于第一个字符串插入了一个z，然后问
题就是如何找到那个z。
我提了两个方法。 方法1: 每一个字符比较，找到了不同的字符，就比较和后面的字符
以确定哪个字符是插入字符。
方法2: 使用hashmap
然后烙印深入问了方法1，有哪些特殊情况。 我说 1. 如果一个字符串是空。 2.插入
字符是长字符里的最后一个元素。 然后他说还有一种特殊情况，插入字符是长字符里
的倒数第二个元素
然后烙印说假设有一个函数，宣称可以使用比O(n)更好的办法解决这个问题，问如何测
试这个函数是否正确。我说了可以输入aaaaabaaaa, aaaaaaaaa。然后他说b的位置如何
确定，我说randomize.
接着烙印说在特殊的情况下，比如ababacbabab, ababababab, 没有连续两个字符相同
，如何提高效率。我说使用binary search. 写了代码。
烙印接着问如果使用hashmap, 描述一下java是如何实现hashmap的。然后问如何有效的
扫描hashmap里的keys. 我说可以增加一个linked list去记录keys.
面试完，想想用XOR也是可以做的。
3. lunch
4. 讨论了dissertation. 准备的东西只讲了一半时间就到了。那白人哥们还真看了论
文。
5. 中国大哥
中国大哥很nice。 非常感谢。
第一道题是测试一个n*n里每一行，每一列，两个对角线的元素之和是否相等。然后问
了测试例子，举了一个正常的返回true的例子，返回false的例子。一个空集.
但是忘了测试如果这不是一个n*n的例子。
第二道题是leetcode上Paint Fence的变形题。做完以后大哥问是不是见过。
6. 中国小哥
系统设计: 给定一个很大byte stream在disk里，如何排序
我开始没有注意到是byte stream,就是讲了常规的merge sort. 后来补充了使用
counting sort. 然后又问了如果有多个处理器，如何加快计算。
我说就是每个处理器维护一个array来进行counting sort.
设计一个iterator来进行树的post order traversal
总结
0. 自己功夫没有到家。
1. leetcode是有用的
2. 最近一两个月花了很多时间看system design, 码有点生，策略不对。还是要以写码
为主。
3. 白板写码真的是和电脑写码不一样，完全两种体验，一定要另外练习。我以后要多
在纸上写写才行。
4. 对于easy medium的题目，一定要多想想test case, corner case.
求一个数的因子 比如24 因子是 2，3，4，6，8，12
这道题是最可惜的，一开始太紧张，有点懵，没有直接想到可以把24化成几个素数来求
解。而是用了一个递归的办法，写到一半才想到可以用别的办法，而且代码还有一个
bug，就是2，3的因子数是空集，如果输入是 n = 6的话，如何处理。写完递归以后，
老白又让写了化成素数的解法。然后老白问n＝32 和 n=35两种情况下，哪个计算量会
少一点
2. 烙印
给定两个字符串 abczde abcde ，他们的差别在于第一个字符串插入了一个z，然后问
题就是如何找到那个z。
我提了两个方法。 方法1: 每一个字符比较，找到了不同的字符，就比较和后面的字符
以确定哪个字符是插入字符。
方法2: 使用hashmap
然后烙印深入问了方法1，有哪些特殊情况。 我说 1. 如果一个字符串是空。 2.插入
字符是长字符里的最后一个元素。 然后他说还有一种特殊情况，插入字符是长字符里
的倒数第二个元素
然后烙印说假设有一个函数，宣称可以使用比O(n)更好的办法解决这个问题，问如何测
试这个函数是否正确。我说了可以输入aaaaabaaaa, aaaaaaaaa。然后他说b的位置如何
确定，我说randomize.
接着烙印说在特殊的情况下，比如ababacbabab, ababababab, 没有连续两个字符相同
，如何提高效率。我说使用binary search. 写了代码。
烙印接着问如果使用hashmap, 描述一下java是如何实现hashmap的。然后问如何有效的
扫描hashmap里的keys. 我说可以增加一个linked list去记录keys.
面试完，想想用XOR也是可以做的。
3. lunch
4. 讨论了dissertation. 准备的东西只讲了一半时间就到了。那白人哥们还真看了论
文。
5. 中国大哥
中国大哥很nice。 非常感谢。
第一道题是测试一个n*n里每一行，每一列，两个对角线的元素之和是否相等。然后问
了测试例子，举了一个正常的返回true的例子，返回false的例子。一个空集.
但是忘了测试如果这不是一个n*n的例子。
第二道题是leetcode上Paint Fence的变形题。做完以后大哥问是不是见过。
6. 中国小哥
系统设计: 给定一个很大byte stream在disk里，如何排序
我开始没有注意到是byte stream,就是讲了常规的merge sort. 后来补充了使用
counting sort. 然后又问了如果有多个处理器，如何加快计算。
我说就是每个处理器维护一个array来进行counting sort.
设计一个iterator来进行树的post order traversal
总结
0. 自己功夫没有到家。
1. leetcode是有用的
2. 最近一两个月花了很多时间看system design, 码有点生，策略不对。还是要以写码
为主。
3. 白板写码真的是和电脑写码不一样，完全两种体验，一定要另外练习。我以后要多
在纸上写写才行。
4. 对于easy medium的题目，一定要多想想test case, corner case.
