共计 1595 个字符，预计需要花费 4 分钟才能阅读完成。
面试过程
今天面试遇到这样一个问题, 有盒子里放了 n 个球, 上面标记有 1 到 n, 比如 1-9, 现在从里面取出一个, 怎么知道取出的是哪个?
听完问题我停顿了一下, 看下取出球上的标号就可以了吧? 肯定不是, 这么简单还考察什么. 我挠挠头问了下, 是不是不能看取出的球, 而只能看剩下的. 得到的是肯定的答复, 只能看剩下的部分.
那就开始解答吧, 按照我的习惯, 一般是把最直观能想到的方法先抛出来, 然后进一步找优化的思路, 所以给出了第一个方案:
1. 把盒子看作集合, 遍历 1-n, 看看哪个不在集合里, contains 方法是 false 就可以了
然后脑子里在想的是, 是不是从内存使用方面去考虑, 我联想到了 flag 的判断, 比如 linux 的文件权限, 读写执行, 所以我马上给出了第二个方案:
2. 1-n, 比如 1-9, 可以用一个 int 表示盒子里的情况, 最开始是最低的 9 个为都是 1, 取走一个, 某一位就变成 0 了, 找到最低位的 0 在哪个位置就可以了
因为依稀记得之前写 Rust 是用过 trailing_ones(计算尾部有几个 1), 结合上面的 flag 思路, 就很顺利地给出了这个改进方案.
面试官停顿了一会, 说有没有其他的方法, 如果这个 n 很大呢.
我马上想, 数量很大, 难道是问布隆过滤器么, 也不对啊, 布隆过滤器不一定能给出正确答案吧. 所以我觉得面试官的这个提示可能是因为我用了 int, 但我不确定, 所以我给出了第三个答案的时候附加了一个小条件.
3. 如果要精确地找出是哪个球的话, 考虑到 int 的位长, 在 n 可能很大的情况下, 可以用位图去记录盒子的情况
但显然我的答案不是面试官期待的, 问我还有没有其他的方法. 难不成要从真实的球的问题, 这时我脑海里又浮现了 ” 几堆砝码, 其中一堆少一个 ”, 或者 ” 很大的文件, 怎么有效处理 ” 之类的问题, 分而治之.
所以我就试探着问了下, 盒子里面有小盒子吗? 因为我想先分成批次, 然后找到需要处理的那一批, 最后单独处理那一批, 这样也算是一种优化. 但依然不对路子, 面试官给了否定的回答, 没有子盒子.
我又想了想, 之前第二种方案, 我是把“取走”这个操作看作 bit 置为 0 的操作. 如果是一个已知的数集合,“取走”就是去掉一个数, 哦, 这个我知道, 所以给出了第四个方案.
4. 遍历 1-n(当时这边说错了), 然后遍历剩下的, 做异或操作, 最后剩下的就算取走球的标号
我当时思绪有点多, 属于是多线程并发了, 讲得不太清楚, 把遍历 1-n, 说成了求和. 当时面试官怎么说的, 具体不太记得清了, 没有肯定, 也没有否定, 只是让我想想有没有其他的方法.
我想了一会, 没找到下一步的方向, 只能暂且作罢了, 不过心里还是记着. 最后面试结束, 在 ” 你还有什么想问 ” 环节, 我就问这个球问题的解法是什么.
5. 面试官说我想得有些复杂了, 给出的答案是, 先计算 1-n 的和, 然后计算剩下球标号的和, 两个相减就可以了
这样我就明白了, 这其实和第四个想法是一样的, 不过我的做法可能更有效率, 嘿嘿 (不过说错了, 我的锅, 唉). 虽然一时间有点语塞的感觉, 和面试官说, 我上面的解法和这个是一个意思, 面试官好像说了下不置可否的嗯, 到此也就结束了这场面试.
一些想法
其实给出第二种方案前, 我也飘过用异或去解的想法, 不过脑子里一过, 这种方法也需要“笨拙”的遍历, 所以没有先说这种方案, 是我的问题么?…
这次面试并不成功, 有些问题我回答的不好, 比如讲一下 Java 内存模型, 我没有答上来. 一方面我想转向 Rust, Java 方面准备地不充分; 另一方面, 刚刚开始面试, 还得查漏补缺.
没有想吐槽什么, 我理解现在的现实就是这么个情况, 面试官和面试者都不容易 (肯定有 v 友两个角色都当过), 表达清楚自己的意思不容易, 两个人要踩到同节奏上也不容易, 理解另一个想法更是需要广阔的视野和敏锐的知觉.
v 友求助, 嘿嘿
我也不容易呀, 饭碗肯定是没有了. 厚着脸皮一笑, 嘿嘿, v 友们有没有可以捞一捞的, Rust 或者 Java 方面的, 工作负责, 物超所值呀 … 唉, 不, 乐观
