就是给⼀一个字符串串，中间是有 [name] 这样需要替换的key。有⼀一个
gettoken() API可以调⽤用，⽐比如gettoken('name')=Steve，要求返回替换了了
key以后的字符串串。lz 问了了⼀一些clarification，说了了⼀一下思路路，然后意识到
⼀一个edge case就是 [name[company]] 这样的 input 怎么处理理。
数的⼆二进制表示是否为回⽂文
给⼀一段html，查询其中⼀一个节点，并且按要求print位置信息。
⽐比如说 <html>
<body><node><node><body>
<node><node>
<html>
查询node的话打印两条字符串串，0:html->0:body->0:node和0:html-
>1:node
第⼆二题给⼀一串串括号，⽤用树的形式表示出来
匹配俩个list的内容是否⼀一样
⽐比如list: [h,e] -> [l, l, o] -> null 和 [h,e,l] -> [l, o] -> null return true
注意data可以为null, length可以为0：
[h,e] -> [l, l, o] -> [] -> [] -> null 和 [h,e,l] -> [l, o] -> null return true
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=437032
给一个string, for example: a---adbbbc --> +++++d+++c, 如果dash的头尾字母相同则全变成加号，连续的相同字母也变成加号。
请问如果dash的首尾不相等的话，比如 “a---bc” 的情况，还是等于 "a--bc" 吗？
在hint提示下用了两次遍历，第一次把---改成字母，第二次把连续的字母变成加号
第一次遇到dash的时候用参数j记录一下当前位置，指针i遇到连续dash继续往后直到遇到字母
脸家店面加最近两个月店面面经总结
刚结束的店面，感觉是新题，发出来希望对大家有帮助。
有点像solve equation
a=b+c
b=c
c=2
条件：只有+号，左边只有一个变量，一定有一个c=2这种右边只有数字的
我用的拓扑排序
另外附上一个自己总结的最近两个月版上的店面总结，每题附上自己的思路，fb考面经的频率还是挺高的，只可惜自己没遇上。
应该就类似expression tree，从底部到顶部的拓扑排序没毛病
另外我还maintain了一个map，比如b=a+c+2, 当b的degree为0的时候，我就知道可以计算b的值了，但我需要知道b依赖哪些变量。
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=439208
给个container，升序排列列，有⼀一个get()，随机出最左或最右，还有个
isEmpty()，要求升序输出所有元素
输出升序list，用个last_pos 来指向上次叫入list的元素位置，每次pop 出来个数，和last_pos的元素比较大小，就知道插入list哪里了
按照理解应该是，get() 会随机的从两端往中间取数，直到isEmpty()。
假设现在先后取到了两个数 a,b ；只需记住a先于b取到就行，然后就可以判断了
1) a < b; 那么a肯定是来自左端，因为若a来自右端，不论b来自哪边都是要小于a的，那么直接将a输出就行（append到一个Q的最后面）
2) a > b; 同样的分析，a肯定来自右端，右端的数需要先存起来不能直接输出 （push到一个stack中）
等到 isEmpty() 后，将stack的数pop出来并append到 Q的后面就行了
给出⼀一个array of treenode，判断array⾥里里⾯面的节点是否属于同⼀一棵树并且
包含这棵树的所有节点。
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=439911
第一题是给出一个array of treenode，判断array里面的节点是否属于同一棵树并且包含这棵树的所有节点。这道题非常简单，set秒掉。
不要根节点应该也可以，每次从array里头遍历节点的时候，只把左右孩子放到set里，节点本身不放进去，最后再遍历一遍array，最后如果不在set里的节点数量大于1，说明不在同一棵树，如果array的size小于set的size，说明树的节点不全在array里
如果面试官已经说明root在array里那么就可以了。
第二题是leetcode 二琪琪原题。之前没有刷到过，在面试官的提示下花了几分钟得到最优解。最后虽然成功做出来了，但超时了5分钟左右，这可能是我挂掉面试的原因
第二题有很多类似的题，有的改成机器人打架的，给个api可以判断两个机器人谁打得赢谁，求最强的机器人之类的，本质其实就是一个数组里面找最大或者最小，你想想，找名人找机器人，不就是找一个某个属性比其他元素都强的元素吗，就是找最大最小的问题啊，保证有解的情况下一遍过，不保证有解第一遍选出candidate，第二遍验证
有⼀一本书， 书上每⼀一⻚页⻚页可以跳到第n⻚页。 问给你⼀一个开始的⻚页， 能否
到书的最后⼀一⻚页。 然后问我什什么情况⽤用bfs什什么情况⽤用dfs
给⼀一个string，要求每个character的neighbor不不能是⾃自⼰己。⽐比如aaabb要
变成 ababa。
两个string代表两个数，有可能是⼩小数或者整数，都是valid的正数。相
加。 "12345.45435"
"1234567"
or
"4242.1345" “0.134” (补零?)
简单的array题，在有序数列列列列⾥里里⾥里里⾥里里输出所有⽐比当前数⼤大n的最⼩小的数，
follow up: 拓拓展了了有重复的数
给⼀一⼀一个string: "facebook"。想象把这个string⾥里里⾥里里⾥里里的每⼀一⼀一个char拆
开，重新拼成新的string。现在给我们⼀一个string，请需要多少
个"facebook" string 才能把这个词拼出来。例例如，"cookcake" 需要两
个"facebook" string。
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=447308
round 1：hr 问题：1. 为什么选fb 2. 你最大challege 在工作中是什么。3 what is your role model 在工作中。 hr 最后15min 一道algorithm： matrix triangle filp。 hr也是cs出身，看样子。
round 2: machine learning design: in youtube search engineer： 如果你想search key word “machine”， 当你type “ma”时， 可能多种选择 “map”， “mat”。。。how to rank it。 how to search in database。
round 3: leetcode 314. Binary Tree Vertical Order Traversal
round 4: leetcode 102. Binary Tree Level Order Traversal
round 5: system design： goe 题： 给你 p（latitude，longitude） search 一个 半径 n miles 的circle 内所有 p（latitude，longitude）。 如何get database， 怎么存 database，设计怎么search。 map reduce 之类
round 6: math 题关于 income tax问题： 举个例子 income 10 000： tax 5% ， 超过部分 10 000 -20 000: 超过部分tax 10%。。。。。。
matrix triangle flip:
以对⻆角线 反转：
input:
[1, 2]
[3, 4]
output:
[1, 3]
[2, 4]
http://massivealgorithms.blogspot.com/2018/11/leetcode-867-transpose-matrix.html
已知⼀一系string id tuples，输出去重以后的结果。例例如输⼊入是：（a，
b，c），（d，e），（c，g），（g，h），输出应该是（a，b，c，g，
h），（d，e）——（a，b，c）和（c，g）⾥里里⾯面都出现c，所以应该合并
起来
Union-Find
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=450889
第一轮: 347. Top K Frequent Elements : 计算频率再Quick Select秒之, 但是面试官希望我用bucket sort 不知道是不是挂在了这.
次最优吧，quick select 虽然avg time complexity = bucket sort。 但是worst case = O（n^2)
第二轮:
236. Lowest Common Ancestor of a Binary Tree 秒之 不解释
follow up: 如果给的目标节点不一定在同一个树中 怎么办: 加一个HashSet记录所有从root开始访问的节点，找完common ancester以后看是否两个目标节点都在 HashSet里。 秒之.
针对lca follow up，想跟楼主讨论下：楼主做法是set存所有node，感觉这样space开销稍微有点大。
如果直接在搜索的时候加两个global boolean, 找到一个，就把对应的turn true。最后check这两个boolean就行。这样space constant
560. Subarray Sum Equals K 秒之
follow up: 证明/解释一下为什么你能从O(n^2) 得到O(n)时间复杂度的解法。 我说的有的没的,面试官也不是很在意.
http://massivealgorithms.blogspot.com/2017/05/leetcode-560-subarray-sum-equals-k.html
第三轮:
BQ:
1.Self Introduction. From 1point 3acres bbs
2.如果你manager给你的任务实际上超出预计任务量 你怎么办
3.最challenging project.
Coding: 假定有一个一个坐标系, 输入是一些列坐标点, 求这些坐标点里能构成的长方形中,面积最小的那个的面积是多少。
讨论了大概5分钟，然后面试官提到如果要你找到所有的长方形怎么办。
马上想起 先选第一个点，再找和第一个点Y值相同的第二个点，再找和第二个点X值相同的第三个点, 如果这三个点都存在计算出第四个点的坐标，判断这个点在不在给的输入中即可。
如果判断在不在,？一个HashSet开始的时候存所有点的 string representation eg x#y, 计算出第四个点的时候 看第四个点对应的string representation在不在HashSet即可。同时用一个 Integer 记录最小面积. check 1point3acres for more.
Time Complexity: O(n^3)
Space Complexity: O(n)
三轮连续没有休息,BQ的时候答得有点晕,自求不犯硬伤就好了。
n^2枚举长方形对角线的两个点，然后看另外两个点在不在set里。复杂度还是n^2
而且我说秒 不是直接上去把代码写完无交流。 正规流程肯定要演完啊。。。 感觉杠精真的多。 实际上面试那天本来就是一确定是LC原题 脑子里立刻就知道怎么做了
string representation eg x#y 里 x指的是这个点的横坐标, y指的是这个点的纵坐标
我说秒 是看到题目你就知道怎么做了。。。。。 戏肯定是要演的。。。 这个是基本默认的事实。。。 你要先说一个naive solution(如果有的话)或者假装和面试官讨论一下其他case。 然后说自己的解法，时间复杂度等,面试官认可了 然后再去写代码。。。 你问得有点幼稚啊，大兄弟
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=450832
1。二位字符矩阵，从左上到右下打印每一条路
2。翻转句子中的词，标点留在原位
我这题写的不好,想法是把单词分在list里，标点当作一个独立的词，然后用两个指针对换单词only
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=450962
3. 从来没见过的题，就是
n = 0 (0, 0)
n = 1 (1, 0)
n = 2 (0, 1)
n = 3 (-1, 0)
n = 4 (0, -1)
n = 5 (2, 0)
n = 6 (1, 1)
n = 7 (0, 2)
…
以此类推
问给一个n, 坐标是多少
当时只有3分钟的时候他问的我这道题，我当场说有规律， 每一圈一个pattern, 但是每一圈的长度不同，具体哪里不同当场没说对，就结束了
飞思布克昂塞面经
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=451873
2. 一个，增加/删除/替换操作均认为是一次动作，最少几次动作可以使之成为回文字符串
3. leetcode 扎气球
4. 一堆点，求两个点连成的线所构成的最大斜率，输出这个斜率和构成斜率的点，不考虑x1==x2的情况
第四题的话，按x轴排序后，最大值斜率只可能出现在相邻两点的连线上
https://blog.csdn.net/tianya_team/article/details/51001826
Facebook 店面+onsite
利口 74： 序号转成1维， 然后二分查找，做完聊了以前做的，过了几天收到onsite通知
onsite:
轮1:
利口 199， 递归解的， 把层数传进去，每层第一个遇到的存进去。利口 480， 用一个中位数的队列做的，中数队列部分时间不够了，大致说了下剩下的
round2:
给一个已经排好序的数组， 返回每个元素的平方，并且也是排好序的数组。感觉解得慌了点，用了额外的空间，做完也没让改进了，直接上第二题。
第二题利口 139, 变成返回最少能组成的词数，方法差不多，也是用dp解的
http://massivealgorithms.blogspot.com/2015/09/leetcode-word-break-java.html
round3:
系统设计，设计记录手机用户浏览和点击广告，并用来算点击率。主要是写的部分，用户读手机不用管
round4:
Behavior, 聊了很多之前做的，还有些是和经理相处的问题，经常被打断。最后剩个5分钟来了一题, -_-||
二叉树 先序 的iterator, 用个stack存节点，最后还在纠结先走左边还是右边的时候，时间到了
round5:
ml 设计，facebook marketplace， 基本上是ranking的问题
. From 1point 3acres bbs
面完大概一周多收到据信，估计主要跪在behavior轮
脸书 Uday onsite
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=450169
面试的时候问清楚了是第二种情况，1 can appear anywhere after 6 and can appear as many time as possible……可能面试官看我完全不懂就临场规定了吧。
当然如果真要求1必须紧跟6做法也差不多。
如果是6之后可以出现任意次1
// dp(i)(0): num of ways to score i points where have not scored 6 points-baidu 1point3acres
// dp(i)(1): num of ways to score i points where have scored 6 points for at least once
dp(0)(0) = 1
dp(0)(1) = 0
dp(i)(0) = dp(i - 2)(0) + dp(i - 3)(0)
dp(i)(1) = dp(i - 6)(0) + dp(i - 1)(1) + dp(i - 2)(1) + dp(i - 3)(1) + dp(i - 6)(1)
如果是每一个1都必须紧跟在某一个6之后
dp(0) = 1
dp(i) = dp(i - 2) + dp(i - 3) + dp(i - 6) + dp(i - 7)
注意判断边界情况
朋友FB最近的电话面试
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=443830
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=451849
第一轮behavior轮天竺小姐姐，面试官找不房间迟了10min，问完有的没的后留了不到十分钟让写一个almostPalidrom
第二轮做internal search的白人小哥哥，让输出一个数的factorial结果，其实就是批了一层皮的大卫数乘法在string上操作，很久以前做过但是写的略慢，就写了这一题。
第三轮华人小姐姐，血崩的一轮，估计是想给我放水给了一道interval AND（intersection），结果我写了个bug，提示后改正，略超时。接着问如果一个很大一个很小怎么操作，答对B里的每个元素两次binary search分别找到A里面的对应的range然后再找AND，然后没写完。而且结束后一想其中一个binary search还出了问题。跪的稳稳地
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=449141
aaaabbbcdaaa and a4b3cda3
abbbcccc and ab3c4
看string是否相同
For a given vector of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K
For example, for K = 10 and vector [2, 4, 5, 7], the solution is 5 and these are all the subsets that satisfy the requirements: [2], [4], [2, 4], [2, 4, 5], [2, 5].
sort vector O（nlogn)
if 2*n<=k
2 457<=8 1*2^3=8
4 5 1*2^1 = 2
5 1
新鲜脸书电面跪经
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=449156
题目是，一个排好序的array，找出所有满足的最大值和最小值相加为定值k的subset的数量。follow-up是找出max+min <= k 的子集的数量。因为答案中有计算2^n，所以问了这个怎么实现比较快。最后一个follow-up是问如果这个array非常长的时候，怎么用多线程来实现算法，完全没思路，山歌虽然说没关系，但是已经跪了
Facebook 再面
面试官听口音和看名字感觉是意大利之类地方的人，口音有点浓重。 开始问了几个general android question，大概5分钟左右，剩下时间开始做题。
题目不是tag的题（或者是我没刷到的？）： 国际象棋问题， 不过不是queen， 是knight， 走法是横1竖2 或者竖2横1（不知道我说的明不明白，不过网上应该能找到这些规则）
example：8x8棋盘 K 是骑士， 1 是 这个骑士 1 move 可以到达的位置。骑士可以走到棋盘外， 但是不能从棋盘外走到棋盘里。 比如第二个example， 棋盘内骑士下一步只能有4种可能move。
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 K 0 0 0 0 0 0 0 0 0 0 K
0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
input 是 骑士的position（x， y） 和 numbers of moves n.
然后输出 n moves 之后， 骑士还在棋盘上的概率。 其中 1 表示一定在棋盘里， 0 表示不可能在棋盘里（我面试后想了想， 应该不可能返回 0， 因为只要骑士在棋盘上， 就一定可以存在让他移动的地方，所以不管n是几，只要反复移动就可以了，如果有大神知道可以返回0 的case 请指正）
本来开始听他说cheeseboard 以为会是 N-queen之类的题， 但是听到后来简直一脸懵逼，还要求返回概率， 楼主既不懂国际象棋（queen的走法还是因为刷题才知道的），数学也是弱鸡（这个概率怎么算还是面试官提示的）， 再加上那个面试官口音确实有点重， 需要他repeat几次才确定题意，所以做的时候已经有点慌了， 好在听完之后就觉得需要做recursive， 得到他点头后， 一直像这个方向靠拢。 最好在他提供了好几个tips之后，算是勉强做了出来， 时间所剩无几。走了几个test case， 然后问了下edge case， 就结束了。 最后问他问题，问的是facebook 怎么做version control。
以下是我的思路：
public float calculate(int[] pos, int n){
if(n == 0)
return 1;
int in = 0;//in 是 在棋盘里的可能move的数量
if(pos[0] + 1 < 8 && pos[1] +2 < 8)
in += calculate(newPos, n-1);//这里楼主面试时候写的是 calculate(pos, n-1), 实际上应该传入新的位置，就是[pos[0]+1, pos[1] + 2] 才对。 不过面试官不知道是没发现还是没怎么care。。）
.
.
.
//一共8组 类似的 if block， 列出8种move的可能（[x+1, y+2], [x+1, y-2], [x-1, y+2]....)
return in/8.0;
}. 1point3acres
补充1：本来开始的题目是 m x m board， 后来因为时间关系, 面试官说我们就用8 x 8 来做就好了， 不过如果是m x m的话， 应该也只是算概率的时候 除以m就好了。
补充2: 以上的代码基本上就是在面试时候写出来， 并没有被要求写完整的代码。 8 个 if block 也没有都写， 但是我把8种情况跟面试官说清楚了， 然后他主动说我们不需要waste time on that。 但是代码写完之后， 他提了以下问怎么能把那8个if block 变得更generic， 更简洁，我当时一下子就想到了LC 一道用array 来写pair的题， 用了类似的思路， 把8个if 变成一个 loop + if 搞定。 面试官连续说了几个good。
总结： 其实面试结束之后再想这道题， 本身不是特别难， 主要是当时确实有点慌了，不过好在这个面试官真的很好，给了好几个tips， 我也一直遵循 think of loud原则， 全程一直跟他交流，表达我的思路。其实面试结束后自己感觉不是特别好， 跟两年前那次比差了不少， 以为过不了， 还特意跟猎头发邮件说面试官口音的问题，问有没有可能加免。 没想到今天中午猎头就回复好消息啦， 感恩！
码字不容易， 画那两个破example更是费劲，也没加积分限制。 各位看官有富裕大米的记得搭上哦
还一个补充， 关于edge case ，其实就是检查input里的pos 是不是 2d array。 因为function的 signature不是面试官给的， 而是自己写的， 所以面试官提了一下， 在最上边加一个 null check + length check 就好了
联署面经
回楼上的，不好意思原帖说的O(1)那个，我混了题目。其实问到的是类似霰酒吧这道，然后拓展到有重复的，按频率为权重随机返回
脸的高频似乎是lru，lfu似乎没有考过-baidu 1point3acres
建立倒排索引，然后分布式，有两种方式，一种是用id shard，每进来一条，写的时候只需要写入一台机器，特别快，读的时候要广播给cluster，可以参考twitter的架构
还有一种是按照key word shard，写的时候要写入多台，读的时候对于每个key word只需要从一台读，可以参考google的架构
FB status就是FB上自己设置的状态的一个句子，其实就是search tweet的马甲题。估计1B users，每个status 100B，数据量其实只有100GB，单机是可以放下的。我有点尴尬说这个好像是个单机就能解决，然后面试官说可以搜索历史记录的，于是就顺理成章的讨论分布式了。还问了怎么rank结果，我说可以按时间，按相关度
每个后面都留了足够的时间问问题，感觉面试官都很nice，体验很好
Facebook惜败
为了能和老婆大人早日汇合，弱弱的我在8月中旬开始了在职找工的刷题节奏。电面在九月初，一道find first unique简单题和一道get intervals from two sorted intervals的中等题。Onsite约在了10月25日，结果今天在回程的飞机上收到了拒信，当时心里很是苦涩，但生活奋斗还是得继续！HR给了deeper反馈，说coding and behavior rounds did well, but designs are below FB expectation.
具体的coding题目其实都是LC原题，但要求bug free，途中对复杂度讨论面试官会故意发问质疑，但只要很友好的解释思路，别一上来就code，保证了好的交流，算法不难的。这次面试官们都非常Nice， 很向往的组，可惜了。。。
a). 10:00 一个韩国的大姐（背景巨牛，各大公司的principal machine leanring SE), 题目是LC124(follow up是打印出path）。
b). 10:45 一个印度的CMU小哥（比较腼腆），高频题LC297. 对空间复杂度要注意，因为要存Null，所以worst case需要O(2n + 1)的space（n是所有node数量）。第二题是LC238，但要注意是允许除法，切记别一上来按照原题思路来做，这样很明显就给人无脑刷题的印象。
c). 11:30 一个中国小哥（很开朗）的behavior轮，问了proud project， conflict，career path等经典的问题。最后一道简单的Dictionary中能不能组成target word，最后follow up关于dictionary很大的情况怎么办，比如用cache。
d). （噩梦开始）12:30， 一个白人大哥很犀利的样子（背景也很牛），爬虫设计，10k的机子爬1B的wiki，不能爬重复的page。本人准备的设计题中恰巧没注重这方面，所以答的很磕绊。大哥先问了单机子多线程怎么实现，怎么加锁，然后到了分布式。其实核心思想是hash url，然后进行更even的分配负载。
e). 1:15，很nice的国人小哥，问的是ML design关于POI（point of interest). 注重点是ML的整体思路，从问题的描述道最后的service搭建，过程中会涉及到database的query，categorical feature的降唯（embedding）等等细节。这轮楼主表示面的一般，但不至于挂。
FB SWE 面经，求大米
一道是给工资和对应区间的税的表格，算工资税
第二道有点像蠡口尔尔其，不过只有+和*和数字，不考虑其他的，我用的stack的方法做，问时间空间复杂度，然后follow up问能不能把空间复杂度降到O(1)
原来的想法的遇到 * 就算，遇到 + 就压到stack里
然后改成，遇到+或者末尾，就把当前的数字加到sum上去，如果是*当前的数字先设成1，然后不断乘，直到遇到+或者末尾，再加到总和上，不断循环
上来直接开始做题,第一题是给一个数组里面是commit number, 分别给good commit 的number和bug commit的number还提供了一个boolean isBug(int commitNumber)说这个function的cost很大
要求返回出现第一个bug commit的number
int findFirstBugCommit(int arr[], int good, int bug)
比如 9, 10, 11, 12, 13, .... 27
good good bug bug
输入(9, 27) 要求返回12
第一题我用了Binary Search, 面试官之后问了test cases, edge cases然后拍了白板的code就进入下一题
第二题是两个binary string相加,写完后followup是改成十以内任意进制相加
脸熟上门
第一轮 behavior + 15-min coding 印度manager 入职6年半
第二轮 coding 华人 new grad入职2年半
第三轮 coding 华人 入职3年半
第三轮: 给一个数列，一个k，求max subarray with k elements。然后LC刘拔鸠
http://massivealgorithms.blogspot.com/2019/01/leetcode-689-maximum-sum-of-3-non.html
非死不可10/12面经
1. 不用 / 和 % 操作符做integer division。给出n和d, 求n / d和n % d。当时想了2个思路，一个O(n/d)的暴力破解，一个O(log(n))的binary search。都写出代码了，面试官让分析一下哪个快，假设n完全随机且d在[1, n]之间随机
对就是那题，但是简单了很多，0 < d <= n，少了很多烦人的case
然后可以用乘法？原题好像不允许用乘法，用乘法的话就直接二分法吧？
第一轮： 上来先问了一些相关经历，自己最proud的project 等等。 然后就做coding， binary tree lowest common ancestor， time complexity O(n)。follow up 是如果有一个treenode 不在树里 应该怎么做； 之后的follow up是设计一个存储结构，使得搜索只需要O(lg(n))时间;
O(logN)的LCA是很经典的算法了（虽然在leetcode考纲之外）可以自己google一下
比较容易写的是倍增算法，对每个结点存储和它距离为1、2、4、8……的祖先结点，然后查询的时候用二分法
第二轮： 上来还是问相关经历，然后做题。设计一个BigInteger class 可以计算任意位数的正整数加和乘，要求写出constructor， add function， multiply function。
非死不可电面
就一题 莉蔻兒毋伞
[size=18.6667px]但是给的时间段是string. From 1point 3acres bbs
比如"10a - 10:30a
直接蒙蔽 在string这里搞了半天搞到最后
https://massivealgorithms.blogspot.com/2015/08/like-coding-leetcode-253-meeting-rooms.html
把时间小时:分钟全变成分钟可以吗 pm再加上720分钟
脸熟挂经
第一题给一个数组 让你求连续最长递增子序列 比如 3 1 2 4 7 2 3 -1 -3 11 返回 1 2 4 7 很简单的一道热身题 结果懵逼了 先写了一个暴力算法 花了太久时间 最后口头优化成O(n)时间 O(1)空间 估计就是跪在这一题了 是lc原题
第二题是给一个string的括号 让你移出无效的括号返回一个结果 注意只返回一个即可
只要一个结果就行 来回扫两遍 每次多出的去掉最后一个就行
gettoken() API可以调⽤用，⽐比如gettoken('name')=Steve，要求返回替换了了
key以后的字符串串。lz 问了了⼀一些clarification，说了了⼀一下思路路，然后意识到
⼀一个edge case就是 [name[company]] 这样的 input 怎么处理理。
数的⼆二进制表示是否为回⽂文
给⼀一段html，查询其中⼀一个节点，并且按要求print位置信息。
⽐比如说 <html>
<body><node><node><body>
<node><node>
<html>
查询node的话打印两条字符串串，0:html->0:body->0:node和0:html-
>1:node
第⼆二题给⼀一串串括号，⽤用树的形式表示出来
匹配俩个list的内容是否⼀一样
⽐比如list: [h,e] -> [l, l, o] -> null 和 [h,e,l] -> [l, o] -> null return true
注意data可以为null, length可以为0：
[h,e] -> [l, l, o] -> [] -> [] -> null 和 [h,e,l] -> [l, o] -> null return true
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=437032
给一个string, for example: a---adbbbc --> +++++d+++c, 如果dash的头尾字母相同则全变成加号，连续的相同字母也变成加号。
请问如果dash的首尾不相等的话，比如 “a---bc” 的情况，还是等于 "a--bc" 吗？
在hint提示下用了两次遍历，第一次把---改成字母，第二次把连续的字母变成加号
第一次遇到dash的时候用参数j记录一下当前位置，指针i遇到连续dash继续往后直到遇到字母
public String convert2Plus(String s) {
char[] ch = s.toCharArray();
int curPos = 0;
while(curPos < ch.length) {
int nextPos = curPos + 1;
while(nextPos < ch.length - 1 && ch[nextPos] == '-') nextPos++;
if(nextPos > curPos + 1 && ch[curPos] == ch[nextPos]) {
char c = ch[curPos];
for(int i=curPos+1; i<=nextPos-1; i++)
ch[i] = c;
}
curPos = nextPos;
}
int i = 0;
while(i < ch.length) {
char c = ch[i];
int j = i + 1;
while(j < ch.length && ch[j] == c) {
ch[j++] = '+';
}
if(j>i+1) ch[i] = '+';
i = j
}
return new String(ch);
}
char[] ch = s.toCharArray();
int curPos = 0;
while(curPos < ch.length) {
int nextPos = curPos + 1;
while(nextPos < ch.length - 1 && ch[nextPos] == '-') nextPos++;
if(nextPos > curPos + 1 && ch[curPos] == ch[nextPos]) {
char c = ch[curPos];
for(int i=curPos+1; i<=nextPos-1; i++)
ch[i] = c;
}
curPos = nextPos;
}
int i = 0;
while(i < ch.length) {
char c = ch[i];
int j = i + 1;
while(j < ch.length && ch[j] == c) {
ch[j++] = '+';
}
if(j>i+1) ch[i] = '+';
i = j
}
return new String(ch);
}
脸家店面加最近两个月店面面经总结
刚结束的店面，感觉是新题，发出来希望对大家有帮助。
有点像solve equation
a=b+c
b=c
c=2
条件：只有+号，左边只有一个变量，一定有一个c=2这种右边只有数字的
我用的拓扑排序
另外附上一个自己总结的最近两个月版上的店面总结，每题附上自己的思路，fb考面经的频率还是挺高的，只可惜自己没遇上。
应该就类似expression tree，从底部到顶部的拓扑排序没毛病
如果是拓扑排序的话是怎么样建图呢？
b=c 就是 c指向b ； a=b+c 就是 b指向a 加上 c指向a ？
是这样的呀，然后从有数字的symbol 作为init 开始bfs 就行
另外我还maintain了一个map，比如b=a+c+2, 当b的degree为0的时候，我就知道可以计算b的值了，但我需要知道b依赖哪些变量。
给个container，升序排列列，有⼀一个get()，随机出最左或最右，还有个
isEmpty()，要求升序输出所有元素
输出升序list，用个last_pos 来指向上次叫入list的元素位置，每次pop 出来个数，和last_pos的元素比较大小，就知道插入list哪里了
按照理解应该是，get() 会随机的从两端往中间取数，直到isEmpty()。
假设现在先后取到了两个数 a,b ；只需记住a先于b取到就行，然后就可以判断了
1) a < b; 那么a肯定是来自左端，因为若a来自右端，不论b来自哪边都是要小于a的，那么直接将a输出就行（append到一个Q的最后面）
2) a > b; 同样的分析，a肯定来自右端，右端的数需要先存起来不能直接输出 （push到一个stack中）
等到 isEmpty() 后，将stack的数pop出来并append到 Q的后面就行了
vector<int> OutputOrdered(Container& ct) { vector<int> res; stack<int> stk; while (!ct.isEmpty()) { int cur = ct.get(); if (!stk.empty() && cur > stk.top()) { res.push_back(stk.top()); stk.pop(); } stk.push(cur); } while (!stk.empty()) { res.push_back(stk.top()); stk.pop(); } return res;}给出⼀一个array of treenode，判断array⾥里里⾯面的节点是否属于同⼀一棵树并且
包含这棵树的所有节点。
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=439911
第一题是给出一个array of treenode，判断array里面的节点是否属于同一棵树并且包含这棵树的所有节点。这道题非常简单，set秒掉。
不要根节点应该也可以，每次从array里头遍历节点的时候，只把左右孩子放到set里，节点本身不放进去，最后再遍历一遍array，最后如果不在set里的节点数量大于1，说明不在同一棵树，如果array的size小于set的size，说明树的节点不全在array里
如果面试官已经说明root在array里那么就可以了。
array里存在而set里不存在的就是一个tree的root，存在多个root时就不是同一棵树
在同属同一棵树的情况下比较set与array的size：. check 1point3acres for more.
在全包含节点的情况下，set比array少一个root，但如果array包含的不全，也就是至少有某个node的child没有被放进去，那么set的size至少会与array相等甚至更大，所以档arrays的size小于等于set时就包含的不全
第二题有很多类似的题，有的改成机器人打架的，给个api可以判断两个机器人谁打得赢谁，求最强的机器人之类的，本质其实就是一个数组里面找最大或者最小，你想想，找名人找机器人，不就是找一个某个属性比其他元素都强的元素吗，就是找最大最小的问题啊，保证有解的情况下一遍过，不保证有解第一遍选出candidate，第二遍验证
有⼀一本书， 书上每⼀一⻚页⻚页可以跳到第n⻚页。 问给你⼀一个开始的⻚页， 能否
到书的最后⼀一⻚页。 然后问我什什么情况⽤用bfs什什么情况⽤用dfs
给⼀一个string，要求每个character的neighbor不不能是⾃自⼰己。⽐比如aaabb要
变成 ababa。
两个string代表两个数，有可能是⼩小数或者整数，都是valid的正数。相
加。 "12345.45435"
"1234567"
or
"4242.1345" “0.134” (补零?)
简单的array题，在有序数列列列列⾥里里⾥里里⾥里里输出所有⽐比当前数⼤大n的最⼩小的数，
follow up: 拓拓展了了有重复的数
给⼀一⼀一个string: "facebook"。想象把这个string⾥里里⾥里里⾥里里的每⼀一⼀一个char拆
开，重新拼成新的string。现在给我们⼀一个string，请需要多少
个"facebook" string 才能把这个词拼出来。例例如，"cookcake" 需要两
个"facebook" string。
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=447308
round 1：hr 问题：1. 为什么选fb 2. 你最大challege 在工作中是什么。3 what is your role model 在工作中。 hr 最后15min 一道algorithm： matrix triangle filp。 hr也是cs出身，看样子。
round 2: machine learning design: in youtube search engineer： 如果你想search key word “machine”， 当你type “ma”时， 可能多种选择 “map”， “mat”。。。how to rank it。 how to search in database。
round 3: leetcode 314. Binary Tree Vertical Order Traversal
round 4: leetcode 102. Binary Tree Level Order Traversal
round 5: system design： goe 题： 给你 p（latitude，longitude） search 一个 半径 n miles 的circle 内所有 p（latitude，longitude）。 如何get database， 怎么存 database，设计怎么search。 map reduce 之类
round 6: math 题关于 income tax问题： 举个例子 income 10 000： tax 5% ， 超过部分 10 000 -20 000: 超过部分tax 10%。。。。。。
matrix triangle flip:
以对⻆角线 反转：
input:
[1, 2]
[3, 4]
output:
[1, 3]
[2, 4]
http://massivealgorithms.blogspot.com/2018/11/leetcode-867-transpose-matrix.html
已知⼀一系string id tuples，输出去重以后的结果。例例如输⼊入是：（a，
b，c），（d，e），（c，g），（g，h），输出应该是（a，b，c，g，
h），（d，e）——（a，b，c）和（c，g）⾥里里⾯面都出现c，所以应该合并
起来
Union-Find
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=450889
第一轮: 347. Top K Frequent Elements : 计算频率再Quick Select秒之, 但是面试官希望我用bucket sort 不知道是不是挂在了这.
次最优吧，quick select 虽然avg time complexity = bucket sort。 但是worst case = O（n^2)
第二轮:
236. Lowest Common Ancestor of a Binary Tree 秒之 不解释
follow up: 如果给的目标节点不一定在同一个树中 怎么办: 加一个HashSet记录所有从root开始访问的节点，找完common ancester以后看是否两个目标节点都在 HashSet里。 秒之.
针对lca follow up，想跟楼主讨论下：楼主做法是set存所有node，感觉这样space开销稍微有点大。
如果直接在搜索的时候加两个global boolean, 找到一个，就把对应的turn true。最后check这两个boolean就行。这样space constant
560. Subarray Sum Equals K 秒之
follow up: 证明/解释一下为什么你能从O(n^2) 得到O(n)时间复杂度的解法。 我说的有的没的,面试官也不是很在意.
http://massivealgorithms.blogspot.com/2017/05/leetcode-560-subarray-sum-equals-k.html
第三轮:
BQ:
1.Self Introduction. From 1point 3acres bbs
2.如果你manager给你的任务实际上超出预计任务量 你怎么办
3.最challenging project.
Coding: 假定有一个一个坐标系, 输入是一些列坐标点, 求这些坐标点里能构成的长方形中,面积最小的那个的面积是多少。
讨论了大概5分钟，然后面试官提到如果要你找到所有的长方形怎么办。
马上想起 先选第一个点，再找和第一个点Y值相同的第二个点，再找和第二个点X值相同的第三个点, 如果这三个点都存在计算出第四个点的坐标，判断这个点在不在给的输入中即可。
如果判断在不在,？一个HashSet开始的时候存所有点的 string representation eg x#y, 计算出第四个点的时候 看第四个点对应的string representation在不在HashSet即可。同时用一个 Integer 记录最小面积. check 1point3acres for more.
Time Complexity: O(n^3)
Space Complexity: O(n)
三轮连续没有休息,BQ的时候答得有点晕,自求不犯硬伤就好了。
| 第三轮那题，如果只考虑和坐标轴对齐的矩形的话，有更优解 把全部x相同的点对两两连线，这样最多连出O(n^2)条竖线，记为(y1,y2,x) 然后把所有竖线过一遍，维护一个(y1,y2)->(x_min,x_max)的hash map，再把这个hash map过一遍就找到答案了 复杂度O(n^2) 补充内容 (2018-10-20 06:13): 好像我也弄复杂了 直接枚举左下点和右上点然后用hash set检查左上点和右下点是否存在就行了，O(n^2)时间O(n)空间 |
而且我说秒 不是直接上去把代码写完无交流。 正规流程肯定要演完啊。。。 感觉杠精真的多。 实际上面试那天本来就是一确定是LC原题 脑子里立刻就知道怎么做了
碰到有同学和我说 你怎么一直秒秒 怎么还fail... 我想说: Top K, LCA, Subarray Sum Equals K 这种秒不了 才是有问题吧，面试官大概率出这题就是想抬我一手. 如果这些题ha做的磕磕碰碰 我估计面试官肯定要多扣分...
我说秒 是看到题目你就知道怎么做了。。。。。 戏肯定是要演的。。。 这个是基本默认的事实。。。 你要先说一个naive solution(如果有的话)或者假装和面试官讨论一下其他case。 然后说自己的解法，时间复杂度等,面试官认可了 然后再去写代码。。。 你问得有点幼稚啊，大兄弟
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=450832
1。二位字符矩阵，从左上到右下打印每一条路
2。翻转句子中的词，标点留在原位
统一回复一下关于第二题，和里口有些区别，因为有标点
比如： Hi, nice to see you. 变为 you, see to nice Hi.
http://massivealgorithms.blogspot.com/2014/12/leetcode-reverse-words-in-string-ii.html比如： Hi, nice to see you. 变为 you, see to nice Hi.
我这题写的不好,想法是把单词分在list里，标点当作一个独立的词，然后用两个指针对换单词only
应该就是这个，不过这题也许有corner case，比如有leading space和trailing space怎么处理之类的，神烦……
3. 从来没见过的题，就是
n = 0 (0, 0)
n = 1 (1, 0)
n = 2 (0, 1)
n = 3 (-1, 0)
n = 4 (0, -1)
n = 5 (2, 0)
n = 6 (1, 1)
n = 7 (0, 2)
…
以此类推
问给一个n, 坐标是多少
当时只有3分钟的时候他问的我这道题，我当场说有规律， 每一圈一个pattern, 但是每一圈的长度不同，具体哪里不同当场没说对，就结束了
最后一题顺时针方向转动的吗
是逆时针的
飞思布克昂塞面经
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=451873
1. 一个int array，求其中集合数量，满足条件：子集中元素彼此异或运算的结果是质数。这个问题应该是hackerrank上的prime xor那道题，大家可以去看看，一开始看这道题真的容易懵逼
面试官没有强调数据的大小范围，是我后来特意问了，才给定了一个相对小范围
2. 一个，增加/删除/替换操作均认为是一次动作，最少几次动作可以使之成为回文字符串
public static int makeStringPalindrome(String s) { if(s == null || s.length() == 0) { return 0; } int n = s.length(); int[][] dp = new int[n][n]; for(int i = 0; i < n; i++) { dp[i][i] = 0; } for(int len = 2; len <= n; len++) { for(int i = 0; i < n; i++) { int j = i + len - 1; if(j < n) { if(s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i+1][j-1]; } else { dp[i][j] = Math.min(dp[i+1][j-1], Math.min(dp[i+1][j], dp[i][j-1])) + 1; } } } } return dp[0][n-1]; }4. 一堆点，求两个点连成的线所构成的最大斜率，输出这个斜率和构成斜率的点，不考虑x1==x2的情况
https://blog.csdn.net/tianya_team/article/details/51001826
平面上有N个点，每两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点，斜率不存在的情况不考虑。
思路：
可以先将N个点按x进行排序。
斜率k最大值为max(斜率(point[i],point[i+1])) 0<=i<n-2。
时间复杂度：O（nlgn）
Facebook 店面+onsite
利口 74： 序号转成1维， 然后二分查找，做完聊了以前做的，过了几天收到onsite通知
onsite:
轮1:
利口 199， 递归解的， 把层数传进去，每层第一个遇到的存进去。利口 480， 用一个中位数的队列做的，中数队列部分时间不够了，大致说了下剩下的
round2:
给一个已经排好序的数组， 返回每个元素的平方，并且也是排好序的数组。感觉解得慌了点，用了额外的空间，做完也没让改进了，直接上第二题。
第二题利口 139, 变成返回最少能组成的词数，方法差不多，也是用dp解的
http://massivealgorithms.blogspot.com/2015/09/leetcode-word-break-java.html
round3:
系统设计，设计记录手机用户浏览和点击广告，并用来算点击率。主要是写的部分，用户读手机不用管
round4:
Behavior, 聊了很多之前做的，还有些是和经理相处的问题，经常被打断。最后剩个5分钟来了一题, -_-||
二叉树 先序 的iterator, 用个stack存节点，最后还在纠结先走左边还是右边的时候，时间到了
round5:
ml 设计，facebook marketplace， 基本上是ranking的问题
. From 1point 3acres bbs
面完大概一周多收到据信，估计主要跪在behavior轮
脸书 Uday onsite
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=450169
| 第一题 sub-array sum to k-baidu 1point3acres 先问了 会不会有 negative value, 说不会。但我还是直接说了 用 set 存 previous sum 的方法，O(N) Time Complexity, worst case O(N) space. interviewer 问能不能 能不用 extra space。就说了 sliding window, 然后让 code. 第二题 find lowest common ancestor among deepest nodes in k-nary tree. 之前刷题只有印象 给俩 node p, q 在里面找。就讨论的一下先找 deepest nodes 然后再 iterate parents together. 没时间写答案了就没写。 第二轮 BQ 介绍自己的 work experience，讲了最近的两个实习，被 interviewer 打断 问 project that you are mostly proud of 又问了和同事冲突怎么办，和如何对待别人给的 constructive feed back. 还有 15 分钟的样子做了一个 merge intervals 第三轮 体验最好的一轮，天竺国的小姐姐很 friendly, 聊的很开心。 第一题 Binary Tree to Circular DDL, inorder 顺序。 第二题 check if is palindrome, can remove at most one character. |
脸书电面面筋
Q1. 求乘方（类似武陵）。人生第一次面试非常紧张，而且当时有点想多拼几题的心态。因为面试官把return type写成了int，竟然忘记检查power是不是负数，面试官给了一个负数的test case，argue了一下这种情况就返回0行不行，面试官说行之后添了一行code。然后心态立马有点崩了，毕竟最简单的一题竟然出了bug，眼泪差点都要掉出来了……
Q2. 二叉树中序遍历（酒肆原题），要求分析时间空间复杂度。做的还算顺，心态拉回来了一些。. check 1point3acres for more.
Q3. （新题？）美式足球，每场可以得2，3，6或者1分，而且得了6分之后才能得1分。给一个分数求多少种取得的方法。注意：如果是5分，[2, 3]和[3, 2]是不同的方式。不算难的dp，掐着时间写完，面试官说他自己看看code的对错就好，自己目测应该是做出来了。
中场深呼吸了几口气，喝了一杯酸奶准备二面。
二面：
Q1. 移除最少不匹配括号，只需要找到一个解（类似伞领医），比如input = "((a)b))(c)(" 那么一个可行的output就是 "((a)b)(c)"。我用了两个栈，面试官问了能不能用一个栈，我想了想给了思路，没有要求再写。然后问了时间、空间复杂度。
Q2. 下一个排列（散衣原题），也问了时间、空间复杂度
Q2. 二叉树中序遍历（酒肆原题），要求分析时间空间复杂度。做的还算顺，心态拉回来了一些。. check 1point3acres for more.
Q3. （新题？）美式足球，每场可以得2，3，6或者1分，而且得了6分之后才能得1分。给一个分数求多少种取得的方法。注意：如果是5分，[2, 3]和[3, 2]是不同的方式。不算难的dp，掐着时间写完，面试官说他自己看看code的对错就好，自己目测应该是做出来了。
中场深呼吸了几口气，喝了一杯酸奶准备二面。
二面：
Q1. 移除最少不匹配括号，只需要找到一个解（类似伞领医），比如input = "((a)b))(c)(" 那么一个可行的output就是 "((a)b)(c)"。我用了两个栈，面试官问了能不能用一个栈，我想了想给了思路，没有要求再写。然后问了时间、空间复杂度。
Q2. 下一个排列（散衣原题），也问了时间、空间复杂度
经验教训：1. 一定要仔细检查input data，千万不要为了拼速度而遇到简单题就急着交。 2. 被面试官指出bug千万不要慌，第一时间更正就好。
只要出现过6分就可以拿1分（话说这好像真是美式足球的规则）
当然如果真要求1必须紧跟6做法也差不多。
如果是6之后可以出现任意次1
// dp(i)(0): num of ways to score i points where have not scored 6 points-baidu 1point3acres
// dp(i)(1): num of ways to score i points where have scored 6 points for at least once
dp(0)(0) = 1
dp(0)(1) = 0
dp(i)(0) = dp(i - 2)(0) + dp(i - 3)(0)
dp(i)(1) = dp(i - 6)(0) + dp(i - 1)(1) + dp(i - 2)(1) + dp(i - 3)(1) + dp(i - 6)(1)
如果是每一个1都必须紧跟在某一个6之后
dp(0) = 1
dp(i) = dp(i - 2) + dp(i - 3) + dp(i - 6) + dp(i - 7)
注意判断边界情况
朋友FB最近的电话面试
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=443830
BST求最长的increasing path的长度
follow up是BT怎么做？
| BST 每个点记录 当前点参与的最长路径，记录当前点的左子树的（连续左子节点）的深度，和右子树的（连续右子节点）的深度 (在dfs回溯时更新）node->leftDepth = node->left->leftDepth + 1, node->rightDepth = node->right->rightDepth + 1,对于每个节点 更新最长值 BT 要记录的东西 当前点为最后一个节点的最长上升路径和最长下降路径(在dfs回溯时更新） node->increaseDepth = (node->val > node->left/right->val)? max(node->left/right->increaseDepth + 1): 1; node->val < node->max(left/right->val? node->left/right->decreaseDepth + 1): 1; 然后每个node 的 increaseDepth + decreaseDepth - 1 用来更新答案就可以 O(N) |
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=451849
第一轮behavior轮天竺小姐姐，面试官找不房间迟了10min，问完有的没的后留了不到十分钟让写一个almostPalidrom
第二轮做internal search的白人小哥哥，让输出一个数的factorial结果，其实就是批了一层皮的大卫数乘法在string上操作，很久以前做过但是写的略慢，就写了这一题。
第三轮华人小姐姐，血崩的一轮，估计是想给我放水给了一道interval AND（intersection），结果我写了个bug，提示后改正，略超时。接着问如果一个很大一个很小怎么操作，答对B里的每个元素两次binary search分别找到A里面的对应的range然后再找AND，然后没写完。而且结束后一想其中一个binary search还出了问题。跪的稳稳地
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=449141
aaaabbbcdaaa and a4b3cda3
abbbcccc and ab3c4
看string是否相同
For a given vector of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K
For example, for K = 10 and vector [2, 4, 5, 7], the solution is 5 and these are all the subsets that satisfy the requirements: [2], [4], [2, 4], [2, 4, 5], [2, 5].
sort vector O（nlogn)
if 2*n<=k
2 457<=8 1*2^3=8
4 5 1*2^1 = 2
5 1
新鲜脸书电面跪经
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=449156
题目是，一个排好序的array，找出所有满足的最大值和最小值相加为定值k的subset的数量。follow-up是找出max+min <= k 的子集的数量。因为答案中有计算2^n，所以问了这个怎么实现比较快。最后一个follow-up是问如果这个array非常长的时候，怎么用多线程来实现算法，完全没思路，山歌虽然说没关系，但是已经跪了
面试官听口音和看名字感觉是意大利之类地方的人，口音有点浓重。 开始问了几个general android question，大概5分钟左右，剩下时间开始做题。
题目不是tag的题（或者是我没刷到的？）： 国际象棋问题， 不过不是queen， 是knight， 走法是横1竖2 或者竖2横1（不知道我说的明不明白，不过网上应该能找到这些规则）
example：8x8棋盘 K 是骑士， 1 是 这个骑士 1 move 可以到达的位置。骑士可以走到棋盘外， 但是不能从棋盘外走到棋盘里。 比如第二个example， 棋盘内骑士下一步只能有4种可能move。
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 K 0 0 0 0 0 0 0 0 0 0 K
0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
input 是 骑士的position（x， y） 和 numbers of moves n.
然后输出 n moves 之后， 骑士还在棋盘上的概率。 其中 1 表示一定在棋盘里， 0 表示不可能在棋盘里（我面试后想了想， 应该不可能返回 0， 因为只要骑士在棋盘上， 就一定可以存在让他移动的地方，所以不管n是几，只要反复移动就可以了，如果有大神知道可以返回0 的case 请指正）
本来开始听他说cheeseboard 以为会是 N-queen之类的题， 但是听到后来简直一脸懵逼，还要求返回概率， 楼主既不懂国际象棋（queen的走法还是因为刷题才知道的），数学也是弱鸡（这个概率怎么算还是面试官提示的）， 再加上那个面试官口音确实有点重， 需要他repeat几次才确定题意，所以做的时候已经有点慌了， 好在听完之后就觉得需要做recursive， 得到他点头后， 一直像这个方向靠拢。 最好在他提供了好几个tips之后，算是勉强做了出来， 时间所剩无几。走了几个test case， 然后问了下edge case， 就结束了。 最后问他问题，问的是facebook 怎么做version control。
以下是我的思路：
public float calculate(int[] pos, int n){
if(n == 0)
return 1;
int in = 0;//in 是 在棋盘里的可能move的数量
if(pos[0] + 1 < 8 && pos[1] +2 < 8)
in += calculate(newPos, n-1);//这里楼主面试时候写的是 calculate(pos, n-1), 实际上应该传入新的位置，就是[pos[0]+1, pos[1] + 2] 才对。 不过面试官不知道是没发现还是没怎么care。。）
.
.
.
//一共8组 类似的 if block， 列出8种move的可能（[x+1, y+2], [x+1, y-2], [x-1, y+2]....)
return in/8.0;
}. 1point3acres
补充1：本来开始的题目是 m x m board， 后来因为时间关系, 面试官说我们就用8 x 8 来做就好了， 不过如果是m x m的话， 应该也只是算概率的时候 除以m就好了。
补充2: 以上的代码基本上就是在面试时候写出来， 并没有被要求写完整的代码。 8 个 if block 也没有都写， 但是我把8种情况跟面试官说清楚了， 然后他主动说我们不需要waste time on that。 但是代码写完之后， 他提了以下问怎么能把那8个if block 变得更generic， 更简洁，我当时一下子就想到了LC 一道用array 来写pair的题， 用了类似的思路， 把8个if 变成一个 loop + if 搞定。 面试官连续说了几个good。
总结： 其实面试结束之后再想这道题， 本身不是特别难， 主要是当时确实有点慌了，不过好在这个面试官真的很好，给了好几个tips， 我也一直遵循 think of loud原则， 全程一直跟他交流，表达我的思路。其实面试结束后自己感觉不是特别好， 跟两年前那次比差了不少， 以为过不了， 还特意跟猎头发邮件说面试官口音的问题，问有没有可能加免。 没想到今天中午猎头就回复好消息啦， 感恩！
码字不容易， 画那两个破example更是费劲，也没加积分限制。 各位看官有富裕大米的记得搭上哦
还一个补充， 关于edge case ，其实就是检查input里的pos 是不是 2d array。 因为function的 signature不是面试官给的， 而是自己写的， 所以面试官提了一下， 在最上边加一个 null check + length check 就好了
联署面经
1.behavior，最proud的是啥，有没有bad design，怎么与manager交流， Valid parentse 简化版，只要求返回一个结果即可
2。word ladder 简化版，比较开放的问题，一开始只需要true or false，后来打印一个有效路径，还讨论了打印所有路径
3。design search FB status，很nice的国人大哥，开放问题，一开始算了一下不需要分布式，后来说可以搜索历史，于是上了分布式，分析了两种ingester分别优化读写的利弊，然后说了sharding，replication，LB这些标准的东西，还想说x-dc replication后来忘了
4. Search rotated sorted array 说思路后秒了。第二题All o(1)data structure，说思路后秒了。嘴贱问如果有重复元素要不要根据加入次数作为weight返回，面试官看起来没有想过这个问题，还有时间，于是讨论了思路，该用了list存所有index，写了一下代码，感觉应该没有问题
4. BST iterator讨论之后秒了。 all anagrams直接说思路，被问是不是见过，说见过，于是换了merge k sorted list，说思路后用heap秒了。然后还有时间，说再问一个题，只说思路即可，问了一个Horse在棋盘上的dp，用bottom up dp做，面试官说convinced，问了复杂度，就没有写
2。word ladder 简化版，比较开放的问题，一开始只需要true or false，后来打印一个有效路径，还讨论了打印所有路径
3。design search FB status，很nice的国人大哥，开放问题，一开始算了一下不需要分布式，后来说可以搜索历史，于是上了分布式，分析了两种ingester分别优化读写的利弊，然后说了sharding，replication，LB这些标准的东西，还想说x-dc replication后来忘了
4. Search rotated sorted array 说思路后秒了。第二题All o(1)data structure，说思路后秒了。嘴贱问如果有重复元素要不要根据加入次数作为weight返回，面试官看起来没有想过这个问题，还有时间，于是讨论了思路，该用了list存所有index，写了一下代码，感觉应该没有问题
4. BST iterator讨论之后秒了。 all anagrams直接说思路，被问是不是见过，说见过，于是换了merge k sorted list，说思路后用heap秒了。然后还有时间，说再问一个题，只说思路即可，问了一个Horse在棋盘上的dp，用bottom up dp做，面试官说convinced，问了复杂度，就没有写
All o(1)data 这题感觉是fb tag里最难的之一, 基本就是LFU了, 要写150多行.
回楼上的，不好意思原帖说的O(1)那个，我混了题目。其实问到的是类似霰酒吧这道，然后拓展到有重复的，按频率为权重随机返回
脸的高频似乎是lru，lfu似乎没有考过-baidu 1point3acres
建立倒排索引，然后分布式，有两种方式，一种是用id shard，每进来一条，写的时候只需要写入一台机器，特别快，读的时候要广播给cluster，可以参考twitter的架构
还有一种是按照key word shard，写的时候要写入多台，读的时候对于每个key word只需要从一台读，可以参考google的架构
FB status就是FB上自己设置的状态的一个句子，其实就是search tweet的马甲题。估计1B users，每个status 100B，数据量其实只有100GB，单机是可以放下的。我有点尴尬说这个好像是个单机就能解决，然后面试官说可以搜索历史记录的，于是就顺理成章的讨论分布式了。还问了怎么rank结果，我说可以按时间，按相关度
每个后面都留了足够的时间问问题，感觉面试官都很nice，体验很好
Facebook惜败
为了能和老婆大人早日汇合，弱弱的我在8月中旬开始了在职找工的刷题节奏。电面在九月初，一道find first unique简单题和一道get intervals from two sorted intervals的中等题。Onsite约在了10月25日，结果今天在回程的飞机上收到了拒信，当时心里很是苦涩，但生活奋斗还是得继续！HR给了deeper反馈，说coding and behavior rounds did well, but designs are below FB expectation.
具体的coding题目其实都是LC原题，但要求bug free，途中对复杂度讨论面试官会故意发问质疑，但只要很友好的解释思路，别一上来就code，保证了好的交流，算法不难的。这次面试官们都非常Nice， 很向往的组，可惜了。。。
a). 10:00 一个韩国的大姐（背景巨牛，各大公司的principal machine leanring SE), 题目是LC124(follow up是打印出path）。
b). 10:45 一个印度的CMU小哥（比较腼腆），高频题LC297. 对空间复杂度要注意，因为要存Null，所以worst case需要O(2n + 1)的space（n是所有node数量）。第二题是LC238，但要注意是允许除法，切记别一上来按照原题思路来做，这样很明显就给人无脑刷题的印象。
c). 11:30 一个中国小哥（很开朗）的behavior轮，问了proud project， conflict，career path等经典的问题。最后一道简单的Dictionary中能不能组成target word，最后follow up关于dictionary很大的情况怎么办，比如用cache。
d). （噩梦开始）12:30， 一个白人大哥很犀利的样子（背景也很牛），爬虫设计，10k的机子爬1B的wiki，不能爬重复的page。本人准备的设计题中恰巧没注重这方面，所以答的很磕绊。大哥先问了单机子多线程怎么实现，怎么加锁，然后到了分布式。其实核心思想是hash url，然后进行更even的分配负载。
e). 1:15，很nice的国人小哥，问的是ML design关于POI（point of interest). 注重点是ML的整体思路，从问题的描述道最后的service搭建，过程中会涉及到database的query，categorical feature的降唯（embedding）等等细节。这轮楼主表示面的一般，但不至于挂。
FB SWE 面经，求大米
一道是给工资和对应区间的税的表格，算工资税
第二道有点像蠡口尔尔其，不过只有+和*和数字，不考虑其他的，我用的stack的方法做，问时间空间复杂度，然后follow up问能不能把空间复杂度降到O(1)
原来的想法的遇到 * 就算，遇到 + 就压到stack里
然后改成，遇到+或者末尾，就把当前的数字加到sum上去，如果是*当前的数字先设成1，然后不断乘，直到遇到+或者末尾，再加到总和上，不断循环
应该是英语母语的小哥，也是两道easy题 （运气特别好😂）基本都是原题
第一道尔把伞，第二道而其罢，follow up非常谜，问我怎么检查输入是valid，如果输入不valid怎么返回通知用户，说了可以返回error code或者exception，然后让我写抛出exception
在做题之前先问了我很多我为什么喜欢脸书，为什么想进，我离开的时候希望能得到什么，于是和面试官扯了近15-20分钟😂感觉这个反而是最难的问题了
Facebook 2019 本科 Summer Intern On Campus面经第一道尔把伞，第二道而其罢，follow up非常谜，问我怎么检查输入是valid，如果输入不valid怎么返回通知用户，说了可以返回error code或者exception，然后让我写抛出exception
在做题之前先问了我很多我为什么喜欢脸书，为什么想进，我离开的时候希望能得到什么，于是和面试官扯了近15-20分钟😂感觉这个反而是最难的问题了
上来直接开始做题,第一题是给一个数组里面是commit number, 分别给good commit 的number和bug commit的number还提供了一个boolean isBug(int commitNumber)说这个function的cost很大
要求返回出现第一个bug commit的number
int findFirstBugCommit(int arr[], int good, int bug)
比如 9, 10, 11, 12, 13, .... 27
good good bug bug
输入(9, 27) 要求返回12
第一题我用了Binary Search, 面试官之后问了test cases, edge cases然后拍了白板的code就进入下一题
第二题是两个binary string相加,写完后followup是改成十以内任意进制相加
脸熟上门
第一轮 behavior + 15-min coding 印度manager 入职6年半
第二轮 coding 华人 new grad入职2年半
第三轮 coding 华人 入职3年半
第一轮: introduction, challenging project, conflict, why facebook, LC迩霸。 面试官迟到所以没有q&a的时间，卡了一下改对代码之后就直接下一轮了。
http://massivealgorithms.blogspot.com/2015/07/implement-strstr-n00tc0d3r.html
第二轮: 写两种能够表示directed graph的数据结构，不保证connected，每个node的值不保证unique。用写的数据结构做LC窈伞霰。
第二轮: 写两种能够表示directed graph的数据结构，不保证connected，每个node的值不保证unique。用写的数据结构做LC窈伞霰。
随你自己定义，只要能表示题目说的directed graph（可能有环，可能有重复值，可能不conncted），就可以，输入和输出是一样的其实
我自己定义了个node，然后list of node就可以。我第二种结构说的是adjacency matrix不过也要加一个node->index的东西来避免重复的val，核心就是在于给node加一个unique identifier
非死不可10/12面经
1. 不用 / 和 % 操作符做integer division。给出n和d, 求n / d和n % d。当时想了2个思路，一个O(n/d)的暴力破解，一个O(log(n))的binary search。都写出代码了，面试官让分析一下哪个快，假设n完全随机且d在[1, n]之间随机
对就是那题，但是简单了很多，0 < d <= n，少了很多烦人的case
然后可以用乘法？原题好像不允许用乘法，用乘法的话就直接二分法吧？
请问下O(n/d)和O(log(n))在d随机状态下怎么比较呢？是需要求O(n/d)的期望=1+1/2+1/3+..+1/n这样吗
是的，假设d在[1, n] 之间随机分布，求期望值。不过面试的时候只是很潦草的说了一下，并没有详细解释
余数可以算完商之后， 用被除数减一下商*除数这样算么...
2. binary tree LCA。假设node的值不重复，但node没有parent pointer。给出了O(n)的解，n是binary tree中node的数量。（遍历binary tree，找出2个node到root的path然后比较）。O(logN)的LCA是很经典的算法了（虽然在leetcode考纲之外）可以自己google一下
比较容易写的是倍增算法，对每个结点存储和它距离为1、2、4、8……的祖先结点，然后查询的时候用二分法
提供一种lgN 查找时间的方法 https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-3-using-rmq/
followup是用RMQ解决LCA问题的经典方法，大家可以gg一下：
1. Tarjan（离线）算法： 在一次遍历中把所有询问一次性解决，预处理时间复杂度O(nlogn),每次查询时间复杂度O(1)，总时间复杂度是O(nlogn+q)。
2. 倍增算法：利用二分两个节点同时往上走，直到相遇，预处理时间复杂度O(nlogn)，每次查询时间复杂度O(logn)，总时间复杂度O(nlogn+qlogn)。
3. RMQ算法
第二轮： 上来还是问相关经历，然后做题。设计一个BigInteger class 可以计算任意位数的正整数加和乘，要求写出constructor， add function， multiply function。
非死不可电面
就一题 莉蔻兒毋伞
[size=18.6667px]但是给的时间段是string. From 1point 3acres bbs
比如"10a - 10:30a
直接蒙蔽 在string这里搞了半天搞到最后
把时间小时:分钟全变成分钟可以吗 pm再加上720分钟
写两个辅助函数先处理字符串到原来的结构，再按原题套路做
欸这题还需要考虑第二天的meeting， leading zero,? 比如23pm-01am
可以说这种题真的有些烦人
但跟他确认格式是 “TT:TT xm - TT:TT ym” 这样的格式（x,y可以是a，p）
如果只是不想出原题，有很多种变换考法，但这种只在format死扣细节的问题，完全没意义啊
白人小哥 非常nice
clarify的题目，给了例子，难点是 时间的表达，10AM - 11：30AM 11：00AM to 1PM 怎么存。
转换成可以sort的开始和截止时间之后，就正常的min heap，每一部分解释一下，保持边说边写
然后是问test case 有没有什么特别的。😅 不知道啥事特别的，就是举了几个没有重合的例子，和有重合的例子，空例子。
然后就是时间复杂度。
说说写写比较慢，说完复杂度就42分钟了。就结束了。
第二轮 利特蔻得 额柳久 外星人字典
国人大哥，大腿，好人，全凭大哥带我飞。
木有刷到这道题，😓😓😓，
想思路用了15分钟！
完全忘记了拓扑排序，用graph traverse 勉强写出来。
还没有跑test case 就到时间了，大哥告诉我一共就26个字母所以可以 int （26），说这是道常见题目，应该注意好好练习一下相关概念
clarify的题目，给了例子，难点是 时间的表达，10AM - 11：30AM 11：00AM to 1PM 怎么存。
转换成可以sort的开始和截止时间之后，就正常的min heap，每一部分解释一下，保持边说边写
然后是问test case 有没有什么特别的。😅 不知道啥事特别的，就是举了几个没有重合的例子，和有重合的例子，空例子。
然后就是时间复杂度。
说说写写比较慢，说完复杂度就42分钟了。就结束了。
第二轮 利特蔻得 额柳久 外星人字典
国人大哥，大腿，好人，全凭大哥带我飞。
木有刷到这道题，😓😓😓，
想思路用了15分钟！
完全忘记了拓扑排序，用graph traverse 勉强写出来。
还没有跑test case 就到时间了，大哥告诉我一共就26个字母所以可以 int （26），说这是道常见题目，应该注意好好练习一下相关概念
脸熟挂经
第一题给一个数组 让你求连续最长递增子序列 比如 3 1 2 4 7 2 3 -1 -3 11 返回 1 2 4 7 很简单的一道热身题 结果懵逼了 先写了一个暴力算法 花了太久时间 最后口头优化成O(n)时间 O(1)空间 估计就是跪在这一题了 是lc原题
第二题是给一个string的括号 让你移出无效的括号返回一个结果 注意只返回一个即可
只要一个结果就行 来回扫两遍 每次多出的去掉最后一个就行
第二题可以用StringBuilder 存这个string， 用stack来check当前括号是否有效，若无效，在stringBuilder里面剔除该字符，返回剩余string？
1. LC 原题, merge K sorted arrays, 唯一就是告诉你数据量可能很大, 我用min-heap做的, heap里面存row的pointer或者row id + current position啥的struct都可以, priority queue; 论坛的朋友如果你有效率更高或者速度更快的, 请留下你的算法. (因为被告知是speed/efficiency挂了, 一脸苦笑, 这个理由也是够搞笑的, 我自己做的还真的心里清楚)
2. 求一个binary tree 里离一个给定node距离小于K的所有节点的集合, 这个也是简单到想笑, 主要就是创建一个hash table存下parent node, 然后用BFS就好了.. check 1point3acres for more.
3. system design, recruiter不给别的feedback, 但是明说system design是positive, 所以也没啥好说的, 题目是设计一个service, 供用户查询任何时间段内的数据信息(之前面过类似的, 查询股票信息系统啥的), 难点在于aggregator知不知道, 怎么数据库sharding, cache怎么用, 怎么做分布式, 还有就是要分析和算QPS, 怎么优化存储, retention的处理等等.
还有两轮的题目, 因为实在太简单了, 我都没啥印象了, 就是LC上easy差不多的题.
面完本以为安心等offer, 结果收到邮件被拒, 还不死心给recruitor打了电话, 结果是不透露具体信息, 然后请来年再面. 感觉挺莫名其妙和有点生气的, 因为所有题目基本都是秒杀, 然后面试官时间充分到给我每轮出2-3个题, 还有5-10分钟聊天. 没有任何卡壳或者说hint啥的. system design也是positive, 完全想不通哪里能挂我. 今年果然脸不行
2. 求一个binary tree 里离一个给定node距离小于K的所有节点的集合, 这个也是简单到想笑, 主要就是创建一个hash table存下parent node, 然后用BFS就好了.. check 1point3acres for more.
3. system design, recruiter不给别的feedback, 但是明说system design是positive, 所以也没啥好说的, 题目是设计一个service, 供用户查询任何时间段内的数据信息(之前面过类似的, 查询股票信息系统啥的), 难点在于aggregator知不知道, 怎么数据库sharding, cache怎么用, 怎么做分布式, 还有就是要分析和算QPS, 怎么优化存储, retention的处理等等.
还有两轮的题目, 因为实在太简单了, 我都没啥印象了, 就是LC上easy差不多的题.
面完本以为安心等offer, 结果收到邮件被拒, 还不死心给recruitor打了电话, 结果是不透露具体信息, 然后请来年再面. 感觉挺莫名其妙和有点生气的, 因为所有题目基本都是秒杀, 然后面试官时间充分到给我每轮出2-3个题, 还有5-10分钟聊天. 没有任何卡壳或者说hint啥的. system design也是positive, 完全想不通哪里能挂我. 今年果然脸不行
第一题数据量大的话 比如K很大这样复杂度为 k*n*log(k*n) k为list个数，n为长度
不如二分两两merge 时间复杂度 k/2 * 2 * n + k / 4 * 4 * n + ... + k * n = log(k) * k * n
correct me if i'm wrong
BST K nearest neighbors也不是最优
https://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/
