12月4
1、返回只包含两个不同字符的最长的连续字串。"hello" => "ell" 或者 "llo"。2、检查一个字符串是否包含k位a进制数的所有表示形式。
保证原字符串的所有字串都是合法的k位a进制数。"00110, a=2, k=2" => true （包括了00，01，10，11）。3、给一个数组a[n]，
令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)。<=这道题我一直在和面试官讨论解法最后没时间了一行代码都没写TAT
不过面试官说很喜欢我的思路。4、给一段输入文字，统计所有2-gram及出现次数。dataset有100G怎么办？你有100台32-bit机器（4G内存），
怎么分发给100台机器处理？瓶颈在哪里？
200G 2-gram /100 = 2G per machine dispatcher/ worker
hashmap 统计 归并
Async job queue
given a text file and a list of string, find the max length of strings that combined from the given list
of string in the text file. Each character in the given list of string can be used only once.
ANS: A list contains all possible prefix strings up to x.
1.括号匹配 一开始用了O(N)的空间, 后来要求用O(1)的空间完成. follow up, 不同types的括号匹配 {,[,( 2.Arraylist去重 一开始忘了数组remove要O(n),所以写了个O(n^2)的方法后来被要求实现O(n). |
12月2
Suppose we are planning a company party. The company organizational structure is so that there is a single Owner who runs the place.
Everyone has one direct manager, but a manager may have any number of direct reports. Everyone must report to the owner, possibly indirectly.
Each employee has associated with him a non-negative “fun” value. What we want to do is invite the set of employees to make the party as fun as possible.
Here is the only constraint: If you invite an employee, you cannot invite that employee’s direct manager.
A
B C
I J D E
F G H
If we include A: total fun value should Fun(A)=sum_{i=I,J,D,E}(Fun(i))
no A: Fun(A)={Fun(B)+Fun(C)}
It’s legal to invite B and C or it’s legal to invite D, E, A, but you cannot invite D and C, or B and A.
后来复习时才注意到这是party at Hali-Bula,经典树形dp。面试时现推的树形dp，才拿到positive feedback。
Onsite：
1
a) counting sort 变种
b) 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所有的盒子
比如 7*7 5*5, 4*6, 3*3
答案是7*7+4*6
2什么时候 java memory leak: 吓唬了我很久，给了一个得是多年互联网架构从业经验的答案。
Given a single list
A->B->C->E….->Z A is Node type, B is Node Type
Node[] result = compute()….
Node {
T value;
Node next;
}
Find how many clusters in the array “result” Node’s value could be
anything, not directly comparable， the LinkedList is the order.
the cluster means all the Node in the cluster is consecutive in the list.for instance,
result: D E F J G H C
cluster 1 c d e fg h
cluster 2 j
3 n x n parcels in city; matrix M contains the cost of each parcel; budget B largest rectangular area in the city you can afford.
4 在social network中，如何推荐陌生人中和自己共同好友最多的人。不用想歪了，直接要求用mapreduce解，完全是考这个经典算法的trick。
5
a) you have a Queue array, Queue<Integer>[] queues，get the shortest length queue,返回的是queue的index。pop is expensive.这个queue是动态更新的，肯定不能直接size();
b) find the queue with min sum queue, all with non-negative numbers.
剰20分钟不到时，狗血follow-up: implement a heap from scratch, all member functions。写出来后，面试官居然不知道先fill了然后建heap是O(n)
Google:
电面:
1. BST的add, find和delete函数
2.给string, 只包含{0,1,?}, ?可以代表0或者1, 输出所有的组合. 例如"10?", 输出"100", "101"
onsite:
1.写一个Stream的interface, 就是有generic, 有peek(), next(), hasNext(), append()方法. 然后写一个merge List of sorted stream, 就是k-way merge. 然后因为是generic, 传入参数要包括一个comparator.
(TODO: Look at Java Stream interface)
2.输入一堆photo, photo有文件名和时间, 输出是一堆album, 要给每个album命名名字, 最多100个photo, 然后分的时候, 要做到user-friendly. 这个面试官是个烙印, 我代码没写完. 大概的思路就是, 按照天数来分, 每个album的名字就是起止时间. 当然还有很多小细节, 比如一天的照片数可能大于100.
3.Leetcode上的minimum window string.
4.shuffle. 输入是[0,2,_,3] 输出是[0,_,2,3]. 就是一个乱序数组, 其中缺少了一个值, 然后输出, 每个数值都在自己对应的index上面. 但是移动的时候, 只能把数字放在空缺的位置上, 要求移动的次数最少. (这个我也不知道OPTimal的方法是什么)
2
5.shuffle数组, 输入是一个数组, 没排序, 输出是奇数index的数字比相邻的偶数数值大即可. O(n)
6.加试电面, 写jump iterator类, 构造函数传入一个普通的iterator, 然后实现next(), hasNext(). next()返回传入iterator的next().next(), 就是每次跳过一个元素输出.
然后再实现一个rotateIterator(), 构造函数传入List<Iterator<T>>, 实现next(), hasNext(). 例如:
传入的三个iterator里面的值分别是[[1,2,3],[4,5,6], [7,8]], 那rotateIterator的next()应该输出[1,4,7,2,5,8,3,6]. 就是竖着遍历每个iterator输出, 如果当前的iterator没有了, 就跳到下一个.
11月25
1写一个新的iterator，next和hasnext要用他给的一个filter去寻找下一个符合条件的元素
2 BST里找下一个元素，给了父节点
3 设计自动售货机
4 字符串排序设计，量大的时候怎么办
5 一些数理统计的东西。10盏灯，每次亮一盏，给一些历史数据，判断下一盏亮灯的概率，不涉及pattern的东西
最后三题需要写一些简单的程序
2 BST里找下一个元素，给了父节点
3 设计自动售货机
4 字符串排序设计，量大的时候怎么办
5 一些数理统计的东西。10盏灯，每次亮一盏，给一些历史数据，判断下一盏亮灯的概率，不涉及pattern的东西
最后三题需要写一些简单的程序
11月
1.找出missing number 范围
number范围[0,99]
input: [0, 1, 2,50 , 52, 75]
output: "3-49,51,53-74,76-99"
2. 找出一个数由最少几个平方的和的组成
例子：
input： 14 output: 9 ,4 , 1 虽然也能由1 +1 +....+1组成 但长度是14 不是最优解
input: 50 ouput : 25, 25
8月
第一个华人面孔，但是加州理工的phd，聊聊project，然后给了我两个排序数组，找到第n个元素，我用了O(n)的方法，但是他说优化，我直觉告诉我是二叉寻找，但是写代码的时候就乱了。感觉把自己绕里面了。然后感觉面试官有点不耐烦。估计真跪了。(TODO: 写LeetCode find median in 2 sorted List)
第二个白人，给我一个string题目，俺秒杀。然后下一个算法题目就跪了。给我一个n*n矩阵，里面有整数，代表每个位置山的高度，然后如果在这个山头下雨，水流只能流去比他矮小或者一样高的山头。矩阵上边和左边是太平洋，下边和右边是大西洋。好吧。现在你找所有能流向两个大洋的点。我上来说BFS每个点，然后你就知道了。但是N*N次BFS，一点都不省时间。我一直在寻找比如你找到一个点，下面一个点就不用找了的方法，但是没找到。然后还是心中乱了，和面试官写psudocode也是乱的。然后就草草结束了。
第三个华人ABC。给我leetcode原题，秒杀，然后聊聊project，指出我project的问题，我无言。。。
第四个白人director，带条狗待我去吃饭，聊聊他们组，和整个这个部分做啥，问我感兴趣不。对了这个部分是youtube，我和director提到你们视频就英文部分做的好，其他语言不是很好啊。比如我同学可以在中文搜索不健康的视频。director很惊讶，不对啊，我们现在可以分辨是不是黄色的。我说那我不知道了，我们都这么找到的个别不健康内容。可能因为不是英文介绍啥的
第五个白人，下午我的精神明显好了。但是想到上午两轮都完了，我就呵呵。对面试官也是呵呵，想说啥说啥，一点都不顾及，思路也清晰了。面试官问我会python吗？我说去你暑假见过，但是几乎不用。面试官说我就喜欢给完全不会python的人看代码，看他接受新的语言能力。然后给我一个质数判断的代码让我解释，我觉得还好。然后给我一个算法题目，我觉得也还好。还是秒杀哦。
oniste 4轮，第一轮是个中国人，然后问给一个sorted list，然后生成随机数，不在list中的，这个也不难，写完，然后第二问，他想问subsequence sum的，我理解错了，写成另外一道题了，最后大家发现理解不一样之后开始说中文了。。然后给他解释了一遍算法，因为也来不及写了
第二轮，面试到现在最恶心的一轮，一个印度3姐，出的问题很简单，比如memcpy实现，还有insert element to sorted list。我写完了，各种挑刺。而且很多都不是问题她硬要说是问题，她给的事TreeNode** head，然后问我假设head为null怎么办。。我说head为null，dereference会fault error，但也没有办法避免，如果给定一个非正常值也会报错。然后她就各种不满意。还问了一个deep copy的问题，然后问了一个奇葩的实现。。。我也没回答好。anyway，这轮肯定gg
中午和一个很老的工程师去中国食堂吃饭，感觉google中餐还不错（也有可能是村里待多的关系）
第三轮，一个白人小哥，问了一个分水岭的问题，一开始理解错了，用dp实现了，然后写到一半，那人在旁边写了一个反例，然后老老实实用flood fill实现了。然后又问了找湖（找一个二位matrix的低点），之后就聊聊天，问些他工作的组什么的。
第四轮，一个白人大叔，问了一组数，找出所有3个数之和小于给定一个数的组合数，我用有点想3sum的实现，但是会有一点点不一样，然后最后还是解决了，他应该还是很满意的，然后问了一个数据存放的问题，如何在O(1)时间内取出一个matrix中间一个区域的数目之和，然后我之前看面经看过这个，然后用容斥原理做了，然后他说这是trade off，有办法能够平衡么？然后我就冒出来一个n个线段树的做法，取了平衡，他对我做法貌似挺满意的。最后第二题也没写代码
TODO: 一维容斥原理, 二维容斥原理
11月10：
第一面：国男，先问了一下heap的基本概念，然后说在一个数组里面找k个大的数。心想果然国男好，还事先给提示。
结果第二题问java中stack和vector，set和list，哪两个是继承的关系。有点蒙，不过还是在面试官的引导下想出来了。
然后又问了youtube上如何对用户推荐视频，我就说用比较常用的matrix factorization。然后国男说我们这个空间复杂度太高，因为youtube的用户太多。而且推进视频的时候不一定要跟用户相关，也就是说不同用户看一个视频的时候，推荐出来的视频应该是一样的。然后我就说在矩阵分解得到视频的向量的时候，直接分析这些向量的相关性就可以了。国男说可以。
第二面：白人，第一题，一种商品的价格和数量不一定是线性关系，给你一定数量的钱，问最多可以买多少。因为不是线性关系，所以直接用二分就好了。不过先找到upper boundary，每次指数增长，不断尝试，直到钱不够就好了。然后在这个区间中做二分。后来说要看一个test，结果没有test经验，理解错了面试官的意思。 第二题，判断valid BST.
中午和一个中国工程师聊了一会儿，说youtube才有700个工程师，感觉还不错。
第三面：白人，这个人感觉很牛，
第一题，给一个函数写一个wrapper，使得这个函数每次调用的间隔至少10秒。我用了java 的concurrentqueue来做，
基本idea就是job queue, 然后每个调用者都是producer，往这个queue里面加一个job，另外用一个线程，
每隔一秒从这个queue里面poll一个job，然后执行。面试官挺满意。
第二题，把一个任意的数组，调整成小大小大小大。。。。的形式。之前面经也出现过
第四面：白人，第一题，压缩字符串，aaabbcccc改成a3b2c4，水题。第二题，设计贪吃蛇的数据结构，queue + 二维boolean数组。然后写一个每次移动的函数。很快写完之后，面试官说好像没啥题了，然后又现编了一道概率题，随便说说就结束了。
在YouTube面的。一上来被问了一大堆关于Android threading的问题，比如foreground thread 和background thread有什么区别，怎样设计程序防止UI卡顿之类的。简历里果然不能乱写。。。
然后是一个设计题，已经有一个程序使用了标准的一个容器（比如List），现在有一堆第三方容器，怎样尽可能少更改源程序来利用这些新的类。其实就是写一个Wrapper Class，直接被面跪了。
算法题倒是挺简单的，两道二分查找。另外有一题给一个数列要求调整成小大小大小大。。的模式，有线性的贪心算法。. from:
另外还有一题是对稀疏向量求点积，HashMap或者直接归并都是可以的~
感觉面得好奇葩，求加RP求过>.<
11月13
1，leetcode 上的longest consecutive sequence, 但是要求按顺序找
2，find the longest increasing sequence in an integer matrix in 4 directions (up down left right), return the sequence; for example: input:
1234
8765, output should be 12345678
这个题我用dfs＋backtracking做的
11月7：(NYC)
1. BST delete item
2. Game of Life (绝对高频题啊！)
3. 给定平面上一堆点，找出通过点最多的直线
4. 根据List1的顺序排序List2
5. 给一个整数矩阵，计算某submatrix所有点的数之和 （多次请求，所以要预处理）
6. maximal rectangle
7. candy crush相关的半设计半coding题
10月31：
1.求一个unsorted 数组的前k大数字。 O(n)
2. 3Sum
10月29：
10月24：
一个数组，保证前半部递增，后半部递减，求数组最大值。二分查找。
10月10：
设计一个类来限制query，如1000qps，或者说每秒钟只能发10封邮件
给定的API，now()返回当前milliseconds
实现类的函数allowRequest()，如果当前还有request剩余true,否则返回false
给定的API，now()返回当前milliseconds
实现类的函数allowRequest()，如果当前还有request剩余true,否则返回false
- The final interview had a tricky question about converting a post-order tree to pre-order. Answer Question
10月6：
- Reorganize array of numbers in "s1 < s2 > s3 < s4 >.... " fashion. The numbers may include duplicates. View Answers (4)
10：30 第四场， 国男
简单寒暄一下，然后问了一个找硬币的题，应该属于背包问题，首先给了一个贪心算法，然后他指出不是总能得到最优解，然后我也发现了，他就让我举例，举了个例子，然后开始想动态规划，然后想出来了，在板上写了code，分析了一下复杂度，然后一起讨论一下边边角角的问题，然后11:15的时候，第二个面试官到了，然后就冲冲结束了。
11：15 第五场， 欧洲男
简单寒暄了一下，喝了口水，然后开始做题，什么俄罗斯方块，比如说常见的俄罗斯方块，每一个图案都是由4个block组成，现在给定一个N表示N个block，把所有有效的俄罗斯方块组合都输出出来，（有效的是指block是横着或者竖着连接的，不是直接斜着连接）。数据结构什么的都自己定义。 这个欧洲哥们的英语超级难懂，交流十分困难，总之这一面比较糟糕。
12：00 - 13：00 吃饭，去了中国食堂，排队超长，幸亏我们去的早。后来甚至都有人端着盘子没有座位的情况，让我想起了我的大学食堂。。。。。。。。
13：00 第六场， 日本男
还是寒暄一下，说一下为什么google，自我介绍一下，然后开始做题，一个图的题，找出所有A - B 有边， B - A也有边的pair。这道题答的也比较烂，开始还理解错了，后来还逼得他给我定义了输入的结构，总之就这样了，还没说完呢，13：45，外面已经站着下一个人了，然后就下一个了。
13：45 第七场 俄罗斯男
他翻了一下简历，发现对一个project有点兴趣，于是我们花了五分钟讨论了一下。然后是题，算法导论里面的矩阵相乘的题，然后用动态规划做出来了，写了代码，一起讨论了一下边缘问题，然后就到了两点半，发现这个room被预定了，后面的人也来了，于是面试就结束了。
9月30：
第一轮：2道coding，问复杂度， 1道design，coding不难
第二轮：1道有关图的题，我给了个解，然后要降低复杂度，又给了一个，然后没时间
，就没写code，面试官说，that should work
第三轮：给了用数组表示的树的题，2问，第一问答得可以，第二问脑袋发晕，程序木有写完。。。。
第四轮: 一个dp题，中间一个corner case没有考虑，给了个hint，后来做出来
第五轮：聊了点简历，然后做题，我给了个答案，对方让降低复杂度，想到了heap，但是没完全想通
第二轮：1道有关图的题，我给了个解，然后要降低复杂度，又给了一个，然后没时间
，就没写code，面试官说，that should work
第三轮：给了用数组表示的树的题，2问，第一问答得可以，第二问脑袋发晕，程序木有写完。。。。
第四轮: 一个dp题，中间一个corner case没有考虑，给了个hint，后来做出来
第五轮：聊了点简历，然后做题，我给了个答案，对方让降低复杂度，想到了heap，但是没完全想通
9.29
- Given a graph as input, write a java method returning boolean true if the graph is bipartitie, else false. View Answer
9月14
| 面试的题目基本都不难，从头说起吧。 我水平很一般，1年前就意识到要刷题，那时候主要看ctci，直到上学期及relocate到湾区之后才刷leetcode比较多。即使在面谷歌的时候我依然没有刷完，还剩10道新题左右，恰好面到了一题我没刷过的题。 个人感觉写出代码只是一方面，面试者的差距体现在follow up的问题上。 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=104400 1. 1st Phone interview: 1) Clone Graph ，5分钟做完，思路比较清楚 2) 开放性问题，如何设计广告推荐算法，从基本的如何利用log，到如何针对不同的用户优化，到加入machine learning。感觉实在乱扯 2. 2nd Phone interview: 1) 在 trillion integer中找出最小的，O(n)；其实在问map-reduce 2) Palindrome Paritioning II 3. Onsite interview (4 rounds) 1) . 1.1) most challenge you take 1.2) 算法题，忘了 1.3) not algorithm: get radnom from distributed system, no duplication 2). 2.1) most bug ever encountered. 2.2) 算法题，在 Set<String> 中找出common suffix 3) 3.1) when we would choose O(nlogn) rather than O(n)，这题其实是为了之后算法的follow up埋下伏笔. 3.2) 算法题，paint brush --> 如何防止StackOverflow？当时卡壳了，其实对matrix用BFS就可以，解法分析在StackOverflow上就有。。。。 3.3) 算法题， given Set<String> set, List<Character> chars, return Set<String> which has longest be covered by the List<Character>. e.g. dgg cat naioe lot 1st case: dcnlggatio -> return [dgg,cat,lot] 2st case: dcnlggatioe -> return [naive] 当时我想的是一个基本的线型算法，然后他开始follow up了； 我的follow up思路不对，老是往map-reduce方面想，但是他要的答案是对input进行预处理。可能就是之前提到的在什么情况下会选择O(nlogn)而不是O(n)算法。 最后他提示说用tries来预处理，我依然没有想法。希望有人能详细解答一下。 4) 4.1) 算法题 given Set<Point>, find the line with most number of Point's |
8月29：
strtok implementation
- given set of characters duplicates possible, and given dictionary (list of words). Find longest word from dictionary that can be made from given characters. How will you do it if '*' (matches one wild character) is also included?
- Access card system design
- Implement a stack with find_min api as well.
- Given set of points, find line with max points on it.
- TODO: utf-8 byte stream verification and character extraction.
8月28：
given a string ,return the longest substring that contains at most two
characters.
characters.
7月31日：
7.18
- Given 3, it should be turned into 0000 0011, then flipped 1100 0000, then return 64+128 = 192. I commented that this was easily done via bitwise manipulations, but I have not done those in a while so I wrote a program out in C to do it manually. View Answer
6月22日：
1. Reorder List (leetcode)
1->2->3->4->5 => 1->5->2->4->3
*****************************************************************
2. Abbreviation: apple can be abbreviated to 5, a4, 4e, a3e, …
Given a target string (internationalization), and a set of strings,
return the minimal length of abbreviation of this target string so that it
won’t conflict with abbrs of the strings in the set.
“apple”, [“blade”] -> a4 (5 is conflicted with “blade”)
“apple”, [“plain”, “amber”, “blade”] -> ???
Problem changed to:
If given a string and an abbreviation, return if the string matches abbr.
“internationalization”, “i5a11o1” -> true
*****************************************************************
Onsite:
1a. Write a function to get a positive integer n as input and return 0 or 1. The probability of returning 1 should be 1/(2^n)：考虑当n比较大的时候，每次产生0或者1，弄n次，如果每次都是1，输出1。
1b. Given an array, return the median. (talk about expected time complexity)
2a. Code review - a class which takes a string, split by separators and return the array of tokens (point out coding problems and indicate how you will implement it)
2b. Longest consecutive sequence (leetcode) (how do you handle duplicates)
2c. design: how to store files given the file paths and contents. (tree?)
3a. Given an array and a number x, find out how many pairs satisfy (a[i], a[j]) st. a[i]+a[j] < x
3b. follow up: if we want to find 3 items that adds up to a number < x
3c follow up: if we want to find k items. Time complexity: O(n^(k-1)*lgn)
4. Give a map which has some obstacles in it. Given a starting point S and ending point E, find the shortest path from S to E. Note that you can go to any(4) direction from S, but during the process, you can only go straight from the previous direction, unless you hit an obstacle.
i.e. if you are at (1, 1) and the next (1, 2) is blocked, you can only go to (2, 1) or (0, 1)
5a. Java “final” keyword
5b. 3-way partition: given an array and number x, reorder the array so that first part will be < x, middle part is = x, and final part is > x.
5c. Design: given an array of integers and a range (i, j), we want to return the min item in the range (balanced binary search tree)
5d. System design: given a machine, how to generate id so that they will not duplicate; if we have multiple machines, what to do
1. 翻转字符串中原音字母。
2. iterator of a list iterators with sorted elements: iterator +优先队列+
customized comparator + 加上一点corner case handling.. 与iterator一起看
3. 只有一个转换小写字符函数， 参数是一个字符，返回一个这个其小写字符， 假设不知道大小写之间关系（'X'='x'-'a'+'A' 不允许的 ），写转大写的函数。
4.Sudoku solver优化 （TODO: Leetcode）
5.两个concurrency问题 基本是写semaphore
6. 3sum变形， 找所有<=
7. 写 web server，性能，安全等考虑
8. web hit count设计...
6月2日：
面试我的是纽约double click组的
第一题leetcode的原题 Merge Intervals，运气比较好
记得给了两种解法n^2 和 nlogn
第二个字符串题目:
将一个字符串转换为数组，按照空格分割字符串，但如果一个子字符串是在一对引号内，那就当作一个元素（无论里面有没有空格）
例如：a b cde "f g""h j" => [a, b, cde, 'f g', 'h j']
还有些细节记得不是很清楚了，这道题都没来得及写完（面试官晚上没睡好，状态不太好，题目也没怎么解释清楚）
一个月后去了onsite，new grads是四轮（2+2）
四轮面试里有三轮遇到了对大量数据的处理，要去面试的同学可以找点题目练（虽然G的面经作用其实不大）
5月27
G onsite:
1. printing a tree structure with giving collection of pairs of <parent,
child> relation. Need to first find the root, and validate wether the given relations is a valid tree, and then printing.
2. LRU 实现
3. 记不清楚了，比较少见的一道题，0, 1开头byte，判断最后一个字符是一个byte还是两个byte的问题。
4. Design a system to fast retrieve Fibonac
5月20：
--------------------------------------
第一轮（中东人）：
给一个字符串，让压缩并解压，压缩算法类似leetcode中的count and say TODO: 写Leetcode
输入：aabbbccd 压缩结果：2a3b2cd（注意，'d'前面没有'1'）
引申：输入中如果有数字的话，解压时需要注意歧义问题，例如2a可以解压为'2a'或
者'aa'，问如何解决。答曰用类似ascii码中加反斜杠的做法，或者加个header来标
志压缩过的位，表示同意。
第二轮（老印）：
（leetcode） edit distance，以DP解之，喜。
（leetcode） word ladder，直接给出BFS，不喜，要优化，想了半天给出的答案皆不喜，最后提示我可以双向BFS，时间不够，没有给出代码。
-----------------午饭-------------------
第三轮（老白）
给一个int的矩阵arr，让返回一个同样大小的result矩阵，每一个result[i][j] = arr[i][j]及其所有左上方元素的和，DP解之，喜。问了各种test case，一一例举之。
（左上方元素定义：以arr[0][0]和arr[i][j]为对角线的矩阵的所有元素和）
第四轮（老印）
给两个int，第一个代表分子，第二个代表分母，让返回转化成小数后的string循环位用括号括起来。例如：输入1,3，返回“0.(3)”。输入1,7，返回“0.(142857)”；暴力解之，用一个LinkedList记录每次的余数，如果出现相同余数，则出现循环，与前一个相同余数的距离就是循环的位数，插之以括号。喜。
第二题：判断两个二叉树结构相等（左右subtree可对调），递归解之，喜。
第五轮（老白）
（leetcode）search in rotated sorted array。直接背答案，条件二分。
5月4日：
--- 类似于斯坦福公开课的karel机器人的题目。给一个机器人的class有4个method，clean() clean机器人所在的点 isclean()返回该点是否clean forward()返回机器人是否前进一格，如果可以并移动机器人 rotate(int degree) 旋转机器人的方向。然后要implement cleanroom的method。room是一个长方形，但是具体的信息未知，也就是说只能用上述四个method clean整个room。首先给出dfs，不同意，因为无法知道房间的大小。面试官很nice的要我不要吧问题想复杂，最后简化问题说从房间左上开始clean。写完code比较满意。follow up问了从任意点开始怎么办。并问我怎么test和optimize 代码。又follow问了java里面test的一些东西，都比较满意。
--- design question，很有意思的题目。给了很长的故事背景，大概的意思是说学校有个传统，毕业之前的一周会选择7个小伙伴，只有互相选择对方的小伙伴双方都能收到邮件A-B, B-A, 如果A选择了B但B不选择A，B不会收到邮件。问我怎么design这个系统，然后实现一些方法比如cansendemail()。然后又follow up怎么保证系统的owner不能看到所有的信息，保证privacy，但系统能保证实现所有的功能。这轮发挥很好，cover了面试官很多想要的答案。
--- lc word search 但是返回match word的次数
--- 给两个部分排序的文件和partially sorted的值m，部分排序是定义为比如1 2 4 5 6 7 3， 3应该在2后面，那么3的partially sorted的值就是4.因为最多放在该点前面4个index的位置。要实现两个file merge的输出，要输出的file是排序的。限制是file很大很大，不能放在内存里面处理。这一题比较有意思，还有很多需要自己specify的地方，面试官也没有写API，全部要我自己定义。我灵机一动给了个双heap merge的解法。30分钟说完思路写完代码，不过最后有2个bug，被他指出来了只修了1个，另外一个没修好。。。这个白人老头面试官一直在假笑···也不给我hint，也不让我问他问题···· 最后走的时候还说你有一个bug，这轮也绝逼是negative了。。。
3月3日：
上午两个人，一个年轻老美，一个国人大哥。
年轻老美问了个机器人走网格的题，虽然没有做过，不过类似的题目看过一些，所以很容易就用dp写了一个。之后就是聊些我做的科研，g家做的类似项目，职业规划等等。
国人大哥面我，上来出了个很简单的string题，直接水过，后来出了个比较难的string题，只让说了想法，没让写程序，估计那复杂度写起来要悲剧。。。感谢国人大哥的放水！大家要互相帮助阿。可惜不知道这位大哥的email和全名，不然要写个感谢信。
下午三个，两个美国老头，目测都60以上把（看来老美一点年龄歧视都没有阿），一个40多老美。
第一个美国老头上来把手机拿出来说正在玩一个游戏，问我怎么编程解决，一个类似华容道的游戏，就说了下bfs的思路，怎么建立图，也没让写程序。后来问了简单的个概率题，我不知道怎么卡住了，后来经过提示搞出来了。后来又问了个矩阵里面搜索元素的题，binary search搞定。问复杂度，由于和常规的bs不一样，结果我答的有问题，他自己估计没想到我这个解法，也没说清楚我这个的复杂度是多少，只说应该比较efficient，就过了。回来之后我才想到正确的复杂度是多少-_-。。。
第二个美国老头问了个字符串查找的题，我灵机一动用hashmap直接写了个O(n)的，就过了。然后问了些底层的string之类，还问了c++的memory leak，我回答说把new/delete写在构造/析构函数里，或者用smart pointer，他说知道sp不错阿，很多人面试用c++，却不知道sp -_-....
最后一个老美问了个设计题，类似dropbox，我就把知道的都乱说一通了，目测他还比较满意。
2月20日：
（1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化。
（2） 韩国人： a) 给一个dictionary, 再给一个set of coding string （g5, goo3,goog2, go2le.........). return all string from dictionary that can be matched with the coding string. 要求尽量减少dictionary look up 次数。给了个方法，但一直不满意复杂度。
（b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包
括所有字典词和coding string.不是很明白。。。凭感觉写了个。
（3） 阿三， 非常拽。。。 给一个dictionary, 一个string,找出dict 里能全部用string里的letter 表示的所有最长的词。给了算法，死活不满意，不让我写code. 估计被黑了。
(4）阿三。 design google calendar . 要求分析如何存data, 如何invoke user created events, 如何handle 100000events per second, 然后要写了一部分thread safe 的code 实现如何invoke event.
(5)年轻白人： (a)leetcode 上的coin 题， 用DP. (b)给你一个password 假定6位， 有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变。比如google, 可能返回， ggl, goe, oog, ool, ........
问如何最有效破译这个密码，写code.
下周Facebook onsite, 求bless
2月14日：
1. 白人。
a. 设计自己的一个Iterator class。 constructor输入的是List<Iterator>. 实现一个method: Object getNext(); 每次得出的结果如下。
假如输入是
Iterator1: a, b, c, d, e
Iterator2: f, g, h, i, j
getNext() 出来的顺序是 a, f, b, g, c, h, d, i, e, j
写完代码后直接问我time complexity 然后就move on下一个题了。。。也没有跟我discuss还是walk through一下code。
b. 问我在什么情况下选择n^2的复杂度而不是nlogn. Open ended question。
c. f(string a, string op, string b)， 要我写出各种testing cases。
2. 白人
a. implement thread-safe queue class
b. all the combination of letters of phone number (leetcode 原题)
写完代码， 一样也是问了下time complexity就move on了。。。
3. 貌似中国人
a. 讲了一会自己做的产品
b. 给9个9 还有 +,-,*, /, ()。 让返回无法表示的最小的正数。
比如 如果 1 无论怎么用这些运算符组合9个9，那就返回1.
开始没有头绪，给了提示问如果只给出一个9怎么办，如果只给2个9怎么办。就想到了recursive，终止条件是 当9的数量为1的时候，查的数是9就是true，其余都是false。两个9的时候，查的数是1(9/9),18(9+9),81(9*9)就返回true。
else if (isValid(target/9, num-1))
else if (isValid(target*9, num-1))
else if (isValid(target+9, num-1))
else if (isValid(target-9, num-1))
else if (isValid(9-target, num-1))
else if (isValid(9/target, num-1))
return false;
虽然代码没有最后写完。面试官认可了这个算法
4.白人，最简单的题
interface TreeNode{
int getNumChild();
TreeNode getChild(int index);
}
int numberofNodes(TreeNode) 实现这个method，得出一个tree里node的数量。一个node可以有任意数量的子节点。每个节点的子节点按顺序从左到右的index都是0,1,2,...
我就用bfs， queue几行就实现了。
然后面试官各种各种的演变。比如边变成有向边，一个节点会有多个父节点。其实就是变成了graph。用一个set保留所有第一次访问过的节点就行了。
然后继续考虑在多线程的情况下会出现什么情况。我说不影响。
他继续play around. 这个TreeNode 增加了 Boolean visited。 看看在现有的代码下，多线程会出现什么错误，不要求改代码就是讨论玩玩。
5. ABC
已经很累了。。。
string getDecimal(int a, int b) a/b 输出小数的表示。比如 2/5=0.4 要输出 0.4
. 如果有无线循环小数则把 重复的数放在（）里。比如 1/6 应该返回 0.1(6)
2月8日：
第一轮
给一个矩阵，每个格子上有三种可能，空房，阻碍物或者是保安，阻碍物不能进，空房四个方向都能进，要写代码给每个空房标记其离最近的保安的距离，比如
000
BGG
B00
B表示障碍物，G表示保安，0表示空房，应该标记为
211
BGG
B11
我说扫一遍矩阵，然后遇到每个G就bfs整个矩阵, 他说不是optimal，optimal可以做到O(N^2)。当时想不出，他说那就先按我那个想法写代码。写完就到时间了。后来回家后就想到optimal的解法了，对所有G一起开始bfs就可以了。
第二轮
写一个函数生成满足下面三个条件的integer
1. 非负
2. 不能有重复数字
3. 递增，既后面产生的比前面产生的要大
我问要一次性全部生成所有数字还是每呼叫一次函数产生一个，他让我先写一次性产生全部的，这个不难，backtracking，follow up是假设现在给一个符合条件的数字，如789，返回下一个（比输入大但是最小的）数字，790。一开始我没思路，说很多edge case，然后多观察几个例子后发现有些规律，说出来后他说看起来不错，然后举了几个例子让我模拟跑一遍，没有问题，他说ok，不用写code了，正好也到时间了
第三轮
问了一个Java的问题
假设有两个class，A和B，B是A的子类，
先有下面几句
A a = new A();
B b = new B();
List<A> la = new List<A>();
List<B> lb = new List<B>();
（反正就是建了A，B的各一个instance，list of A 和 list of B 各一个instance）
然后问下面四句哪句能过compiler，哪句不能：
a = b;
b = a;
la = lb;
lb = la;
答案是只有第一句能过，我一开始答1和3能过（我真心不熟Java，python里面的话啥能过啊亲）。
然后出了一道python generator的题，写代码，还有follow up，也要写代码，最后都超出时间了。
中午吃饭, 下午接着面
第四轮
问我知不知道zip文件，我说用过但不知原理。他就说我们来讨论一下
假设一个文件压缩后的表示是
#3, #5, #6, 2 5, #8...
”#k“形式的代表这个数字k，两个数字“i j”形式的代表取前 i 个
数字做 j 长的 circular重复，像上面那个表示，前面3个都是表示单个数字，然后 2 5表示取前2个数字 （既56），组成5个数字，不够的从头再取，所以就是56565最后上面解压缩后应该为
3, 5, 6, 5, 6, 5, 6, 5, 8...
要我写的是压缩算法的代码。
我提出从头扫，一边一边用hashtable记下见过的number，每前进一位就检查hashtable有没有符合当前数字模式的number出现过，然后他说还不错，写代码。一边写一边出现bug，一边发现很多写代码前没考虑的东西，最后勉强算写完，时间也到了，他说这个他也没写过，是在一篇paper上看到的算法，原算法跟我的有些不同，倒是都用了hashtable。。。
第五轮
拿着我简历进来，说有人跟你谈过你的简历吗，我说没有，他表示万分惊讶，然后在我简历上挑了一个research project让我说说，说完后用c++出了一个题，一个cipher类，有一个member function是对输入加密，加密方法为对input的每16个Byte和一个increasing counter做xor，这个increasing counter也是有16Byte，从00..01（前15Byte都是0，最后1Byte是1）开始，还有一个要求，举例说：
第一个input 有20个Byte，前16个Byte就和00..01做xor，后4个Byte和00..02的前4Byte做xor然后之后再对第二个input加密的时候，对这个input的前12Byte用00..02的后12Byte（即11个Byte 0，1个Byte 1）然后让我写这个class我问了一句要是couter的数用完了怎么办，他反问我这个counter有16Byte，多久会用完。因为已经很累了，算错了好几次，中途我还说16乘以8等于64。。。反正在他逼迫下我硬着头皮模拟算了一下，得出结果就是很久很久很久才会用完，不用担心。然后又因为好久没写c或c++，还有真的很累，脑袋一片发麻，茫然不知如何下手，他看不下去了就说那你就写一个能从小到大生成这个counter能表示的所有integer的函数吧，你要对python熟一点的话就用Python，这个写完后有两个小bug，迅速改正过来，然后就到时间了。问我还有没有问题，我就随便问了一下这个office有哪些project，然后就结束了。
2月5日：
1. clone directed graph(recursive, non-recursive)
longest common suffix of two linked list
data structure design
2. how many (m, n) pairs such that m*m+n*n<N
线索化二叉树
3. 判断一个点是否在一个凸多边形内, O(n), O(logn)
4. group items(BFS)
MapReduce(filter a collection of documents, the words which occur more than 5000 times)
第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3,4,5]，然后window的宽度是2，那么就输出[3,5,7,9]
第二轮是给一个int N，让输出所有的长度为N的valid string的个数，valid string的定义是由A,B,C三种字母组成，并且在这个string中任意连续的三个字母不能包括A,B,C三个字母，比如BACCA就不是valid string，因为前三个字母B,A,C包含了这三个字母。我用了一个三维的DP做，但是边界条件没有写好
第三轮特别简单，问了买卖stock那道题，以及在这上面又问了其它一些边边角角的东西
第四轮问了两个题，给一个array of int，以及一个range (low, high)，找出array中所有的continuos subsequence使得这个subsequence的和在range之中。第二个问题是grid的题，假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路走到右下角
1月17：
1. 一个2d的黑白棋盘，黑色的格子都是连在一起的，现在给一个黑色的格子的坐标，请找出最小的矩形，包含所有的黑色格子
2. Implement Iterator接口，但是增加一个功能，peek()返回next()的值，但是不能移动pointer。 constructor已经指定，就是 PeekIterator(Iterator iter)
这题有个special case需要考虑
然后就是原题，maxSubArr()
3. 一个特殊的binary tree，叫full tree，定义是每个节点要么有2个children，要么没有。现在我们要copy一个给定full tree的形状，请写encode和decode方法
4. 检查()序列对是否正确；
follow up 1： 如果有三种 ()[]{}怎么办
follow up 2: "()()(" double quote里面的ignore，如何判断
总结，当天晚上差不多12：00到酒店，大概2点才上床，早上起床眼睛全是血丝。。去g面试做题完全没状态，maxSubArr就5行代码都一个bug。 不过居然还是让进了HC，虽然毫无悬念的挂了。总体来看，题目有新题，但是仔细想还是能想到的，不过google对coding速度要求很高，HR建议我继续好好练习coding，12-18个月再来。
interview 1:
1. 给一个char[]和一个字典，求所有在字典中并且由char数组里字母构成的单词，假设isWord()可以直接判断某个单词在不在字典里。
2. 数组的permutation
3. 你会怎么设计1中的字典？
interview 2:
1. 8进制数的plus one
2. 写一个树（非二叉树）的iterator,注意不是traversal，并分析复杂度。题目都不难，但是还是避免不了小bug，希望能过吧。。。顺求bless
2013年10月27日：
第一个，什么是bst，怎么用，怎么查，然后给一个bst，给一个数，返回离这个数最近的数，要求写code，然后问我code有什么问题，问我coding style如何改进。我当时不知道这个coding style指的什么，后来就是讨论哪儿有冗余code之类。谈想法，写code。
第二个，什么是多线程，给一个函数copy(char* src, char *dest), 如何设计这个函
数，是多线程safe的，谈想法，写code。
第三个，给一个无限长的整数序列，求这个整数序列的中数，要求limited memory，要求谈想法，写code。
第四个，谈做过的project，给两个paragraph，如何判断这两个paragraph是相似的，谈想法；给一个字符串，由多个word组成，要求求出这个连续的k以内的word组成的word组合的次数，比如hello world all, k = 2 则返回hello 1, world 1, all1,
hello word 1, world all 1， 要求谈想法，写code
第五个，如何设计Google Search的输入时候的自动提示功能
2013年11月：
1.1 gas station
1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
2. most frequent character in a huge string (10works 1master)， 如果一个big
3.1. return random node of a list, what if it can be modified concurrently
3.2. 1k Ads, how to make it only appear once across all servers, no master server
4.check generalized tree, follow up:return all generalized tree of its
children， 比如
1
2 3
4 5 6
这种情况下，2，4，5，6是valid的节点。
5.how to design general cache
2013年8月：
Onsite 1st
1 White Female Mira
1.1 Find intersection from two lists
1.2 How many 0s tailing in N!
2 Indian Male
2.1 10 buttons passcode with 4 digitals. Generate a sequence to
brute force it. Upper bound and lower bound of length, code to
3 White Male geek
3.1 Guess how a PDF file is structured
3.2 How to present a rectangle. Check two rectangle is intersected
3.3 Program structure.
3.4 Run Unit twice, passed the first time, and failed at the second. Why?
3.5 Forced context switching
Lunch Steve
4 ABC Male
4.1 Design a system to upgrade patches on remote data center
How to transfer the patch
How to install patch between computers (in the data center), fast and safe. If error happens, how to fix it. What will make this system down
Onsite 2nd
1 White Male
1.1 A function to validate UTF-8 String
1.2 How to break down a the watch-video page
1.3 Design a system to server video thumbs
2 White Male
1.1 Design a class to serialize and deserialize an object
第一个人: 关于 quadtree 的
比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
那么这个 image就是黑(B)的，如果所有的pixel 是白(W)的，那么这个 image就是白的。否则的话，需要把这个 image等分成四份，如下图
__________ __________
| | 等分成四份就变成 | | |
| | |____|___|
| | | | |
|________| |____|___|
分成四份以后每个小份就是一个 sub-quadtree
问题1 : 为这个 quadtree里面的 node 设计 data structure
然后的问题是关于两个 quadtree 的 intersection, 有两个 quadtree, 它们描述的 image 是两个相同的 area比如 都是 [0 1] x [0 1] 这个相同的二维区域的image.
问题二: 写一个函数，返回两个 quadtree的intersection,这个intersection的规则是: 如果一个区域在 第一个quadtree 里面是白的，这个相同的区域在 第二个 quadtree里面是黑的，那么intersection就是白的，简单的说白是 0, 黑是 1, intersection就是两个bit 的 AND
第二个人:
问题 1: construct binary search tree from a sorted array ( leet code 的原题)
问题 2: storm8的 online test 的升级版。
一个 m x n 二维区域，每个点上有一定数量的钱，考虑路径 : 从坐下角(m-1, 0)出发，终点是 右上角(0, n-1), 在每个点只能向右或者向上走，现在有两个人，从起点出发，走到终点，问怎么样求出这两个人能拿到的钱的和的最大值。 一看这个就傻了. 两个人的，太难了。 面试官让我先算一个人的算法。这个easy. 然后他就问两个人怎么搞，我当时首先想到的是，会不会是 greedy, 先算第一个人的，然后把第一个人走过的路径上的每个点上的钱变成0,再算第二个人的。我当时试图证明这个 greedy是正确的，但也证明不出来。 面试官说你能举出一个反例证明你的 greedy 不 work也行，我当时就试了试
1 2 3
4 5 6
7 8 9
跑了一下 greedy的算法。 但是这个似乎不能做为一个反例。时间到之前没想出反例.
第三个人:
问题1 : binary search. 我问他 如果 target miss/hit 怎么处理，他说 you told me. 我就说 比如 1 2 2 4, target = 3, 那么应该返回 index 3, 如果target 是 2, 就应该返回 index 2. 他说 OK。 然后我写了，他亲自跑了一个test case
问题2 : 写一个 hashtabe, 实现两个方法 find， insert
第四个人:
问题1 ： google的 search bar 里面敲入 一些字母的时候， 会出来一些提示，问怎么实现，我说用 prefix tree. 然后就问， 比如 输入 ca, 出来的可能是 cat, california, 问有什么方法可以加快 search, 可不可以提前 search, 我说可以提前 search cat 和 california, 等到用户确定是什么的时候，再输出相应的search的结果， 这样会快一点。
问题2 : 一个服务器上有一个很大的 integer array A, 客户端会每次通过 两个 index start, end， 来拿到 A[start, ..., end] 这个 sub array 上的 minimum, 如何在服务器上实现快速的找出 A[start, ..., end] 的最小值.
2013年2月：
1. 面相严肃的白人，问的内容比较非主流——code review。有一个NoSQL Db的interface能查询某个key对应的value，某人用这个interface实现两个table的query result aggregator，并且还有一段unit test。加起来只有短短20行代码，让我喷40分钟，还要讲正确的实现方法是什么。不知道这是哪倒霉intern写的代码，也许N多面试的人狂批……这个大概是针对有一定工作经验的人的测试，没在大公司干过的new grad碰到肯定瞎了。感觉我虽然讲了很多，还是没有完全答出他想要的内容。
2. 头发像是用了飘柔的白人，害得我一直在想象他头发随春风飞舞的样子，也许分散了做题的注意力:(貌似是临时拉来充数的，从头到尾不是在笔记本上找题，就是突然随口问一句又说题目不好再换道其它的。纠结半天问出经典题：实现insert, delete, getRandom都是O(1)时间复杂度的数据结构。知道算法的话写起来不难，中途他追问了一下hashmap的原理。最后没几分钟时他突然开始问一个设计题，要实现一个service，接到request后call N个其它service获得data，组合起来返回结果给caller。正好我们组有个这样的service，我直接把我们的实现说出来了，是先为N个service生成一个input/output的dependency graph，再按topsort的顺序call。他就问如果有1000TPS怎么办，我说我们组的做法就是scale up，因为这种service一般是read-only的，不用太考虑consistency问题，直接加服务器并做好cache问题不大。他说他们组以前是这么做的，我顺水推舟问现在怎么做的，他神秘兮兮地没回答。后来我想了一下，估计他们是用distributed queue搞了一个asynchronous的系统。
3. 烙印，一开始跟他谈我的工作内容，明显觉得话不投机。被问了怎样serialize和deserialize一个tree。这又没准备过，临时写了个serialize成json的实现，后来又扯了下层序遍历。感觉他肯定给了我negative。
4. 午饭时间是我向HR点名指定的1337哥陪同，感觉好幸福……
5. 貌似欧洲白人，长相挺nerd。问了极其恶心的text justification。这题虽然在leetcode上AC过，当场还是不出意料地写了一白板bug。他也知道这题麻烦，但毕竟写的不好，估计给我的多半是negative。
6. 50岁老美，工作内容是往搜索结果里加与用户隐私信息相关的内容，态度很和蔼。问了一道老题，给一个一次只能读4k字节的函数int read4096(byte *buff)，要求实现能读任意字节数的int read(byte *buff, int n_bytes)。他说如果愿意的话可以用java写，我想了想，java的IO根本不会，还不如用C++呢。本来一年多几乎没碰过C++，只是面试前在leetcode上拿几道练了下手，写的过程却意外地顺利，写完后跑了一个普通test case，没看出问题。
他又追问，加一个让文件指针返回到文件头部的函数reset()，要求实现把文件指针移到任意字节处的函数seek(int n_bytes)。在原来的基础上改改，倒不算难。我发现有edge case没处理好，他看时间不多就说不用再改，结束了面试。
4月份总结：
No comments:
Post a Comment