15道Google面试题，你会做吗？
jopen 12年前
<p> 英文原文：<a href="http://www.businessinsider.com/15-mind-bending-interview-questions-that-every-google-engineer-can-answer-2012-1?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+typepad%2Falleyinsider%2Fsilicon_alley_insider+%28Silicon+Alley+Insider%29">15 Mind-Bending Interview Questions That Every Google Engineer Can Answer</a></p> <p> <strong>导读：进入像谷歌这样的互联网公司是许多人的梦想，而这些公司的面试却是很大的槛。那么，谷歌对</strong><strong>前来应聘的工程师会提出什么样的问题呢？我们这里收集了来自职业发展社区 Glassdoor 的一些面试者真实经历的面试题。</strong><strong>虽然这些题目没有人想象的那么匪夷所思，看似很简单，但实际上这些题目都值得好好思量一番。</strong></p> <p> 来看看谷歌为他们准工程师们准备的题目，看看你能做出多少：</p> <p> <strong>1. 请写出一个整数乘法的算法</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/074a804f7e24ed86f7ced9fb628c1e9d.jpg" width="400" height="300" /></p> <p> 挑战：这是一个相当开放性的问题，设计初衷是看看工程师是否会定义参数。</p> <p> 编程语言是什么？是汇编语言吗？</p> <p> 是：那么你得白手起家开发出一套基本运算来。</p> <p> 否则的话：那就简单了，只需将数字套进去即可，因为大部分语言均支持数学运算。</p> <p> <strong>2. 合并两个排序链表</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/2c33fdf7afc697f9eddfcf833f3bcb12.jpg" width="400" height="267" /></p> <p> 挑战：这类问题是 Google 面试问题的一个共同趋势：找出解决问题的有效办法。</p> <p> 合并两条链表一般会在链表之间发生“冲突”（因为它们各自有特定的次序，而你的合并会把次序搞乱），你必须找出一种算法快速消除这些冲突。</p> <p> <strong>3. 给出一组时段（以秒计），让你找出重叠的部分</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/3aec3d2641b2d85edf36203196955e06.jpg" width="400" height="300" /></p> <p> 挑战：Google 一般也会要你解决一堆数学问题。</p> <p> 这些设计的意图是让工程师对问题进行有效的思考，而不是仅仅知道如何对每个问题进行编码。</p> <p> 此处的问题会需要你利用一个聪明的数学技巧来解决。</p> <p> <strong>4. 如果有一个含有n个节点的列表，对于一个有向无环图来说，最多可以有几条边？</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/cf87938db2492e0e36883752bab85879.jpg" width="400" height="300" /></p> <p> 挑战：这是著名的旅行商问题（traveling salesman problem）的一个派生。</p> <p> 这是一个不要求你找出聪明的数学算法而是要你拓展思路的数学问题。你必须在节点间画线，条件只有一个：无论你从哪里开始，永远不要回到原点</p> <p> <strong>5. 在 Java 里面，finally、final 和 finalize 的区别是什么？</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/310793d9356e28bca07ed59bce28f97d.jpg" width="400" height="300" /></p> <p> 挑战：看看你知不知道这些术语。比方说，finalize 处理的是“垃圾回收”，而 finally 则是指向一个特定的错误。</p> <p> <strong>6. 从一大块文本中去掉重复的行</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/74e2423f1994889987acb9e760b8a326.jpg" width="400" height="271" /></p> <p> 挑战：一个基本问题，看你是不是能估算出问题是否可以在有限的时间内解决。</p> <p> 这样的问题通常可以采取暴力攻击手段，但也有可能永远都无法解决。</p> <p> <strong>7. 给你一个字符串，找出包含给定字符集的最小窗口</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/71fc080ce88312d8c1c6e01a718e0afa.jpg" width="400" height="300" /></p> <p> 挑战：此类问题有许多解决方式，完全取决于你选择的算法是什么。</p> <p> Google 要找的是能选出最快算法的工程师。</p> <p> <strong>8. 写一段程序计算出某字符串是否另一字符串的轮换（rotation）</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/c4deeb8fb00d422f97470820e98d7650.jpg" width="400" height="300" /></p> <p> 挑战：这个问题靠的是看你是不是能够灵活掌握一些计算机方面知识的转义。</p> <p> 比方说，“strings”一语通常是指由字符、单词或可打印、可见的东西组成的多行字符串。不过同时也可以是矩阵（二维对象）及别的对象。</p> <p> 你必须检查看看它是不是可以轮换（rotate），然后跟另一个进行对比。</p> <p> <strong>9. 旧金山能容纳多少个气球？</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/7f6fa55e933669289b7ebe0b59fe0f2f.jpg" width="400" height="300" /></p> <p> 挑战：此类问题 Google 的面试官一般都会问到，目的是想看看你设定的“边界条件”是什么样的。</p> <p> 这个问题有许多解决方式，可以通过添加限定条件来进行简化—比如说旧金山的面积，这种限定在进行编程的时候是很重要的。</p> <p> <strong>10. 粘滞位是什么？为什么要用？</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/98312a96d8ba8b1d449cb2c15cc1e799.jpg" width="400" height="300" /></p> <p> 挑战：粘滞位是一个系统管理术语，指在 Unix 系统中设置文件或者目录访问权限的标志位，如果设置，只有 owner 或者 root 权限用户能够重命名、删除文件。</p> <p> Google 想测试一下，看看你是否了解一些管理的细节，而不是只会编程。</p> <p> <strong>11. 给出一组整数，值范围在很窄的区间，但是区间未明，如何找出其中位数？</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/4e04807cffffe878bd57c8508f790e7a.jpg" width="400" height="300" /></p> <p> 挑战：又是一个要你能够利用聪明的数学技巧的问题，离散数学课你有没有认真听？</p> <p> 这可不是什么简单问题。</p> <p> <strong>12. 给出一组区间，找出交集数最多的一个</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/a140cf833bf1a15a933d67874d3e5ae3.jpg" width="400" height="242" /></p> <p> 挑战：现在 Google 要你确信知道自己检查的是问题的正确部分，无视没有价值的部分，这样才能够令算法更高效。</p> <p> <strong>13. 100 个整数组成的数组，打乱次序，拿掉其中一个数，把它找出来</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/af147620ff8f09967b0ded01c571e642.jpg" width="400" height="300" /></p> <p> 挑战：运用另外一个数学技巧可以几行代码搞定。</p> <p> 测试目的是看看你是不是不仅知道用什么办法，还知道如何实现代码。</p> <p> <strong>14. 判断某个数独解决方案是否正确</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/56735744242470a95491ea472e6d4226.jpg" width="400" height="225" /></p> <p> 挑战：这个要你想出办法用另一种数学技巧从算术上快速检验解决方案。</p> <p> <strong>15. 给你一支股票的日价，找出一次买卖交易（buy-sell trading）如何操作才会损失最大</strong></p> <p style="text-align:center;"><img border="0" alt="15道Google面试题，你会做吗？" src="https://simg.open-open.com/show/d90ef19d100403b51787b8112c40b400.jpg" width="400" height="300" /></p> <p> 挑战：这个问题非常棒，你必须竭尽所能，把所有的知识本领都用上。</p> <p> 看看边界条件（即挑出变动最大的股票价格点）然后有效地算出波动最大的一次。</p> <p> 我们能想到的唯一像样一点的办法是暴力计算，把每一个股价都遍历一遍。<br /> 来自: <a id="link_source2" href="/misc/goto?guid=4958327982487549063" target="_blank">www.36kr.com</a></p>