字节跳动--朝夕光年客户端开发实习生一面凉经

人生中第一次找实习，本来投的是西瓜视频测开方向，但是笔试就g了，本来已经不抱希望，但是没过几天朝夕光年捞我了，并且说不用笔试直接面试。欣喜之余又暗暗担心，毕竟我知道我这两把刷子根本不够用----果不其然，今天在面试官那支支吾吾了一个小时，当晚6点就收到了拒信。但是没关系，知己之短，难能可贵；总结经验，收拾好心情，再出发！

下面是面试官问我的问题，希望能帮到大家：

1. 没有自我介绍，上来直接分析我的项目：“可以介绍一下你的大创项目吗”：用pygame做的攻防游戏

“我看里面用了stack来优化数据结构，为什么用stack而不用其他数据结构？”：可以使用其他数据结构比如hashmap，stack只是方面优先攻击最新产生的目标

“你觉得PriorityQueue可以吗？它和FIFO队列有什么区别呢”：这块我上来就回答错了，说priorityqueue是基于链表，其实原理是二叉堆

“那你觉得它增删的时间复杂度是多少？”（面试官企图引导我发现问题）：其实是O(log n), 但是我完全不懂，直接答O(n), 还振振有词的扯到comparable

“那arraylist的增删的时间复杂度呢？”：（面试官还企图引导我回到正轨）：O(n) ,"那这样的话，数组和链表都是O(n)？"：突然发现自己的错误，想到大顶堆可以用priorityqueue实现，然后改正说priorityqueue其实是堆（到死都没想到二叉树）

2. ”好那我问你第二个项目“面试官发现我不简单，于是企图在别的方面启发我

“能说一下你的unity游戏做了哪些吗”：说刚开始做，只做了人物的连招，小地图的绘制（组里同学做的）

“你是怎么实现怪物掉血？”：对象池，每个子弹当成一个对象，每个子弹和怪物碰撞检测

“近战是怎么实现怪物掉血？”：不会了，说还是通过碰撞检测，给武器加碰撞检测。后面查了查，应该是动画关键帧回调 + 范围检测。

3. 面试官看完说不出啥了，就说那我们看看你第三个项目吧（java 2D射击类小游戏）

“上面你说了unity的碰撞检测，2D游戏里面是你的子弹是怎样和怪物碰撞检测的呢？”：计算子弹中心点和怪物中心点的距离，小于怪物半径则碰撞。

“但是这样做每次update都要执行碰撞检测，是不是性能会有所下降？”：是的，怪物一多就卡

“有没有想到什么方法可以优化”：支支吾吾半天没想到，后面查了一下，面试官想问我的是地图子格划分的方法或者光线投射法

4. 面试官见我这个也没说出来，遂问下一个项目：你的简历里有写实现通用图灵机

“说一说你对图灵机的理解”：还好是刚做的作业，答曰：模拟人们用纸笔进行数***算的过程，结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动head。

“他的变体是怎么实现的”：改rules table

“图灵机有一个经典问题，图灵机停机问题，了解过吗”：懵了，不会，后来查了查，是一个经典悖论，上课好像讲过（寄），停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，可以有一个程序判断其本身是否会停机并做出相反的行为。这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。

5. “你还记的操作系统里面经典的哲学家吃饭问题嘛”：上学期刚学的，说把两个叉子看成一个整体，同时拿起或放下，只通知饥饿的邻居

6. “那我们还是跳回算法部分吧”

“你之前提到过hashmap”，那么你觉得他的查询时间复杂度呢？：这个精心准备过，答：O(1)

"为什么是O(1)呢" ：其实是问底层的东西，答：hashmap是一个数组拉链，先根据key值算y所属类的hashCode方法计算出key的hash值，然后将hash值通过哈希函数计算出更加复杂的hash值，再将算出的hash值和数组长度进行&运算，获得当前put进来的数据要在Entry数组中存放的位置。然后就去数组上找这个位置，然后分情况讨论，hashcode相同的情况和不同的情况。

“你刚才提到了红黑树，能说一下红黑树是什么嘛”：非平衡的二叉搜索树

面试官看到我可能比较熟悉二叉树方面的知识（其实二叉树正是我的弱点，这波是自己给自己挖坑），于是考了一道算法题“10个球里面有一个球质量和另外9个不一样，如何找到这个球”：这时候已经懵了，瞎说一通

面试官给了提示，可以和二叉树联系起来嘛：不能

面试官进一步给提示：那我们直接写一个函数吧，判断是不是平衡二叉树：想到层序遍历，但是这时候已经完全懵了，连dps都忘了（gg）

面试官看我实在想不出来，说我才大三，还有时间努力（gg）

说实话感觉并不难（可能是一开始我连简单的问题都没回答上来），只是我比较笨，像层序遍历之前刷题的时候自己都直接做出来过。。。。。。归根到底还是自己基础知识太薄弱，今后要多重视基础，学跑得先学走，总之这次面试交了我很多，包括抗压能力。

面完在宿舍一蹶不振两个小时后又重新收拾心情，再度出发。

#实习##面经##Java##搞笑##游戏研发工程师#