职位类型：程序员
面试地点：北京
招聘公司：奇虎360
现在这大环境也不好，找工作这么难，找个好工作就跟难了，但是我相信，只要你有真本事，就不会发愁找工作滴！最近我就开始想我向往的公司发出了求职信，并且成功获得了面试邀请，所以现在先让我们一起看看面试问题吧。
一面主要是考察算法和数据结构，难度因面试官而异。听同学说他一面的时候，面试官就让他写了个堆排序，然后就是不听地问项目，感觉很轻松。我就没那么好运了，至少问了五六个算法，还好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年前从华科毕业的，如今已经是一个头目了。他说，咱们是码农，不过码农分几个等级，对于那些你交给他个任务，他能写出代码的，那是最初级的。如果他能把代码分成个几层，层次分明。那是较高一级的。如果他能指出你这结构不对，应该怎么怎么样更好，那是更高级别的。如果想要发展，就要朝着高级别努力，不过前提是你得写得出代码，连代码都写不出来的，那就是要被开掉的。
