面试复盘6——后端开发——一面+二面面经——跨越两年的一场面试，可惜没有开门红

前言

本文主要用于个人复盘学习，因此为保障公平，所以本文不指出公司名，题目编号只是为了自己区别而已。对待面经，望读者还是更多从其中学习总结，而不是去碰原题。

面试岗位信息

游戏开发工程师，看样子应该就是后端了

笔试（12.12）

笔试的两个题目很简单，都是基础题，也没有过多说什么。都是可以直接两个for循环做出来的，自己考虑了一下优化再写了思路就完成了。
第一题采用了循环链表的方法。第二题则是用了双指针。
12日晚上做的，第二天上班时间就约面了，约到了14。

一面（12.14）

一面整体是从笔试入手的，先自我介绍，之后就是讲一下笔试的思路，随后问相关知识点。

第一题我用到了循环链表，便问到了我复杂度，并且探讨为什么不用vector，而要用链表实现。

问题1 ：在插入 删除操作时，为什么链表的复杂度比vector要低？

知识点导航——链表和顺序表对比。

每次执行完删除操作后，顺序表都需要移动其余所有元素，比如100个元素删除了第九个，那需要从10开始依次移动。但链表中，只需要第八个连接到第十个即可。

——————————————
第一题不是太在状态，这个简单的题目迷惑了半天没说清。但好歹答出来了关键点，因此进入了第二题。
第二题大概内容是两个数组，找出重复元素。并升序输出。
我采用的是双指针，但很显然 有序集合才是最优解。
面试官让我先讲了思路，随后再聊如何继续优化。
因此我想到了有序集合，求交集即可。

问题2：Set查找一个元素是否在其中的时间复杂度。Vector查找的复杂度。

问题3：如果让你实现一个Set，你会选择什么样的方法实现。

Set的底层是红黑树，红黑树的本质是一棵二叉搜索树。因此其可以在平衡的情况下保证查询、插入、删除的复杂度为log(n)。

Vector的底层是数组，查找的复杂度是O（1），插入删除的复杂度是O(n)。

问题4：二叉树翻转。

LeetCode-226

问题5：二分查找的流程。

LeetCode-704
复杂度： Log 2 n
具体证明见此

问题6：数学题1

箱子里面5个黑球3个白球，求取出一黑一白的概率。

C51*C31/C81即可

问题6：数学题2

玩家每天登录获得一个字，一共四个字。每个字的获取概率相同，求集齐的期望天数。
参考此文的题目2

总结

这家公司还是很考察数学功底的，技术方面只问了算法基础，其余就是数学，完全没有八股文。而且BOSS上面回复的第一句话就是“高考数学多少”…
在此奉劝各种学弟学妹，别对数学掉以轻心。

结果

第二天上班后hr发送：没过。