【面试】大佬是如何面试别人List相关知识的

淡淡的烟草味﹌ 2021-09-30 23:36 287阅读 0赞

> 本文公众号来源：编程新说李新杰 作者：编程新说
> 
>   
> 
> 
> 看后总结：良心面试官

面试我们应该正确对待。知道的就回答，不知道的就请教，似是而非的就探讨，开开心心的度过一个小时的交谈就行了。至于结果那要看缘分了，而且这是一个双向选择。  
  
**?****记一次面试**  
  
有位应聘者来面试，我和他坐到了小会议室里。他，很年轻，刚入行，应该还培训过，是不是计算机专业我已经记不清了。  
  
但这不重要，照例还是从List问起。一是List可以说是最简单的，二是简单的问题更能考察一个人的思维表达能力。  
  
我：做Java开发的，List肯定用过，你都用过哪些List的实现类呢？  
  
他：一般都用ArrayList。  
  
我：除了ArrayList，你还知道哪些List，没用过也行。  
  
他：（有点紧张）不知道。  
  
*其实他的水平大概我也清楚了，完全可以再问两个问题草草把他打发走。但只要时间允许的情况下，我是不会这样做的。  
  
一方面是不让面试者觉得自己因水平较差不受重视。  
  
二是这部分人大都是转行培训刚入坑不久的新人，不想让他们的自信心受到打击。  
  
三是面试的过程其实对面试官也是一种锻炼，也可以借机refresh自己的记忆。  
  
最后说句良心话，面试者为了这个面试花在路上的时间估计都要一个小时，如果用5分钟就让人家走，感觉有点说不过去。*  
  
我：还有一个LinkedList，不知道你有没有见过。  
  
他：知道，平时没用过，所以没什么印象。  
  
我：一个叫ArrayList，一个叫LinkedList，根据名字你说下它们底层是怎么实现的？  
  
他：应该一个是用数组实现的，一个是链表实现的。  
  
我：那你能不能说一下数组和链表的主要区别是什么？  
  
*大概过了好几秒，他没有回答，也不说不知道。我觉得可能是我问的方式略微笼统，我就又具体了一些。*  
  
我：数组和链表是数据结构里的概念，这你应该知道。我的意思是从数据结构的角度，数组有什么特点，链表有什么特点，或者说它们在内存里大致是怎么分布的？  
  
他：数据结构的东西不太会。  
  
*我觉得我的问题已经很清晰了，但凡是正常的开发者，多多少少都应该能说出点，可是，他没有。  
  
看得出他有点紧张，所以我每次都是微笑着、用很柔和的声音和他说话，就害怕太强势了给他造成影响。  
  
虽然这么简单的问题，他都不会，我还是很耐心地给他讲解，就当是锻炼自己了。*  
  
我：定义一个数组，只需指定一个长度即可。然后就可以通过变量名+索引（或者说下标）的形式访问数组元素了，下标不能超过数组长度，否则就会发生索引越界异常。  
  
比如数组a，长度是10，那么第一个元素就是a\[0\]，最后一个就是a\[9\]。想访问哪个元素只要指定下标就可以了。像这种可以随意访问任何元素的，有个专用名词叫做随机访问。  
  
那我们来看下它在内存中是如何分布的，才支持随机访问。其实数组在内存中是一段连续的空间，你可以把它想象成一个梯子，一个格子紧挨着一个格子。  
  
数组名，也就是这个a，指向了这个空间的起始处地址，也就是数组的第一个元素的地址，所以其实和a\[0\]指向的是同一个地方。但a和a\[0\]的含义不一样，a表示内存地址，a\[0\]表示这个地址上存的元素。  
  
这里的下标0其实指的是相对于起始处地址的偏移量。0表示没有偏移，所以就是起始处地址的那个元素，也即第一个元素。  
  
a\[1\]表示相对于起始处地址偏移量为1的那个元素，实际可以认为底层执行的是\*(a + 1)。a+1表示从起始地址开始向后偏移1个之后的地址，那么\*(星号)的意思就是取出那个地址上存储的元素。因为向后偏移了1个，其实就是第二个，所以a\[1\]叫取出数组的第二个元素。  
  
因数组在内存中是一段连续的空间，所以不管访问哪个元素都是这两步，加上偏移量，然后取数据。这就是它支持随机访问的原因。说白了就是所有元素按顺序挨在了一起。  
  
也可以看出来，不管数组的长度是多长，访问元素的方式都是这两步，都在常量的时间内完成。所以按索引访问数组元素的时间复杂度就是O(1)。  
  
ArrayList只不过是对数组的包装，因为数组在内存中分配时必须指定长度，且一旦分配好后便无法再增加长度，即不可能在原数组后面再接上一段的。  
  
ArrayList之所以可以一直往里添加，是因为它内部做了处理。当底层数组填满后，它会再分配一个更大的新的数组，把原数组里的元素拷贝过来，然后把原数组抛弃掉。使用新的数组作为底层数组来继续存储。  
  
他：你讲的非常好，我完全听懂了，比我当时那个培训班的老师讲的好多了。  
  
我：LinkedList也实现了List接口，也可以按索引访问元素，表面上用起来感觉差不多，但是其底层却有天壤之别。  
  
与数组一下子分配好指定长度的空间备用不同，链表不会预先分配空间。而是在每次添加一个元素时临时专门为它自己分配一个空间。  
  
因为内存空间的分配是由操作系统完成的，可以说每次分配的位置都是随机的，并没有确定的规律。所以说链表的每个元素都在完全不同的内存地址上，那我们该如何找到它们呢？  
  
唯一的做法就是把每个元素的内存地址都要保存起来。怎么保存呢？那就让上一个元素除了存储具体的数据之外，也存储一份下一个元素在内存中的地址。  
  
整个就像前后按顺序依次相连的一条链，我们只要保存第一个元素的内存地址，就可以顺藤摸瓜找到所有的元素。  
  
这其实就像一个挖宝藏游戏，假设共10步，告诉你第一步去哪里挖。然后挖出一个字条，上面写着第二步去哪里挖。依次这样挖下去。第九步挖出字条后才知道宝藏的位置，然后第十步就把它挖出来了。  
  
可见为了得到宝藏必须这样一步一步挖下去。中间的任何一步都不能跳过，因为第十步宝藏的位置在第九步里放着呢，第九步的位置在第八步里放着呢，依次倒着下来就到了第一步的位置，而第一步的位置已经告诉你了。  
  
所以数组更像是康庄大道、四平八稳。链表更像是曲径通幽、人迹罕至。一个像探险，步步为营。一个像回家，轻车熟路。  
  
可见按索引访问链表元素时，必须从头一个个遍历，而且链表越长，位置越靠后，所需花费的时间就越长。所以按索引访问链表元素的时间复杂度就是O(n)，n为链表的长度。  
  
也说明了链表不支持随机访问。所以ArrayList就实现了RandomAccess（随机访问）接口，而LInkedList就没有。  
  
他：你讲的真好。  
  
**?****后记**  
  
后来这个应聘者给我司前台打电话，说他自己水平太差，无法到我司来。但是叮嘱前台一定要转达对我的感谢。  
  
说面试时他内心非常紧张，但面试官总是面带微笑很温和地跟他说话。遇到不懂的地方，总是非常有耐心地给他讲解，旁征博引，举一反三。最后他都听懂了，而且也不紧张了。  
  
我感觉这是我收到的对我最高的评价，不是吗？

推荐阅读：

*  [MySQL知识点总结][MySQL]
 *  [通过淘宝，大白话讲解大数据各个方向的分工][Link 1]
 *  [《大型网站系统与Java中间件》读书笔记 （二）][Java_]
 *  [面试官:“谈谈Spring中都用到了那些设计模式?”。][Spring]
 *  [【吐血推荐】什么是领域驱动设计？DDD？][DDD]
 *  [基础：为什么计算机只认识0和1？][0_1]
 *  [面试题：你的Redis怎么持久化的][Redis]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

**200多篇** **原创** **技术文章** **海量视频资源** **精美脑图** **面试题**

**长按扫码可关注获取**

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png]点个再看![640?wx\_fmt=png][640_wx_fmt_png 1]

[MySQL]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247485341&idx=1&sn=3447d1843e65e6a6365dd1d2ddbdca3b&chksm=ebd7469cdca0cf8a89eed4a3858cb84b8a227283081058ad889351ee33926054db9e707cedac&token=1279473248&lang=zh_CN&scene=21#wechat_redirect
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247485337&idx=1&sn=5e7bc6831cc236d1452192d1165faae5&chksm=ebd74698dca0cf8e66289afd39f37436c190dfb29dd4d27459f78a8ccf3965a6e9d1510688ee&token=299822969&lang=zh_CN&scene=21#wechat_redirect
[Java_]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247485332&idx=1&sn=d5124382dd89c6f0b724d3feac001d34&chksm=ebd74695dca0cf83a5a412faabd5fb7099fe2e8b1d425170d66b7bf77190a00572c78210c53b&token=323270755&lang=zh_CN&scene=21#wechat_redirect
[Spring]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247485324&idx=1&sn=c1ee95e48a9554e5e02314e1563d2137&chksm=ebd7468ddca0cf9ba59f0196031b1c2842a4b1affd38d20519c481dc2bee3318d660f1f06479&token=2042355911&lang=zh_CN&scene=21#wechat_redirect
[DDD]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247485322&idx=1&sn=6676735b2d3eb5ba01628626affb9e19&chksm=ebd7468bdca0cf9d17d036cbd84768d52fb8c7c1fb7a7527b9390b58d667250aba1a052c9ace&token=2042355911&lang=zh_CN&scene=21#wechat_redirect
[0_1]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247485320&idx=1&sn=26b7d46a1c2ca32e9d4ef981d39594bd&chksm=ebd74689dca0cf9fd2f6534045a5080abba0a922f804022cd59b79aef73db236b4d8c77922e3&token=2042355911&lang=zh_CN&scene=21#wechat_redirect
[Redis]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247485316&idx=1&sn=0e9977c178b29f8f71405d29d8d2aa35&chksm=ebd74685dca0cf9356183ab6571bd15860c0fc80b4c1fcf19aa9b799d28a4c4c58976a8651ba&token=2042355911&lang=zh_CN&scene=21#wechat_redirect
[640_wx_fmt_jpeg]: /images/20210827/c440259d6507470db26c46688ddb2d3b.png?wx_fmt=jpeg
[640_wx_fmt_png]: https://ss.csdn.net/p?https://mmbiz.qpic.cn/mmbiz_png/iaIdQfEric9TxAghDEtyL0yGWb5bwkkbojspAFsIK81p9GbZ7ibpE1PM7HSBxvSm0BjwYa4v6JIlMIhYMMEDeOdUg/640?wx_fmt=png
[640_wx_fmt_png 1]: /images/20210827/12f9ed1c69a141faa154f29c4101d2b6.png?wx_fmt=png