一位编程学长的面试经历.docx
《一位编程学长的面试经历.docx》由会员分享，可在线阅读，更多相关《一位编程学长的面试经历.docx（12页珍藏版）》请在冰点文库上搜索。
一位编程学长的面试经历
签了Offer按理说应该发个帖子庆祝一下，但是我实在是没有那个兴致。
如今正好大伙都放假，那么我也来说说我的面试经历吧。
话说我虽然不说才高八斗，但是至少在计算机方面还是比较有信心的。
至少没感觉到身边有哪些人明显比我水平高。
或许是我身边的人都深藏不露也说不定。
但是总而言之吧，我一上来自信心还是很足的。
于是乎没怎么准备，就投出了简历。
最初的面试是Google。
当时谷歌的面试题目很简单，就是二叉树的后序遍历。
当然，简单归简单，只是我当时犯了一个重大错误，就是明明一个if选择条件语句可以解决的问题，我习惯性的一下子一个while就上去了。
由于与其他搜索树的结构不同，相对简单的二叉树并不需要明确的广度终止条件，所以当我写完了之后，才发现是个死循环。
当然咯，面试官随口一说，我也就发现了。
只不过这面试就Failed了。
经历过出师不利之后，我痛定思痛，集中准备了几天，然后就又出征了，可是万万没想到的是，我的噩梦才刚刚开始。
由于是毕业季临近，所以我很快就得到了第二个面试机会.这次面试的题目是：
进程和线程有什么不同？
我信心满满的回答：
线程之间可以共享部分内存,而进程之间不可以。
面试官说：
还有呢？
我一愣，这怎么还有啊？
于是我硬着头皮说：
在调度上，或许Windows的线程调度会与Linux有所不同，说不定Windows下面线程之间的切换要快一点。
我这么说自然是有道理的。
因为微软的操作系统是不开源的，我只能凭着经验去猜测。
在Linux下面，线程的调度和进程是一样的，也就是说Linux在调度的时候对进程和线程不会加以区分。
面试官听过之后说：
还有呢？
我：
没了吧。
就这些了。
面试官：
不对，还有。
我：
真没了。
要不你告诉我还有什么区别？
当然，说道这里我已经比较生气了，因为这已经近乎无厘头了。
但是面试官似乎并不饶我，继续用一种居高临下的问询的眼光看着我说道：
答案我不能告诉你，但是还有，你仔细想想。
我这下真的有些愤怒了，于是我说：
-我不知道Windows下面是怎么弄的，但是Linux下面我可以跟你来说一说。
Linux本身没有进程和线程的区分，唯一的区别是在进行fork系统调用的时候，你可以设置是否复制全部内存，部分内存和不复制任何内存。
复制全部内存的话就是我们熟知的进程复制；复制和共享部分内存就相当于一个线程；不复制内存的话一般后面紧跟exec系统调用，是用来启动一个新程序的。
Linux在进行fork的时候，使用了copy-on-write的机制，可以降低对于内存写入的次数，提高效率。
但是具体到任务表示上面，进程和线程并无不同，内核也不会进行特殊的关照。
我说到这里顿了顿，看到面试官依然没有发言，于是我接着说：
-那么现在请你告诉我，除了共享内存之外，线程和进程之间有什么不同？
我说完了之后就盯着面试官看，因为我实在是不知道这种明确到1+1=2一样的知识搞得那么高深莫测有什么意思。
面试官避开我的眼神，嘴上说着：
还有其他的不同。
面试以不愉快结束，我又fail了。
当然，我的征程还远没有结束，很快我就又迎来了一次施展拳脚的机会。
这次面试官问的问题是：
有m个已经排好序的数组，每个数组有n个数字。
现在想要让你把这m个数组合并成一个大数组，数组是排好序的。
我听过之后微微一笑，因为这个问题其实并不难。
我仰起头想了想，说：
m*n*log（m）。
面试官问：
什么？
我说：
时间复杂度是m*n*log（m）。
面试官：
你怎么实现呢？
我：
用一个堆再加一个数组。
根据那m个数组的数据结构，或许还需要另一个大小为m的数组来记录下标。
这时候我觉得这个问题可以结束了，已经没什么可多说的了。
可是万万没想到啊，很多面试官其实每次就准备一个题目，你很快得出结论的话，面试官就得想方设法让你撑满整个的面试时间。
于是就有了下面的对话。
面试官：
你确定是最优解了么？
我：
我确定
面试官：
你再想想？
我：
是m个数组吧？
面试官：
是的
我：
每个数组有n个数字？
面试官：
是的
我：
m*n*log（m），这就是最优解了。
面试官：
你不尝试着换个思路？
我：
难道是分布式？
或者是Hash排序？
面试官想了想：
不是。
这下我心里真发毛了。
因为我断然想象不出来亚马逊有什么逆天的科技能够做出比这种解法更优化的解法，但是看着面试官“慈祥”的笑容，我决定试一下另外一个法子。
我用了所谓的“逆二分法”。
这个做法还是我被逼无奈当时临场创造出来的，数据结构复杂不说，最后的时间复杂度依然是m*n*log（m）。
而且为了排序方便，我使用了红黑树。
当我写下rb_node的时候，面试官都惊呆了。
面试官问：
这是什么？
我：
这是Linux内核当中的红黑树结构。
面试官：
能用么？
我：
能
面试官：
你确定？
我：
是得用到点技巧，但是可以用在普通程序之中。
当然，直到时间最后，我还有一点小尾巴没有写完，面试结束，我又fail了。
当然，我还有机会。
可是万万没想到啊，后来的面试官一上来一个问题就是：
请实现一个缓存。
我都愣了：
缓存？
什么缓存？
准备干什么用的？
面试官：
你别管了，就是一个缓存。
我：
真的？
你让我实现整个的缓存？
我们面试可是时间有限的哦。
面试官：
是的，就是实现一个缓存。
我咽了口口水，好吧，来者不拒，不就是缓存嘛，来吧！
我提笔就开始写下了一个结构体，一个计数器，一个堆排序和队列。
其实本来我想要故技重施用红黑树的，但是考虑到上一次用rb_node被“不理解”了，这次我们就用堆算了。
我边写还边说：
这次我们就用堆排序，因为缓存页面的换入换出我们本质上每次只换最不长用的那一个页面......
就在我奋笔疾书的时候，面试官显然看不下去了。
面试官让我停下，指着白板就问：
这是什么？
我：
这是缓存的结构体表示
面试官：
这是什么？
我：
这是计数器，用来计算缓存上一次使用到现在的时间的。
面试官：
这是什么？
我：
这是排序链表，用来控制缓存换入换出的。
面试官：
你的读写操作呢？
我：
还没开始写呢，你急什么啊？
面试官默默的接过我手里的水笔，在白板上写下了一行字，然后说：
缓存的操作，不就是这样的么？
我抬眼一看，赫然发现一个函数声明：
longcache_read（longloc_s,longloc_e,longaddr_s,longaddr_e）;
我当时就觉得五雷轰顶，心里暗骂，这他喵的是什么缓存啊？
但是我还是忍住了。
我说：
嗯......你这个后面两个变量应该用指针吧？
面试官：
为什么？
我：
因为你不确定你给定的内存范围是可用的啊，万一里面有东西，不能分配这段内存呢？
你用两个指针变量，这样的话分配哪段内存就直接让函数返回你就可以了。
要不然你这个函数怎么用啊？
我调用完了，你给我返回说内存无法分配，那么我难道还内存地址自增一，一个一个试下去，看看哪个能成功么？
面试官貌似觉得我说的有点道理，于是就添加了两个指针符号。
然后我接着说：
你这不叫缓存？
面试官说：
啊？
那这叫什么？
我：
你这叫做“读取文件到内存”。
面试官楞了一下，然后说：
读取文件到内存，不就是缓存么？
我又没让你实现整个缓存，我就是让你实现基本的缓存操作啊？
我苦笑不已，然后又fail了。
屡战屡败之后，我痛改前非，洗心革面，重新做人。
在最后，我投了一家小公司，获得了面试机会。
面试题目是：
求解１*２*３*...*100的最后结果数字结尾有多少个０。
我当然知道答案是100/5+100/5/5=24。
但是这次我学乖了。
我仔细的思索了许久，说：
这个问题很有挑战性。
面试官脸上露出了一丝得意。
我接着说：
从数字上分析，在1到10中间，有两个数字可以导致最后0的产生，他们分别是5和10。
以此类推，从1到100中间，有20个这样的数字。
我顿了顿，观察一下面试官，果然一丝欣慰划过他的脸庞——我中计了。
面试官准备发言了。
可是峰回路转，我立马一挥手，止住要说话的面试官，接着说道：
但是25,50,75和100这四个数字中，因为有各有两个因子5存在，所以这最后的结果应该再加上四。
于是最终结果应该是20+4=24.
面试官说：
那么你能写个程序来算么？
我先写了个循环。
面试官接着问：
你能用递归么？
我又写了个递归。
面试结束之后，我看着面试官脸上满意的微笑，转过身，挥一挥衣袖，拂去功与名。
面试的本质是什么？
面试，其实就是员工去挑选将来的工作同事。
而作为一个新人，你并不需要展现自己的实力有多么强大。
因为如果你“功高盖主”，威胁到了“员工地位”和“公司结构”的话，那么他们断然是不会把你招进去。
你需要做的，就是
1、有点小谦虚，再有点小求知欲
2、基础知识都掌握了
3、有点小动手能力，能写几行小代（呆）码（萌）
4、居然还有点创新精神和创新能力啊
这自然就是可塑之才，有潜力，也有能力。
举个例子吧，如果你在面试中碰到一个题目，说：
请把一个（排序）二叉树转化为一个（排序）双向链表，你应该怎么做呢？
答案自然不简（fu）单（za），前后大约需要不到15行代码（包含大括号）：
注：
牛人请移步后记中的新版本。
-
structnode{node*left,right;};
inlinenode*rmost（node*root）{return!
root->right?
root:
rmost（root->right）;}
inlinenode*lmost（node*root）{return!
root->left?
root:
lmost（root->left）;}
voiddoeverything（node*root）{
if（root->left）{
doeverything（root->left）;
root->left=rmost（root->left）,root->left->right=root;
}
if（root->right）{
doeverything（root->right）;
root->right=lmost（root->right）,root->right->left=root;
}
}
-
但是你要是一上来就给出这个答案，我保证你fail掉。
你要怎么来呢？
先说：
这个问题很有挑战性（体现你的谦虚和求知欲）
再说：
可以进行中序遍历，然后挨个改变左右指针（体现你基础知识夯实）
然后再把中序遍历写出来（体现你有很强的动手能力）
然后再给出一个递归的解法（体现你有创新精神和创新能力）
最后，如果你还嫌不够作死的话，可以添加点编译优化（卧槽，人才啊，公司要的就是你这种人）
学长我，大概也只能帮你到这里了。
后记：
忆初中时，师数与家长曰：
凌学优异，分高，奈何不问问题？
莫非学习不主动？
家长询问，余面有苦色，对曰：
无题可问，何以问题？
想我挑灯彻夜，百读史书，涉猎广泛，无所不究。
奈何今只得凭此雕虫小技混吃等死，了却残余。
寥寥晨朝，依依晚暮，兮兮此生，嗟嗟哀叹。
回忆曾年，星月相照，不免悲从心中来，垂泪无处去。
罢了罢了。
余文记之，若尔等但凡有丁点所得，亦为不枉此文吧。
=====================================================
后记2：
你们怎么能骂人呢？
我也是有自尊的啊，你们怎么能随便骂人呢？
骂的多了我也承受不了啊。
因为我承受不了了，所以我就来再写个后记。
第一个指责说：
二叉树用if是很简单的啊，你怎么用了while呢？
树遍历哪里需要while了？
你个大傻×
话不能这么说，因为用if去遍历树结构，无论你是二叉树，三叉树还是四叉树都是可以的，所以说只要用if就能解决“几乎所有的”树遍历问题。
当然咯，这是不可能的咯。
如果说你需要遍历的不是一个树，而是一个不规则联通图？
或者说你的树的分叉是不固定的呢？
这你就要用到while了吧？
当然，除了用while，你还需要两个队列（如果是广度优先遍历的话）。
如果你使用深度优先遍历的话，你需要一个栈或者用递归。
当然咯，树的结构表示也会有所不同。
但是总而言之，对于一种情况，就是树的广度不确定的情况，你是得用while的。
其他所有情况你都可以用if（喂喂，这话应该倒过来说吧老兄）。
第二个指责说：
你为什么不去证明m*n*log（m）就是数学上的最优解呢？
大傻×
我当然不是没证过，但是面试中我是用的一种类似证明np问题的方法的：
你看，如果说你能找到一种比m*n*log（m）更优秀的解法的话，那么当n=1的时候，我们就找到了一个优于n*log（n）的排序方法，而这在历史上是从没有过的。
我又进行了简单的递推，说明不仅仅是对于n=1，对于n>1也是不可能的。
然后面试官的原话是：
Idon'tknow.Whydon'tyoutryadifferentsolution?
我自然不会盲目的就去try了，我拿起水笔，在我开始写代码的时候，我说了如下的话：
Icoulddefinitelytryanothersolution,butthetimecomplexitywillbenobetterthanm*n*log（m）。
第三个指责就是说：
你为什么用rb_node啊，那就是作死，你个大傻×
你不得不说当时我有点作死的想法了，因为我实在是不理解这面试还带这样的？
给你一道题目，规定你不许用堆排序？
所以我心里就想，好呀，你不让我用堆是吧，我给你来个二叉树排序吧。
其实我觉得当一个面试者话说道这个份上，面试官也应该知道这个面试者对于这道题目已经是不在话下了，没必要再多问下去了。
如果还有其他有意思的题目，可以拿出来；如果没准备其他的题目，可以聊聊项目之类的事情。
你说你非抓着我不放，一定要用“另一种解法”去解答一个已知问题，这是一种什么精神？
我觉得这一定是中国特色的社会主义精神，叫做：
有条件要上，没条件创造条件也要上。
人家明明走在康庄大道上，我们一定要把他拉下来一起摸石头。
第四个指责就是说：
缓存那块，为什么要把long改用指针呢？
在32位系统里面，long和指针是同样大小的啊，你这不是吹毛求疵，没事找事么？
你个傻×
这个可就真冤枉我了。
我用指针，主要是为了让那两个输入端变成输出端。
C是没有引用传递的（其实C++的引用传递实际上也是传指针），所以说你要想把输入端搞成输出端，你得用指针。
这样的话，尽管指针指向的地址是不能变的，但是指针指向的地址里面的值是可以改变的。
当然了，这里给你们补充一个小知识，就是：
如果我想让指针指向的地址里面的值也不改变，怎么办呢？
传递参数的时候，在这个指针变量前面添加const。
最后一个指责就是说我最后一个自己给自己出的题目解答的不好。
这个大约有点道理。
因为我出那个题，主要是当时我就在想，出一道什么题目来作例子呢？
要选择这个题目，他要满足三个条件：
1、在现实当中有应用价值（我不喜欢为了做题而做题）
2、基于常见的数据结构（要不然我光描述题目就得描述半天，喧宾夺主，砸绕冗词）
3、要有循序渐进的多种解法
其实现在我还在想，要是当时我给自己出汉诺塔问题的话，估计大家也就没有那么多机会来骂我傻×了。
只是呢，汉诺塔不满足以上的任意一个条件。
1、现实中没人会去专门写个软件去解答汉诺塔问题
2、不少人恐怕不知道汉诺塔是什么意思
3、虽然可以用深度优先搜索树来解决（老大，别用广度优先搜索树，你的空间用度马上就上去了），但是本质上只是递归的另外一种形式（用堆栈来代替递归）。
基于以上想法，汉诺塔问题就没有选中，而选中了二叉树转双向链表的问题。
这种两种数据结构配合使用的情形在Linux内核当中可以见到（好像是文件管理？
）。
那么当然了，我也没花多少时间去考虑解法的问题，就大约想了想，觉得这个问题就是先处理左子树，在处理右子树，依次递归下去，也就完了。
当然我也发现了递归套递归，最后写成了O（n^2）的问题，但是我总觉得，这是本文的细枝末节，无需多虑。
况且这个问题真正看懂解法的人，估计一下子也能明白过来应该怎么改进，所以无伤大雅。
但是万万没想到啊（这个世界果然充满了惊喜），不少人就开始以此为契机，大力开喷，你说仅仅是纠错也就罢了，可是这个喷的我实在是狗血淋头，让我自觉惭愧，什么“你面试我这里也绝对进不了”这种话也都可以说的出来啊。
这就像是“我诅咒你一辈子买泡面没有调料包”一样，让我如此的心寒（你这是干甚么嘛）。
我想起来，当年鸦片战争中，北洋水师提督丁汝昌还在打仗的时候，后面弹劾的折子和谕旨就一封封往刘公岛上送，说：
丁汝昌同志，你现在已经因为贪污腐败，任人唯亲，避战畏战，屡战屡败，是死罪了，赶紧剿灭日本联合舰队后回来领死。
你看，我们当年的中国人就如此泾渭分明，正义凛然。
你打仗，有什么了不起啊？
该是死罪就是死罪，我们秉公执法，连戴罪立功的机会都不给你。
当然我们都知道，丁汝昌没有回去领死，丁汝昌自己服鸦片自尽了。
丁汝昌真是个没骨气的老东西啊～～！
但是正义凛然的中国人民并没有饶了万恶的丁汝昌，抄家，连坐，曝棺于县衙，坚决不让丁汝昌的尸体下葬。
哎呀哎呀，让我看到这段史料的时候真的是义愤填膺，拍手称快。
中国有这么些仁人志士，岂有不王（亡）的道理啊？
我忽然觉得我们中国真的是充满希望。
因为不少人都很听语文老师的话。
语文老师一定教导过我们，这个写文章呢，不要写立论文，要写驳论文。
这个立论文多难啊，你得面面俱到，处处小心。
驳论文就不一样，你只要抓住对方一点，把握机会，毫不留情，狠狠批斗，就一定能把对方打倒，真所谓既扬名来又立万，得来全不费工夫（咦？
好像50多年前有这么一段故事？
）。
什么叫做大智慧？
依我看，这就是不折不扣的大智慧。
你看看，中国人就是不一般嘛。
只要这样长期的坚持下去，肯定能屹立于世界民族之林～～！
当然咯，所谓知错就改尤未迟也，亡羊补牢犹未晚矣。
我呢，也再次洗心革面，重新做人，这就把一个O（n）的解法给大家放过来。
这次我可是下了点功夫的哦，编译应该是没问题了。
至于拿数字去测么，那就是诸位的事情了。
-
#include
typedefstructnode{
structnode*left,*right;
}node;
voiddoeverything（node*root,node**lmost,node**rmost）{
node**llm=（node**）malloc（sizeof（node*））;
node**lrm=（node**）malloc（sizeof（node*））;
if（root->left）{
doeverything（root->left,llm,lrm）;
root->left=*lrm,root->left->right=root;
*lmost=*llm;
}else{*lmost=root;}
if（root->right）{
doeverything（root->right,llm,lrm）;
root->right=*llm,root->right->left=root;
*rmost=*lrm;
}else{*rmost=root;}
}
-
你看，这下子我连头文件都给包含好了，正所谓帮忙帮到底，送佛送到西嘛。
（喂喂，本来我就不是抱着帮忙的目的写这篇文章的吧～～）
升级会员 