box面经 攒人品

原帖地址:一亩三分地

发个完整的Box面经攒人品,希望对大家有帮助
网上逛stackoverflow发现他们家招人,在官网上投了简历,很快recruitor就联系了,发现另外一个组有个职位更合适,简单聊了聊组是做什么的就安排了电面。
电面是2sum和3sum。leetcode上的简单题。顺利通过。
很快安排了onsite,总共四轮。
1. 定义uniform tree是指所有node的value一样,写算法怎样判断一个树是不是uniform tree,时间复杂度,空间复杂度。然后扩展一下,问一个root下count所有的uniform tree,时间复杂度和空间复杂度。
2. 电梯设计题,50层楼4部电梯,主要考虑怎样优化让人等的时间最短,写一些代码实现,只有一个小时时间,写不了很多code就结束了,这一轮是两个人面。
3. 2个小时的coding,要求带自己的电脑,在自己的IDE里开发,一个带有transaction功能的数据存储,要求:
a. set 存key-value pair
b. get 给定key,返回value
c. count 某一个value出现的次数
d. delete 删掉某个key的value
e. begin transaction 开始一个transaction
f. commit 将所有在transaction里的操作永久存入
g. rollback 删掉最后一个transaction里的所哟操作
ex:
set(1,a);
set(2,b);
set(3,c);
get(3); –> ‘c’
set(4,c);
count(4); –> 2
delete(2);
get(2); –> null
begin;
set(2, d);
get(2); –> ‘d’
commit;
get(2); –> ‘d’
begin;
set(5,e);
set(6,e);
count(e); –> 2
rollback;
count(e); –> 0
4. multithreading,用户都对某个文件夹内的文件进行操作,怎样保证不出错。