Google Software Engineer, Early Career – United States – OA – 谷歌面试真题

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. 代码优化和测试
    • 确保代码结构清晰、注释详细,方便面试官理解。
    • 通过示例调用验证代码的正确性,确保实现逻辑符合预期。

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

面试后交流:

展示兴趣

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

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

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

author avatar
azn7u2@163.com

Leave a Reply

Your email address will not be published. Required fields are marked *