Linkedin 店面面经(已挂),请帮忙分析

原帖地址:mitbbs

背景:EE毕业但是做行业软件的,工作好多年了一直用C++。没有专门学过计算机专业
课。刷题刷了好几个月了。

上星期经历了几次店面,Linkedin是我自己觉得面得最好的,以为可以拿onsite了,结
果被据了。
别的店面感觉比Linkedin差很多的都过了,所以特别surprise. 我把问题详细贴出来,
并附上我自己的解答,请大家帮忙分析一下,是哪里出了问题,还是被三哥黑了。面试
一共分三部分。因为最后的题做得比较快,三哥还跟我谈笑风生了几分钟,说你的
coding不错,你来面试的时候需要多准备点系统设计,多线程之类的,搞得我以为我都
拿到onsite在为下一步准备了。

1. 10分钟互相介绍,然后问之前做的最难的项目,我说了一下,三哥问了几个问题,
双方都比较满意(之后的回答过程中,三哥不会说你哪里回答得不大好,但是会一直追
问直到他说ok,当然也不知道这个ok是好还是嘿嘿你丫错了)

2. 基础知识。
Q: virtual memory是如何工作的?优缺点?
A:操作系统一般在内存不够时分配虚拟内存,不够的虚拟空间存硬盘上。优点是内存
不够时还能转,缺点是硬盘读写速度慢
Q:如果有两个进程P1和P2,两个进程都分别读取地址0xabc,会发生什么?
A:因为是两个进程,系统会开两个不相干的地址空间,各读各的没有干扰。
Q: 那这样的读取到底是怎么实现的?P1说我要读0xabc,怎么就知道它能读到自己想要
的内存?
A: (这个我不明确科班的答案),就说操作系统应该有一个进程对page的映射,系统
知道在哪个page里面的地址空间里找。
Q: 这样的不同进程分配不同地址空间的做法有什么优缺点?
A: 优点是不同进程之间的地址各不相干,不会干扰;另外多个进程可以在总内存不够
的时候仍然能转;缺点是进程间通信比较麻烦。
Q:process和thread的区别
A: process是不共享内存的,thread共享内存。后来网上查了一下,好像主要是这个,
当然也说thread往往是light work,但是我觉得漏掉这个应该没有关系,三哥很快说ok
了。

3. 电脑上做题
三哥先敲了道简单的问我问题,我估计这个答得不是太好。
int a;
int* b[100];
Q: 如果改变a或者b有什么问题?
A: 改变a就是赋值还好,改变b实际上是改变了指向array的指针,可能会有问题。(后
来回想起来当时有点紧张,其实改变b也没有关系,或者应该说具体点,如果没有别的
指针指向array的话,array里面的内容没有变量指向,会有leak)
Q: 如果是多个线程要改变a或者b呢?
A: 那就有问题了,会conflict(我知道data race,但是当时没有说这个词)。
Q: a是从内存哪里来的?
A: heap
Q: 那b呢?
A: b指向的array内容也是从heap来的,但是b自己可能来自进程stack吧(后来想我是
不是错了,b是指针跟int差不多也得分配内存空间)。

然后编程题,设计一个数据结构,实现add(e), remove(e), removeRand(e), 都是O(1)
复杂度。我提出了用hash+array,并且在remove的时候,把array尾巴和remove的位置
swap,同时更新hash。三哥说这主意不错你写吧。
下面是我的程序。写完后三哥说cool, sounds good,又问了几个followup,说如果数
有重复怎么办。我说那个hash的value要改成list,记录所有相同元素的位置。那你现
在怎么产生随机数呢?我还没怎么想好,三哥就说是不是要看看重复的个数之类的,然
后就跟我瞎聊了。

大家帮我看看,我是哪里不对挂掉的呢?

template
class element {
public:
element() {}

void add (T e) {
array.emplace_back(e);
hash[e] = array.end() – 1;
}

void remvoe (T e) {
if (count(hash[e]) {
auto it = hash[e];
hash.erase(e);
if (!hash.empty()) {
auto lastit = array.end() – 1;
swap(*it, *lastit);
hash[*lastit] = it;
}
array.pop_back();
}
}

void removeRand() {
if (!array.empty()) {
default_random_engine re ((random_device())());
uniform_int_distribution dis(0, array.size() – 1);
int index = dis(re);
T e = array[index];
remove(e);
}
}

private:
vector array;
unordered_map::iterator> hash;
};