Facebook 第一轮电面，三道题。

keepworkinghard 发表于 2016-9-2 07:48
您是什么时候毕业啊？年底么？
祝onsite offer

感谢！
是明年五月

CeciliaM 发表于 2016-9-2 07:51
……我忽然想起来只要inorder遍历一遍就行了啊！我在干什么啊！！！
_(・ω・｣ ∠)_ ...

对，应该2种方法，一个左右最大最小值递归，另一种inorder递归。。。都是时间O(n), in-place....

CeciliaM 发表于 2016-9-2 07:58
感谢！
是明年五月

现在google全职，要先做oa么？

iPhD 发表于 2016-9-2 08:02
对，应该2种方法，一个左右最大最小值递归，另一种inorder递归。。。都是时间O(n), in-place....

递归的话有函数栈，感觉应该都算 Space O(h) ?

keepworkinghard 发表于 2016-9-2 08:06
现在google全职，要先做oa么？

我做了OA，内推是直接MTV onsite

CeciliaM 发表于 2016-9-2 08:10
递归的话有函数栈，感觉应该都算 Space O(h) ?

对，递归都是O(h), h是树的高度，如果平衡的话就是logn.
in-place的数学定义是复杂度小于等于logn，不是非要常数才叫in-place.

iPhD 发表于 2016-9-2 08:13
对，递归都是O(h), h是树的高度，如果平衡的话就是logn.
in-place的数学定义是复杂度小于等于logn，不是 ...

受教！大感谢！

CeciliaM 发表于 2016-9-2 07:40
是把所有duplicate的都去掉，比如如果有很多个k的话，只留下第一个。
维持其它字母的顺序不变。
所以re ...

完全不像原题啊。原题316 不是个Hard space O（1） 还得按字母顺序么。
Remove all duplicates from a given string
感觉是这个

c++里string后面append东西的复杂度挺复杂的，跟具体怎么用有关。
http://stackoverflow.com/questio ... append-vs-push-back
觉得你答O(1)也许不能算错...

cicean 发表于 2016-9-5 04:09
完全不像原题啊。原题316 不是个Hard space O（1） 还得按字母顺序么。
Remove all duplicates from a g ...

完全没读懂316是个什么意思……