什么逆天公司 让我填高考排名分数就算了，还问我大学努不努力～
老鬼约 3 分钟今年“逆天背调”真的不少呀。我刷到个吐槽：投个中厂，先让你填高考排名分数，还追问大学努不努力、有没有 ACM 队。哥们都想好了，你要我真打过 ACM，我还来这儿看“水面试经验”？
我觉得这种公司最大的问题不是问得多，是问得像在查户口，还特别爱给你加一条“态度题”。
我最后的想法很朴素：既然它想“会会你”，那就去面试会会它，顺便看看面试官到底能抽象到什么版本。
要是对方还要我背高考作文，我就当场打开电脑：来，现场写个排序，看看谁更努力。😄
昨天晚上加班，本来想摸鱼刷两把视频，结果被一个叫“优美的排列”的题锁死在工位，整个人站位都不优美了。
大概意思你肯定看过：从 1 到 n 这些数字排一排，第 i 个位置的数字要么能被 i 整除，要么 i 能被它整除，问一共能排出多少种。听起来挺温柔一个题，结果实际就是排列版的“你来收拾这 n! 个房间吧”。
我当时脑子一抽，第一反应还是那种很直男的暴力想法：所有排列搓出来，一个个检查。心里还安慰自己：这不就全排列吗，写个回溯就完了。写完跑了一下 n = 10，风扇呼呼转，人没了。那一刻我突然想起线上那次 Postgres 压测，大家一开始都以为扛得住，结果一压就跪，默认方案从来都不省心。
后来冷静下来想了想，这题其实特别生活化。你就当是给部门团建排座位：
每个座位有编号 i 每个人胸牌上有编号 num 规则就是：要么 num 是 i 的倍数，要么 i 是 num 的倍数 这不就是“某些座位只能坐特定的人”吗？所以核心就俩字：剪枝。
我当时就一边嘟囔一边敲代码：先位置从 1 开始往后坐，每次只在“能坐”的人里挑。Java 随手糊了个最土的 DFS：
publicclassBeautifulArrangement{
publicintcountArrangement(int n){
boolean[] used = newboolean[n + 1];
return dfs(1, n, used);
}
privateintdfs(int pos, int n, boolean[] used){
if (pos > n) {
// 每个位置都坐满了，就是一种合法排列
return1;
}
int ans = 0;
for (int num = 1; num <= n; num++) {
if (used[num]) continue;
if (num % pos != 0 && pos % num != 0) continue;
used[num] = true;
ans += dfs(pos + 1, n, used);
used[num] = false; // 回溯
}
return ans;
}
}
这个写完其实就能过大部分人心里的那关了：逻辑简单，面试的时候嘴上还能叭叭解释“这是典型的回溯加剪枝”，显得很会那种。
但写完我自己看着有点不爽，你知道那种感觉吧，就像写 SQL 明明能用索引，结果 full scan 扫整表，总感觉亏了。位置从 1 到 n，其实前面位置“约束更紧”，能坐的人更少，所以我后来习惯是从前往后排，也会顺手开个小优化：把能坐这个位置的人先预处理出来。
我当时就随手在 main 里打了个小玩具：
publicstaticvoidmain(String[] args){
int n = 4;
List<Integer>[] canSit = new List[n + 1];
for (int i = 1; i <= n; i++) {
canSit[i] = new ArrayList<>();
for (int num = 1; num <= n; num++) {
if (num % i == 0 || i % num == 0) {
canSit[i].add(num);
}
}
System.out.println("座位 " + i + " 可选：" + canSit[i]);
}
}
跑一下你心里就有数了：哪个位置选择多，哪个位置简直“饥荒”。再配合刚才那个 DFS，把 for (num = 1..n) 换成遍历 canSit[pos]，再判断一下 used[num] 就行，少了一大堆无效循环。
再往后其实还能玩得更狠一点，用 bitmask 记状态，把 boolean[] used 换成一个 int，每一位表示某个数字用没用过，顺手再搞个 Map<Integer, Integer> memo 做记忆化，key 用 (pos << n) | mask 这种拼一下，也能说得过去。不过这个对大部分面试来说就属于“有了是加分，没有也不至于挂”的那种。