英国找工之算法

英国找工告一段落，本来想写个面试过程中的算法题合集，但这的算法题实在是太简单了。

刚开始找工的时候觉得算法怎么也是必考项，还是练习一下吧，于是刷了几轮Codeforces，结果还是一样的菜，和当年铜牌的我还是一个水平（甚至被AI惯坏了有点退步）。

我的同事给我推荐了LeetCode，是个好网站，八股题大合集。不过还是应了那句话，再菜的竞赛生刷力扣也会感觉很水。的确，这里easy、medium和很大一部分hard对我来说读完题就有思路并且写出来全A，而且这是允许多次提交的，漏掉细节也不是什么大问题，毕竟实际工作中也确实这样。

装逼结束，回忆一下我的题目吧。

首先是亚马逊的OA，第一道大水题忘了，第二道我感觉给我拉了坨大的，DP+线段树优化？

输入一个整数数组$a$（长度1e5），将整个数组划分成若干个连续子数组，每个子数组必须满足：

1.是原数组中的一段连续子区间 $[l, r]$；

2.满足：$a_r < \max(a_l, a_{l+1}, \dots, a_r)$；

找到一种合法划分方案，使得段数尽可能多，输出段数。

思路为：$dp[i] = \max \left( \{ dp[j] + 1 \mid 0 \le j < i,\ \max(a_j, a_{j+1}, \dots, a_{i-1}) > a_{i-1},\ dp[j] \ne -1 \} \right)$，比较好理解。

这玩意肯定是对的，但是吧，这玩意得用线段树啥的优化成$O(n\log n)$才能过，要么就是我思路不合适，总之最后没优化完交了个$O(n^2)$的，T了一半的点，比较无语。好在亚马逊疑似知道自己给我端上一盆大的，还是给我面试了。

投行的OA也有一些有印象的，例如有道题得算乘法逆元不然会在这卡住： $a^{p-2} \equiv a^{-1} (\mod p)$。其实大部分都是模拟题，检测到底会不会写代码。

再例如比较简单的DP：

将一个数字串转化为英文字母串，即1~26可以转化为a~z，例如：

2112可以转换为baab、bal、ul、uba、bkb（不同分割方式）

输入：一个数字串，输出：其可以转换为的英文字母串的种类数。

思路就是：$dp[i]=dp[i-1]* \big\{S[i-1]\ne 0\big\} + dp[i-2]*\big\{10\leq S[i-2]S[i-1]\leq 26 \big\}$，最后输出$dp[n]$，其中$S[0..n-1]$为输入的数字串，大括号内表达式真为1，假为0。

解释一下，$dp[i]$表示前$i$个字符的解码方式数；如果当前单个字符可以合法转换为字母（即1~9），就在前i-1的基础上贡献一种解码方式；如果当前和上一个字符可以合法转换为字母（即10~26），也在前i-2位的基础上贡献一种解码方式。

到了面试环节，题目就更加简单。例如亚马逊面试给的题：

给一个长度为$n$的数组，每个元素都是一个英文单词(最大长度$m$)，你要找出其中所有的复合词（可以由数组中其他两个元素拼接而成的词）。

这是可以一直优化的题目，我优化到$O(nm\log nm)$那哥们就不想理我了，虽然最后又优化成$O(26nm)$，用了字典树，但感觉那哥们也没想到这个，在那啊对对对，给我过了。

面试里更多是耗时间的水题，例如如何把指针连接的二叉树存到文件里，然后读出来；设计五子棋游戏变量结构以及关键方法；如何将会议编号稳定映射到一个固定服务器，并在超载时切换服务器...

感觉到了面试这一步更多就是行测了，以及一些运气。技术水平呢，我认为到我这个水平就够了。