Preface
一亩三分地不是很友好，不想在上面分享面经了，就在我自己的一亩三分地记录下我的全职找工作的心酸历程吧。
Pony.ai [In progress]
楼教主的公司，刚A轮完吧，8.2onsite完后到现在还没有消息，猎头说是在计算head count，等面完很多candidates再做决定吧
电面：
Round1：leetcode上的string calculator 3，字符串计算器3，实现加减乘除和括号，不需要考虑不合法情况和空格。。。好难，刷题好累。用中文面试好喜感，一直想着说段子，感觉给面试官一股很不正经的感觉。
上门：
Round2：给你几个质数，他们作为分母的所有分数，然后找出第k小的分数，大概就是比如质数2，3，5。那么就有1/2, 1/3, 2/3, 1/5, 2/5, 3/5, 4/5, 那么第2小就是1/3。然后还有follow up就是如果k很大的时候，怎么解。
Round3：维护一个中位数。先要支持add和get。做完后要支持remove。remove真的难想，就一直靠面试官提示。
Round4：给一堆(x, y)的二维坐标，每一个坐标对应一个整形的score。以原点为圆心的，会有很多圆存在。需要找出一个圆，使得这个圆内的（包括圆上）所有score的和最大。这个是考察想各种corner case。
Round5：最后一面，上来先出了一个概率题，是在一个圆上随机取三个点，连起来是个钝角三角形的概率。然后是给我一个int数组，让我最后把奇数index的值都比偶数位的大。例如[1,2,3,4,5,6,7,8]要变成[1,5,2,6,3,7,4,8]这种形式，实在想不出O(n)的解，就直接说我不会，然后出了个islands的变种。dfs就可以解决。
Facebook [Rejected]
电面：
Round1: 美国小哥，两道题。Leetcoode15. 3Sum和leetcode199. Binary Tree Right Side View
上门：
Round2：先上来一道task schedule，考虑顺序不变的情况。然后follow up是间隔k很小，task数量很多的时候，怎么解。做完后再出了一道二维坐标轴给很多点，找离圆心最近的k个点。
Round3：数字的permutation，next large number，比如3245返回3254。然后出了一道max interval overlap。给一群区间，然后求最多有多少个区间相交。
Round4：behavior questions. 你觉得最挑战的project，为啥最挑战，为啥不说其他的，遇到了什么挑战，怎么解决的，学到了啥。你为什么要申请facebook。你觉得facebook和uber乃至其他公司的区别是啥。然后出了道coding，print all paths of a tree。给了递归和循环两种解法。
Google [In progress]
OA：
1. Email处理。 email地址分为local@domain。（1）local里dots('.') between some characters 要去除。（2）local里如果有'+'，'+'和后面的全去除。比如'a.b@example.com' -> 'ab@example.com', 'dupli......cate@example.com' -> 'duplicate@example.com', 'd.u.p.l.i.c.a.t.e@example.com' -> 'duplicate@example.com', 'ab+work@example.com' -> 'ab@example.com'。处理完后的邮件地址一样的放在一组，返回所有组，里面不止一个邮件地址的组的个数。
2. leetcode159变种。采水果。小红去果园采水果。有2个篮子，可以装无数个水果，但是只能装一种水果。从任意位置的树开始，往右采。遇到2种情况退出，1. 遇到第三种水果，没有篮子可以放了，2. 到头了。返回可以采摘的最多的水果个数。 比如[1,2,1,3,4,3,5,1,2] return 3。[1,2,1,2,1,2,1] return 7
上门：
Round1：一群人互相付钱，最后要怎么清账，然后return List<Check>，Check就是谁要付给谁多少钱的数据结构。
Round2：isSummahable，就是给一个isDict(String word) API，给一个word，看他能不能每次删掉一个字母，仍在dict内，然后最后可以是一个字母也在dict内。然后考虑时间复杂度，怎么优化，做成一个server，怎么优化，然后多个语言都要考虑。头脑风暴。
Round3：Tree的Serialize，多个child，考虑各种树的情况怎么handle，还有escape，输出类似html，<a><b><c><d/></c></b><e/></a>
Round4：去data center修broken的机子，给一大堆broken机器的左边，从(0,0)进去，每一行只能从最左边一列和最右边一列走，然后怎样走才可以最快得访问所有broken的机器。
Nuro [Rejected]
电面：
Round1：Nuro是一家做机器人送货的创业公司，现在只有45个engineers，我在linkedin上看到投了后收到了面试。面试官是个带口音的外国人，然后出了一道C++的题目，我表示2年没有动过C++了，写的是个球啊。而且一开始信号很差很差，交流不下来，他换了个位置再打回来才可以正常沟通。
要求写一个自己的Vector类，要求在如下2个条件下，空间更效率：
1. 只有3个或者更少的元素，
2. 所有元素在1-100之间。
要用尽可能少的空间，但是要保证对于所有情况的正确性。（比如也会有1000）。
写出operator[]和push_back，可以用std::vector。
还好，最后做出来了，但是沟通太不顺畅了，希望能过吧。杨超越保佑。
Dropbox [In progress]
OA：
丢盒子OA Malware Defender给你一个matrix，n X n的。代表n台电脑之间的conn情况，1表示相连，0表示不连。给你一个int list，代表这些原始电脑感染了病毒。并且根据电脑之间如果有conn，就会传染病毒。要你如果可以使一台原始电脑没有病毒，这样可以使传染后没有病毒的电脑最多，返回电脑的index和拯救的电脑的个数。
我先用dfs把所有连接在一起的电脑的id都设成一样的。（union find思想）然后再去找最多id一样的且满足 id一样的电脑只有1台带有原始病毒（不然即使1台可以没有原是病毒，还是全都会被传染）。test cases all pass。
如果要考虑是个有向图的会麻烦很多，但是也是可以做的，也会all pass。
On Campus：
未完待续
VMWare [In progress]
OA：
VMWare Propel OA: 总共4个选择题和三个coding题
1. 给preorder和postorder的序列，选inorder序列
2. FIFO system，4个page，一开始都没有load，先access100个不同的page，按某个顺序，然后再反着来。总共会有多少次page fault
3. 一个无向图，n个点，e个边，选择当图用（1）邻接矩阵（2）邻接列表时DFS的时间复杂度。
4. 忘了
5. break a palindrome。给定一个palindrome。要改变一个char，使得新的string不是palindrome。而且要是lexicocographically最小的，不然就返回"IMPOSSIBLE"。找左半边不是"a"的。
6. Intelligent Substring。给一个字符串，只有小写英文字母。然后会对应1或者0。求最长的子字符串的长度，要求0的个数不超过k个。sliding window。
7. The perfect team。就给你一个字符串，每个char代表一个人擅长的科目，然后要组队，要求队伍里五个人各擅长一门科目，求可以最多可以组几个队伍。数数取最小。
上门：
未完待续
Amazon [In progress]
OA1：
今天下午刚收到Amazon的New Grad OA，十分激动，自己终于被亚麻看上了。然后迫不及待打开
第一部分 coding debug，感觉智商受到了侮辱，太简单了，7道题，感觉1道题都不需要1分钟。如果这都做不出，还是别写代码了。。
第二部分 选择题，一些找规律，还有逻辑题，还有情景分析题，不知道自己会不会有的做错了。
第三部分 工作评估，一些工作情景打分。
第四部分 feedback
Code Debugging (20 minutes) - You may use online resources that are publically accessible to everyone (e.g., the JDK or STL). But, please do not access sites that require login or are private repositories, as browser usage is logged. Manage your time wisely! If you get stuck on a code debug problem, move to the next problem and revisit the questions as needed. You will have to choice of viewing code in Java, C++, or C.
Logic Ability (35 minutes) - During this section, you will be asked a series of problem solving multiple choice questions. Speed of completion for each question is not a factor in your score. Complete as many as you can during the time allotted. You will not be able to skip and return to questions.
Work Style Assessment (10 minutes) - This will be a series of questions asking you to rate your preference in certain situations or behaviors
Experience Survey (no time limit) - This is required and your assessment cannot be scored until this is completed. It is a short survey that will ask you about your experience taking the assessment and is not scored.
希望收到OA2.
最后附上亚麻今年招聘流程：
SDE Interview Process
1. Online Assessment, Part 1 (1 hour): Code debugging and logic/problem solving multiple choice
2. Online Assessment, Part 2 (3 hours): Work style simulation and coding problems
3. Final Technical Interview: You will be contacted by end of September on the results of your assessment. If qualified, we will provide information on scheduling your final technical interview.
4. Offer: We will notify you of your final interview results via email. If applicable, offer documents will be viewable on your candidate portal.
OA2：
昨晚收到OA1，做完后今天早上起床收到OA2，就把它做了。
第一部分是工作情景分析，就是各种情况，你会怎么做选择，这些问题应该没有明确答案，所以也不多说了。
第二部分就是coding题，2题
1. 飞机上放电影，给一个int[] dur代表所有电影的时间长度, 和一个int 飞行时间长度，要选取2部电影，保证2部电影加起来的时间小于等于飞行时长减去30分钟。然后选取2部电影，使得总长度最长，如果有多组总长度一样长的，选取包含单独最长的电影的组合。我直接O(n^2)扫一遍all pass了。
2. 树的问题，每个结点有一个value表示这个结点有多少代码行数被改动了，然后子树就是他依赖的结点，要去找一个结点使得 它当前结点改动的代码行数+他依赖（子树）的所有结点的代码行数 的平均最大。
比如 100
/ \
120 80
/ | \ \ \
40 50 60 50 70
那么100结点就是(100+120+80+40+50+60+50+70) / 8 = 71.25
120结点就是(120 + 40 + 50 + 60) / 4 = 67.5
80结点就是(80+50+70) / 3 = 66.6667
那么就要返回100这个结点
Salesforce Quip [In progress]
OA：
Quip是Salesforce的子公司，有很多套题，抽中了kumu8，没在地里找到，做的累死了
第一题，用自己的数据结构实现一个类stack的功能
1. push k，就是stack push 一个 value k
2. pop, 就是stack pop top value
3. inc e k，把stack bottom e values plus k
有两个要注意的，第一个是时间复杂度不能太高，我用ArrayList + HashMap + PriorityQueue实现的，第二个是防止数据overflow，我用BigInteger做的
input是List operations
然后每一个op都是在三种情况内，自己parse后做，然后每一个op都要在最后打印当前stack top value，如果stack 空的就打印EMPTY
第二题，定义一个alphabet，只有A和Z两个字符
string是proper的当且仅当满足2个条件
1. A和Z的个数相等
2. 每一个prefix情况A都要比Z多
比如AZ就是proper的，ZA就是不proper的，AZZA是不proper的
给input一个proper的alphabetStr，然后我们要做变换使得变换后的string，lexiorder最小，变换要满足如下条件
1. 寻找str里2个连续的proper 的 substring， 连续是指 前面一个的end index = 后面一个的start index - 1
然后互换这两个substring的位置，形成新的alphabetStr
如此变换后得到的最小的lexiorder的string就是输出
比如
AAZAAZZZ -> AAAZZAZZ
AZ
AAZZ
这两个连续的substirng互换就可以使得lexiorder更小。
我是无脑狂遍历做的lol
电面：
给一大堆英文单词dictionary，从所有2个字母的单词，每次可以在它前面或者后面加一个字母，新的单词也要在dictionary里，找到最长的链。因为dictionary里有25w个单词，我跑的时候codepad就报内存不足，但是java的garbage collection应该不会耗用太多内存。面试官让我就从"at"开始搜，很快就返回了结果。
上门：
未完待续
Twitter [In progress]
OA：
虽然知道twitter oa做了大概率还是就石沉大海，我还是做了下
分为2个部分
第一个部分2道coding题
1. brace 就是判断给定字符串由 '(' ')' '{' '}' '[' ']'6种字符构成，然后判断是否闭合，用stack做就可以了，当然input是一个list of string，判断n个string是否闭合，然后return list of string，'YES' or 'NO'
2. who's closest 给你一个字符串，给你一个list of int, 然后对于每个idx int对应的char，去寻找字符串中离idx最近的一样的char的idx，如果2个距离一样近，返回小的那个，如果没有，返回-1，所以最后会返回一个list of int。从idx往两边搜就可以做完，然后cache存一下就可以all pass，避免超时
第二部分1道coding题
prime in subtree
先给你n个nodes int， List first index （n-1个），List second index（n-1个），List values（n个），List queries（k个）。然后先要自己构建树，first和second两个list里pair的就画一个无向线，然后树的root从第一个node开始。构建完树后再去给定query index的node，求对应包括自身节点和所有子节点的value是否为prime的个数。我首先构建树是不分parent和child，直接把pair的2个idx互相加进各个的children里，然后从root（第一个node开始dfs搜索）去边。这样构建完树后再去用dfs算prime in subtree，然后用dp存一下，就可以全过了。
没有截图，但是有个帖子有http://www.1point3acres.com/bbs/thread-438534-1-1.html
Snowflake [In progress]
电面：
Round1：parse一个数学表达式，给定输入是一个树，比如(a+1) * (b+1) - (c-1) / (a+1)。然后把相同的subtree cut掉，比如第二个(a+1)就可以指向第一个的节点。
那就是这样的树：
'-'
/ \
'*' '/'
/ \ / \
'+' '+' '-' '+'
/ \ / \ / \ / \
a 1 b 1 c 1 a 1
我用hashmap存下每个节点对应的preorder string作为key，node作为value，然后遇到hashmap已经有的就直接指向之前的节点，存下当前节点的parent和flag来表明左孩子还是右孩子。
然后followup是，+和*是可以不分左右顺序的关系的，这时候该怎么cut，也就是说(1+a)和(a+1)是一样的，还有(a+1) * (b+1)有八种一样的表示。我没有答出来，结束后想到可以定义一个rule，作为唯一的string representative。
最后他又出了一题，既然我用preorder string来做为节点的标识，那我怎么给一个preorder string，我去计算结果。我给了个递归的代码，但是这样时间复杂度爆表。然后想到这就是string calculator的变种，然后就可以想到用栈来存放计算。但是就这么口嗨了下。
Round2：给2个linked list的head node a和b，然后这两个linked会在某个node相交，然后后面的节点都是一样的。要去找到这个merge point。
我先问了假设，假设所有node的char label是唯一的。先给出一个一个解，从a走到底，把label扔进hashmap，然后再从b走，找到已经访问过的node就是merge point。
然后他要求O(1)空间的解法，提示了下，从a走到底得到长度aLen，从b走到底得到长度bLen，然后让长的先走|aLen-bLen|。然后就可以同时走判断是否到了merge point。
然后他说如果linked list很大，但是merge point在比较前面怎么做，要了下hint，就是给一个window，实现mergeWithin(Node a, Node b, int n)。就是判断前n个节点是否会有相交。然后n从1开始，一直double下去直到找到。这样时间复杂度是O(k)。k是max(a到merge point长度，b到merge point长度)。我给出了O(k)空间和O(1)空间的解，还以为这轮要的hint太多，会挂，没想到过了。
上门：
未完待续
Cisco Meraki [In progress]
电面：
Round1：考察unix命令，不让google，我只能man查询了怎么做。
第一个是查询是否有web server正在跑，然后是在listen哪个port number。考察netstat
然后是给一个文件夹下所有的文件和文件夹给owner赋予rw权限，all users赋予r权限，考察chmod
最后是查询一个文件夹下所有文件是否包含一个字符串，考察grep
最后最后还考察怎么查询一个文件下所有文件拥有相同的权限，所有文件夹拥有相同的权限
我感觉我对unix命令不是很熟悉，然后都是一边和他讨论一边man了查看怎么写的。可能他看我很单纯，而且真的是从零学起做出来了就给了pass吧。
Round2：面了一道partition问题，给一组customers 和对应的 number of devices，要去分成2组，使得两组customers的devices相加的和尽可能小。
上门：
未完待续
Pinterest [In progress]
OA：
第一题是处理log，看每个整点到每个整点：40是否有记录，统计每个整点的记录个数，然后如果有0的就返回那个时间段，没有就选最小的那个时间段
第二题还是处理log，就是看哪个用户在连续8分钟内有至少20个请求，且有至少有10个action是一样的
电面：
// You are building an educational website and want to create a simple calculator for students to use. The calculator will only allow addition and subtraction of positive integers.
// Given an expression string using the "+" and "-" operators like "5+16-2", write a function to find the total.
// Sample input/output:
// "6+9-12" => 3
// "1+2-3+4-5+6-7" => -2
// We also want to allow parentheses in our input. Given an expression string using the "+", "-", "(", and ")" operators like "5+(16-2)", write a function to parse the string and evaluate the result.
// Sample input:
// expression1 = "5+16-((9-6)-(4-2))"
// expression2 = "22+(2-4)"
// Sample output:
// evaluate(expression1) => 20
// evaluate(expression2) => 20
// We want to allow students to use variables when entering expressions in the calculator. In addition to the formula string, we’ll add a new input to our function that holds variables and their values:
// {"e": 8, "y": 7, "pressure": 5}
// and our string inputs now have a format like
// "(e+3)-(pressure+temperature)+2".
// Evaluate the formula result as fully as possible using the input variables. It is possible that not all variables have known values, in which case you should preserve them in the output.
// Sample input:
// variables = {"e": 8, "y": 7, "pressure": 5}
// expression = "(e+3)-(pressure+temperature)+2"
// Sample output:
// "8-temperature"
上门：
未完待续
TigerGraph [In progress]
上门：
未完待续
Citadel [In progress]
OA：
1. 第一题是很简单的字符串处理，要求把输入的日期格式进行转换。例如: 1st Mar 1984 => 1984-03-01
2. 第二题是有一系列的股价，每一天可以买入一股，可以卖出多股，也可以什么都不做，交易次数不限，要求求出最大收益。这道题同时要求从stdin读入数据。
比如：
股价为[5,3,2]，则收益为0
股价为[1,2,100]，则收益为197，可以在前两天买入，最后一天都卖掉
3. 第三题极其复杂，给了一系列二叉树的parent-child pair，要求验证这个是合法的二叉树，并且返回使得结果的lexical order最小的serialize的string。这道题同时给了许多种error code，包括more than 2 children, circle等等，还要求返回lexical order最小的error code。
例如：给出序列 (a, b) (a, c) (b, g) (c, h) (e, f) (b, d) (c, e)
要求输出 (a(b(d)(g))(c(e(f))(h)))
（就是Google实习OA题目）
电面：
binary string和design of ringbuffer
Jingchi.ai [In progress]
电面：
未完待续
Petuum [In progress]
电面：
given an int array, generate the product except corresponding index, like [1,2,3,4,5] return [120, 60, 40, 30, 24] in linear time.
count all characters in a string
Apple [In progress]
SimCloud组：
电面：
send http request get content of a log file and deal with log, parse ip, and count
Media组：
电面：
given an int array, each time you can pick from the most left or the most right and remove it, your opponent will do the same, you want your sum of all pick as much big as possible. like [1,2,300,4] return 301
Rubrik [In progress]
电面：
未完待续
Indeed [In progress]
OA：
经典墨水题，人生苦短，别用python，超时无法解决
Linkedin [In progress]
OA:
1. 按照int的binary里多少个1来排序，一样的话再按数值大小排序
2. 给int n，生成1-n的各种permutation，使得奇偶数相隔，dfs可做，超时1个case，凉凉
