一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1889|回复: 22
收起左侧

Linkedin电面,请帮忙分析为何挂掉

[复制链接] |试试Instant~ |关注本帖
iseeyuan 发表于 2015-12-15 13:06:43 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Linkedin - 内推 - 技术电面 |Fail在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

上星期经历了几次店面,Linkedin是我自己觉得面得最好的,以为可以拿onsite了,结-google 1point3acres
果被据了。
别的店面感觉比Linkedin差很多的都过了,所以特别surprise. 我把问题详细贴出来,
并附上我自己的解答,请大家帮忙分析一下,是哪里出了问题,还是被三哥黑了。面试
一共分三部分。因为最后的题做得比较快,三哥还跟我谈笑风生了几分钟,说你的
coding不错,你来面试的时候需要多准备点系统设计,多线程之类的,搞得我以为我都
拿到onsite在为下一步准备了。
. Waral 鍗氬鏈夋洿澶氭枃绔,
1. 10分钟互相介绍,然后问之前做的最难的项目,我说了一下,三哥问了几个问题,
双方都比较满意(之后的回答过程中,三哥不会说你哪里回答得不大好,但是会一直追
问直到他说ok,当然也不知道这个ok是好还是嘿嘿你丫错了). from: 1point3acres.com/bbs

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

3. 电脑上做题. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
三哥先敲了道简单的问我问题,我估计这个答得不是太好。
int a;
int* b[100];
Q: 如果改变a或者b有什么问题?
A: 改变a就是赋值还好,改变b实际上是改变了指向array的指针,可能会有问题。(后
来回想起来当时有点紧张,其实改变b也没有关系,或者应该说具体点,如果没有别的. Waral 鍗氬鏈夋洿澶氭枃绔,
指针指向array的话,array里面的内容没有变量指向,会有leak)
Q: 如果是多个线程要改变a或者b呢?
A: 那就有问题了,会conflict(我知道data race,但是当时没有说这个词)。
Q: a是从内存哪里来的?
A: heap.鐣欏璁哄潧-涓浜-涓夊垎鍦
Q: 那b呢?
.鏈枃鍘熷垱鑷1point3acres璁哄潧A: b指向的array内容也是从heap来的,但是b自己可能来自进程stack吧(后来想我是. 1point3acres.com/bbs
不是错了,b是指针跟int差不多也得分配内存空间)。

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

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

template <class T>. more info on 1point3acres.com
class element {
public:. visit 1point3acres.com for more.
    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;. visit 1point3acres.com for more.
                swap(*it, *lastit);
                hash[*lastit] = it;
            }. 鍥磋鎴戜滑@1point 3 acres
            array.pop_back();
        }.1point3acres缃
    }
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    void removeRand() {
        if (!array.empty()) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            default_random_engine re ((random_device())());
            uniform_int_distribution<int> dis(0, array.size() - 1);
            int index = dis(re);
            T e = array[index];
            remove(e);. visit 1point3acres.com for more.
        }
    }
   
private:
    vector<T> array;
    unordered_map<T, vector<T>::iterator> hash;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
};. 1point 3acres 璁哄潧

评分

1

查看全部评分

cocaptainco 发表于 2015-12-15 13:19:51 | 显示全部楼层
patpat楼主,我遇到的所有三哥面试官都在店面把我挂了,感觉三哥不是很友好,会抓住你的任何一个小问题挂你。
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2015-12-15 13:22:58 | 显示全部楼层
看了细节,觉得可能两个地方不对,一是int a 是allocate在stack上的,二是我觉得unordered_map存iterator不太对吧,因为vector本身满了要重新分配空间,iterator有可能会被invalidate 掉,不如直接存index
回复 支持 反对

使用道具 举报

boyshone 发表于 2015-12-15 13:34:32 | 显示全部楼层
int a 和 int* b[100]都是在stack上的

需要new  才会到heap上去的
回复 支持 反对

使用道具 举报

 楼主| iseeyuan 发表于 2015-12-15 13:39:52 | 显示全部楼层
谢谢回答。看来这里答错了。这种heap,stack的东西能否给个简单的链接,我好学习一下?
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2015-12-15 13:40:03 | 显示全部楼层
boyshone 发表于 2015-12-15 13:34. From 1point 3acres bbs
int a 和 int* b[100]都是在stack上的

需要new  才会到heap上去的

有道理。。。一不注意就漏了
回复 支持 反对

使用道具 举报

 楼主| iseeyuan 发表于 2015-12-15 13:41:15 | 显示全部楼层
iseeyuan 发表于 2015-12-15 13:39
谢谢回答。看来这里答错了。这种heap,stack的东西能否给个简单的链接,我好学习一下?

多谢你和cocaptainco的回复。-google 1point3acres
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
看来这里答错了。这种heap,stack的东西能否给个简单的链接,我好学习一下?
回复 支持 反对

使用道具 举报

boyshone 发表于 2015-12-15 13:44:58 | 显示全部楼层
iseeyuan 发表于 2015-12-15 13:41
多谢你和cocaptainco的回复。

看来这里答错了。这种heap,stack的东西能否给个简单的链接,我好学习一 ...

我觉得这种小的知识点知道就是知道
平时多积累就可以了
回复 支持 反对

使用道具 举报

chouclee 发表于 2015-12-15 13:50:31 | 显示全部楼层
也不一定是答得不好。。。他家很看重速度,电面一般至少得写两道code才行吧,多的有人能写3题的
回复 支持 反对

使用道具 举报

tailofjune 发表于 2015-12-15 13:57:19 | 显示全部楼层
实话实说,你的2和3答得都不好,挂掉其实并不太能归咎到三哥上.
回复 支持 反对

使用道具 举报

 楼主| iseeyuan 发表于 2015-12-15 14:03:59 | 显示全部楼层
tailofjune 发表于 2015-12-15 13:57
实话实说,你的2和3答得都不好,挂掉其实并不太能归咎到三哥上.

谢谢提点。能否具体点。
上面有人指出3当中有答得不好的,我查了一下,关于stack和heap是答得不好。
http://blog.csdn.net/ns_code/article/details/21260229
请问3有何补充?

2当中又有哪些答得不好呢?更好的答案是什么?我查了一下,好像跟我说的看起来差不太多。
回复 支持 反对

使用道具 举报

tailofjune 发表于 2015-12-15 14:37:51 | 显示全部楼层
iseeyuan 发表于 2015-12-15 14:03
谢谢提点。能否具体点。
上面有人指出3当中有答得不好的,我查了一下,关于stack和heap是答得不好。
ht ...

Q: virtual memory是如何工作的?优缺点?
A:操作系统一般在内存不够时分配虚拟内存,不够的虚拟空间存硬盘上。优点是内存
不够时还能转,缺点是硬盘读写速度慢
virtual memory和内存够不够应该没什么关系.你的优缺点说的是对的,但是感觉再答全点更好.
Q:如果有两个进程P1和P2,两个进程都分别读取地址0xabc,会发生什么? 鏉ユ簮涓
回复 支持 反对

使用道具 举报

tailofjune 发表于 2015-12-15 14:39:19 | 显示全部楼层
iseeyuan 发表于 2015-12-15 14:03
谢谢提点。能否具体点。
上面有人指出3当中有答得不好的,我查了一下,关于stack和heap是答得不好。
ht ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
上一个直接复制的有点问题.... 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

Q: virtual memory是如何工作的?优缺点?
A:操作系统一般在内存不够时分配虚拟内存,不够的虚拟空间存硬盘上。优点是内存
不够时还能转,缺点是硬盘读写速度慢
virtual memory和内存够不够应该没什么关系.你的优缺点说的是对的,但是感觉再答全点更好.
Q:如果有两个进程P1和P2,两个进程都分别读取地址0xabc,会发生什么?
A:因为是两个进程,系统会开两个不相干的地址空间,各读各的没有干扰。
这个基本是对的,但是不同进程的虚拟地址也是可以映射到相同的物理地址的,但我觉得他可能没想问这个.. 鍥磋鎴戜滑@1point 3 acres
Q: 那这样的读取到底是怎么实现的?P1说我要读0xabc,怎么就知道它能读到自己想要. more info on 1point3acres.com
的内存?
A: (这个我不明确科班的答案),就说操作系统应该有一个进程对page的映射,系统
知道在哪个page里面的地址空间里找。. Waral 鍗氬鏈夋洿澶氭枃绔,
这个概念上是对的,但是感觉你能答点细节就更好了.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Q: 这样的不同进程分配不同地址空间的做法有什么优缺点?. Waral 鍗氬鏈夋洿澶氭枃绔,
A: 优点是不同进程之间的地址各不相干,不会干扰;另外多个进程可以在总内存不够的时候仍然能转;缺点是进程间通信比较麻烦。
优点是对的,但是再答全点就更好了,缺点感觉比较牵强.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Q:process和thread的区别
A: process是不共享内存的,thread共享内存。后来网上查了一下,好像主要是这个,
当然也说thread往往是light work,但是我觉得漏掉这个应该没有关系,三哥很快说ok
了。
你这里说的内存到底指什么,是指物理内存还是虚拟内存,是指寻址空间还是什么.这个题感觉你答得很模糊,并且只答了这一个点.

这一几个问题都是关于操作系统知识的,如果我得到你这样的答案我会感觉你是知道这些知识的,但是并不很清楚.-google 1point3acres
3. 电脑上做题
三哥先敲了道简单的问我问题,我估计这个答得不是太好。
int a;
int* b[100];
Q: 如果改变a或者b有什么问题?
A: 改变a就是赋值还好,改变b实际上是改变了指向array的指针,可能会有问题。(后
来回想起来当时有点紧张,其实改变b也没有关系,或者应该说具体点,如果没有别的指针指向array的话,array里面的内容没有变量指向,会有leak)
有指针的话我觉得应该是C/C++吧.我记不太清了,不过你确定这样定义的b是可以改变的吗?b是一个数组.还是说你的意思是改变b数组里的元素?
Q: 如果是多个线程要改变a或者b呢?
A: 那就有问题了,会conflict(我知道data race,但是当时没有说这个词)。
这个我没太清楚题意.
Q: a是从内存哪里来的?
A: heap
Q: 那b呢?
A: b指向的array内容也是从heap来的,但是b自己可能来自进程stack吧(后来想我是 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不是错了,b是指针跟int差不多也得分配内存空间)。
这两个你也知道不是很好了.
回复 支持 反对

使用道具 举报

 楼主| iseeyuan 发表于 2015-12-15 14:51:17 | 显示全部楼层
tailofjune 发表于 2015-12-15 14:39
上一个直接复制的有点问题...

Q: virtual memory是如何工作的?优缺点?

多谢点评!看来我需要补习一下操作系统方面的知识。
回复 支持 反对

使用道具 举报

puppetartist 发表于 2015-12-15 15:19:52 | 显示全部楼层
Q: virtual memory是如何工作的?优缺点?
A:操作系统一般在内存不够时分配虚拟内存,不够的虚拟空间存硬盘上。优点是内存
不够时还能转,缺点是硬盘读写速度慢

你这完全是字面意思乱答的吧。还有优点缺点也全部不对啊。每一个process,包括OS kernel,用的都是虚拟内存,每个虚拟内存map到具体的physical内存。 你这样回答一下就暴露你对OS基本不了解啊。
回复 支持 反对

使用道具 举报

chouclee 发表于 2015-12-15 16:31:59 | 显示全部楼层
puppetartist 发表于 2015-12-15 15:19
Q: virtual memory是如何工作的?优缺点?
A:操作系统一般在内存不够时分配虚拟内存,不够的虚拟空间存硬 ...

Virtual memory 会用到disk的。。。你说的是virtual address to physical address.
回复 支持 反对

使用道具 举报

chouclee 发表于 2015-12-15 16:32:12 | 显示全部楼层
puppetartist 发表于 2015-12-15 15:19
Q: virtual memory是如何工作的?优缺点?
A:操作系统一般在内存不够时分配虚拟内存,不够的虚拟空间存硬 ...
-google 1point3acres
Virtual memory 会用到disk的。。。你说的是virtual address to physical address.
回复 支持 反对

使用道具 举报

puppetartist 发表于 2015-12-16 02:29:36 | 显示全部楼层
chouclee 发表于 2015-12-15 16:31
Virtual memory 会用到disk的。。。你说的是virtual address to physical address.

Virtual Memory 用到disk无非是把disk 上内存map到memory里,或者是把backing store在disk里之前的内存又从新取回到memory里用,但无论如何,Virtual memory不可能跨过physical address直接和disk有联系,不知道你说的virtual memory 用到disk是怎么个用法。
回复 支持 反对

使用道具 举报

chouclee 发表于 2015-12-16 13:36:23 | 显示全部楼层
puppetartist 发表于 2015-12-16 02:29. Waral 鍗氬鏈夋洿澶氭枃绔,
Virtual Memory 用到disk无非是把disk 上内存map到memory里,或者是把backing store在disk里之前的内存又 ...

就是你说的用法啊。。。我只是想说“每一个process,包括OS kernel,用的都是虚拟内存” 这句不怎么对,虚拟内存是为了应付RAM不够的问题,windows都可以关闭虚拟内存的,所以大家才说楼主说的出发点基本没错呀,只是中间还有VA转PA,内存置换页算法等等一堆没有讲。
如果说“process,包括OS kernel,用的都是virtual address”,这么说主流OS就没问题了。
回复 支持 反对

使用道具 举报

zsycn 发表于 2015-12-29 03:22:16 | 显示全部楼层
去看cmu 15213 课程,网上资料都有。就是《深入理解计算机系统》那本书,能解决你的大多数问题
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 08:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表