谷歌面试编程题与答案（MIT版） | 面试笔记

目录

问题 1：硬币谜题

问题 2：在数组中执行检索操作

问题 3：A 到 I（字符串向整数的转换）

问题 4：反转字符串内单词的排列顺序

问题 5：寻找最近邻点

问题 6：洗牌算法难题

问题 7：检测单链表中是否存在环状结构

问题 8：计算 2 的 x 次方

问题 9：二叉搜索树相关问题

问题 10：排查并修复错误

---

问题 1：硬币难题

假设有 8 枚体积相同的硬币，其中仅有一枚的重量略高于其余 7 枚（但无法确定具体是哪一枚）。同时，你拥有一个传统的天平工具，可用于比较重量，从而判断哪一枚硬币更重（或是否重量一致）。那么，在这种情况下，最少需要称量多少次才能准确识别出那枚较重的硬币？

优质解答： 最少需要进行 两次称量。具体操作为 从 8 枚硬币中选取 6 枚，将它们平均分配至天平的左右两侧，每侧放置 3 枚。 称量后可能出现以下两种情形：

1. 天平两侧重量不一致。

1）若左侧托盘中的三枚硬币总重量较大，则表明较重的那枚硬币位于左侧；若右侧托盘较重，则说明较重硬币在右侧；

2）随后从这三枚硬币中任选两枚再次进行称量。若两者重量相等，则未被称量的那一枚即为最重的硬币；若两者存在差异，则只需对这两枚再次进行一次称量即可确定。

2. 天平两侧重量相同。

1）当