Facebook meetqun | shawnlincoding

Facebook meetqun | shawnlincoding

1.add binary
2.decode ways

2,
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
问题来了，follow up要one pass (不能找最左有多远，最右有多远)， 不要hashmap

3,
1. divide(int, int)
2. fibonacci recursive
3. BST to doubly LinkedList

4,
coding question 1： find first bad version，貌似CC150+Leetcode有
coding question 2: decode ways，lc原题

5,
http://www.meetqun.com/thread-596-1-4.html计算几何

6，
奉上上周fb面经3道。
1. draw a circle with radius R. Try to optimize the solution as much as possible. You can assume the center is the original point.
2. search a value in a rotated sorted array.
3. implement a function to write to a socket from a file: void write2socket(socket sk, String file_name), given the API 【i】int socket.write(input_buffer, int offset, int size) . offset is begining pos in buff and the return value is the number of bytes actually written into the socket. socket.write() can write arbitrary bytes(smaller than size-offset) each time.

7,
1. 从one billion的数组中取出最大的100个数。不过之后问了我一个follow up，说是如果我只取最大的一个呢？我说就是都扫一遍，O(n)复杂度。不过他说能不能提高一点，hint是for loop。我当时想了半天没想出来，不知道怎么做。。。所以从这开始就有点慌了
2. prefix notation
prefix notation如果从右扫到左就不用考虑特殊情况了，直接输出stack里最后剩的唯一一个数

8,
1. 给定matrix，只有0和1，求1的连通size，连通只算上下左右，不算对角线。比如：
0 1 0 0 1
1 1 1 0 0
1 0 0 0 1
0 0 0 0 1

2. 简单题，翻转linklist。

9,
1 Reverse List 不让用额外空间
2 Validate Binary Search Tree

10,
search in rotated array
1, 记得两种情况，可能往左可能往右2
2，duplicate 最坏O(N)

find min in rotated array
记住array可能没被rotated，就是正常的

find peak
数组为空，size 1, 2的Corner cases

题目是给一组数，假设边界无穷小，求peak (比相邻都大）
我一想是原题，binary search，时间lgn。就装模作样思考一会儿，然后写代
写完被提示，数组可能有重复怎么办？ 代码work吗？有没有更快解法?
答案是不work，比如元素都相同，没法binary search啊。
那怎么办？那好，我就想把mid，挪一挪，试试mid+1，+2…直到最后。
被告知，不够好，再想想
最后在提示下，告诉我从头开始扫，如果发现后一个比前一个大就找到了，否则继续。这样程序很简单，就一个for loop.
高潮来了。问我时间复杂度。 o(n）啊，一个for loop么，这么简单都考我？
他提示：平均时间多少？ 假设数字随机
最后明白，这只能列式计算 1/2+2*1/4+3*1/8+4*1/16+5*1/32
那结果是多少呢？ 傻了，不会算。
然后时间就到了，肯定没戏了。。。
后来明白应该这样算，假设 x=1/2+2*1/4+3*1/8+4*1/16+5*1/32
那么 x/2=1*1/4+2*1/8+3*1/16+4*1/32.。。。。
两式一减 x/2=1/2+1/4+1/8+…=1
所以x=2
所以第二个算法的时间其实是o(1)比binary search o(lgn）还好！
真是没想到，思维完全被刷题的答案固化了

11,
1）pre-fix String search
2) String evaluation: eg. Given 3 +2x +5y -(3 +5x) = 8 -7y +2x and X value，return Y value
http://www.fgdsb.com/2015/01/08/parse-formula/

12,

求binary tree所有root到left的路径。
A
B C 的话，要返回BA和CA
(to do iterative)

13,

1. inorder tree iterator
2. binary search的变种
3. 给一个数组代表股价，求股票交易的最大profit，只需要买进一次卖出一次
4. 逆波兰表达式求值

14,
第一轮电面，是个印度小哥，上来介绍了一下他自己，然后开始问问题。2D空间给一堆点，求一个点（不需要是所给的点中的一个），到所有点的曼哈顿距离最小。
distance = |x – x1| + |y – y1|。我说分别求所有点的横坐标和纵坐标的medium，组成的那个点就是需要求的那个点。然后他让我证明。证明说了好久，讲完已经过了三十几分钟了。他又问，如果那个点必须是所给的一堆点中的一个。我想了一下，跟他说我想不到什么好的解决办法，问他有没有hint，他说暴力解然后他说，你写吧，后一个的。写完他说没问题，让我问了几个问题就结束了

15,
题目是这样的，输入是a list of tasks，还有dependency list，相互之间有约束，必须要在dependent tasks结束之后才能做某一个。
比如1，2，3，4， 1优先于2，4优先于3。那么可以这么安排，1 -> 4 -> 2 -> 3，只要给出可行的order就好

16,
两个大数相乘（leetcode上的multiply strings吧），本来窃喜了一下，结果
我问什么类型的input，他说，你觉得呢。。我说string，他说，除了string呢。（我给自己挖了个坑）答long，然后意识到不行，他问为什么不行，我说如果很大的数还是hold不了，会overflow，他问long多少会overflow，我说2^64，他问2^64是多少。。。。我不知道了，也没有计算器速度算，扯了个one trillion，他记下了然后他问，那用什么input，我说可以用array，他说，恩，好，你写吧。我问，用string还是array，他说either。我选了string。然后他问算法复杂度，我一开始说了个O((m+n)^2)的，他说虽然不是他想要的，不过还是写吧。我写了两行，觉得他既然不想要这个，继续写也不好，想想之前做过一个O(m*n)的，就跟他说，有个这个复杂度的，不过要牺牲点空间，他说，好。然后我速度写完了。他说how to make your algorithm ten times faster，我想了想，貌似不能降低算法复杂度了，他说不是降低算法复杂度，是让它算得快一点。好吧，我是EE的，也没怎么研究过这个（虽然都是借口）我记得bit manipulation会比较快，就说了，他问怎么实现，我也讲了，然后他说，是会快一点，但是不会ten times faster，怎么实现ten times faster。。。我不知道，问他怎么解，他说，首先，如果是他做，他会选array作为input，然后，巴拉巴拉

Read full article from Facebook meetqun | shawnlincoding