Massive Algorithms: Google Interview Misc Part 6

http://www.1point3acres.com/bbs/thread-191823-1-1.html
“3a2[mtv]ac”, decompress to: aaamtvmtvac，括号可以嵌套。
这个我觉得不是很难，大概花了15分钟理清了思路并写好了代码，大概就是找匹配括号递归解，面试官也找不到bug表示认同。

但吊诡的地方来了，面试官说把这种字符串compress回去...这显然有多种情况，于是我问是不是要求压缩后最短，面试官说肯定越短越好。
比如对于aaaa, 肯定4a比2[aa]好。

我思考了一会，只想到了枚举所有substring及其连续出现次数，然后选择match出现次数最多的substring作为压缩。
面试官觉得复杂度高了，问还能不能优化，感觉他自己语气也不是很肯定，提示了一下我有没有类似two pointer的解法。
我个人觉得这道题真心不简单，没什么想法，一直卡到了这轮结束...

Round2
国人小哥，非常友善
1 在BST中给定[min, max] 求在此值域里的所有node之和. 简单递归.
2 一个数组里找某个index, 使sum[:i] == sum[i+1:], 也是经典题。我一开始用了O(n) space, follow up就是优化成了O(1).
这里代码写的有点慢，但都在没给提示的前提下bug free了。
3 上道题的变种，此时要求数组和带有权重，每个nums[i]需要乘以一个weight, 这个weight等于和某个index的距离。
eg:
nums = [1, 3, 5, 7, 8]
假如当前处理到nums[2], 则leftsum = 1 * 2 + 3 * 1 = 5, rightsum = 7 * 1 + 8 * 2 = 23这道题其实也不难，我找到思路后跟面试官说了，他表示赞同还举了举大拇指（人真是太好了），但时间不够我写代码了，只写了几行。

Round3
白人小叔+Shadow
1 walls and gates的变种，要求离各个gate距离之和最近的grid。经典题了.
2 randomize and return an array with value from 0 to n. 经典题了.两道很快写完了之后，白人小哥看了一会都没发现什么问题，就说good, 然后就聊项目。
项目问题问得不深，所以足足聊了3个，他一直态度都不错但也没表现出对我的项目非常感兴趣的样子，就说good, cool之类的。

Round4
1 buildfile with tag and dependency, return one of the invalid tags. Toposort搞之，但回家之后才发现自己搞错了复杂度...这里感觉会特别悲剧。2 给一堆有序的单词和一个prefix, 叫你从单词里找出range是以这个prefix开头的, 我第一感觉是binary search。回头想了一下这题要是多次查询的话应该是用Trie, 但我写完代码之后已经时间不多，他也没问到。
两道题他都叫我写了好几个testcase验证，都没发现问题，但感觉他有拖时间的嫌疑.
http://www.1point3acres.com/bbs/thread-105862-1-1.html

第一轮先扯扯淡，问为什么喜欢Google之类的，然后问了问实习的code review过程，然后看了他写的一段代码主要是求某个数字是不是素数之类的，
要求code review，问代码有没啥问题，算法有啥改进没，巴拉巴拉扯了一堆。接着就出了一道题就是说google有很多文档是javascript格式，
比如bar.js, foo.js, 里面各自定义自己的foo, bar, 可是bar.js文件运行需要foo.js作为requirement, 要求输出array类似于['foo.js','bar.js'],
就是作为requirement的文件必须排在前面，原谅lz比较啰嗦，follow up的问题就是如果foo.js里面定义了foo1,foo2,..., bar.js里面只列出了foo2, 但是输出还是['foo.js','bar.js']要怎么办。
第二轮对lz简直就是个disaster，就是一个房间也就是二维矩阵里面有obstacle，已知有k个点，求房间中离这k个点距离之和最短的那个点。
然后lz死活就只能想到recursion, 复杂度是o(n^k+1), 当时脑子就短路，死活想不到更优解法，忘了直接用bfs，经面试官提醒也没有写完代码

http://www.1point3acres.com/bbs/thread-112534-1-1.html
1. Given class tapeReader

class tapeReader {
public:
int readAndAdvance() {...};
bool moreToRead() {...};
}
[3, 4, 8, 7]
class tapeReader t;
t.readAndAdvance(); //3.鏈枃鍘熷垱鑷�1point3acres璁哄潧
t.readAndAdvance(); //4
t.readAndAdvance(); //8

寫一個class peekTapeReader，裡面需有一個新function(peek())，定義如下：

class peekTapeReader {
public:
int peek() {...};
}. Waral 鍗氬鏈夋洿澶氭枃绔�,
[3, 4, 8, 7]
class peekTapeReader p;
p.peek(); //3
p.peek(); //3
p.readAndAdvance(); //3. From 1point 3acres bbs
p.peek(); //4

2. 標準code interview題
給一個車牌號碼(美國的)，以及一個dictionary，請找出dictionary裡含有所有該車牌號碼裡的所有英文字母(case insensitive)的最短字串。ex:
車牌 RO 1287 ["rolling", "real", "WhaT", "rOad"] => "rOad"
follow up:
(1) 如果dictionary裡有上百萬個字，該如何加速?
(2) 如果dictionary有上百萬個字，然後給你上千個車牌號碼，要你回傳相對應的最短字串，該如何optimize?

-- build count map for each word in the list.
-- put each word and its count map to TreeMap<key(word length)>.

3. 標準code interview題
給所有tree的edges(parent, child)，重建tree之後回傳root，或NULL if it's invalid input

edges{ (1, 2), (1, 3), (1, 4)};. 1point 3acres 璁哄潧
1
/ | \

复制代码

這題主要考對invalid case的思維周密程度，我想我表現得沒很好

http://www.1point3acres.com/bbs/thread-114594-1-1.html
给你一组Treenode，他们每个有一个id，一个parentId，一个value，让你输出所有subtree的sum of value
注意这个是没有children node的，只有parentId。她先问是top down还是bottom up，因为只有parentId所以是bottom up，然后输出吧，其实就是层遍历，但是重点是如何找每一层的node，什么时候跳出循环，她hint了我，然后写的时候出了java api的bugs。。不过还是立刻改过来了，然后问运行时间，结果中途电话还断了一次。。居然面试还能超时5分钟。。。也是醉了

2. 一个纯正美式发音的小哥哥，一上来非常aggressive，根本不问你算法题，让你说一个做过的最有意思的project，我说了dht，他一听dht，好家伙撞枪口上了，立刻问实现了什么功能，我说find insert delete。。，他问如果node going down怎么办，我说backup replicas，他不过瘾，接着问，如果用backup，你那些功能运行效率会有什么变化，我突然间蒙了一下，然后反应上来是多update了好几个database。。。然后他觉得还不爽，让写一个code来找finger。。。还好我记得怎么搞。。写完了他满意了
然后问你知道bst么，我说知道。。。然后他说那你写个linkedlist reverse in place吧。。。（我靠）。。然后写完了他说ok，你有啥问题，我随便提了一个，他回答完了说没事儿没事儿不问问题that‘s fine，然后开心的写feedback去了

3. 第三个是个类似大叔的美国人，上来先让讲了一个你认为有困难的project，然后说怎么克服他的。。。之后问abstract和interface区别，然后是char array reverse in place，最后来了一道大神题，就是那道plate和dictionary那道，我写出来了brutal算法，就是O（N＊M），然后他问能优化么，他妈的到现在我也不知道怎么优化，米群网里的答案也没提过有优化的事儿啊，他非常肯定的说有O（N ＋ M）算法，他说可以对dictionary进行处理。。。（求教大神到底怎么搞的啊，难道是用trie？？？？），他说没事，很多人都没到得了brutal算法这一步。。。。我算明白了，这是要据我的节奏

http://www.1point3acres.com/bbs/thread-181048-1-1.html
第一轮很简单，是输出连续递增（必须每一个数字比前一个大1）subsequence的最大长度，比如  1,2,3,4,5,6,10,11,12,100,200答案是 6 （1,2,3,4,5,6）

题是linked list 表示两个整数，相加，不能修改指针，所以就不能reverse了
写出来后问了些问题，感觉代码有些小bug
http://www.1point3acres.com/bbs/thread-183346-1-1.html
题目是给你一个board，里面存储user的信息，user有id和socre。
board有adduser(id, score)(返回add进去的user当前的rank), findByRank(k) (这个返回id)。
Add如果本身已经有id在board中，需要对这个id的score进行update。
开始想的是用map加binary search中，中途脑子短路，写到一半发现似乎做不出来了。。。。(面完之后想想，这个方法应该是做的出来的。)
面试官说应该要用binary search tree做，听到这里基本就知道gg了。
然后就是悲剧的开始，只会做binary search tree的添加点的操作，update和delete 操作基本忘干净了，不记得具体的步骤了。

http://www.1point3acres.com/bbs/thread-171867-1-1.html
第一个是问我比如有一个输出哈喽沃德的程序，在命令行里敲下执行命令之后，在屏幕上显示哈喽沃德的字符之前，是怎样一个详细的过程？（比如程序编译，以及输入输出流之类的），这个问题我基础不牢靠吭哧吭哧瞎答了一气。

第二个问题就是代码，让实现一个ringbuffer。心里窃喜。但由于些许紧张写的过程并不是非常流畅，也是吭哧吭哧写完了。
- 主要就是实现一个写入函数，一个读取函数（读取最旧的一个值）。
- 写完之后让写一下测试，口述一下运行过程。
- 然后说一下每个函数的复杂度，（这个复杂度实现出来肯定就是O（1）了）

http://www.1point3acres.com/bbs/thread-161293-1-1.html
第一轮：一个中年白人，表情比较严肃，让我介绍了一下自己和现在在做的projects。剩下不到半小时，让我设计一个rate limiter，就是给定每秒接受request的最大次数，当一个新的request来的时候怎么判断是否接受。这题看似很简单，但你只要想到用queue或者其他数据结构去存储request，你就输了。我事后问了很多人，他们的思路跟我一样，都是用数据结构去存储request，这样当存储的request过多会有很多问题，是个死胡同。我在网上找了经典答案，确实非常巧妙，不用任何数据结构，也不涉及多线程问题 http://stackoverflow.com/questions/667508/whats-a-good-rate-limiting-algorithm。当时我沿着错误的思路修修补补，面试官怎么都不满意，总提出漏洞，看来这完全不是他想要的答案。这题我认为你做过就会做，没做过的话在面试中打死你都想不到这么巧妙的解。我事后感觉第一轮被亮红灯无疑了。

第二轮：一个看起来像阿拉伯人的三四十岁的男人，问了我几个behavioral questions，当时受第一轮影响心情很不好，回答这些问题也没能很有激情。剩下大概半小时，问了我一个挺简单的算法题，按照定义好的priority，给字符串排序。比如定义好的priority list是[o, r, d, e, r]，给定字符串是"horse"，得到结果是"orehs"，即如果字符串中的字符出现在priority list中，按priority排序，剩下字符append到后面。这题我一遍就用最优解把所有的edge case都考虑到了，面试官看完我的解基本没有异议。此轮过后士气有所恢复。

第三轮：一个白人老头儿，一脸笑呵呵的。上来就给我出了一道算法题，给你一段字符串，你怎么把它压缩成指定的格式，比如“adddbffffsssssscvvvvv”压缩成“a3xdb4xf6xsc5xv”。这题看似很简单，但坑很深。我本来还暗自高兴，三下五除二就把代码完整写出，当时想的更多的是怎么把它在时间和空间上优化，后来才感觉到这题分明是在考 edge case。比如在压缩“x”的时候怎么办，在压缩“3xd”的时候出现歧义怎么办，压缩数字的时候又怎么办。我提出用转义字符，但他说不能改变压缩格式。这题我后来做了很多改进来处理edge case，有些是自己想到的，有些是他提示的。不知道这种题这种表现算如何，是不是不应该被面试官指正啊，但这题一气呵成处理一切 edge case 似乎也太难了。
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
第四轮：一个白人小年轻，也是一脸笑嘻嘻的，但仍然掩饰不住问题的刁钻。让我设计 load balancer，这题我之前大概看过，但也不是这次刷题遇到的。这题比较开放，我讲了几种大概的思路，但他刁钻的提出让我从多线程的角度去分析，如果一下来了太多的 load request 怎么办，如果你与 server 之间的沟通有延迟怎么办，怎么设置安全锁来保证你得到的当前各个 server 的状态是实时的。我去，我记得当时我也就看了关于 load balancer 的几种处理思路，没有考虑这么多的细节，答得不是很好。从来刷题也没刷到过考多线程这么深的问题，不知多线程问题在Google是不是很多被问到，还是我太背啊。

第五轮：一个黑人大叔，面无表情。让我设计一个service，当得到一个新数据，如何更新最近得到的N个数据的平均值。我真是受leetcode毒害太深，上来就按照根据固定输入得到固定输出的模式来写算法，后来发现这不是个简单的算法题，更新平均值算法本身很简单，难点在怎么在service中存储最近得到的数据。后来我用一个固定大小的queue来存储最近的数据，新的数据来了以后，最老的数据出队，新的数据进去，然后更新平均值。这题跟第一题属于同一类型，但比第一题简单，都是service设计，输入是源源不断的，而不是像leetcode里的算法题那样一次输入数据然后得到结果。

结果：肯定是fail了啊，第一题就废了，后面也没能力挽狂澜。这次之所以感觉考得奇怪，就是觉得跟leetcode的题目差别太大，比如第一题和最后一题都是让你设计service，而不是写一个算法，设计的时候更多要从class角度考虑，而非method层面。第二题和第三题算是leetcode式的算法题，但第三题坑太多。第四题是设计题，我本有所准备，但没想到它不是那种oop设计这么简单，线程问题被问了一大堆，汗！
http://www.mitbbs.com/article_t/JobHunting/32907123.html
1. Binary Search Tree, right next() function on each node
   还有一个follow up question想不起来了
2. Leetcode , merge interval 变种
   find mean in two sorted list with same length
   一个Design问题
3. 基本都是design的问题，design google recommendation
4. 设计/测试replicate cache的方法
5. 一个martrix，每行每列都是sorted，找到前kth 个
merge sorted list只用到了行排序，没有列排序

1、communication的问题，这个你需要找个人mock一下
2、做题太慢
3、Design没有答到点子上
4、你现在level很高，但表现一般，HC觉得没法按照你现在level雇你

http://www.mitbbs.com/article_t/JobHunting/33106617.html

1. Integral image

其实就是生成一个2D矩阵，里面的每一个点
(i,j)都记录了从这个点到(0,0)所形成的矩形的元素之和。这道题其实是最简单的。

2. 一条线段长度L，雨滴直径D，雨滴从不同位置等概率下降到线段上，模拟一下这个情况，求出多少雨滴可以把线段覆盖完全

雨滴那道题是让你写个程序模拟一下这个场景，不是直接给出数学公式。

3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度。把那些从没成为过最高优先度的alarm删除。

写了一下第三题，基本思路是类似于sweep-line算法，用一个max heap保持当前权重最
高的alarm，按照时间顺序扫描，碰到alarm start event, add alarm to the heap,
for alarm end event,
remove the alarm from the heap. keep track the top of the heap, which
should be kept.

public class WeightedInterval {
    public List<Alarm> removeAlarms(List<Alarm> alarms)
    {
        SortedMap<Integer, List<Alarm>> times = new TreeMap<>();
        for(Alarm alarm : alarms)
        {
            if(!times.containsKey(alarm.start)) times.put(alarm.start, new
ArrayList<>());
            times.get(alarm.start).add(alarm);
            if(!times.containsKey(alarm.end)) times.put(alarm.end, new
ArrayList<>());
            times.get(alarm.end).add(alarm);
        }

        List<Alarm> ret = new ArrayList<>();
        PriorityQueue<Alarm> pq = new PriorityQueue<>((a, b) -> {
            if (a.weight == b.weight)
            {
                return Integer.compare(a.start, b.start);
            }
            return Integer.compare(b.weight, a.weight);
        });

        for(Map.Entry<Integer, List<Alarm>> time : times.entrySet())
        {
            for(Alarm alarm : time.getValue())
            {
                if(alarm.start == time.getKey())
                {
                    pq.add(alarm);
                }
                else
                {
                    pq.remove(alarm);
                }
            }

            if(!pq.isEmpty()) pq.peek().remove = false;
        }

        ret.addAll(alarms.stream().filter(alarm -> alarm.remove).collect(
Collectors.toList()));

        return ret;
    }

    public static class Alarm {
        final int start;
        final int end;
        final int weight;
        boolean remove;
        public Alarm(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
            remove = true;
        }
    }
}
http://www.jiuzhang.com/qa/339/

有一个需要clarify的地方是，如果和其他的alert一起同时成为最高的优先度，这种需要去掉么？

下面的解答基于不需要去掉与其他alarm同时成为最高优先度的那些alarms：

将起始时间终止，终止时间和对应的优先度以及alarm的id打散。一个alarm会变成两个item：(start_time, alarm_id, priority, is_start=true), (end_time, alarm_id, priority, is_start=false)
把所有的2N个items排序。按照第一个field time从小到大排序。
依次访问排序后的每个item
1. 如果is_start=true，那么 check priority 是否在某个集合中，如果不在的话就create一个entry 给这个priority，将alarm_id添加到该priority的一个list里，表示当前是该priority的alarms有哪些。entry包括两个部分，一个是priority，作为key，第二个是一个list，表示有哪些alarms，作为value。
2. 如果is_start=false，那么找到集合中priority对应的entry，然后把alarm_id从里面删除，如果entry里的list空了，就在集合中删除这条entry。
3. 上面的操作完成后，检查目前集合中priority最高的entry，把这个entry里的alarms都标记为成为过最高优先级的。
最后再check所有的alarm，看看哪些没有被标记过。

这中间有一个优化需要做的是，需要把list分为已经标记过成为最高优先级的，和没有标记过成为最高优先级的。否则反复标记同一个alarm成为过最高优先级会耗费时间复杂度。这个list，本身因为需要支持插入和删除的话，那么其实实际上应该是两个hashset。

整体的时间复杂度是(NlogN + NlogP)，N为alarms的个数，P为Priority的个数，NlogN是排序的复杂度，NlogP是后面统计处理的时候的复杂度。至于这个集合既需要做key-value的查询，又需要找最大值，那么自然是HashHeap。这种数据机构，我们会在《九章算法强化班》中讲解。

这种算法的名字叫做：扫描线算法。是Google的大爱。

类似的题目是这题，也是Google出过的题：
http://www.lintcode.com/en/problem/building-outline/

4. rotate array by k steps（leetcode），要最优解：reverse不能用
5. （1）俄罗斯方块，求出正在下落的物体和底部的最短距离。（2）一幅图有一系列二维的点，判断此图是否对程

对称那道题要考虑很多corner case，比如说所有点在一直线上，那么也是对称的，因
为每个点和自己对称。中心对称不考虑。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=144709&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
Phone interview 1:
白人小哥.给一个Interval的class, 就是一个区间,左闭右开,比如 [1, 3) 意思是从1到3除了3的所有interger. 让我在这个class里implement一个method, 判断与另一个Interval是否有overlapping.
第二问是写一个method, 返回在Interval 1而不在Interval 2的区域.
一道如此简单的题...因为我前面实在太紧张了全身是汗面的吭吭哧哧...面完以后我都准备move on了, 看来小哥最后还是放了我一码让我有了二面.

Phone interview 2:
白人小哥.更简单了... Leetcode原题Plus One
如果现在Google要release全新版本的Chrome, 我要怎么保证这个新的Chrome全方位的work? 意思就是测试些什么,怎么测试这个新版本的Chrome,才能放心的release出去.
最后他还开心的问了我的名字到底怎么念,我就知道大概有个底儿了~

Onsite:

第一轮: 印度哥哥. 大早上的堵了一个多小时开过去腿都麻了,上来就开始coding,直接蒙圈儿.
第一题, 给一个array比如[4,2,1,3,5],根据这个array现在我们能有了一个新的array => 每个数是在原array里, 在它左边的所有比它大的number的个数,就是[0,1,2,1,0]. 题目是现在给了这个[0,1,2,1,0]要求原array, 原来array的range是1~n
第二题, 知不知道binary search? 但是现在array是unsorted的可是依然看做sorted array来做binary search, 返回在array里面所有可以在这种情况下binary search出来的数.

第二轮: 韩国哥哥.
经典的地里出现过的String压缩编码解码类似题, 后悔当时看到没有好好写过一遍.给一个String比如"abcdfffffffxyz", 写两个methods, encode和decode. encode就是比如"fffffff"变成"7xf",decode就是要变为原字符串.我说"ff"怎么办,他说变成"2xf"你不觉得更长了吗? 我才明白了,应该是encoded后的String要比原来的短,不然为啥要encode,的亏我问了这个问题...然后又问他,如果原String本来就是"5xt"这种结构, decode不就无法辨认了吗?他说很高兴你提出了这个问题,但是不用管它,一会再讨论,先写吧.
写完以后他就问我如果原String本来就是"5xt"这种结构,我encode应该怎么处理? 我就傻了... 因为一直觉得encode后的字符串长度一定要比原来的短,所以根本想不出来他要的解法. 说了四五种方法他都不满意, 最后给我hint说,要是有个"1xt"这样的你怎么处理? 当时脑洞大开想出来了... 其实是要变成三个"1xt"这种结构, 比如原String就是"5xq", 就encode成为"1x51xx1xq"就好了. 但是这种方法违背了encode后要变短的rule,所以我是真没想出来.....
还讨论了好多种情况, 最后一种是"1aaaaa"这种情况怎么变, 我说"1x15xa". 他说这是6个字符,能不能只用5个? 实在想不出来,这时候第三个小哥进来了,韩国哥哥就过来告诉我说,其实看做1a和aaaa两部分encode就好...
面完我就觉得跪了....

第三轮: 中国小哥.
第一个问题是测试的,比较简单. 测试Calculator,input就是比如俩数一个operator, 都有什么case, 怎么测,应该有什么预期结果或错误.
第二题, 一个array,rearrange成为另一个array, 现在给了这两个array, 求是怎么变化成第二个array的. 挺简单的就用了Hashmap秒了...
然后问我,那现在给你原array,也知道了是怎么变化的了,所以我们现在可以用原array求出变化后的array对吗? 但是我要run这个method好多次比如k次, 怎么最快能求出array被 rearrange了k次以后的结果? 最后我就推倒出求LCM.
面完他亲切的用中文跟我说,我是他见过面的最好的,时间复杂度最低trade off也说的好. 谢谢小哥给了我信心~么么哒~

第四轮: 印度姐姐.
假装没有准备的样子现场想题目... 谢谢姐姐没有对我下死手T T
海上有一片岛, 每个岛就是一个node, 岛和岛之间有的连着有的没连着. 所有连着的岛是一个Group. 求在这片海上, 包含岛屿个数最小的group的岛的个数,和最大的group的岛的个数. 就是返回两个个数值, 肯定就是int[2]嘛. 先讨论了用什么数据结构存储, 跟她说了trade off. 然后开始写.
全程想给我挑错, 不断质疑我的代码... 还好我这一轮在高压下还是写的极其顺畅, 一个bug没有出现, 对她也是笑脸相迎, 躲过一劫...

第五轮: 中国大哥. 竟然中文给我面试, 也是感动哭...
第一题, 一个二维数组代表了一个岛. 周围都是海, 岛的左侧和上侧通向Pacific, 右侧和下侧通向Atlantic. 每个数字都代表了那个位置的海拔高度. 现在下雨了, 雨只有从海拔高的地儿能流向海拔低或者一样的地儿. 返回岛上的分水岭的点, 就是在某个/某些点上, 雨水既能流进Pacific, 又能流向Atlantic. 大哥可能也知道白板写不下,让我写纸上. 足足写了4页A4纸,当然字也写的大...手都写疼了...
第二题, 给个Google map, 你就测吧...

我的offer效率很高我完全没想到, 5个工作日从onsite到签offer, 真心感谢hr姐姐. 因为我有个WalmartLabs的competing offer正好是那天截止, hr的意思也是我的feedback很好,所以HC没有犹豫,也马上有组想要我, 所以hr加班加点在进HC当天就跟offer team合作把offer弄出来了. 这里再次感谢各位面试官对我高抬贵手, 以及WalmartLabs....

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

下面是求职总结.

自我介绍一下. 毕业快两年了. Master读的是普通学校的水专业Information Science. 我是极其水,几乎零基础,项目都抱别人大腿, 当时没有好好学习知识, 现在别提多后悔了... 去年开始找工作的时候, 连HashMap是什么都不知道... Leetcode就刷了七十道, 总拿女生不要太累了要不就这样吧这种谎言安慰自己... 找到了现在的SDET工作,公司和待遇自然也是好不了. 今年三月开始奋发图强, 八月初开始投简历, 十月十五日当天拿到Google和WalmartLabs的两个offer (对没错,WalmartLabs真的不给考虑时间,当天deadline). 总之是零基础, 靠努力学习和坚持不懈活了下来. 如果你跟我的情况类似,希望我的经验可以帮到你~
CC150. 看了一遍version 5. 据说新版本v6页数多了一倍... 还是希望大家坚持把每一章都看了,对新手帮助很大.

Leetcode. (没有做过Lintcode等等, 我觉得选一个刷题网站全弄会了其实就可以...) 三月到十月共刷5遍,订了subscription,每遍仔细做了每一道题. 过程确实相当痛苦,每天还要上班,一有空就得刷题,周末也不得停歇. 尤其前两遍,基本都是看完答案背着写一遍的,可能也是因为我比较笨... 但是幸亏坚持下来了~ 当我做到第四遍的时候, 有一种通了的感觉, 即使拿到一道新题, 也能比较快的有思路. 这里还是希望我们找工作的朋友们好好刷Leetcode, 弄通弄懂算法精髓, 举一反三. 不要有侥幸思想, 非牛人刷了一遍就想找到非常满意工作的真的少之又少.

Geeksforgeeks. 讲解非常清楚明白易懂, 尤其在学习数据结构和算法上面帮助很大. 它对于很多算法都会有一系列的问题的讲解, 看过之后基本对于某一部分的题目都没什么问题了. 比如Trie,BST的讲解, longest common subsequence一个系列,KMP算法等等,我都是得益于它. 一个算法想不明白,可以先去搜搜geeksforgeeks有没有讲解~

Data structure & Algorithms. 最基础也是最重要的部分, 千万别小瞧基础. 为什么一再强调数据结构与算法基础? 就算刷了十遍leetcode/lintcde等等刷题网站,面试还是会有没见过的题的. 遇到完全没见过的题该怎么办,没有强大的基础知识储备,怎么看穿这道题的本质,怎么很快有思路? 一切都要靠基础, 甚至比刷题本身更重要.
每个数据结构一定要做到彻底明白概念, 结构, 功能, 怎么用. 一定要亲自在IDE里面至少implement一遍!! 推荐书目: 我精读了Data Structures and Algorithms in JAVA. 非常适合初学者, 每个数据结构的实现和用法都写的极其详细. 精读了每一章, 并且implement了两遍里面所有数据结构. 我也听有的人说精读Introductions to Algorithms, 但是这本书感觉不是很适合我这种初学者... 如果你有基础或者是科班出身,面试之前详读Intro to Algo我觉得会很受用的.
刷题的过程中,会遇到很多没见过的算法和数据结构的用法. 比如说graph, 在leetcode里面会有用到dfs, bfs, topology, dijkstra等等算法, 每当遇到一种没见过的, 就脱离这道题, 去网上搜索这究竟是什么, 怎么实现的, 怎么用, 在IDE里面自己亲自实现算法本身, 很生疏的算法要多实现几遍. 这个过程是让我提高最大最快的一步.

Java Conception. 内推我Google的大牛朋友让我看Thinking in Java和Effective Java这两本书. 虽然没有看完,但是确实是非常棒的两本书, 尤其是Thinking in Java. 据说每看一遍都会对Java有全新的认识, 非常值得一看. 如果实在没有时间,只是为了面试紧急补课, 至少看会这个网站的Java面试题 http://www.programmerinterview.com/

Big Data. 今年以来,我发现几乎所有公司的面试都不约而同的添加了大数据相关的问题,就连Walmartlabs的SDET职位的面试中都遇到了,不得不说大数据真是现在一个很猛的trend... 在面Bloomberg的时候就是因为大数据的问题不会而吃了亏挂了,回家以后恶补了很久...
这里推荐这个blog,很多朋友都应该看过: http://blog.csdn.net/v_july_v/article/details/7382693我很想知道写这个blog的是个怎样的人,真心膜拜... 他的总结几乎囊括了所有大数据方面的知识背景,实在赞叹. 对于这个帖子里面提到的知识点,他都有专门介绍的链接,全面又方便. 如果想面试无敌的话,每个知识点都要自己多查资料弄懂,每道题都自己过一遍. 对于里面提到的不同方法要多比较, 每种方法什么时候适用, trade off是什么都要清楚. 重中之重是Map Reduce和External sort.

Thread & Locks. 考得不多但是面ebay碰到了. 主要知识点: thread和process区别, multithread, lock, semaphore, 对resource分配, deadlock, 怎么解决/预防deadlock. 还有BlockingQueue 和 Producer-Consumer经典题要会implement.这里有几个经典问题:
http://www.careercup.com/question?id=4783236498587648
http://www.careercup.com/question?id=5652784707796992

OOD. 老老实实实现了两遍Singleton, Factory, 还有MVC pattern. 设计一个class应该也算在OOD范围里: 写过无数遍LRU, Trie, Iterator, BST以及变种, BlockingQueue等等, 生怕被问到...

System Design. 这个对不住大家,我最后没面到过系统设计,所以不太知道自己这点准备到底充不充分... 如果你要面Facebook几乎肯定是要考系统设计的,还是得好好准备. 一定要看FB的engineering blog, 看的越多越好. 基础的概念至少要会: load balancer, cache, memcache, consistent hashing, round robin, master slave, sharding, pre-computed, map reduce, difference with SQL/NoSQL.... 有很多牛人总结的系统设计帖,我就不多置喙了,这里推荐几个帖子.http://massivetechinterview.blogspot.com/2015/06/itint5.html
http://www.mitbbs.com/article_t/JobHunting/32777529.html
http://blog.csdn.net/sigh1988/article/details/9790337
还有这个公开课,太棒了,新手入门必备,谢谢成哥推荐~ https://www.udacity.com/course/viewer#!/c-cs253/l-48737165
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137081&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
Phone1
讓你完成一個 class 的幾個function

class AvgLatency{
AvgLatency(List<String) methods, int window_size)
double GetAvgLatency(String method)
AddLatency(String method, int latency)
}

window_size , 如果 window = 3 當他要 average 的時候, 只有最近三個有效
每個 method 的 window_size 都設定一樣就可以

ex:
avgLatency({"GET","POST","DELETE"}, 3)
add("GET", 10)
add("GET", 6)
add("GET", 6)
add("GET", 6)
GetAvgLatency("GET")  = 6

Phone2
findGaps

[0, 1, 2, 50, 52, 75], n=100
3-49,51,53-74,76-99

Onsite
Round1 一個英國人,一個國人 shadow
UTF8 validation
http://codereview.stackexchange.com/questions/59428/validating-utf-8-byte-array

0xxxxxxx  single byte
10xxxxxx  continous byte
110xxxxx  2 bytes sequence
1110xxxx  3 bytes sequence
11110xxx  4 bytes sequence
111110xx  5 bytes sequence
1111110x  6 bytes sequence
11111110  7 bytes sequence
11111111  8 bytes sequence

Valid 0xxxxxxx
Valid 110xxxxx 10xxxxxx
Valid 1110xxxx 10xxxxxx 10xxxxxx
Valid 0xxxxxxx 110xxxxx 10xxxxxx 0xxxxxxx
invalid  10xxxxxx
invalid  110xxxxx 0xxxxxxx 10xxxxxx
invalid  110xxxxx

Round2 韓國人
pattern 可以跨 strings, 但是必須要是連續的, 注意是 iterable, 所以是不能回頭的
我是 stringBuffer 去保存已經走過的部分, 如果不 match rewind 的時候就從 stringBuffer 裡面的 character 開始 check
不夠再從 iterater 拿

boolean contains(String pattern, Iterable<String> strs)
ex:
pattern: "abc"
strs : "ab", "cd"  -> true
strs : "aa", "bcd" -> true
strs : "ab", "ac"  -> false

這一輪寫到最後一秒, 算是寫完了, 也跟他討論了一下複雜度
事後想想有個資料結構用錯, 導致答案會有問題, 估計跪就跪在這輪了
这个题目把所有iterator里面的string连起来，用一个KMP是不是就可以？

Round3 美國人-正妹姐姐
Symetric rotation number
boolean checkNum(String num)
ex: 16891 旋轉 180 以後還是 180
確認這個數有沒有符合這個規則

Follow Up: List<String> genNum(int len)

產生所有這個長度以下的所有組合
ex: len=3, {0,1,8,00,11,88,69,96,000,010,080,101,111,181,808,818,888,609,619,689,906,916,986}

Round4 美國人-小帥哥
Leetcode: count islands

後面的 follow up 都是討論而已, 沒寫 code
Follow up: 如果是大地圖怎麼處理, 要你切 map, 考慮每個 submap 之間的關係
Follow up2: 平行化處理, 這個條件, 可能會讓你前面所想方法要重新思考

這時剩下15分鐘, 他就說再來個 follow up 好了 = =, 跟大圖無關, 一樣是 count island, 假設已經做了第一次的處理
Follow up3: 如果他現在要新增島到地圖上, 請回傳最新的 count
ex: int add(int x, int y), the function should return the new count

Follow up3.1 這個 function 能不能做到比 O(N*N) 還要好? (N為 map 邊長)
就是當初在 count islands 的時候把每個 island 都建成一顆 tree
所以再判斷新加上去的 island 周圍的時候, 只要判斷周圍的 island 是不是有 common ancestor O(lgN)
如果是分開的兩個島, 現在被新的島串起來了的話, 就將兩顆 tree 接起來就好

當整張地圖的資訊無法一次處理, 必須要分批處理的時候, 你可以想象就是 google map 這樣的 scale, 你要如何 count islands?
How do you divide the map? How do you optimize your algorithm on memory or time complexity?

4.3Follow up 大概是这样吧。并查集，但是时间复杂度好难算啊，Find说是当成alpha函数的反函数，基本是常数

话说onsite Prob2，即使不暴力，最坏也要回溯到头，StringBuffer也要存下所有，这个和暴力没啥区别吧，而且暴力好写，确实面试官不让全部append然后kmp么

第一關的 UTF8 validation
一開始真的很緊張, 我跌跌撞撞地想出一個算法, 我用了 shift 和 counter 不算是什麼 clean code, 但 at least 給出一個解法, 這關表現平平

第二關的 pattern matching
我花了很長的時間跟他解釋我的算法, 到最後寫的時間不太夠, 到最後才發現我的算法有個錯誤, 會導致最後的答案有誤

你前輩的經驗沒錯, 題目都不會算太難, 都是考些基本的算法和解題能力, 我只有真的後兩關才真的算是答得得心應手, 我認為面試的重點不一定要 "豪不費力", 但必須要隨時保持你思路的清晰, 能夠自己分析自己的算法, 自己找出自己算法的盲點, 當你能夠清晰的表達你的算法, 不是胡言亂語的時候, 面試官通常都會給你足夠的提示讓你找出盲點。

最後的建議 "Be confident", 在解題的時候把你所想清楚的表達出來
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=145396&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
问题是给定一个9位的键盘，

1 2 3
4 5 6
7 8 9
只有中间没有其他键的两个键才能相连，比如1可以连 2 4 5 6 8 但不能连 3 7 9
但是如果中间键被使用了，那就可以连，比如5已经被使用了，那1就可以连9
每个键只能用一次，给定一个长度L，求问有多少unique path with length L

见我卡住了就说先写brute force吧，然后再提示说用回溯法
第一轮那题是只需要count，还是print out all unique path？除了DFS有什么好方法吗？

1. 给定一个函数 boolean isWord(string s)，可以判断这个字符串是否是一个合法的英语词汇
然后给一个初始的字符串s，只能对它做删除字母的操作，求问最长的合法的英语词汇
//没有处理一个键只能用一次

private int count = 0;
public int getNumberOfKeyboardUniquePath(int n) {
if (n <= 0) {
return 0;. visit 1point3acres.com for more.
}
String[] map = {"24568", "1345679", "24567", "1235789", "12346789", "12356789", "24568", "1345679", "24568"};
helper(map, new StringBuilder(), n, "123456789");
return count;
}
private void helper(String[] map, StringBuilder sb, int n, String choices) {. visit 1point3acres.com for more.
if (sb.length() == n) {
count++;
return;
}
for (int i = 0; i < choices.length(); i++) {
char c = choices.charAt(i);
sb.append(c);
helper(map, sb, n, map[(int)(c - '1')]);
sb.deleteCharAt(sb.length() - 1);
}
}

2. 输入一个数组，输出和【0,99】之间的gap，leetcode原题

3. 输入一个二进制int，两个digit之间交换位置
比如 01010011 交换之后就变成 10100011
0和1交换 0和1交换 0和0交换 1和1交换
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=147881&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
现在给你一个list of words (你的 vocabulary)，然后给一个字符串，让你判断这个字符串是不是singleTypo，就是有且仅有一个字符打错了 <=> 也就是替换一个字符能变成list里边的单词
挺类似 LC 的 One Edit Distance，小哥为了简便，把插入一个字符能变成list里边的单词的这种情况去掉了
Example :
[size=13.3333px] vocab = ['apple', 'pineapple', 'banana', 'cucumber']

singleTypo('adple') # True 把第二位的 d 改成 p 就行

singleTypo('addle') # False 有俩不一样

singleTypo('aple') # False 缺少字符

singleTypo(‘apple’) #False 一样也不行

我当时的解法是，因为没有长度不等的情况，所以每次都过一遍vocabulary，然后拿出和查询单词长度相等的字符串进行比对。比对的时候，从头到尾扫一遍，看有多少个字符是不一样的，这个是 O(n * k), n是多少个长度相等的，k是要查找的字符串的长度
还有一种解法是替换每个位置上的字符，看能不能成功，复杂度是 O(26 * k), k 是要查找的字符串的长度
另外一种是字典树，如果没有匹配成功，用别的替换看行不行

给你一个 infinite 的 2维 space，实现两个方法

(1) update(x, y, v) : 更新 x,y 这个位置上的值变成v (暗含两种情况，如果 x,y 已经有值，就更新如果 x,y 没值，就是说原来的矩阵大小还没到 x,y 这点，就得往 x,y 这放一个值)

(2) query(x1, y1, x2, y2) : 算出这两个点之间的所有的值的和

我一看下边的两个方法，我擦，这不面经么！还出现过两次！还 update 和 query

我就说，那就用二维线段树做！

小哥可能没太理解我的解法，因为我题都没理解对。。。小哥就说那你写吧，边写边解释

然后我就开始写

刚写完建树，小哥说，你这个感觉不对啊，题目要求的是 infinite 的空间哇

我当时就傻了。。。WTF！！！啊啊啊啊，纯傻X了

然后时间就剩几分钟了，我就按照 LC 的 Range Sum Query 2D - Immutable 的方法实现了 query 方法

刚写完query就到点了

其实没有要求
query多，update少
query少，update多
query，update一样多
这三种可以当follow up
https://sites.google.com/site/codingbughunter/frequently-asked-question/google-mj

先是写个 data structure, 让我 guess 这是什么 data structure,

class N {

private N l; // can be null

private N r; // can be null

private String data;

}

一紧张说成 linkedlist, 赶紧改口说是 tree,

然后就是描述问题,要求写一个 Iterator<String>, 每次调用 next 都是按 in order 顺序

返回 BT 里面某 node 的 value,例子如下

root.data = “m”;

root.l.data=”g”;

root.r.data= “q”;

m

g q

a h p s

z

Iterates in this sequence: a, g, h, m, p, q, s, z

Google Interview Misc Part 6

Labels

Popular Posts