【游戏开发面经汇总】- 算法编程篇
这是一篇鸽了很久的文章，也是这个面经系列的第三篇文章-算法编程篇。掐指一算，距离上一篇文章发表已经时隔几个月了，这几个月发生了一些事情，让我难以有表情和精力去继续进行写作（可能也是心态发生了变化，变懒了）。不外我如今总算是有了时间，写作欲望也再度燃起。当下整个互联网范围包罗游戏行业的形势都不太好，但我想，仍然还是会有无数热爱游戏开发的少年坚定地想要进入这个行业，所以我但愿我的这些文章能给他们带来一些辅佐。这篇文章将由三个部门组成，分袂是总体概述，筹备策略，以及我按照本身和同学们几十次的面试经历汇总而来的真题合集。当真看完这篇文章，你必定会有所收获。
一、总体概述
1.1 考察意义
首先需要说明一下算法编程在面试中的地位，以及考察的侧重点。我在之前的文章说过，在游戏开发的面试中考察的常识主要可以分为四点：计算机基础常识、图形学常识、算法和编程能力，以及实际的项目经验。当然，这四者不是完全独立的，也有很多是相辅相成的，往往也会一起综合考察。此中的算法和编程能力部门，是对于实践动手能力要求最高的，往往需要我们现场直接做题，也就是我们常说的“手撕代码”。
为什么要考察这部门呢？我想大师也很容易能想出来，无论是计算机基础常识，图形学常识又或者是项目经验，在面试中很多时候都是凭”嘴”说出来的，空口无凭，有些人完全可以吹得天花乱坠，把本身包装得非常优秀，面试官也未必能够分辩出真伪。而且实际上这些问题的考察，有一部门确实是可以浑水摸鱼的（当然越有经验的面试官越不容易被糊弄过去，尤其是像技术总监这样的，几乎不成能），所以也有人靠着背一口顺溜的陈腔滥调文斩下无数offer。为了避免这种面试时夸夸其谈，但是到了实际工作中却一窍不通，一行代码都写不出来的现象，面试官必需要通过必然的手段来保证，招聘进来的人中不会存在这种只会纸上谈兵和浑水摸鱼的南郭先生。法式员傍边有一句很经典的话：”talk is cheap，show me the code”，就是实干精神最真实的写照，这也可以解释为什么很多公司，可以说大部门公司的面试中都要包含算法编程这一个过程。
其实算法编程题，不仅仅是游戏开发中需要考察的常识，而是几乎所有法式开发岗位城市考察的内容，所以，这篇文章不仅仅针对于游戏开发有用，对于所有技术开发岗位都是有参考价值的。
1.2 考察题型和形式
其次需要再重点说明一下考察的题型和形式。考察题型，主要包含两大类，除了我们常见的LeetCode那类的算法题之外，还包含一种方向实际开发工作中会遇到的工程题，概略就是面试官会描述一个具体的场景和需求，让你去实现一个方案去满足这个情景下的需求，这类标题问题我在文章中的第三部门会举例说明。
此外，本篇文章中所描述的算法编程题，主要指的是面试过程考察的算法编程题，并不包含笔试中的标题问题。笔试相对于面试中考察的标题问题，题量更大，也更复杂，往往都需要AC，也就是通过机器测试。当然筹备策略是一样的，只是说一般笔试考察的复杂度和严格度都要比面试要高而已。我个人并没有参加过很多次笔试，所以就不专门介绍了。我在这里也保举大师如果筹备充实的话优先投提前批，很多公司的提前批是不需要参加笔试的。
考察的形式，最常见的一种就是通过牛客网进行，因为牛客网具备长途和共享屏幕的功能，常常成为很多互联网公司长途面试的第一选择。也可能还因为牛客网自身就具备很多题库，有些标题问题是直接从题库中提取的。
在牛客网长进行的考察，页面上会有一块IDE区域，页面旁边可能会有标题问题的描述，如果有标题问题，那么IDE区域里面一般会提供对应的类定义、函数声明等（见下图），也有可能这个标题问题是由面试官口头描述的，那么界面上就不会有标题问题描述，也不会有函数的声明，只会有一个赤裸裸的main函数。
在面试中考察的算法编程题，绝大部门情况下都不需要AC（至少我是没遇到过），甚至都不需要编译运行成功。只需要让面试官看到你写的代码是否正确就行，但面试官可能会需要你解释清楚你这些代码的含义。
另一种形式，面试官同样会现场出题，但是是允许你用本身的IDE去实现，其实除了IDE以外，考察方式跟上面的差不多。反正只要是个可以写代码展示的处所就行，你要不介意，用windows自带的记事本都行。因为这些年由于疫情的原因，大部门的面试都是线长进行，如果是线下进行，可能还会有“白板编程”，也就是在白板，或者是纸上手写代码or伪代码，这种方式应该才更接近于我们常说的“手撕代码”，我猜测外企中这种考察形式斗劲多，但是因为我没有参加过外企的面试，所以就不妄下结论了。
最后还有一种考察形式，标题问题一样出，但是不要求你写出来，只要口头描述出来就行了。其实这种打嘴炮的方式压力最小，只要本身有必然的算法基础，多多少少可以说出一些东西。此外，有一些工程题，是没有尺度答案的，也不太可能现场就写出一个解决方案，面试官此时就会通过这种口头回答的形式，去考察你的开放性思维，看看能不能提供一些有价值的解决思路。这一块的考察，其实一半可以算作是算法编程部门，一部门也可以算作项目经验部门，因为没有必然的项目经验堆集，是很难一下子回答上来的。但是口头描述也会存在描述不清楚的可能，所以如果有必要，可以主动提出写出代码来暗示，就像我上面引用的那句话一样，Coding他丫的就完事了，说不定还会让面试官对你高看一眼，感觉你不是一个只会纸上谈兵的人，我有一轮面试的时候就遇到了这样的情况。
下面我按照本身的个人经验，列举一下在实际的求职过程中，各家公司习惯的考察形式：
（1）字节跳动和网易这两家公司一般是采用牛客网的形式，而腾讯和华为这两家公司一般会采纳自备IDE的形式；
（2）字节跳动和华为这两家公司对于算法编程题的要求是斗劲高，也斗劲严的。字节的每一轮面试，开门见山必是一道算法编程题，而华为在笔试阶段需要在3个小时的时间内做出4道算法大题（如果我没记错的话)，采用牛客网的形式，需要AC。而第一轮面试的开始，华为也会例行公事般地要求写一道算法题。除了国内的互联网公司之外，像微软谷歌这种外企，想必对于算法编程能力的要求就更高了，据说谷歌更是达到了反常的水准；
（3）网易这家公司，至少会有一轮面试需要在牛客网上手写代码，其余几轮可能会通过口头问答的形式来考察一些算法编程题；
（4）腾讯斗劲佛系，有些面试官不喜欢考察就不考察，有些面试官开局会直接甩你两道题做，然后告诉你他过一个小时过来验收（说的就是北极光，第一次遇到的时候吓尿了，好难！），也有面试官会出一道具体的工程题让你用本身的IDE做，给你提供具体的函数声明，然后让你去实现它。
还有一点是大师可能斗劲关心的就是标题问题的难度程度，其实这些年有一个斗劲常见的说法就是，LeetCode上的Medium难度级别，我认为是斗劲靠谱的。
1.3 注意事项
最后说一下面试中的注意事项，算法编程题，考察的不仅是你的算法和编程能力，也有考察你解决问题的能力。因为我们不成能所有的算法题都见过（当然我们的方针就是要涵盖所有常见的算法题），当你面临一个没有见过的问题，你如何按照现有的常识去找到一个可行的解决法子，这也是面试官非常重视的。所以，当你面临一个不熟悉的问题的时候，千万不要直接说我不会做，而是要竭尽所能地去找到一个可行的方式，甚至逐渐逼近最优解。你需要在这个过程中不竭和面试官保持沟通，甚至旁敲侧击地试探这个标的目的是否可行。你甚至可以直接告诉面试官，需要给你一点时间思考，慢慢想。在实际的工作中，我们会遇到很多问题，这些问题并不必然有现成的答案，需要我们一步一步去解决，所以面试中非常忌讳一遇到不熟悉的问题就说我不会。你再怎么瞎扯，也得给我找到一个不那么离谱的答案。
我记得我在第一次实习面试的时候，跟面试官掰扯一道算法题，扯了三四十分钟，最后面了超过一个小时，拖得太久了面试官才宣告结束的。那道题是一道STL的经典算法，我当时仍然没有能找到最佳的解法，但是至少也提供了一个可行的方式，虽然时间复杂度较高，以及我说到后面已经不知道我这个方式到底特么到底行不行得通了，但我一直没有放弃，不管对不合错误把我能想到的都说了，也许面试官也是看到了我的这点对峙，当初才让我通过了面试吧。
二、筹备策略
这些年在筹备算法题的时候，我也查阅了很多资料，参考了很多前人的经验。此中推崇得斗劲多的网站和资料有：《LeetCode》、《牛客网》、《剑指Offer》，还有各种面试宝典、面试指南等。
《剑指Offer》我本身看过，但其实我不是很保举，因为上面的很多写法都是偏老旧的C风格，没有操作现成的STL尺度库的容器和算法，很大都据布局都是裸写，各种指针满天飞。不外也要承认，这本书上的很多算法思想和工程经验，都是有参考价值的，所以如果要看这本书，我保举仅仅是“看”就行了，没必要刷它上面的题，以及按照它的写法去筹备面试。
翻了一下之前的笔记，发现当时本身的法子是，针对每一个题解，用本身的语言简单归纳算法的核心思想，这样可能斗劲便利理解和记忆，大师也可以测验考试一下是否对本身有用：
（不外当我在写完这篇文章之后发现，确实有很多真题是能够在《剑指Offer》里面找到的，所以它还是挺有价值的，只是这些真题，同样大部门也能在LeetCode找到，所以，大师按照本身的时间情况选择吧，有空的话还是可以过一遍这本书）
其实在筹备算法这一块，我只有一句话，LeetCode永远滴神，我认为真的没必要看太多的网站或者参考资料，大道至简，选择一个标的目的一顿怼就完事了。为什么强推LeetCode呢，因为上面也说了，面试中考察的题型和难度，长短常接近LeetCode的Medium题的，而且里面的很多题型，也是在实际的面试中呈现了很多次。
至于牛客网，我认为它算是面试求职资料的一个大汇总，刷题当然也不差，但是我可能更喜欢用它的面经汇总和模拟面试功能。
下面我列一下斗劲有用的参考资料，以及筹备的方式：
（1）LeetCode按照怎样的挨次来刷题斗劲好？ - 知乎 (zhihu.com)
这一篇参考资料其实已经写得很好了，这里再简单说一下我的经验。总结来说，如果你时间丰裕，可以按类别来刷，比如链表、数组、二叉树、DP等，这样可以强化对于此类题型的记忆，刷多了就得心应手了。如果你时间不多，急仓猝忙秋招就筹备要开始了，那么我也十分保举你去刷LeetCode的 “hot 100” 标题问题，里面收集了最热门的100道题，这些标题问题的命中率是相当高的，必刷！！ 力扣 (leetcode-cn.com)
（2）GitHub - MisterBooo/LeetCodeAnimation: Demonstrate all the questions on LeetCode in the form of animation.（用动画的形式呈现解LeetCode标题问题的思路）
这是一个以动画形式来讲解LeetCode解题思路的仓库，非常有助于我们可以形象地舆解算法道理，同样强力保举。
（3）leetcode channel - 专注北美算法面试 - CSON (cspiration.com)
最后一个资料，则是有大神已经帮我们按照类别归纳总结了，如果要按照题型来刷，跟着这个列表刷题即可。
最后我在说一下我本身的经验。我在参加秋招之前，刷题量其实不算很多。在备战研究生复试期间，我们学校有个刷题网站PTA，我在上面刷了概略200道题（实际题量可能100多点，很多是反复刷了两次，而且还有一部门是简单题），然后花时间看了一遍《剑指Offer》，也照着里面的写法“抄”了一些标题问题，这个过程相当于我是在加深对于这个标题问题的印象，但是后面看来仿佛没什么用，后期我更是直接就不看了。后来我就在每天尝试室打杂的生活中抽出一点时间去刷LeetCode，非周末的情况下可能一天也就刷个一两道题，当不时间实在是太紧了，看完剑指Offer仿佛都五六月份，没多少时间了。所以我的策略也如上面所说的，我只刷 ”Hot 100” 里面的题，刷着刷着就到了面试的时候，100道题也没刷完。但是我诧异地发现，面试中大部门标题问题我都可以做出来。后来开始面试之后刷题速度也放慢了些。直到8月底，我结束秋招提前批的时候，我诧异地发现，在面试中遇到的90%的标题问题我应该都已经做出来了，而此时我在LeetCode刷题量，仅仅还是逗留在第一页的50道题摆布。
所以我想大师应该可以大白，我为什么称之为永远滴神了吧。
最后还想说的一些个人想法是，算法这块，最重要的不是纯挚地追求刷题量，而是要真正掌握标题问题后面的算法思想，做到触类旁通。因为标题问题是灵活多变的，你想要在面试中遇到的都是完全一致的标题问题，那不太可能（个别题是会呈现，但总会有没见过的），但是无论什么标题问题，它背后都有着核心的算法思想，比如贪心算法、空间换时间、DFS、动态规划等等都是一致的，而且有些标题问题，也是一题多解的，只要你熟练掌握了此中一种算法，你就可以解出来。正如这篇“武功秘籍”的名字所言——“万剑归宗”：万变不离其宗，无论是什么样的标题问题，其背后必定对应一个核心的算法点，只要你是真正掌握了这个算法，必然可以迎刃而解。
在面试中的算法编程题，我认为“熟练度”的重要性大于你的“逻辑能力”或者说“智商”的，因为在面试过程中短短的十几二十分钟时间，你是很难通过你的逻辑能力去推导出一道你完全没有见过（或者看不穿它背后考察的算法）的标题问题的解法。一般一眼你看过去，知道背后考察的是什么要点，基本上就很快能写出来，如果你看了几分钟还是看不出来任何一种背后的算法，那你概略率也是做不出来的了。引用一句老话——“无他，唯手熟尔”。所以，多刷题，多思考。
三、真题合集
最后，可能也是最有用的部门，真题合集来了。这是我按照本身数十次的面试经历，和一些同学们的面经，综合汇总出来的一系列面试真题，但愿看到这里的同学们，都能够当真仔细地掌握这些标题问题。等到某一天大师如果面试中遇到了这些标题问题，请记得回来给我点个赞哟。
真题合集分为两类，算法题和工程题，这里补充一点算法题其实应该指的是“数据布局和算法”题，因为算法往往会和数据布局一起考察，所以数据布局的标题问题考察也放在这个范围，此外关于数据布局的一些问题，在我的第一篇面经文章中也多有提及，可以互为补充（写完之后发现好多都反复了）。至于工程题，其实随机性斗劲大，除了一些常见的基础题型，还有一些可能是面试官本身本身在工作中会遇到的一些问题，想考察你的开放性思维，所以这些标题问题很可能网上是没有尺度答案的，我也不必然能给出一个非常正确的答案，这点就得靠大师本身努力啦。
在这个部门，我只会列出标题问题和对应的链接，并简单地说明解题思路和一些我的经验，不会给出详细的题解，有些标题问题如果没有题解的话，还需要大师阐扬主不雅观能动性，自行去搜寻和测验考试解答。因为有些标题问题年久掉修，我也忘记当时是怎么做的了，或者有些标题问题是来自其他同学的面经，我也没做过。此外，这类的文章我的原则都是要尽可能保证严谨性，但的确是精力有限，为避免后续久不久又会有伴侣说我表达有误，对于那些我不是很确定的问题，我就不给出答案了（狗头）。
标⭐的暗示是高频标题问题，⭐越多越高频，要么是在真正的面试中呈现了两次及以上的频率，要么是经常能在各种面经和网络资猜中看到的标题问题；为了区分标题问题和答案，标题问题我用加粗来标明。
3.1 算法题
[*]用栈来实现队列（⭐）
232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com) 这是一道十分经典也斗劲简单的标题问题，我直接上链接了，大师可以先自行实现，再看下面的题解（我给出的是标题问题的链接，题解在旁边，请自行点击查看）
[*]反转链表（⭐）
206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com) 直接看题解吧。
[*]判断一个链表是否有环（⭐⭐）
剑指 Offer II 022. 链表中环的入口节点 - 力扣（LeetCode） (leetcode-cn.com)，也是斗劲经典的标题问题，用快慢指针法可以斗劲好地解决这个问题。
[*]爬楼梯（⭐⭐）
70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)，应该就是斐波那契数列，可以用递归的法子，更好的应该是用DP的方式，逆向算出中间成果，避免递归。
[*]堆的道理、建堆的过程，最小(大)堆插入一个元素的过程（⭐⭐）
这是一道嘴炮题（只需要口头描述）+ 基础题，请去再翻一遍《数据布局》的课本，而且深刻理解、熟练背诵。感觉这道题应该放在《计算机基础篇》的，不外懒得搬过去了，想起来了就放在这吧。
[*]哈希表的道理，如何措置冲突，如何删除元素（⭐⭐⭐）
同上（请记住哈希表里面的删除可能并不是简单地直接删除掉）。
[*]合并持续区间（⭐⭐⭐）
56. 合并区间 - 力扣（LeetCode） (leetcode-cn.com)，类似的问法或标题问题：合并两个持续数组
[*]删除序列中的特定元素（⭐⭐⭐）
27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)，例如给定一个序列 {2，1，5，9，1，3，1} 中删除所有的1，用双指针法，也可以参考《STL源码分解》中的的Remove_if算法讲解，感觉是一个斗劲巧妙的算法。算了直接搬运我前面的面经：
[*]求一个无序序列中的前K大(小)个数（⭐⭐⭐）
剑指 Offer 40. 最小的k个数 - 力扣（LeetCode） (leetcode-cn.com) 类似的问法或标题问题：求一个无序序列中第K大(小)的数；
这个Top K算法，感觉已经说烂了，但的确是一个非常非常高频的问题，再次搬运我第一份面经的答案过来，一般是嘴炮题（但是似乎也有需要写出来的）
[*]给一个数组，里面给定一系列三角形的边长，问你如何求得此中三条边构成的最大三角形周长
这是我本身遇到的真题，应该就是做一个逆排序，然后挨次斗劲三条边是否满足三角形边长的条件（任意两条边大于第三条边），而且是不需要判断三次的，判断最小的两条边和最长那条边一次就行。
[*]给两个数，n，sum，后续给一个长度为n的数组，问你求数组中和为sum的组合数，不能有反复的组合
也是我本身遇到的真题，这应该是个背包问题，本身用的是排序+DFS；更快的做法应该是用动态规划。
[*]对只含有 {a, b, c} 三种元素的数组进行排序
[*]一个只有0和1的数组，可以将一个0变为1，求持续1的最长长度
[*]给定一个nums数组由一些非负整数组成，现需要将他们进行摆列并拼接，每个数不成拆分，使得最后的成果最大，返回值需要是string类型，否则可能会溢出
这个标题问题，依稀记得是一个全摆列的常识点，涉及到某个数学的定律，在PTA上似乎见过。
[*]有1、3、5元三种硬币，问组成m元有多少种方式
背包问题
[*]有n个硬币，已知一个是轻的给我一个天平，最少多少次找到
[*]求两条链表最长公共序列
[*]删除链表倒数第N个节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)
[*]二叉树前中后序遍历
太基础了，我都不好意思列出来，翻课本去吧。
[*]二叉搜索树的实现：查找、删除、插入
同上
[*]计算二叉树上中最长的持续路径
298. 二叉树最长持续序列 - 力扣（LeetCode） (leetcode-cn.com)
[*]给定一个二叉树, 找出这个二叉树中的一个子树, 使得子树节点最多且子树是一个二叉搜索树, 返回节点总数和子树根节点
[*]求二叉树指定层的节点数量
给定二叉树的根节点和一个整数，暗示第几层，求该层的节点数；这是一道我遇到的真题，当时我用了层序遍历的方式实现，后来面试官又问能不能用递归的方式实现，然后我又测验考试用递归的方式实现。总之这题去刷层序遍历的标题问题应该就可以搞定。
[*]判断一颗二叉树是否是平衡二叉树
110. 平衡二叉树 - 力扣（LeetCode） (leetcode-cn.com)
[*]括号匹配
面试题 08.09. 括号 - 力扣（LeetCode） (leetcode-cn.com)
[*]从一个母字符串找一个子字符串的头位置索引
[*]一个二维矩阵，横坐标和纵坐标分袂为一个字符串，构成一个矩阵，设一个位置(x,y)，如果s1 == s2可以从当前位置走到右下角，如果不等则只能选择往右或者往下，求从矩阵左上角走到右下角最短路径
这道题是其他同学上的面经摘录的，感觉标题问题描述得不是很直不雅观，不外考察得常规得dp，做相关的标题问题应该会遇到
[*]给定一根横轴，上面随机分布着n个点，每个点的位置、速度是随机的，但是点的标的目的只能向左或者向右，如果两个点相遇就会碰撞消掉，假设有解的情况下，求最后一对点碰撞消掉的时间是多少？
这也是我遇到的一个真题，考察的应该是贪心算法。
[*]实现快速排序
图解快速排序（C++实现）_MagnumLu的博客-CSDN博客_c++快速排序，经典算法问题，我随手搜一个链接吧，记得当时学的时候有什么挖坑法、填坑法，应该是斗劲容易理解的实现方式。
[*]LRU cache
146. LRU 缓存 - 力扣（LeetCode） (leetcode-cn.com)，当时刷题的时候看到这题，想着没有谁会那么反常和无聊出这道标题问题吧！？没想到还真呈现了，在我同学中发现了两个案例（捂脸），有精力的还是刷几遍吧。
3.2 工程题
[*]实现一个单例模式（⭐⭐）
其实这道题，算是工程题里面考察的斗劲高频的一道，大师必然要掌握。继续搬运：C++ 单例模式 - 知乎 (zhihu.com)
[*]实现Shared_Ptr（⭐）
这道题其实也斗劲经典，看过《C++ Primer》的同学，而且本身真正当真完成过作业的同学城市感觉No Problem（当真去学习智能指针那章吧），面试官甚至会问得很细，构造函数、拷贝构造函数和赋值运算符具体怎么实现，移动构造和移动赋值运算符需要实现吗之类的问题，算了，继续搬运吧：
[*]实现一个按时器（⭐）
这道题要考察采用什么数据布局以及实现思路。具体的标题问题描述我已经不太记得了，但是这个问题确实呈现过几次，有记得的伴侣可以补充一下。我只依稀记得这道题的答案是使用最小堆，存放的元素是时间点。
[*]实现Memcopy函数
随便找个链接，memcpy实现及其优化 - 简书 (jianshu.com)
[*]实现一个对象池
某工作室常年的面试题，有备无患，请掌握它 对象池--C++对象池的实现_979797的博客-CSDN博客
[*]实现排名系统
如果有很大的数据量，如何获得排名前一百名的数据（游戏排行榜问题），如何求出一个玩家的分数在处事器内的排名百分比；排名系统，全球的数据，怎么设置排名系统，用什么数据布局，插入、改削、查询的复杂度是多少？
[*]实现俄罗斯方块游戏
如何设计一个俄罗斯方块游戏的系统，有哪些类，成员和函数是什么，如何实现？这个是线下面试时遇到的一个标题问题，只需说一下你筹算设计哪些类，完成什么样的功能，概略如何实现，不需要写出代码。
[*]实现战斗/技能系统
如果让你实现一个RPG游戏的战斗/技能系统，你筹算怎么实现？同上，概略描述一下本身的实现思路即可。
[*]实现照片分类的功能
这是我遇到的一个真题。需求概略是，有一组照片，需要按照页来显示，每页显示固定数量的照片。照片分为彩色和灰色，而且每张照片具有一个path字段，暗示照片的路径。然后让你实现一个方式 vector GetPhotoPathByPage(const vector& photos, int page,int photo_count_per_page, bool only_show_gray_photo)，打印出指定页的照片路径，存放在一个vector中返回。
参数说明：photos是所有照片的调集，page是指定的第几页，每一页的照片数量是photo_count_per_page。需要注意一点，only_show_gray_photo如果是true，暗示只打印灰色照片，如果为false则不用管照片是彩色还是灰色；这道题还有一个重要条件，只能用一个for循环来完成。
这道题纯粹是实际开发工作中会遇到的需求，也是典型的游戏客户端开发的需求，很考察实际的代码能力和工程经验，应该不难，如果有充沛的时间应该大部门都可以顺利完成，但是难的应该是现场考察的情况下，一般会斗劲紧张，第一次看到一个陌生的需求，如何又快又好地写出代码，我想还是没那么容易的。
[*]一个双层For循环，采用列主序的方式遍历，问你如何改良这段代码，让它运行得更快，以及为什么？
这题其实考察了斗劲底层的计算机常识，说的是一个缓存命中的问题，列主序的遍历方式缓存命中率会更低，因此会导致更低的效率 Cache的基本道理 - 知乎 (zhihu.com)
[*]哈希表扩容的卡顿优化
我们都知道哈希表，那么哈希表满的时候要扩容，如果此刻有100W个数据，哈希表不够用了，要进行rehash，这个时候会造成顿卡，问怎么解决这个顿卡的问题？这也是一个典型的面试官在实际开发工作中遇到的问题，想看看求职者中有没有小聪明可以给出扶植性的答案，这是一个开放性问题，各种想法都可以说，考发散思维，如果回答得好应该会让面试官刮目相看。我也忘记当时我是怎么回答的了，反正应该是给出了本身能想到的各种解决思路，多少能挨到一点边吧。
[*]在地图上，给定一个圆的区域，想要在这个圆上投放100只怪物，如何实现能够使得这些怪物在圆里面均匀地随机分布？
也是我遇到的一个真题，感觉考察的是数学常识，解析几何和概率论之类的，当时我仿佛是想出了什么面积法，把一个圆像蛋糕一样纵向切分，再按照半径大小由内向外切分，尽可能划分成不异面积大小的区域，之类的。
[*]给一张图，有仇敌、墙、空地，炸弹能放在空地上，炸该行该列没被墙盖住的仇敌，问给一个炸弹最多能炸多少仇敌？
[*]实现刀兵对人击打分歧部位，造成分歧伤害？
[*]如何实现仇敌发现你，知道仇敌的视野范围，然后要考虑你人的半径，抽象成二维的（看到边缘也算看到）
[*]一个随机数生成器，52张扑克牌，怎么发给四个人，保证随机？
[*]游戏怎么快速查找在一块区域里面的对象？
[*]AI寻路 A*算法？
【寻路】A星算法浅析 - 知乎 (zhihu.com)
页:
[1]