不知名双非渣渣的Unity客户端秋招笔试面试记录

---------------- 2023年9月2日多益网络笔试 ----------------

选择题

大部分是数据结构题，还有几道数据库，大概有10-15题。

• 给定哈希函数，哈希数组长度和数据，采用线性探测法，问你平均查找长度
• 问你常见排序算法的时间和空间复杂度，在某些情况下应该使用什么排序算法
• 给定一张连通图，节点n个，e条边，问你邻接矩阵非0元素至少有多少个
• 给定一张连通图，节点n个，e条边，问你邻接表dfs一次所有图，时间复杂度
• 给你一个序列，构建堆，问你某个节点在树的第几层
• 给你一个序列，构建小根堆，问你堆的中序遍历是什么
• 数据库是给你一条sql语句，问你什么意思
• 感觉这些题只要把牛客上的数据结构题全写几遍，基本上就没问题了，可惜我没写.....

填空题

记不太清了，好像是问了几个排序的题，

问答题

• 第一题英文翻译，翻译二叉搜索树和优先队列使用的存储结构比较
• 第二题让你写出两种排序的思路（题目直接标了“冒泡除外”，哈哈...）
• 第三题，给需求，写sql语句

编程题

有n个房间，每个房间有一些钥匙（数字）。你可以在任意房间前走动，但是你需要拥有改房间编号的钥匙才能打开房间，获取房间里的钥匙。刚开始时，你在0号房间，问你最后你可以打开所有的房间吗？

要求先写结题思路，再写代码

（吐槽一下，多益笔试是在战盟里写的，战盟的编译器是Cpp98，并且运行无法输入测试用例，只能自己在代码里写死测试用例）

案例一

room = { {1}, {2}, {0} }

0房间获得1房间钥匙开启1房间

1房间获得2房间钥匙开启2房间

2房间获得已有钥匙

至此，可以访问所有房间

输出：true

案例二

room = { {0,1}, {3,1}, {0}, {0} }

由于只能开启0，1，3号房间，2号房间无法开启

输出：false

我是用相当于dfs的方式写的，不一定对，刚开始存储0房间的钥匙，遍历钥匙能开启的房间，然后继续搜索这些房间里的钥匙能开启的房间，这样递归下去，如果这个房间之前就访问过，返回。外层应该还需要一层for，忘记自己写没写了.....

总结

考了很多数据结构和基础算法知识总体来说不是很难，如果你会考研数据结构或者牛客数据结构全写过几遍，那么这些题根本就是小case，可惜我比较菜，写的不多，基础有点差，写的不是太好，希望给个面试。