2015/1/27 电面

lintcode原题：

construct a binary tree from preorder and inorder traversal

在线测试本题：http://t.cn/RADxG4J

2015/2/19 onsite

round 1
1)shuffle an array. 证明等概率

2)unique path, 无障碍物情况下从起点到终点的所有不同路径数

follow up: 有一个障碍物结果怎样，两个又是多少

follow up: 写出代码输出所有路径

round 2

实现一个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？写出代码

round 3
1)随便讲一个知识点，assume面试官没有任何相关背景，五分钟讲清楚。

2)Make friends: 有n个人，每个人要交且只交k个朋友。输入n和k，输出一种交朋友的情况。

round 4

面试官是4个组的director，问了很多behavioral question，如说一个以前的mistake，说一个最喜欢的做过的项目。

lintcode原题word break，输出一种分割即可。 (在线测试本题：http://t.cn/RADxMwk)

follow up: 英语中，几个字母组成单词的概率远小于不是单词的概率，怎么优化？