WEBKT

技术面试,如何考察候选人的算法能力?一道关于“寻找山峰”的题目剖析

43 0 0 0

题目描述

题目要求详细说明

输入输出示例

解题思路

1. 暴力法(线性扫描)

2. 二分查找(对数时间复杂度)

参考代码

代码解释

面试中需要注意的点

扩展思考

总结

作为一名技术面试官,算法能力是考察候选人编程基础和问题解决能力的重要方面。今天,我将分享一道我在面试中经常使用,且能有效区分候选人水平的题目——“寻找山峰”。

题目描述

题目名称: 寻找山峰(Peak Finding)

题目背景: 假设你是一名地理学家,正在研究一个山脉的地形。你手头有一份高度数据,这份数据可以简化为一个整数数组 heights,其中 heights[i] 表示第 i 个位置的高度。我们称一个位置 i 为山峰,如果满足以下条件:

  1. heights[i] 大于其相邻位置的高度,即 heights[i-1] < heights[i] > heights[i+1]
  2. 对于数组的边界情况,如果 i = 0,只需满足 heights[i] > heights[i+1];如果 i = n-1,只需满足 heights[i] > heights[i-1]

题目要求: 编写一个函数,找到并返回数组 heights 中的任意一个山峰的索引。注意,数组中可能存在多个山峰,你只需要返回其中一个即可。

难度: 中等

题目要求详细说明

  • 函数签名: 你需要实现一个函数,其函数签名如下(以 Python 为例):

    
    

def find_peak(heights: list[int]) -> int:
pass
```

  • 输入: 一个整数数组 heights,表示每个位置的高度。

  • 输出: 返回一个整数,表示山峰的索引。如果数组为空,或者没有山峰,可以返回 -1

  • 时间复杂度要求: 尽量优化你的算法,使其具有尽可能低的时间复杂度。一个好的解决方案应该具有 O(log n) 的时间复杂度。

  • 空间复杂度要求: 尽量使用常数级别的额外空间。

输入输出示例

示例 1:

输入:heights = [1, 2, 3, 1]
输出:2
解释:3 是一个山峰,其索引为 2。

示例 2:

输入:heights = [1, 2, 1, 3, 5, 6, 4]
输出:1 或 5 (1 处的 2 和 5 处的 6 都是山峰,返回其中一个即可)

示例 3:

输入:heights = [1, 2, 3, 4, 5]
输出:4
解释:5 是一个山峰,其索引为 4。

示例 4:

输入:heights = [5, 4, 3, 2, 1]
输出:0
解释:5 是一个山峰,其索引为 0。

示例 5:

输入:heights = [1]
输出:0
解释:只有一个元素,它就是山峰。

示例 6:

输入:heights = []
输出:-1
解释:数组为空,没有山峰。

解题思路

1. 暴力法(线性扫描)

最直接的方法是遍历整个数组,对于每个位置,检查它是否满足山峰的条件。这种方法的时间复杂度为 O(n)。

def find_peak_linear(heights: list[int]) -> int:
n = len(heights)
if n == 0:
return -1
for i in range(n):
if i == 0:
if n == 1 or heights[i] > heights[i+1]:
return i
elif i == n - 1:
if heights[i] > heights[i-1]:
return i
else:
if heights[i-1] < heights[i] > heights[i+1]:
return i
return -1

虽然暴力法简单易懂,但在面试中,面试官通常会期望你提供更优的解决方案。因此,我们需要考虑如何优化算法,降低时间复杂度。

2. 二分查找(对数时间复杂度)

由于题目没有明确说明数组 heights 是有序的,因此我们不能直接应用传统的二分查找。但是,我们可以借鉴二分查找的思想,通过比较中间元素与其相邻元素的大小,来缩小搜索范围。具体步骤如下:

  1. 初始化 left = 0right = n - 1,其中 n 是数组的长度。
  2. left <= right 时,执行以下步骤:
    • 计算中间位置 mid = (left + right) // 2
    • 检查 heights[mid] 是否为山峰。如果是,直接返回 mid
    • 如果 heights[mid] < heights[mid + 1],说明山峰一定在 mid 的右侧,因此更新 left = mid + 1
    • 否则,说明山峰一定在 mid 的左侧(包括 mid),因此更新 right = mid - 1
  3. 如果循环结束仍未找到山峰,说明数组为空或不存在山峰,返回 -1

这种方法的时间复杂度为 O(log n),空间复杂度为 O(1),是一个更优的解决方案。

参考代码

以下是使用二分查找实现的 Python 代码:

def find_peak(heights: list[int]) -> int:
n = len(heights)
if n == 0:
return -1
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if is_peak(heights, mid):
return mid
if mid < n - 1 and heights[mid] < heights[mid + 1]:
left = mid + 1
else:
right = mid - 1
return -1
def is_peak(heights: list[int], i: int) -> bool:
n = len(heights)
if i == 0:
return n == 1 or heights[i] > heights[i + 1]
elif i == n - 1:
return heights[i] > heights[i - 1]
else:
return heights[i - 1] < heights[i] > heights[i + 1]

代码解释

  • find_peak(heights) 函数是主函数,用于查找山峰。
  • is_peak(heights, i) 函数用于判断索引 i 处是否为山峰。
  • find_peak 函数中,我们使用 leftright 变量来维护搜索范围。
  • 在每次循环中,我们计算中间位置 mid,并检查 heights[mid] 是否为山峰。
  • 如果 heights[mid] 不是山峰,我们根据 heights[mid] 与其相邻元素的大小关系,来缩小搜索范围。
  • 最终,如果找到山峰,我们返回其索引;否则,返回 -1

面试中需要注意的点

  • 沟通: 在开始编写代码之前,务必与面试官充分沟通,明确题目的要求和限制。例如,可以询问数组中是否存在重复元素,以及是否允许修改原数组。
  • 边界情况处理: 在编写代码时,务必注意处理边界情况,例如数组为空、数组只有一个元素、以及山峰位于数组的边界等情况。在上面的代码中,is_peak函数清晰地处理了边界情况。
  • 代码风格: 编写清晰、简洁、易读的代码。使用有意义的变量名,添加必要的注释,并保持代码的缩进一致。
  • 时间复杂度和空间复杂度分析: 在完成代码后,务必分析算法的时间复杂度和空间复杂度。这可以帮助你更好地理解算法的性能,并向面试官展示你的分析能力。
  • 测试: 在完成代码后,务必进行充分的测试,以确保代码的正确性。可以编写一些测试用例,包括正常情况、边界情况和异常情况,来验证代码的逻辑是否正确。
  • 优化: 如果时间允许,可以尝试优化你的算法,以降低时间复杂度和空间复杂度。例如,可以使用二分查找来优化线性扫描算法。

扩展思考

  • 如果数组中有多个山峰,如何找到所有的山峰?
  • 如何找到最高的山峰?
  • 如果数组是一个二维数组,如何找到山峰?

这些问题可以帮助你更深入地理解山峰问题的本质,并展示你的解决问题的能力。

总结

“寻找山峰” 是一道经典的算法题目,它可以有效地考察候选人的编程基础和问题解决能力。通过分析暴力法和二分查找两种解决方案,我们可以更好地理解算法优化的重要性。在面试中,除了编写正确的代码之外,还需要注意沟通、边界情况处理、代码风格、时间复杂度和空间复杂度分析、测试和优化等方面。希望本文能够帮助你更好地准备技术面试,并在面试中脱颖而出。祝你面试顺利!

此外,在实际面试中,我还会根据候选人的表现,适当调整题目的难度和深度。例如,如果候选人很快就解决了基本问题,我会进一步询问他们如何处理更复杂的情况,或者要求他们对算法进行优化。通过这种方式,我可以更全面地了解候选人的能力和潜力。

算法狂人 算法面试二分查找山峰问题

评论点评

打赏赞助
sponsor

感谢您的支持让我们更好的前行

分享

QRcode

https://www.webkt.com/article/9154