阿里一面

发表于 更新于 本文字数： 4.9k 阅读时长 ≈ 9 分钟

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

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

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

项目及询问相关知识

预约电话后我又发给了小哥哥一份较新的简历，上面写了自己新做的 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 的一种错误用法。面试官给我讲了下，应该算是懂了

    对于运算符 [] 的重载，一开始是返回对应下标的值，我写了出来

    1
    2
    3
    4
    int operator [] (int i)
    {
    	return pArr[i];    
    }

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

    1
    2
    3
    4
    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++ 语法我真的弱爆了，不会。

    面试官小哥哥教了我

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

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

    1
    int operator [] (int i) const;

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

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

    算法

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    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。” 然后互道拜拜一面也就结束了。

总结

总结一下吧，自己的基础还是太薄弱了。C++ 语法， Linux 知识以及网络、网络编程，这些还是要恶补。面试的算法题都比较基础，自己下面刷题不能眼高手低，不写这些比较基础的题？（orz，虽然还是觉得自己应该不愿意去写。。。）

2019.3.31
23:18