本篇用于记录面试过程中遇到的算法题和编程题。我在找实习过程中看了很多人的面经,学到了很多知识,很幸运能获得前人的经验,因此我也稍微留下一点点东西。八股、场景题我都不擅长,算法和编程题我还是回答得比较好的。介绍一下背景:西北农林科技大学本科,ACM EC银 regional 银淘天 客户端开发一面: 题面: 给一副牌,可能有重复,判断是否存在顺子。 做法: 桶排序去重,然后看是否有连续的5张牌,最后特判10 J Q K A。这样写复杂度是严格不超过牌数的。 现场情况: 我当时也写了上文提到的方法,没什么问题。字节 后端开发一面: 题面: 滑动窗口,给一个数组,长度为K的滑窗,求每个滑窗最大值。 做法: 很经典的题,我的写法是双端单调队列,队列一端控制窗口不越界,另一端控制队列里的数字均为有效。 举个例子,一对下标i,j(i<j),如果nums[j]>=nums[i],那么i就没有存在队列里的必要了,可以出队。 现场情况: 我写的就是上文的做法。然后面试官让分析了复杂度,这样做复杂度是O(n)的。 面试官问了一下有没有优化的空间。 我当时队列大小是数组长度,提出将队列换成双端队列,动态大小,这样额外空间不超过O(K)。 而且代码里我是单独处理了前K个元素,后来换了个写法,在一个for循环里处理完。非常建议大家记一点优化,可以不会具体怎么做,写的代码也可以非完美,但面试官问如何优化时要能说出点东西。具体优化思路:代码方面(冗余代码,太多if,变量名称,有没有好的方法写短点)时间方面(有没有复杂度更低的做法,不知道怎么优化可以指出当前代码复杂度瓶颈在哪,即哪一部分用的最多,可以直接诚恳地说不懂,但觉得这里可以优化)空间方面(是否使用了定长数组,尽量用多少空间开多少空间,能不能不用额外空间等等)字节 后端开发二面: 题: 给一个十进制数n,和一个包含若个1位数的数组,用数组中的数字组成小于n的最大数。 做法: 分情况讨论+贪心。 如果本题是不超过n,先看看不超过n怎么做,从高位往低位考虑。 每次从数组里选一个能填的最大值,如果某一位填的数字没有n上的数字大,那么后面的位均可以填最大数。 特殊处理最高位找不到合法数字的情况,假设n是x位数,这时候答案就是x-1个数组里的最大数。 特殊情况里还需要特判x=1的情况,这时候无解。 如果小于n,特殊情况是不变的,我们可以先按照不超过n的方法构造出一个解,如果此时解满足小于n,直接输出。 否则从低位往高位找到第一个可以填写小于n对应位数字的位置,如果有则修改该位,其余低位填上最大数。 如果找不到这样的位置,那就输出x-1个数组最大数。 现场情况: 我一开始没有考虑任何特殊情况,写完贪心之后自己出数据的时候想到了特殊情况,直接把代码推翻重写。 好在前面写得比较快,总共用了20分钟完成所有情况的讨论。 面试官问了我思路,并且让我说了一下复杂度,其实严谨复杂度就是O(10*log_10(n)) 然后解释了一下复杂度的含义,log_10(n)是n的位数,1位数数组大小不超过10,面试官表示没什么问题。字节 后端开发三面: 题1: 给一个字符串s,和一个字符串数组arr,问字符串能否由数组里的串组成。 做法: 动态规划,将arr里字符串存入哈希表,枚举s的每个子串去哈希表里找是否出现。 如果出现就用链表连一条子串头到子串尾的边。 设dp[i]表示s的前i个字符是否能被匹配,转移方程就是dp[i]转移到dp[j](j>i),当且仅当i+1到j有连边。 这样做复杂度是O(n^2 hash())的,这里hash()是和你选择的哈希表有关,我用的是C++的map,所以是log 现场情况: 我写的也是动态规划,但是判断串是否出现用了map。面试官问复杂度,这里直接说了n^2logm 其中n=len(s),m=arr.size(),面试官不太满意,问了一下优化。 我当时并没有特别严谨想过这个优化问题,我首先考虑的瓶颈是判断每个子串是否出现这部分。 给面试官说了这个瓶颈,表示认同。我说可以试试AC自动机优化这个匹配过程。面试官赞同。反问,回答用哈希。 题2: 设计一个数据结构,满足:①O(1)插入、修改、删除;②能够按照插入顺序遍历元素。 做法: 这里很明显每个元素有两个顺序,一个是结构顺序,一个是插入顺序。 开两个链表+哈希表分别表示两个结构即可,和跳表有点像。 现场情况: 我一开始回答得差不多。面试官反问了为什么哈希表是O(1)的。 回答哈希表并不是严格O(1),而是均摊O(1),如果数据过大或者哈希函数不合适或者冲突不合适,复杂度也会高。 再问如果数据类型是字符串该怎么哈希,回答将哈希映射成一个高进制数,用自然溢出或者取特殊模数。 取双哈希,双种子等方法增强哈希强度。 题3: n个数字,数字范围[0,m],求任意两数异或和的最大值。 做法: 0/1字典树经典问题,将数字转成0/1串,高位往低位插入字典树中,查询时尽量往异侧走,这样异或值最大。 现场情况: 看到题10分钟内写完了。 面试官问了问复杂度,复杂度是O(nlogm) 然后讲了讲做法就没了。腾讯 后台开发一面: 题1: 给一个没有括号的四则运算表达式,求值 做法: 经典栈模拟题。 现场情况: 写了栈做法,并讨论了除以0的情况。面试官范围如果字符串非法怎么办。忘记考虑了,回答增加合法性判断 题2: 给一个数组,问是否存在满足和为K的倍数的子数组 做法: 前缀和套路题,在模K意义下求前缀和,只有有某一种前缀值出现2次,那就有解。 现场情况: 和上面做法一致,加上map判断,其实可以用哈希表,但面试官没有追问。 题3: 给一个数组,只有两个数字出现1次,其他数字都出现2次。求对应的两个数字。 做法: 求异或和,得到的异或值肯定非0,异或和里任意找某个非0二进制位,将数组按这一位分类异或。 得到的两个异或和即为答案。 现场情况: 和上面做法一致,给出了为什么异或和一定非0的证明。三道题只用了20分钟,面试官没有追问。还有一些其他厂的,面完没复盘就不记得了,想起来再补充。面试里的算法、编程题,我感觉还是需要一些trick的,遇到的题目几乎都是很有章法的题。在面试时编程部分算是我的舒适区,每次都在编程题这里找回场子,大部分面试官都挺满意我编程题的表现。不过不是很清楚这样的表现能否为面评加分...在与一些其他竞赛选手交流的时候发现,奖项的作用是使面试时遇到的题目变难,以及更加严格的要求,写出题是理所应当,写不出就是巨大减分项。所以整体来说,面试的时候我写编程题还是很紧张的,虽然目前没有遇到过让我思考超过1分钟的题目,但我还是不感到轻松,每次知道做法之后都在绞尽脑汁想合法性、想corner case、如何让代码优美一点、如何增加可读性...最后祝大家面试顺利,拿到想要的offer