Snapchat 电面+onsite 面经

原帖地址:米群网

2015/1/27 电面
leetcode原题:construct a binary tree from preorder and inorder traversal

2015/2/19 onsite
round1
1)shuffle an array. 证明等概率
2)unique path, 无障碍物情况下从起点到终点的所有不同路径数
follow up: 有一个障碍物结果怎样,两个又是多少
follow up: 写出代码输出所有路径

round2
实现一个bloomfilter的数据结构,接口如下
class Bloomfilter {
private Key[] table;
private List hashFunc;
public boolean contains(Key k) {}
public void put(Key k) {}
public void remove(Key k) {}
}
该数据结构类似于HashSet,put函数存key进去,contains查询是否存在,remove删除对应的key。它提供了一组hash函数列表hashFunc。
question:
1)该数据结构有个特点,contains函数如果return false,那key一定不存在Bloomfilter内,但如果return true,则可能存在,可能不存在,为什么?
2)实现这个数据结构的三个函数
3)这个数据结构有什么缺点?怎么Scale?写出代码

round3
1)随便讲一个知识点,assume面试官没有任何相关背景,五分钟讲清楚。
2)Make friends: 有n个人,每个人要交且只交k个朋友。输入n和k,输出一种交朋友的情况。

round4
面试官是4个组的director,问了很多behavioral question,如说一个以前的mistake,说一个最喜欢的做过的项目
leetcode原题word break,输出一种分割即可
follow up: 英语中,几个字母组成单词的概率远小于不是单词的概率,怎么优化?