search similar people的API
大致说一下前端,后端,不用太细
给一排房子,用RGB三种颜色染色,相邻不能染成同色,每个房子染对应颜色会有对应的weight(W[N][3]),求最大的weight和
follow up,N种颜色
nested array,etc [[1,2], 2, [[3], [4]]],input是nested array的iterator,实现next element的iterator
版上高频
design,tiny url
高频
比较长
/**
* Find threevalues that can be the lengths of the sides of a triangle.
* Three segmentsof lengths A, B, C can form a triangle if and only if:
*
* A + B > C
* B + C > A
* A + C > B
*
* e.g.
* 6, 4, 5 can form a triangle
* 10, 2, 7 can't
*
* @paramsegmentLengths the lengths of segments that might form a triangle.
* @return threevalues that can be the lengths of the sides of a triangle,
* or an empty array if there are no suchvalues in segmentLengths.
* sample input:segmentLengths = [10, 5, 7, 4, 3]
*/
第一反应brute force 因为没见过 同时手极快的google了 然后google到了这个(没权限发链接 大家自行google geeksforgeeks/find-number-of-triangles-possible)
但是面试官不要求count 有多少个triangle 只要return 一组 就行了 此题的重点是要sort 好像背后还有什么数学原因
我当时就扫了遍帖子 说要sort 然后后面写了个iteration match 第一组符合的pair
Find the size of longest palindrome subset of an array
高频
注意是subset而不是subarray。不能改变order。所以[1, 2, 2, 0, 1]的longest palindrome subset是[1, 2, 2, 1],应该返回4。
检查两个bst是否identical
TODO
Deepest comman ancestor (with parent nodes).
LinkedIn这题都快问烂了...我说了用hashmap的方法,他说你能不能不用额外空间,我想了一下又说了那个把两个节点调到一个高度的做法。
对就是每个node除了left和right还有个parent
Class Node {
Node left;
Node right;
Node parent;
}
root节点parent是null. 没有parent的做法的确是递归,但是有parent指针的话递归就划不来了。举个例子:
____3___
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
要找4 和 8的lca,把4先设成到2,因为2 和 8 深度一样。然后2 和 8 一起沿着parent往上,碰到的第一个一样的节点就是第一个祖先了。
实现一个Max Stack, 支持peekMax() 和popMax().
很自然地用两个栈去做,但是这样popMax的时候很费时间。然后我又加了一个stack存的是max value的index, 把stack全变成ArrayList, 然后就开始纠结pop了。。。结果corner case太多没写完。。。不过他也说这题要简单clean是比较难
linked list找intersection~本来窃以为不要太简单~没想到他居然无数个follow-up
分情况讨论:
- 两个没有环,不想交
- 两个没有环,相交
- 两个有环,不想交
- 两个有环,相交
在第三种情况纠结了很久,然后决定上slow, fast pointer找到两个环的起点,然后固定一个起点,另外一个环走一圈看有没有重复
之后又扯淡了很久~
就是面经里的那道nestedInteger, 只不过我的题目是个变形. 当时要求多加一层就是求得是ReverseDepthSum. 也就是层数越深,所获得的weight value越低.
举例就是 {{1,1},2,{1,1}}
the function should return 8 (four 1's at weight 1, one 2 at depth 2)
Given the list {1,{4,{6}}} the function should return 17 (one 1 at weight 3, one 4 at depth 2, and one 6 at depth 1).先得走通一遍得到层数,然后对应上乘出来才可以得到结果.
面经里的Add Interval那题
其实L家如果准备很充分还是很有帮助的. 跟原题一样,不过后来又继续followup如何remove Interval.
给定一个中心点,然后找到K个nearest points.
这个当时我复习电面的时候看过下,
但是后来就一直没管了,就记得用priority_queue来做就好了,结果被问到了minHeap和maxHeap,在这两个概念上纠结了很久,