白话经典算法系列之十 一道有趣的GOOGLE面试题

谷歌面试15个疯狂经典问题谷歌面试15个疯狂经典问题谷歌是一些处于经济衰退浪潮中的初级经理和软件xx的避风港。

然而，它的招募门槛很高。

首先，谷歌更喜欢常春藤联盟(由美国八所著名大学组成)的毕业生；其次，即使候选人超过30岁，谷歌也非常关注他的GPA分数。

第三，谷歌需要想改变世界的人。

而且，即使候选人符合上述要求，也可能会被谷歌在面试中提出的问题难倒。

以下是15个谷歌面试问题，让很多申请人抓狂。

问题1:一辆校车能装多少个高尔夫球？职位：产品经理问题2:在西雅图清洗所有的窗户要多少钱？职位：产品经理问题三：在一个重男轻女的xx，家家都想生男孩。

如果一个家庭生了一个女孩，它会有另一个，直到它生了一个男孩。

请问这个xx的男女比例是多少？职位：产品经理问题4:世界上有多少个钢琴调音师？职位：产品经理问题5:为什么井盖是圆的？职位：软件工程师问题6:为旧金山设计一个紧急疏散计划。

职位：产品经理问题7:时钟的指针xx总共重合几次？职位：产品经理问题8:解释“xx牛肉”的含义。

职位：软件工程师问题9:一个人开车去酒店，什么都没有。

到底发生了什么？职位：软件工程师问题10:你想知道你的好朋友鲍勃有没有你的正确电话号码，但是你不能直接问他。

你必须在卡片上留言，让伊芙把它交给鲍勃。

除了问题之外，你还应该在卡片上写什么，以确保鲍勃能理解信息，而夏娃看不到你卡片上的电话号码。

职位：软件工程师问题11:你是海盗船的船长，你的船员要投票决定如何平分金条。

如果同意你的船员人数少于一半，你就会被杀死。

你应该如何提议分发金条，以便获得更多赃物并生存？职位：工程经理问题12:你有八个同样大小的球，其中七个重量相同，只有一个稍微重一点。

给你一个天平，你只能称两次。

怎么才能找到不同重量的球？职位：产品经理问题13:你在一栋100层的大楼里给了你两个鸡蛋。

有时候鸡蛋很脆弱，有时候又极其坚韧。

这意味着如果鸡蛋掉在1楼，可能会摔碎，而如果鸡蛋从100楼掉下来，可能会安然无恙。

1) 1) 村子 有村子 有100对 妻对 妻，，其中 个 都瞒着自 的妻子偷情其中 个 都瞒着自 的妻子偷情。

村 的 个妻子都能立即发 除自 之外的其他男人是否偷情 的 个妻子都能立即发 除自 之外的其他男人是否偷情，，唯独 知道 自 的 到 有没有偷情知道 自 的 到 有没有偷情。

村 的规矩 容忍通 村 的规矩 容忍通 。

任何一个妻子，一 能证明自 的男人偷情一 能证明自 的男人偷情，，就必须 把他杀死就必须 把他杀死。

村 的女人全都 格照 规矩办 格照 规矩办 。

一 一 ，，女头领出来 布女头领出来 布，，村 至少有一个 偷情村 至少有一个 偷情。

请问接 来会发生 么 请问接 来会发生 么 ？？答案： 是一个典型的递 问题。

一 所有的妻子都知道至少有一个男人出轨， 们就可以按递 方式来看待 个流程。

先让 们假设只有一个 偷情。

他的妻子见 到任何偷情的男人，因 知道 个人就是自 ， 就会杀了他。

假如有 个 偷情， 他俩的妻子只知道 是自 的那一个男人偷情。

因 会等 一 看那个人有没有被杀死。

假如第一 没人被杀死， 就能确定 自 的 也偷了情。

依 类推，假如有100个 偷情， 他们能安全活 99 ，直到100 时，所有妻子把他们全都杀死。

聘职位：产品 理日)日)假设在一段高假设在一段高假设在一段高 公路 公路 公路 ，，旦0分钟之内见到汽车 过的概率是0.950.95。

那么那么，，在10分钟内见到汽车 过的概率是多少分钟内见到汽车 过的概率是多少已(已(已(假设缺省概率固定假设缺省概率固定假设缺省概率固定))答案： 题的关键在于0.95是见到一辆或多辆汽车的概率，而 是仅见到一辆汽车的概率。

在旦0分钟内，见 到任何车辆的概率为0.05。

因 在10分钟内见 到任何车辆的概率是 个值的立方根，而在10分钟内见到一辆车的概率 为1 去 立方根，也就是大约6旦还。

聘职位：产品 理旦)旦)有四个人要在夜 穿过一条悬索桥回到宿营地有四个人要在夜 穿过一条悬索桥回到宿营地有四个人要在夜 穿过一条悬索桥回到宿营地。

问题：一辆校车能装下多少个高尔夫球？需要假设校车的容积，例如，依维科、沃尔沃、大奔……假设用公交车，车的容积（宽×高×长）=3×4×25=300立方米，一只高尔夫球半径约10厘米，因为装入后有空隙，按照立方体算，体积约0.008立方米，故该校车可容纳300/0.008=37500个高尔夫球。

应聘职位：产品经理问题：如果让你清洗西雅图市所有的窗户，你会对此索价多少？这题可能考验的是项目经理面对未知时的决策能力，理性的解法需根据城市面积，估算建筑表面展开面积，再估计室外窗户面积，室内窗户面积，并计算不同的层高成本的系数，总合出一个估值。

感性一点，可以迎合谷歌的风格，例如如果我能发明一种迅速清洗窗户个工具，那么我将提供一次几乎免费的清洗工作，这样当每扇窗户都离不开我时，我就可以开始鲸吞索价了。

应聘职位：产品经理问题：在一个重男轻女的国家里，每家每户都想生男孩。

若一户人家生了一个女孩，便会再生一个，直到生下的是男孩为止。

请问这个国家的男女比例是多少？答案是接近 1：152：48是正常出生的男女比例，因为很少有人会在生了女孩以后掐死，即使再重男轻女也要考虑后代的繁衍问题。

一胎生女的概率是0.5，连续两台生女的概率是0.25，连续三胎生女的概率是0.125，连续四胎及更多胎生女的概率更少。

极小概率事件可以忽略，不会影响总体。

应聘职位：产品经理问题：全世界共有多少位钢琴调音师？google上可以查到发达国家的人口数和钢琴普及率，那就可以计算了。

例如，需要知道美国的人口和总体经济状况，假如美国共有3亿人口，按三口之家计算，全美国共有1亿个家庭，如果一半家庭即5000万个家庭属于富裕阶层，拥有钢琴比例按10％这个比例可能有点偏高，但在推算大致比例时是允许的。

那么就有500万个家庭拥有钢琴，这样全美国就有500万架钢琴。

假设每架钢琴一年调音一次，一个调音师一年调音1000架次的话，那么全美国调音师的数量就是5000000/1000=5000。

谷歌面试题目谷歌面试一直以来都是全球求职者梦寐以求的机会。

在面试过程中，谷歌常常会提出一些具有挑战性的问题，以衡量应聘者的思维能力和解决问题的能力。

本文将介绍一些典型的谷歌面试题目，并提供解析和解决方法。

1. 扔硬币问题问题描述：假设有两个硬币，一个是正面朝上的硬币，另一个是反面朝上的硬币。

你无法看到硬币的正反面，只能进行一次操作：选择其中一个硬币，然后翻转它。

然后你需要选择一个硬币，告诉我它是正面朝上的概率。

解析和解决方法：考察概率的基本原理。

首先，我们可以列出两个硬币的可能状态：1. 正面朝上的硬币和反面朝上的硬币。

2. 正面朝上的硬币和翻转后正面朝上的硬币。

3. 反面朝上的硬币和翻转后反面朝上的硬币。

根据问题描述，我们知道至少有一个硬币是正面朝上的。

我们可以进一步分析这个信息：- 如果我们选择的硬币是正面朝上的硬币，那么它不可能是第2种情况，因为翻转后应该是反面朝上的，所以它一定是第1种情况。

因此，它是正面朝上的概率为1。

- 如果我们选择的硬币是反面朝上的硬币，那么它也不可能是第3种情况，因为翻转后应该是正面朝上的，所以它一定是第1种情况。

因此它是正面朝上的概率为1/2。

综上所述，选择的硬币是正面朝上的概率为1/2。

2. 排列问题问题描述：给定一个由不同字符组成的字符串，输出所有可能的排列。

解析和解决方法：这是一个经典的排列问题，可以使用递归来解决。

首先，我们定义一个函数permute(string s)来解决给定字符串s的排列问题：1. 如果字符串s为空，说明没有字符可供排列，直接返回一个空列表。

2. 如果字符串s只包含一个字符，那么只有一种排列，即返回长度为1的字符串列表，其中唯一的字符串就是s本身。

3. 如果字符串s包含多个字符，那么我们可以将问题分解为两个步骤：a. 选择一个字符作为排列的第一个字符。

b. 对剩余的字符进行排列。

我们可以使用递归来实现这个思路。

具体步骤如下：1. 遍历字符串s中的每个字符，记当前字符为c。

谷歌（Google）算法面试题1.谷歌面试题：给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。

回答：此题的关键是让生成的1到7的数出现概率相同。

只要我们可以从n个数中随机选出1到n个数，反复进行这种运算，直到剩下最后一个数即可。

我们可以调用n次给定函数，生成n个1到5之间的随机数，选取最大数所在位置即可满足以上要求。

例如初始的7个数[1,2,3,4,5,6,7].7个1到5的随机数[5,3,1,4,2,5,5]那么我们保留下[1,6,7],3个1到5的随机数[2,4,1]那么我们保留下[6]6就是我们这次生成的随机数。

2. 谷歌面试题：判断一个自然数是否是某个数的平方。

当然不能使用开方运算。

回答：假设待判断的数字是N。

方法1：遍历从1到N的数字，求取平方并和N进行比较。

如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。

复杂度为O(n^0.5)。

方法2：使用二分查找法，对1到N之间的数字进行判断。

复杂度为O(logn)。

方法3：由于(n+1)^2=n^2+2n+1，=...=1+(2*1+1)+(2*2+1)+...+(2*n+1)注意到这些项构成了等差数列（每项之间相差2）。

所以我们可以比较N-1，N-1-3，N-1-3-5...和0的关系。

如果大于0，则继续减；如果等于0，则成功退出；如果小于0，则失败退出。

复杂度为O(n^0.5)。

不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。

3. 谷歌面试题：给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。

如何才能从这个无穷尽的流中随机的选取1000个关键字？回答：定义长度为1000的数组。

对于数据流中的前1000个关键字，显然都要放到数组中。

对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为1000/n。

所以我们以1000/n的概率用这个关键字去替换数组中的随机一个。

google 面试题在求职过程中，Google 面试被广大求职者所津津乐道。

作为世界著名科技公司，Google 的面试要求严格而高效。

本文将介绍一些常见的Google 面试题目及其解答，希望对准备 Google 面试的求职者有所帮助。

问题一：请介绍一下自己。

这是一个非常常见的开场问题，但也是你展示个人能力和特点的关键时刻。

当回答这个问题时，应该注意控制时间，突出重点，提供与求职岗位相关的信息。

例如，你可以提及自己的教育背景、工作经历以及专业技能等。

问题二：你在前一份工作中的最大成就是什么？请详细介绍。

这个问题旨在考察你在工作中的表现和成果。

你可以选择一个与应聘岗位相关的成就并详细描述，包括你在项目中扮演的角色、遇到的挑战以及最终取得的成果。

问题三：在你过去的工作中，你最大的失败是什么？并告诉我们你是如何处理的？这个问题旨在检验你的诚实度和应对挫折的能力。

在回答时，应谈及你面临的困难、原因以及你是如何从失败中学习，并采取措施避免类似问题再次发生。

问题四：告诉我们一件你认为非常有趣或者独特的项目或经历。

这个问题测试你的创意和个人风格。

你可以选择一项与您的兴趣或特长相关的项目或经历，并详细介绍该项目的目标、挑战、你所扮演的角色以及最终取得的成果。

问题五：请向我们解释什么是“分布式系统”？Google 在其基础架构中广泛使用分布式系统，因此，对于求职者来说，对分布式系统有一定的了解是必要的。

回答这个问题时，应简洁明了地解释分布式系统的定义、特点，并提供一个实际应用的例子来加深理解。

问题六：Google 的公司文化是什么样的？Google 以其独特的公司文化而闻名。

在回答这个问题时，你可以提及 Google 注重早餐文化、奖励创新、提供舒适工作环境等，并结合自己的理解和价值观，展示你与 Google 公司文化的匹配度。

问题七：你在工作中遇到过的最大挑战是什么？你是如何克服的？这个问题旨在考察你面对困难时的应对能力和解决问题的能力。

Google的面试题在刁钻古怪方面相当出名，甚至已经有些被神化的味道。

这个话题已经探讨过很多次，这里贴出15道Google面试题并一一给出了答案，其中不少都是流传很广的。

怎么样？下边来热热身，看看你有没有可能去Google工作吧！第一题：多少只高尔夫球才能填满一辆校车？(职位：产品经理)解析：通过这道题，Google希望测试出求职者是否有能力判断出解决问题的关键。

网友的答案：我想，一辆标准大小的校车约有8英尺宽、6英尺高、20英尺长——我能知道这些数字完全是因为我曾经无数次被堵在校车后面。

据此估算，一辆校车的容积约为960立方英尺，也就是160万立方英寸。

一个高尔夫球的半径约为0.85英寸，我认为一个高尔夫球的体积约为2.6立方英寸。

用校车的容积除以高尔夫球的体积，得到的结果是66万。

不过，由于校车里面还有座位等等各种东西，而且高尔夫球的形状使得不同的球之间会有不少空隙。

我的最终估算结果是50万。

这听起来有些荒唐。

如果我直接猜的话，我给出的答案肯定是10万以下，不过我相信我的数学水平。

当然，如果这里的校车是小布什当年坐过的那种，结果还要除以2，差不多是25万个。

第二题：让你清洗西雅图所有的玻璃窗，你的报价是多少？(职位：产品经理)答案：这一题我们可以玩点花招，我们的答案是“每扇窗10美元”。

第三题：有一个人们只想生男孩子的国家，他们在有儿子之前都会继续生育。

如果第一胎是女儿，他们就会继续生育直到有一个儿子。

这个国家的男女儿童比例是多少？(职位：产品经理)答案：这一题引发了不少争议，不过我们发现，这一题的解答步骤如下：1、假设一共用10对夫妻，每对夫妻有一个孩子，男女比例相等。

(共有10个孩子，5男5女)；2、生女孩的5对夫妻又生了5个孩子，男女比例相等。

(共有15个孩子，男女儿童都是7.5个)；3、生女孩的2.5对夫妻又生了2.5个孩子，男女比例相等。

(共有17.5个孩子，男女儿童都是8.75个)；4、因此，男女比例是1:1。

谷歌面试中，15个让人疯狂的经典问题第1篇：谷歌面试中15个让人疯狂的经典问题对一些身处经济衰退大潮中的初级经理和软件开发者而言，谷歌是一个避风港。

但其招聘门槛较高，首先，谷歌更青睐长春藤联盟(由美国八所知名大学所组成)的毕业生；其次，即使应聘者已年过30，谷歌也很在意其gpa(平均成绩点数)分数；第三，谷歌需要的是那些想改变世界的人。

而且，即使应聘者满足了上述要求，也有可能在面试中被谷歌提出的问题所难倒。

以下是15个让许多应聘者抓狂的谷歌面试题。

问题1：一辆校车能装下多少个高尔夫球？应聘职位：产品经理问题2：如果让你清洗西雅图市所有的窗户，你会对此索价多少？应聘职位：产品经理问题3：在一个重男轻女的国家里，每家每户都想生男孩。

若一户人家生了一个女孩，便会再生一个，直到生下的是男孩为止。

请问这个国家的男女比例是多少？应聘职位：产品经理问题4：全世界共有多少位钢琴调音师？应聘职位：产品经理问题5：下水道井盖为什么是圆的？应聘职位：软件工程师问题6：为旧金山市设计一个紧急疏散方案。

应聘职位：产品经理问题7：时钟的指针一天内总共会重合多少次？应聘职位：产品经理问题8：阐释"死牛肉"的意义所在。

应聘职位：软件工程师问题9：一个人开车来到旅馆，变得一无所有。

究竟发生了什么事情？应聘职位：软件工程师问题10：你想知道好友鲍勃是否有你正确的电话号码，但又不能直接问他。

你必未完，继续阅读 >第2篇：谷歌面试中，15个让人疯狂的经典问题对一些身处经济衰退大潮中的初级经理和软件开发者而言，谷歌是一个避风港。

但其招聘门槛较高，首先，谷歌更青睐长春藤联盟(由美国八所知名大学所组成)的毕业生;其次，即使应聘者已年过30，谷歌也很在意其gpa(平均成绩点数)分数;第三，谷歌需要的是那些想改变世界的人。

而且，即使应聘者满足了上述要求，也有可能在面试中被谷歌提出的问题所难倒。

以下是15个让许多应聘者抓狂的谷歌面试题。

Google面试题以及最佳答案面试题以及答案(一)应聘职位：软件工程师10)假设你在衣橱里挂满衬衫，很难从中挑出某一件来。

请问你打算怎样整理一下，使得它们容易挑选?答案：此题没有固定答案。

考验的是被面试者在解决问题方面的想象力和创造性。

我们觉得读者Dude的这个答案可能会给Google留下深刻印象：把它们按布料的种类进行哈希(HASH)组合。

然后每类再按2-3-4树或红黑树(都是计算机算法)排序。

应聘职位：软件工程师11)给你一副井字棋(Tic Tac Toe)。

你来写一个程序，以整个游戏和一个玩家的名字为参数。

此函数需返回游戏结果，即此玩家是否赢了。

首先你要决定使用哪种数据结构处理游戏。

你还要先讲出使用哪种算法，然后写出代码。

注意：这个游戏中的某些格子里可能是空的。

你的数据结构需要考虑到这个条件。

答案：所需要的数据结构应为二元字符数列。

调用此函数检查6种条件，判断是否有赢家。

其中第6种条件就是看是否还有空格。

如果有赢家，则字符判断玩家是X还是O。

因此你需要一个旗标。

如果有赢家则返回此值并结束游戏，如果没有则继续游戏。

应聘职位：软件工程师12)为1万亿个数排序需要多长时间?请说出一个靠谱的估计。

答案：这又是一个没有标准答案的题目。

目的是考察被面试者的创造性。

我们倾向于两位读者给出的简单答案：用归并排序法(Merge Sort)排序。

平均情况下为O(1,000,000,000,000 Log1,000,000,000,000)。

最差情况下为O(1,000,000,000,000 Log1,000,000,000,000)。

现在可以做到每秒10亿次的运算，所以大约应需要3000秒。

应聘职位：软件工程师13)请设计一个蛙跳游戏的算法，并写出方案的代码。

答案：这个游戏的目标是引导一个青蛙避开来往车辆，横穿一条繁忙的公路。

你可以用一个数列来代表一条车道。

将方案简化成一条N车道的公路。

我们只找到一个对此问题的解答，它来自Glassdoor网站：一个方法是写一个递归算法来决定何时等待，何时跳进下一个车道。