发个TA(猫头鹰)的面筋

原帖地址:mitbbs

网上投的,一开始是做online的两道题,一个是求树的Amplitude
In a binary tree T, a path P is a non-empty sequence of nodes of tree such
that, each consecutive node in the sequence is a subtree of its preceding
node. In the example tree, the sequences [9, 8, 2] and [5, 8, 12] are two
paths, while [12, 8, 2] is not. The amplitude of path P is the maximum
difference among values of nodes on path P. The amplitude of tree T is the
maximum amplitude of all paths in T. When the tree is empty, it contains no
path, and its amplitude is treated as 0.
For exmaple.

Input:
5
/
8 9
/ /
12 2 8 4
/ /
2 5
Output:
7
Explanation:
The paths [5, 8, 12] and [9, 8, 2] have the maximum amplitude 7.
另外一个就是写数据库的sql,不是很难,时间很够用。
然后是一轮电话面试,感觉是国人,就问了一个求一个由火材棍组成的square里总共有
多少个正方形,其中火材棍可以连续,或者不连续,例如
—— —— —— ——
| | | | |
—— —— ——
| | | |
—— —— —— ——
| | | | |
—— —— —— ——
剩余时间聊聊project和他自己介绍TA的相关情况
onsite飞到波士顿,一共四轮。
1 国人大哥,很亲切,上来直接中文,搞得挺惊讶的,问了一些java的知识,然后是买
卖股票1和3,然后说设计一个card game的数据结构,如何能快速比较胜负关系,我以
为是像香港赌片里那种规则,结果是让我按德州扑克设计,从来没玩过,简单说了一下
,大哥说换一个吧。就换设计一个online的table reservation系统,数据库如何设计
主要是,答的一般。
2 说英语的亚洲人,上来介绍阻力情况和他做的,后来问了写java相关的知识,然后问
了一个nary tree的LCA,每个节点都有father指针。一开始用一个set的做的,后来用
了两个相交linkedlist求交点的方法。
3 白人大叔,人很亲切,上来自我介绍,然后轮到我介绍自己,然后就问了一道题,给
一个函数,
alarm(boolean success, long timestamp, String requestName),意思是当一分钟之
内某个request的failure比例达到一定程度时fire alarm。先跟大叔讲了思路,大叔表
示赞同,然后开始撸,用了priorityqueue存Request(success,timestamp, name)的对
象,维护一个60秒的queue。问了时间复杂度,如何初始化的一些相关问题,不是很难
。最后大叔表示满意。
4 国人大叔,大boss,上来直接中文,很亲切,问了java相关问题,然后让写一段遍历
的代码,就是给你一个集合,让你返回符合输入的一个子集,输入是一个predicate和
一个type。后来问多线程下怎么办,怎么加锁,如何加cache。
总得过程很愉快,办公楼不错,里面很漂亮,没见到什么老印,国人不少。一周过后拿
到offer,感谢面试中国人的帮助。 105k base,50k RSU,有搬家费,但是没说,还有
就是12%的bonus,另外他家的福利挺好的。请问这个offer在波士顿地区如何,本人phd
,3年工作经验,不在波士顿,要relocate。感觉波士顿的房价很贵啊,跟湾区有一拼
呢。谢谢。