杭州双非渣硕。前段时间师兄内推雷火,没有笔试直接打电话约我去面试了,地点在网易大厦。早上不到七点起床,晚上七点多才回到宿舍,可以说是很疲惫了。
本来面试现场投影上写的上午三轮交叉面,如果通过的话下午一轮总监面一轮hr面。 结果我上午三面完了之后,下午又给我来了四轮面试,没有总监面和hr面,所以一共7轮技术面(第一次参加面试就这场面,吃不消吃不消),还好都是1v1的形式。
因为对第一轮面试印象深刻一点,就单独说一下,其他六轮题目我可能搞混,索性后边直接一起列出来了。
一面:面试官很年轻,看样子就比我大几岁,感觉技术很强,有种邻家大哥哥的感觉。。。
一开始让自我介绍;(有没有问我项目记不清了,反正后边几面也有问到)。然后给我一张纸,让我把知道的排序方法都写下来,(我写了六七种吧记不清了,主流的都写了,包括希尔排序 桶排序),然后让我把他们的实现方法都介绍一下,然后时间复杂度 空间复杂度都写一下,把他们是否稳定都写一下;你了解的最复杂的数据结构是什么?(我一开始说的散列表,问我有没有更复杂的,我说各种树,红黑树,B+树,B树,平衡树等等)问我这些可能都是本科时候学的,现在还记得起来么?(能记得大概,具体的左旋右旋可能细节想不起来);ps:其实我还是能说出来一点的,但是当时怂了怕让写出来就gg了;两个平衡二叉树合并怎么做?(一开始以为就是简单的比较大小+递归,后来发现好像还得满足高度的特性,就先说了平衡二叉树的特点,然后想了一小会,面试官说不会也没关系,恩不会);(4.9日修改:今天才发现平衡二叉树其实只要求高度差不大于1,并不要求左子树比根小,右子树比根大... 有这种要求的是红黑树。我记错了! 这样的话 合并两颗平衡二叉树其实就是层序遍历吧,唉当时要是没记错就可以撸出来 了。。。)
现在有100W个账户密码,要存起来,要求查找时速度尽可能快,你选择什么数据结构?(B+树);
为什么?(我简单扯了扯B+树的特性);
说一下要往里插入、删除、查找账户密码的复杂度。(我不太确定,瞎猜的:nlogn,nlogn,logn);对图论算法了解多少?(BFS,DFS,最短路径,最小生成树,最小割最大流...)平常有用过吗?(项目里用过DFS BFS);好,现在给你道题,一个二维坐标系,给你n个点的坐标,画一条直线把他们分成两份(任意直线),要求数量尽量等分,复杂度不能太高。
(刚说完图就出这道题,我下意识觉得考察我图论,想了一下感觉不是的,然后给他讲了讲我的思路:假设按照y坐标分,那么遍历n个坐标,用一个最大堆来保存,然后从顶部弹出n/2次,如果当前顶部的数和最后弹出的数不一样,就可以在中间画一条线);
他说如果所有点纵坐标都一样呢?如果有点重合的呢?
(我有点蒙蔽了,觉得我这思路是错的,又想了几分钟其他的方法,又不由自主往图论上想,最后还是没想起来。其实貌似再同样做法对横坐标处理一次应该可以避免他说的问题吧),最后问他怎么做,他说用二分的思想,然后对横纵坐标求中位数、众数什么的,我也没太听懂,装模作样点了点头;玩过哪些游戏?(说了一大堆)对哪个比较熟?(LOL) 现在让我对亚索的e做测试,怎么测?(我吧啦吧啦一大堆把能想到的都说的,ps:这里之前问过师兄经验,要有条理,用树状图来测,先分成几大类,再慢慢细分之类的)。但最后面试官又提醒我e技能带不带普通攻击,会不会触发装备特效?(这点确实没想到,但也是提醒了我,后边几轮面试也有问测技能的,我就把这一点都说上去了)。问我亚索的e在一小段时间内是不能对同一目标使用的,怎么测?(简单说了一下) 你觉得不能对一个目标释放e的判断是怎么实现的(我一开始说面向对象,对每个单位对象设置时间标记之类的。后来他说不是面向对象,提醒我是buff还是什么,我说是buff);在e的瞬间敌方回城了你觉得应该被带到泉水吗?(不应该)。
那dota里白牛的大招会不会?(会。ps:因为我也玩过dota);
你觉得是为什么?(可能在代码实现上白牛的大招是在大招释放完毕后出现在目标的身后); 那亚索怎么避免这样?(可以在释放技能时根据目标和自己的位置关系计算出技能释放后的位置,而不是以释放后的目标位置为参照物);
你觉得这样可以解决吗?(可以);讨论bug和外挂的问题:面试官小声嘀咕+心算“你现在研二...dota高中玩的....恩应该是6.72版本”。
(我内心:???卧槽! 这都能算出来)。说一下你当时玩dota的时候发现的bug。
(我内心:???dota做得这么好,哪里有bug啊。 想了一会说 确实没发现);当时某种情况下蝙蝠开大招的时候可以A自己的塔,是最出名的bug。
(我内心:??? 还有这种事? 我怎么不知道)说一下dota 的外挂吧。
(??还有外挂? 哦对 开图挂)那你知道原理是什么吗?
(我内心:???卧槽 我说我不知道开图的效果是怎样的,所以不好说原理,是整个地图战争迷雾都没了吗?还是只对英雄有记号?)显然面试小哥也没开过全图不知道效果 那你说说LOL的外挂吧。
(??lol还有外挂? 我赶快扯开 我还玩过穿越火线,那个外挂特别多)都有什么你说说看。
(显示幽灵,透视,穿墙,自动瞄准,飞天 入地。。。)那你知道原理吗?
(我内心:??卧槽 到底还是没躲过 我说曾经幽灵模式刚出来的时候,可以通过删除安装目录下的一个文件,来使幽灵的刀子显形,而且我也确实试过是可以的)面试官点点头 算是混过去了;可能还有暂时想不起来了...有什么要问我的么?(问了一下我理解的防护就是测开,需要对做抵御外挂的工作吗?) 也要做的,这个东西不想做也避免不了。 结束。
其余六面:
除了最后一面面试官觉得我已经比较累了,其余的都要自我介绍;项目被问了好几次,包括具体实现,项目主要解决的问题,从项目中学到的最好的技术,项目经验对做我们这个岗位的好处(因为我的项目就是可靠性自动化测试) 等等;很多测试场景题,包括测技能,测英雄,登录窗口等等,问你怎么测;概率题:
两盒火柴每盒n根,每次随机从任意盒取出一根, 求当一个盒子被取完时,另一个盒子刚好还剩r根的概率。
(有点紧张有点懵逼,最后答错了,但还是讲了一下思路写了一下我的公式虽然可能是错的但总归没放弃抵抗~) ;
智力题:
两个盲人各买了一白一黑两双袜子,不小心弄混了,问他们自己怎么分成刚好每人一白一黑。(之前见到过,稍微想了一下就答上来了。但是先入为主是我理解的那样了,面试官问我为什么觉得袜子都是一样大的,不可以用手区分开?当然实际上我问的话 她肯定说是一样大的 只凭手感摸不出来~);一个圆桌,两个人往上放硬币,只能平铺不能重合,最后一个放的人胜利(接下来硬币无处可放了),问先放的赢还是后放的赢。
(初中就见过的题,直接跟他说这题我做过,然后讲了一下秒杀之);
测试知识题:
说一下了解的测试方法;性能测试有哪些指标;比如对一个登录功能做性能测试,有哪些指标?(响应时间,可同时处理的最大请求数量...) 怎么测出可同时处理的最大请求数量? (秒答 二分)面试官会心一笑 “恩 二分 没问题” ;用什么做的单元测试(junit);有没有做过压力测试(没有);面试官看到我的项目里有提到流程图,于是问了以下题目:任务流程图,是串行的,比如跟一个个NPC对话,但是有可能有的玩家提前跟某个NPC对话,导致后边的任务出不来了,这种情况下怎么测?(把串行的所有任务全排列)。如果当任务太多了会怎样?(那测试用例数量要爆炸了)怎么优化?(想了一会想不出来,硬憋一下 问能不能用 堆排序的思想,先两两颠倒顺序测试,把已测试过的当成一组再两两测,这样测试用例应该减少很多)。面试官还不太满意,让从游戏的角度来说,(我实在不太会,又说根据重要程度,比如正常的流程肯定是最重要的,然后根据日志,玩家走得比较多的流程 来排序,重要度高的分配更多测试资源)。最后面试官说他们现在就遇到了这个问题,然后讲了下他的思路;还有很多,一时想不起来了;java基础:
protected,public,private的区别(面试官说我protected说的不太对);抽象类和接口的区别;static的作用;List和ArrayList的区别;int和Integer的区别;全局变量,临时变量,静态变量分别存在哪里;c++和java 的区别;java内存里有什么(结构);说说垃圾回收机制(忘得差不多了,加上知道自己已经忘得差不多了更加紧张, 就把能想起来的随便说了说);怎么判断哪些对象是可以删除的? 可达是什么意思?接口有什么限制;可能还有一些,暂时想起来这么多;数据结构:
讲一下你知道的数据结构;有一些数,每次可以插入,或者取出第1/4大的数,用什么数据结构?(我回答:维护当前数据量1/4大小的 最小堆,插入时被挤出来的数用最大堆保存,取操作从最小堆顶部取,然后把最大堆顶部取出插入最小堆。 瞎说的不知道对不对 不过看面试官当时的态度反馈 应该还算满意);数组和链表的区别;BST的特点;应该还有,记不清了;
算法题:
求a和b的最大公约数;(讲思路,一开始想的是用最小的数往下递减,每次判断另一个数能不能被整除;刚说完就优化了一下,改成不是每次递减,而是用除以2,除以3...这样找。 我知道好像有公式还是什么的...但我真的想不起来了);字符串转int类型,要求不能用已有的方法,也不能强转。
问了下其他的要求,比如+-号之类的,还有不是数字的字符返回error等。还问了如果超过int最大值怎么办,他问int最大值是多少(214..什么的,具体不知道..我平常都直接用的Integer.MAX_VALUE),好吧 这样也行算你过了。
(ok,纸上手撕,用的 str.charAt(index)- '0'做的,但最后还是16进制标记0x没有考虑到);求x的n次方,已知可以用n*(n-1)!来做,但有没有更好的方法。
(ok,纸上手撕,前两天刚好看到了, 先对x,n判断是否是负数,0之类的, 然后把n转成2进制,通过&1和右移来做);给一个二叉树,怎么得到这颗树的镜像。(简单题目, 讲了下思路,递归,左右对称就好了);01背包
(ok,纸上手撕,dp,很久没写了对这个不太熟,一开始用的一维来写的发现错了,后来改成二维写出来了);给一颗树,判断是不是BST。
(ok,纸上手撕,用的递归,方法里有max和min两个约束,不符合直接返回false,初始是Integer.MAX_VALUE和Integer.MIN_VALUE往左递归时更新max,往右递归时更新min。)
面试官自己在纸上画了画,表示第一次见到我这种方法,但好像也没啥毛病,恩没毛病~;说两个nlogn复杂度的排序方法,衡量算法的三个维度?快排是稳定的吗?快排基准点怎么选择?
(这已经是第六面了,我一直以为稳定是指复杂度的稳定,结果经面试官提醒才知道理解错了... 这样想起来一面时候让写的稳不稳定怕是也错了);印象中还有让讲思路的题目,但实在想不起来题目了。
算法总结:
纸上手写还是跟平常自己做的时候感觉不一样的,自己太急了,没仔细想好就开始写,导致写错的要划掉很难看,还有写完了没有检查代码,一些特殊情况也没太多考虑。 主要是面试官在旁边,不好意思让他一直等着,就老想赶快写完得了。还好面试官挺好的,不是很苛刻,不然小细节能怼死我。