你好，我是德鲁伊，我的专栏《数据结构与算法面试宝典》已于 2021 年 3 月 1 日在拉勾教育上线。
看着专栏的订阅数直线上升，我既兴奋又忐忑。兴奋的是，积累数年、打磨半年之久的“算法面试”终于和大家见面了。忐忑的是担心词不达意，表达不严谨的地方，让大家花更多的时间来消化。
不过大家的留言非常踊跃，这两天，我发现几位专栏同学在留言中针对例题提出的一些问题很有趣，我想借着这篇的机会，拿出来分析一下，搂草打兔子，万一你也有这些疑问，那就一起解决了，最后我还会给你一些算法面试的应答技巧。

有趣的 Q & A

例题 3：找出数组中右边比我小的元素

【题目】一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。
输入：[5, 2]
输出：[1, -1]
解释：因为元素 5 的右边离我最近且比我小的位置应该是 A[1]，最后一个元素 2 右边没有比 2 小的元素，所以应该输出 -1。
接口：int[] findRightSmall(int[] A);
关于这道题，我从留言中摘选的问题如下：
问题解答
老师，请问例题三中，不用考虑边界情况吗？比如数组长度为 1 和为 0 的时候。若数组长度为 0，是直接返回空吗？





在真实的面试中是需要考虑的。特别是微软的面试。 
如果是这种未定义的情况。或者说，面试题目中没有明确说明的情况。比如为空的时候返回什么？ 
在真实的面试中需要和面试官商定。或者说你向他建议返回 null 还是 new int[0]
【小结】在面试中，写代码时一定要注意边界验证。接下来我们看一下关于题意的交流。

例题 2：大鱼吃小鱼

【题目】在水中有许多鱼，可以认为这些鱼停放在 x 轴上。再给定两个数组 Size，Dir，Size[i] 表示第 i 条鱼的大小，Dir[i] 表示鱼的方向 （0 表示向左游，1 表示向右游）。这两个数组分别表示鱼的大小和游动的方向，并且两个数组的长度相等。鱼的行为符合以下几个条件:
  1. 所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离；
  2. 当方向相对时，大鱼会吃掉小鱼；
  3. 鱼的大小都不一样。
输入：Size = [4, 2, 5, 3, 1], Dir = [1, 1, 0, 0, 0]
输出：3
请完成以下接口来计算还剩下几条鱼？
int solution(int[] Size, int[] Dir);

关于这道题，我从留言中摘选的问题如下：
问题解答
大鱼吃小鱼的题，假如大小为 3、5 的鱼向右游，大小为 4 的鱼向左游，怎么能保证 4 能吃到 3 呢？



我们假设 > 表示向右游，< 表示向左游 3，5 > <4，在这种情况想，size = 5 的鱼游动过去的时候，肯定会把 size = 4 的鱼吃掉。
所以最终栈中只有 3, 5>。也就是说，size = 4 的鱼无法吃掉 size = 3 的鱼。
大鱼吃小鱼如果两条鱼一样大，但是方向不同的情况是不是有点问题，会被吃掉？

题目有条件：鱼的大小都不一样，也就是没有一样大的鱼。
【分析】首先要说明的是：
  • 大鱼和小鱼只能在一条直线上游动（肯定和你平时玩的游戏不一样！）
  • 此外，它们只能向左游，或者向右游。
  • 并且所有的鱼的速度都一样。只是游动的方向不一样。
  • 没有一样大的鱼。
我们来看一个简单的例子，用 > 表示向右游，< 表示向左游。接下来我们通过几个 Case 详细说明一下这情况。
Case 1：假设有两条鱼，向着同样的方向游。比如，3>, 5> 一起向右游动。这个时候，大鱼是吃不了小鱼的。因为它们总是向一个方向游，并且速度一样，鱼也不能换方向。
Case 2：假设有两条鱼，<3, 5>，这个时候大鱼仍然吃不了小鱼。因为它们是向相反方向游动的。
Case 3：假设有两条鱼，3> <5，此时它们相向而游，大鱼一定会把小鱼吃掉。所以最后只会有 <5 留下来。
Case 4：假设有 3 条鱼，3> 5> <4，首先碰面的是 5> <4, size = 5 的鱼会把 size = 4 的鱼吃掉。情况就退化成为 3> 5>。所以这种情况下，还会有 3> 5> 留下来，也就是还有两条鱼会留下来。
【小结】如果在面试中，没有听清楚面试官的问题，那么一定要提出自己的问题，最好是举个输入例子来表明自己哪里不清晰。

思考题：求出相邻的木板能剪出的最大矩形面积

【题目】给定一个数组，数组中的元素代表木板的高度。请你求出相邻木板能剪出的最大矩形面积。
关于这道题，我从留言中摘选的问题如下：
问题解答
老师，请问相邻只是指两两相邻，还是多个两两相邻。








这里的意思是说，你必须使用连在一起的木板来切出一个大的长方形。
比如，给定数组 A= [1000, 1, 1000]
在拼长方形的时候，你可以 A[0], A[1] 一起。A[1], A[2] 一起。或者 A[0], A[1], A[2] 一起。因为你挑出来的都是相临的。
但是，不能 A[0], A[2] 在一起。因为这两个并不挨着的。
简单地说，就是必须要连续的子数组。
【小结】在阅读专栏的时候，难免会遇到各种各样的问题，及时的交流能够搬开学习过程中的障碍。

德鲁伊的叮嘱

其实专栏内容和面试场景是不太一样的。专栏写作应该是表述得越清晰越好，而面试提问则不需要遵循固定的原则。
有时候面试官提出一个问题，会故意说得不清不楚，预设陷阱的情况在面试中时常存在。
做了多年面试官，结合我在实际工作中的切身体会，我再给你提几个醒，说说面试时应该问什么、不能问什么、提问的时长。

关于问什么

比如：请实现一棵树的层次遍历。
实际上这就是一个非常不清晰的问题。面试官的用意是希望候选人遇到模糊的问题时，能够主动识别出，然后有针对性地提出你的疑问，这也是在展现你的洞察力和沟通能力。
你可以向面试官提问，比如：什么样的树？是二叉树吗？还是多叉树？返回值是什么样的呢？树里面结点的值是整数吗？还是用字符串？
总之，在面试中，你拿到一道题，如果看得很明白，也尽量就一个 Case 和面试官做一下交流。
如果你看不明白，有点迷糊，那么更需要通过和面试官交流把题意弄清楚。你可以主动去问清楚需求，而不是毫无思考就开始干活。给面试官传达，你在实际工作中具备挖掘和理解客户需求的能力。

关于不能问什么

有的问题是不适合在澄清题意的时候问的，尤其是套答案式的提问（不要抖机灵）。比如：这个是用二分搜索吗？具体算法的操作步骤是这样吗？

关于问多久？

提问时间不宜太长。一般就问题本身的交流大概会在 2~3 分钟以内，除非遇到了特别长的面试题。

德鲁伊说

我在写作专栏时，对一些内容的描述可能不够准确，非常期待你们的指正！我认为，这也是技术人应有的态度，请你不要迟疑提出疑问，也不要吝啬表达自己的观点。借着这个机会，也是我学习和思考如何将课程更加清晰地呈现给你，也让我们一起把算法面试前的准备做得更充分！
作者与读者的思考路径不同，多一些不一样角度的碰撞，可能会产生意想不到的价值。当然，也可能诞生一篇加餐内容。：）
继续阅读
阅读原文