Google 的初级软件工程师职位（美国）（Google Software Engineer, Early Career）要求至少一年相关工作经验。该职位的申请者已收到一份时长不超过30分钟的在线评估测试，截止日期为太平洋时间6月1日凌晨5:45。

据悉，此次OA均为性格测试，csoahelp在这里帮不上什么忙，大家按照自己最真实积极的想法做题即可，一定不要浪费此次珍贵的机会。

等待OA做完之后，紧接着是VO，我们一起看看其中一位候选人接受到的真题吧。

面试题：寻找 k 个最接近的元素

given a sorted array arr = [1,2,3,10,11,12], find k=3 closest elements around target m = ？

面试过程还原：

Clarification（澄清问题）：

• 面试官：我想确认一下，如果我们有数组 [1, 2, 4, 5]，目标值 m 是 3，我们肯定会选择 2 和 4。剩下的一个元素是选择 1 还是 5？因为它们离 3 的距离是一样的。
• 候选人：那我们任选一个吗？
• 面试官：是的，任选一个即可。
• 面试官：最终的结果是一个长度为 3 的数组吗？需要排序吗？
• 候选人：是的，最终的结果是一个长度为 3 的数组，不需要额外排序。

Algorithm: 我觉得这个题目可以通过 binary search 和 two pointers 的组合来做。

步骤1：Binary Search

• 我们先使用 binary search 找到整个数组中和目标值 m 最接近的数字。
• 初始化 left 和 right 指针，分别指向数组的起始和末尾。
• 使用 closest_idx 记录当前最接近 m 的元素索引。
• 在搜索过程中，通过比较当前元素与目标值的距离，不断更新 closest_idx。
• 如果目标值大于中间元素值，就将 left 指针移动到 mid 右边，否则将 right 指针移动到 mid 左边。
• 最终 closest_idx 是距离 m 最近的元素索引。

步骤2：Two Pointers

• 使用两个指针 left 和 right，分别指向 closest_idx 和 closest_idx + 1。
• 初始化一个结果集 result。
• 在 result 长度小于 k 时，循环寻找最接近的元素。
  • 检查 left 和 right 指针是否越界，如果都越界则终止循环。
  • 获取 left 和 right 指针指向的值，如果越界则用 float("inf") 表示。
  • 比较 left 和 right 值与目标值 m 的距离，选择较小的那个加入结果集。
  • 根据选择结果移动相应的指针。
• 返回 result 集合。

复杂度分析：

• Binary search 的时间复杂度是 O(log n)。
• Two pointers 的时间复杂度是 O(k)，因为最多需要找 k 个元素。
• 综合时间复杂度是 O(log n + k)。

面试经验总结：

1. 二分搜索：
   • 二分搜索是找到最接近目标值的有效方法，可以在对数时间内确定最近的元素。
   • 注意边界条件和中点计算方法，避免陷入死循环。
2. 双指针法：
   • 双指针法可以在线性时间内找到 k 个最接近的元素，通过比较两个指针所指元素与目标值 m 的距离，动态调整结果集。
   • 处理好指针超出数组边界的情况，确保结果集的正确性。
3. 代码优化和测试：
   • 确保代码结构清晰、注释详细，方便面试官理解。
   • 通过示例调用验证代码的正确性，确保实现逻辑符合预期。

通过这种方法，可以高效地解决寻找最近元素的问题，在面试中展示出良好的算法设计和编码能力。

面试后交流：

展示兴趣：

• 候选人：我对这个问题非常感兴趣。请问这个岗位的主要项目是什么？我加入后主要会负责哪些项目？
• 面试官：你会加入我们的某某团队，主要负责某些项目。你的入职培训和项目介绍会在入职后的前几周进行。

经过我们的面试辅助服务，候选人顺利通过了本轮面试，我们一起期待下一次的面试题目吧~

如果您对我们的服务感兴趣，随时留言咨询我们。