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)。
面试经验总结：
- 二分搜索：
- 二分搜索是找到最接近目标值的有效方法，可以在对数时间内确定最近的元素。
- 注意边界条件和中点计算方法，避免陷入死循环。
- 双指针法：
- 双指针法可以在线性时间内找到
k个最接近的元素，通过比较两个指针所指元素与目标值m的距离，动态调整结果集。 - 处理好指针超出数组边界的情况，确保结果集的正确性。
- 双指针法可以在线性时间内找到
- 代码优化和测试：
- 确保代码结构清晰、注释详细，方便面试官理解。
- 通过示例调用验证代码的正确性，确保实现逻辑符合预期。
通过这种方法，可以高效地解决寻找最近元素的问题，在面试中展示出良好的算法设计和编码能力。
面试后交流：
展示兴趣：
- 候选人：我对这个问题非常感兴趣。请问这个岗位的主要项目是什么？我加入后主要会负责哪些项目？
- 面试官：你会加入我们的某某团队，主要负责某些项目。你的入职培训和项目介绍会在入职后的前几周进行。
经过我们的面试辅助服务，候选人顺利通过了本轮面试，我们一起期待下一次的面试题目吧~
如果您对我们的服务感兴趣，随时留言咨询我们。
