阿里一面

原文链接
周五的时候突然收到了阿里面试预约的电话，毫无准备，因为自己还没投简历。问了下原来是学长内推的，和面试官预约了今天上午9:30面试。预约的时候能感觉到小哥哥是个极其温柔的人，所以很期待这场面试。虽然从预约到面试仅有两天，但全然没有准备谷歌时紧张，或者说没有紧张感。

没想到面试持续了两个小时，自我感觉还算良好。面试整体分成三部分吧：

围绕项目询问相关知识
实现一个 vector
算法

项目及询问相关知识

预约电话后我又发给了小哥哥一份较新的简历，上面写了自己新做的 HTTP 服务器项目，所以这次的面试一开始问了一些这个项目的事情，以及围绕这个项目问了一些相关知识，对印象比较深的问题做下纪录吧：

简要介绍下项目（我照着我 Github 读了一遍）
做了压力测试吗，“没有”（看来后面要用wenbench做下。。。）
epoll与select poll的区别， ET 模式与 LT 模式的区别
什么是非阻塞模式，（我用买生日蛋糕打比方，非阻塞模式是不停的过来询问有没有做好，面试官小哥哥问为什么不是他做好来打电话通知你，这样不是更高效吗。。我记得这好像是一种实现方式，记不太清楚了，orz，明天问问老师吧，我这种速成学习果真只是应付应付，其实什么都不清晰）
使用线程池提高并发度，并降低频繁创建线程的开销。怎么提高并发度的，为什么说创建线程的开销大。
我是怎么给线程分配任务的，（RR策略）。有没有什么优化方式？我回答的是能够知道当前负担较少的线程，把新任务分给它。面试官告诉我换一个角度，建一个任务队列，每个线程做完当前任务后去这个队列中领任务。问如果这么做有没有要注意的，我的回答是如果两个线程同时完成去领任务的话要注意同步，对任务加锁。
我的线程模型为分主线程、IO线程、worker线程。为什么要这么分，我回答是实现 Reactor 模式。面试官：什么是Reactor模式，这种模式的优点是什么？orz，给跪了，这个不清楚。缺点是什么，或者说有没有什么情况这种线程切换是不能忍受的。如果问我缺点是什么我不知道，但后面这句提示了我，回答说如果worker线程耗时比较短，很快就能完成，这里线程切换时间比重较大，这种情况是不能忍受的。
你说使用了 HTTP 长链接，什么是长连接，什么是短连接，它们各自的使用场景是什么。orz，这个，我凭着之前扫过一眼的印象，觉得长连接就是能够保持连接，短连接就是发完报文直接关闭而不保持，当时心虚不知道对不对，但也就这么说了出来。看面试官的反应应该是对的吧。然后说应用场景，我就说如果双方一次会话信息交互频繁的话使用长连接，比较我们在网页上聊天，双方一直保持连接，避免频繁的建立关闭连接，而如果双方只发送短报文，交互次数不频繁的话就短连接。看面试官反应应该是对的？
支持优雅关闭？什么是优雅关闭，为什么要这么做。我就把四次挥手迁了出来，用四次挥手来回答这个问题，说出了四次挥手的过程，以及 time_wait 和 close_wait状态，心里想着他肯定会问这两个状态相关的知识，果不其然问了 time_wait ，这也刚好是我准备的。回答了为什么要有 time_wait 状态，而不立即关闭客户端连接。（感觉面试的时候你可以引着面试官向你会的知识方向）
零拷贝？什么是零拷贝，为什么零拷贝能提高性能，你是怎么实现零拷贝的。这也算是自己之前准备的吧，但其实自己也并不太清楚。就说比如 socket 读写的时候在用户空间和内核空间的数据需要拷贝，如果不拷贝的话就可以提高些性能。怎么实现，splice()函数和管道。

这一方面印象较深的问题大概就这些吧，后面想起来的话再添加。对这方面做个总结，就是知识果真是积蓄而来的，速成只能知道表面皮毛而不可知其根本。自己网络、操作系统、Linux这些方面的知识还是太薄弱了，一个月地疯狂补习根本是不足够的，达不到自己心中的要求的。后面还需要静下以来深入地学习。（现在只能应付应付吧，对自己的评价是其实什么也不知道，需要深入地知道一项知识，知其根本。）

手写vector

下面部分聊到了STL的容器知识，面试官让我说一些容器以及它的一些本质。自己比赛用的STL还算可以，于是就说了几个。vector是动态数组，list双向链表，set（集合，不允许重复）、map（键值对）红黑树，multiset, multimap（允许重复的，自己不太清楚是不是红黑树所以略过没说），deque（双端队列，好像是块状数组，不太了解，之前扫过一眼），stack栈，queue队列，priority_queue优先权队列、堆。unordered_map哈希、桶。问什么是哈希、这个为什么是桶。自己口糊了一波，但其实并不知道。。说了哈希以及哈希冲突的解决办法。unordered_set不了解。

然后是手写实现一个 vector，这个暴露问题比较大。

不会使用异常
不会使用模板，数据类型请求用int，所以其实写了个int动态数组。
其实不知道vector的内部实现。好像 push_back() 以及resize()是需要用reserve()函数的，自己不了解这点，所以在 push_back() 和 resize()中写的扩容，面试官说冗杂，设计不是很好。
不会写返回左值引用。
对函数重载中的const不了解
拷贝构造函数一般要在参数前加 const
memcpy()不会使用
new delete不了解底部实现，自己使用了delete的一种错误用法。面试官给我讲了下，应该算是懂了

对于运算符 [] 的重载，一开始是返回对应下标的值，我写了出来
```
int operator [] (int i)
{
    return pArr[i];    
}
```

之后是写返回左值引用，相当于我写a[i]=1，是对数组中这个数赋值操作，orz，不会了。面试官告诉我了如下代码

  int & operator [] (int i)
  {
      return pArr[i];    
  }

orz, 这样就可以了。返回一个引用。

但面试官的问题显然是准备好的，在拷贝构造函数中让我用 memcpy()来拷贝。我不太会用这个函数，给面试官说了自己觉得这个函数应该需要目标数据首地址，源数据首地址，拷贝的长度。面试官说嗯，并给出了函数的原型。然后自己写下了 memcpy((int *)pArr, (int *)vec.pArr, vec.size()*sizeof(int));写的时候意识到pArr是私有的，不能通过对象来访问，于是打算回去写个begin()，面试官拦住了我，问他这么写可不可以memcpy(pArr, &vec[0], vec.size()*sizeof(int)); 我纠结了下，感觉 &vec[0]不太对，不知道是返回一个立即数还是返回这个引用。于是面试官引出了刚才的重载出了问题，我说嗯，会发生歧义，不知道调用哪个。问我怎么修改，orz，C++语法我真的弱爆了，不会。

面试官小哥哥教了我

  const int& operator [] (int i) const;
  int& operator [] (int i);

然后告诉我第一个其实也可以换成

  int operator [] (int i) const;

相当于只加一个const，而我们看比较正式的代码都会采用上面的写法，在前面加个 const，为什么，orz，这个我也不知道。嘟嘟囔囔半天说不出来正确的。小哥哥告诉我说这样返回的是结果引用，如果采用下面方法的话会进行一次拷贝，性能不好。你这个数组用的int，性能下降不会太明显。如果是一个类的话，就会明显了。orz， 这个真的学习了。很感谢面试官，真的学习了很多知识。

面试官说反应出我C++语法不是很熟练，但没太大关系。应该是理解我打ACM出身，用C++只是用来解决一些算法题目，对一些语法不了解。

算法

下面就是算法部分了，这部分比较顺利，第一题对我来说算是秒杀吧，经典题目，合并K个有序链表。直接写了出来，但后面改的时候脑袋一抽，尼玛写了个根本没必要的while循环，现在想来根本没必要，还会导致性能下降。

  ListNode* merge(const vector<ListNode*> &lists) {
  if(lists.empty())
  reutn nullptr;
  int n = lists.size();
  while(n > 1)
  {
  int k = (n+1)>>1;
  for(int i=0; i<n; i++)
      lists[i] = mergeTwo(lists[i], lists[i+k]);
  n = k;
  }
  return lists[0];
  }
  ListNode * mergeTwo(ListNode* list1, ListNode* list2)
  {
      ListNode *pList = new ListNode();
      ListNode *cur = pList;
      while(list1 && list2)
      {
          if(list1->val < list2->val)
          {
              cur->pNext = list1;
              list1 = list1->pNext;
          }
          else
          {
              cut->pNext = list2;
              list2 = list2->pNext;
          }
          cur = cur->pNext;
      }
      while(list1 != nullptr || list2 != nullptr)    //根本没必要
      {
          if(list1)
          {
              cur->pNext = list1;
              list1 = list1->pNext;
          }
          if(list2)
          {
              cur->pNext = list2;
              list2 = list2->pNext;
          }
      }
      return pList->pNext;
  }

让我分析下复杂度，自己口糊了一个和链表长度有关， O(K longN)，面试官想了一会，好像觉得对。。聊了会说这是经典题，原来做过。orz，其实没做过，这种题我一般不愿去做，逃。。然后问我知不知道经典算法，我问了下。面试官说了一下，我没听太清楚，就问是不是优先权队列，面试官小哥哥说是。然后我口糊了一波实现，小哥哥说对的。然后我夸了一波这算法，清晰，balabala的。小哥哥看我秒了一道算法，然后又问了一道，说不用我写，说下思路就行。。woc，这太TM爽了，毕竟我就是口糊选手。。。敲代码不行，但口糊我可不怂。

问n个元素，求最大最小值。我？？？这题肯定有玄机，不管了，先暴力？？遍历一遍不就好了？O（n），准备说比较多少次，2（n-1）。有没有什么优化。我寻思着这也不能优化到 O（log n）呀。小哥哥给了个提示，不是数量级上的优化，那我就放心了。。想了一会还是没想出来，小哥哥给了第二个提示，优化到 $O({3 \over 2}n)$ 。想了不久，说每次取两个数先比较，小的和当前存的最小比，大的和最大比，这样每2个数由原来的比较4次优化到了3次。小哥哥说不错。应该是正解了。然后小哥哥说不错很好，后面应该也有同学会接着面。我没听明白什么意思，大概就理解成一面过了，后面有他同事接着面试我的意思？今天也挺长时间的，balabala，我说今天周日，和小哥哥面试刚好学习。然后问了他在阿里最大的收获或感受。小哥哥笑了笑，聊了一些。说起搜索推荐、机器学习的时候，小哥哥说：“哎呀，其实这个low爆了，很低端的。我们就是调调参，读读paper。”然后互道拜拜一面也就结束了。