暑期实习面试 算法题/编程题记录

本篇用于记录面试过程中遇到的算法题和编程题。
我在找实习过程中看了很多人的面经，学到了很多知识，很幸运能获得前人的经验，因此我也稍微留下一点点东西。
八股、场景题我都不擅长，算法和编程题我还是回答得比较好的。
介绍一下背景：西北农林科技大学本科，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