FB电面 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

FB电面

FB电面# JobHunting - 待字闺中

b*n2015-04-09 07:04

1 楼

周一面，小印女，至昨天都没有消息，以为被黑了。结果今天发邮件去催，说准备再加
一轮电面。看来三妹没有黑我啊
做了两道题：
1. 给定数组和target，连续元素和等于target，分析复杂度。给出了O(N)的解，结果
分析的时候在三妹的提示下从N^2说到NlogN一直到N。
2. 给定一个trie，和接口函数Node *get_child(char c), vector get_all_
child(), is_terminal_node(Node *node)。给个单词，看在不在trie里面

h*02015-04-09 07:04

2 楼

第一题数组是sorted的吗？

P*r2015-04-09 07:04

3 楼

第一题元素是非负吗？不然怎么O(n)？

t*22015-04-09 07:04

4 楼

第一题是sliding window的思路吗？从左到右一个一个加，如果sum超过target了，从
左边一个一个减去直到sum小于target？

b*n2015-04-09 07:04

5 楼

数组没有排序，正负都可以，就是一个sliding window，就是O(N)，因为内循环其实只
走了一次。我当时看到两层循环，下意识就平方了

【在 b******n 的大作中提到】

: 周一面，小印女，至昨天都没有消息，以为被黑了。结果今天发邮件去催，说准备再加
: 一轮电面。看来三妹没有黑我啊
: 做了两道题：
: 1. 给定数组和target，连续元素和等于target，分析复杂度。给出了O(N)的解，结果
: 分析的时候在三妹的提示下从N^2说到NlogN一直到N。
: 2. 给定一个trie，和接口函数Node *get_child(char c), vector get_all_
: child(), is_terminal_node(Node *node)。给个单词，看在不在trie里面