大厂面试程序员岗位经历

现在这大环境也不好，找工作这么难，找个好工作就跟难了，但是我相信，只要你有真本事，就不会发愁找工作滴！最近我就开始向我向往的公司发出了求职信，并且成功获得了面试邀请，所以现在先让我们一起看看面试问题吧。

一面主要是考察算法和数据结构，难度因面试官而异。听同学说他一面的时候，面试官就让他写了个堆排序，然后就是不听地问项目，感觉很轻松。我就没那么好运了，至少问了五六个算法，还好hold住。

1.写个快速排序吧。 　　

答：这个算是基本功吧，对于想要互联网公司offer的筒子们，最基本的几个排序都得做到能随时随地手写代码，而且不出错。手写代码也是对基本功的考察，千万不要觉得能在电脑上写代码就ok了，记住，一定要在白纸上写下来，你才能确定你会写。 　　

2.IP的有效值是1.0.0.1~255.255.255.255,写个程序，参数是一个char*的IP，返回这个IP是否合法。 　　

答：这题在考察程序员对边界条件的考虑。至少有以下几点是要考虑到的：1.IP超过或不足四位;2.某一位超过了合法范围;3.某一位除了数字，还包含了其他非法符号。这一题可以使用strtok取出IP的每一位，然后检查该位是否合法(数值范围，是否包含非法字符)，最后检查是否有四位。 　

3.一个字符串数组char *A[]={"China","Chinese","Chese",...}，求这个数组中字符串的最长公共前缀，例如这三个字符串的最长公共前缀是Ch。 　　

答：使用字典树，类似的问题还有给你一些QQ号，让你求这些QQ号的最长公共前缀。字典树大家可以去网上搜一搜。 　　

4.求两个字符串的最大公共子串，例如"abcdefg"和"zxdefy",最长公共子串是"def"。 　　

答:动态规划。具体的解法和代码在我的随笔Algorithm分类中有。 　　

5.单向链表反序。 　　

答：这个简单，网上一大堆解法。 　　

6.多个已序数组求交集。 　　

答：这个问题携程也考了，具体做法是将这些数组两两分组，求交集，再将结果继续两两分组，求交集，直到最后得出结果。对于两个已序数组A,B，求交集的方法是令i,j=0if A==B[j],则A是交集中的值，i ,j ; if A>B[j],j ; if A 　　

一面总算是抗住了。本以为二面会轻松一点，谁知道二面更难。

1.了解进程池吗? 　　

答：不了解，只知道线程池。 　　

追问：那你说说线程池。 　　

答：线程池的思想是这样的：一台服务器有许多任务要处理，同时不断有新的任务进来。从前是来一个任务就起一个线程，起的线程来完成任务，完成以后就销毁该线程。如果任务很多的话，这样不断地起线程，销毁线程，会很费时间。于是就有了线程池。线程池就是一次起多个线程，将任务放在一个队列中，线程池中的线程从队列中取出任务去执行，执行完了以后检查队列是否为空，如果为空，说明所有任务都执行完了，线程就会休眠(注意不是销毁)，等到又有新的任务时，主线程会去唤醒线程池中的线程，让他们继续工作，这样就避免了不断地分配和销毁线程。简单的线程池实现代码可以在网上搜到。 　　

追问:在线程从任务队列中取任务时，有没有办法不适用锁? 　　

答：这个问题腾讯也问了，腾讯的问法是，进程间的共享内存，有没有办法不适用锁而同步地读写?我完全不会，诶。 　　

面试官后来提示说，这个任务队列不一定要所有线程共用一个，可以让一个线程有一个任务队列，这相当于让多消费者的模型变成了单消费者。这样消费者之间就不用加锁同步了。而生产者和消费者之间，要想不适用锁的话，可以用循环队列来实现。对于这个知识点，我会在另一个帖子中详细说明。 　　

2.咱们来看看进程池吧，首先，一个进程A,起了子进程H，H阻塞在读取它的stdin上，A向H的stdin发送数据，这个怎么实现? 　　

答：完全懵了，什么叫一个进程A起了子进程H?后来我才弄明白，原来他的意思是，A进程fork产生了一个子进程，然后子进程调用exec函数，启动了H。我原来的想法是，既然H是A的子进程，如果不设置FD_CLOEXEC标志，那么H的文件描述符0(标准输入)应该和A的是共享文件表项的。那直接让A往自己的标准输入里写不就行了吗?后来面试官的意思是用管道，让H将stdin打开在管道的一端上(fdopen)，然后A向管道里写数据。这个应该更稳妥吧。谁能保证FD_CLOEXEC不会被设置呢? 　　

追问:现在A能向H发命令，然后H读取命令，开始工作。如果A起了多个H，那么，A就成了控制进程，而多个H就成了工作进程，这就是进程池了。现在，A读取一个文件，每读取一行，就将内容发送给工作进程H，然后由H写到自己的标准输出上，这个怎么实现? 　　

答：这个直接用一个循环，顺序写向每个进程就好了。 　　

追问：那如果在写第一个进程的时候就发生阻塞了呢?而后面的进程可以正常工作。 　　

答：傻了，应该用select嘛。将要写的文件描述符都加到select的可写描述符集中，这样哪个可写就写哪个。 　　

追问：现在将A的标准输出重定向到另一个文件上，然后让H的输出结果都写到该文件上，怎么实现? 　　

答：想了老半天，终于想出来了。还是select嘛。再建一个管道，将H的标准输出打开在管道的一端，另一端放在select的可读字符集中，如果可读，A就可以读到H的输出了，然后再写到标准输出上，就行了。 　　

3.用过epoll没? 　　

答：没有。大家赶紧去学一下吧，太多面试官问了。 　　

4.写个memcpy吧。 　　

答：这个简单，只要注意如果dest或者src为空的时候，就直接返回。 　

5.非递归地中序遍历二叉树。 　　

答：其实面试官之前问的是后续遍历，不过他看我没写过非递归的，就降低了一点难度，让我写个中序遍历。递归的写法很简单，相信大家都会。这里为什么要用非递归呢?因为非递归的效率更高。我以前就偷懒，想着会一种写法就够了，谁知道今天恰恰考了非递归。不过咱也不能直接来句不会。你可以不会，但不要马上说不会，这体现出你遇到困难很容易就放弃。应该先想一想，如果实在不会，有的面试官会给你一些提示，如果你能按照提示答出结果，也许面试官会更欣赏你，这证明你很会学习，一点就通。面试官看我无从下笔，说你先给我花花栈的结构吧。我一听，栈?莫非这一题要用栈才能解?其实递归不就是程序自己调用自己，而程序不就是在栈里运行的吗?简单来说，递归的最后一层，就像栈顶元素。最后一个进去，最先解出来。顺着这个思路，我居然写出了代码。面试官看了看，ok。 　　

至此，二面结束。 　　

后来和面试官谈了谈职业发展方面的内容，颇有收获。面试官年纪也不大，3年前从华科毕业的，如今已经是一个头目了。他说，咱们是码农，不过码农分几个等级，对于那些你交给他个任务，他能写出代码的，那是最初级的。如果他能把代码分成个几层，层次分明。那是较高一级的。如果他能指出你这结构不对，应该怎么怎么样更好，那是更高级别的。如果想要发展，就要朝着高级别努力，不过前提是你得写得出代码，连代码都写不出来的，那就是要被开掉的。