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

发布时间:2024年01月08日

前言

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

面试岗位信息

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

笔试(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发送:没过。

文章来源:https://blog.csdn.net/Ws_Te47/article/details/135376360
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。