阿里一面

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

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

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

项目及询问相关知识

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

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

❤采之欲遗谁,所思在远道。❤
0%