2021年一位编程学长的面试经历.docx

签了Offer按理说应当发个帖子庆祝一下，但是我实在是没有那个兴致。如今正好大伙都放假，那么我也来说说我面试经历吧。
话说我虽然不说才高八斗，但是至少在计算机方面还是比较有信心。至少没感觉到身边有哪些人明显比我水平高。或许是我身边人都深藏不露也说不定。但是综上所述吧，我一上来自信心还是很足。于是乎没怎么准备，就投出了简历。
最初面试是Google。当时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被“不理解”了，这次咱们就用堆算了。我边写还边说：这次咱们就用堆排序，由于缓存页面换入换出咱们本质上每次只换最不长用那一种页面......
就在我奋笔疾书时候，面试官显然看不下去了。面试官让我停下，指着白板就问：这是什么？
我：这是缓存构造体表达
面试官：这是什么？
我：这是计数器，用来计算缓存上一次使用到当前时间。
面试官：这是什么？
我：这是排序链表，用来控制缓存换入换出。
面试官：你读写操作呢？
我：还没开始写呢，你急什么啊？
面试官默默接过我手里水笔，在白板上写下了一行字，然后说：缓存操作，不就是这样么？
我抬眼一看，赫然发现一种函数声明：
long cache_read(long loc_s，long loc_e，long addr_s，long addr_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行代码（包括大括号）：
注：牛人请移步后记中新版本。
-
struct node{node* left，right;};
inline node* rmost(node* root) {return !root->right?root:rmost(root->right);}
inline node* lmost(node* root) {return !root->left?root:lmost(root->left);}
void doeverything(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也是不也许。
然背面试官原话是：I don't know. Why don't you try a different solution?
我自然不会盲目就去try了，我拿起水笔，在我开始写代码时候，我说了如下话：I could definitely try another solution，but the time complexity will be no better than m*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 <stdlib.h>
typedef struct node{
    struct node* left，*right;
}node;
void doeverything(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;}
}
-
你看，这下子我连头文献都给包括好了，正所谓帮忙帮究竟，送佛送到西嘛。
（喂喂，本来我就不是抱着帮忙目写这篇文章吧～～）