xiaoshancom 2008-1-20 16:00
Google面试题集
原文：[url=http://fafeng.blogbus.com/logs/14168877.html]http://fafeng.blogbus.com/logs/14168877.html[/url]
本作品采用[url=http://creativecommons.org/licenses/by-nc-sa/2.5/cn/]知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议[/url]授权。
[size=11pt]Q[/size][font=宋体][size=11pt]：你有一序列数字，其中有些是负数，有些是正数，从该列中找出最大和的子序列，要求算法复杂度[/size][/font][size=11pt]O(N)[/size][font=宋体][size=11pt]。比如：[/size][/font][size=11pt]-5, 20, -4, 10, -18[/size][font=宋体][size=11pt]，子列[/size][/font][size=11pt][20, -4, 10][/size][font=宋体][size=11pt]具有最大和[/size][/font][size=11pt]26[/size][font=宋体][size=11pt]。[/size][/font]
[size=11pt]A[/size][font=宋体][size=11pt]：首先你应该通过序列建立一个新的序列，它值为包含它在内以及之前序列之和。举例来说如果序列为：[/size][/font][size=11pt][-7 12 -5 13 -2][/size][font=宋体][size=11pt]，那么新序列将是：[/size][/font][size=11pt][-7 5 0 13 11][/size][font=宋体][size=11pt]。该子列占有的最大序列和是在新序列中从最小数字索引加[/size][/font][size=11pt]1([/size][font=宋体][size=11pt]在这个例中[/size][/font][size=11pt]-7([/size][font=宋体][size=11pt]索引[/size][/font][size=11pt]0))[/size][font=宋体][size=11pt]是最小，于是我们从[/size][/font][size=11pt]5([/size][font=宋体][size=11pt]索引[/size][/font][size=11pt]1)[/size][font=宋体][size=11pt]开始直到该列表中的最大数[/size][/font][size=11pt]13([/size][font=宋体][size=11pt]索引[/size][/font][size=11pt]3)[/size][font=宋体][size=11pt]，于是结果[/size][/font][size=11pt](12, -5, 13)[/size][font=宋体][size=11pt]总和[/size][/font][size=11pt]20[/size][font=宋体][size=11pt]。为何这样行？因为如果我们从它最小数到最大数，这是在总和中最大差异的数字，因而这个数字和将是序列中的最大。[/size][/font]
[size=11pt]Q[/size][font=宋体][size=11pt]：哪些比特在[/size][/font][size=11pt]TPC/IP[/size][font=宋体][size=11pt]三个包中是握手？[/size][/font]
[size=11pt]A[/size][font=宋体][size=11pt]：它是[/size][/font][size=11pt]SYN[/size][font=宋体][size=11pt]、[/size][/font][size=11pt]SYN+ACK[/size][font=宋体][size=11pt]、[/size][/font][size=11pt]ACK[/size][font=宋体][size=11pt]。源想发送数据到目的地，第一步它发送[/size][/font][size=11pt]SYN[/size][font=宋体][size=11pt]去问目的地是否它准备好接收数据，然后目的地想去回答它是否准备好接收比特流于是它发送[/size][/font][size=11pt]SYN+ACK[/size][font=宋体][size=11pt]，然后源需要对该目的地来确认它得到的是请求于是源返回[/size][/font][size=11pt]ACK[/size][font=宋体][size=11pt]。[/size][/font]
[size=11pt]TCP[/size][font=宋体][size=11pt]是面向连接的而[/size][/font][size=11pt]UDP[/size][font=宋体][size=11pt]不是。[/size][/font][size=11pt]TCP[/size][font=宋体][size=11pt]：连接建立[/size][/font][size=11pt]->[/size][font=宋体][size=11pt]数据传输[/size][/font][size=11pt]->[/size][font=宋体][size=11pt]连接终止。[/size][/font]
[font=宋体][size=11pt]发起主机（客户端）发送一个同步[/size][/font][size=11pt](SYN[/size][font=宋体][size=11pt]标记设置[/size][/font][size=11pt])[/size][font=宋体][size=11pt]包发起一个连接。任何[/size][/font][size=11pt]SYN[/size][font=宋体][size=11pt]包拥有一个序号，该序号在[/size][/font][size=11pt]TCP[/size][font=宋体][size=11pt]段头是一个[/size][/font][size=11pt]32[/size][font=宋体][size=11pt]位区。比如说这个事物的该序号值是[/size][/font][size=11pt]x[/size][font=宋体][size=11pt]。[/size][/font]
[font=宋体][size=11pt]其它主机接收数据包，从客户端记录了[/size][/font][size=11pt]x[/size][font=宋体][size=11pt]的序号，并回复一个应答同步[/size][/font][size=11pt](SYN-ACK)[/size][font=宋体][size=11pt]。该应答号在[/size][/font][size=11pt]TCP[/size][font=宋体][size=11pt]段头是一个[/size][/font][size=11pt]32[/size][font=宋体][size=11pt]位区，它包含这个主机想要接收[/size][/font][size=11pt](x+1)[/size][font=宋体][size=11pt]的随后序号。该主机还发起了一个返回事物，这包含一个带有它自身值为[/size][/font][size=11pt]y[/size][font=宋体][size=11pt]的发起序号的[/size][/font][size=11pt]TCP[/size][font=宋体][size=11pt]段[/size][/font]
[font=宋体][size=11pt]。[/size][/font]
[font=宋体][size=11pt]发起主机答复以下一个序号[/size][/font][size=11pt](x+1)[/size][font=宋体][size=11pt]和一个简单的值为[/size][/font][size=11pt]y+1[/size][font=宋体][size=11pt]的应答号，它是其它主机的序号值[/size][/font][size=11pt]+1[/size][font=宋体][size=11pt]。[/size][/font]
[size=11pt].............................................[/size]
[size=11pt]Q[/size][font=宋体][size=11pt]：告诉我当你输入[/size][/font][size=11pt]www.google.com[/size][font=宋体][size=11pt]进入网页浏览器时发生什么[/size][/font]
[size=11pt]A1[/size][font=宋体][size=11pt]：解释[/size][/font][size=11pt]DNS[/size][font=宋体][size=11pt]通过[/size][/font][size=11pt]UPD[/size][font=宋体][size=11pt]端口[/size][/font][size=11pt]53[/size][font=宋体][size=11pt]的运作等等，[/size][/font][size=11pt]IP[/size][font=宋体][size=11pt]地址由[/size][/font][size=11pt]DNS[/size][font=宋体][size=11pt]返回[/size][/font][size=11pt]([/size][font=宋体][size=11pt]有时[/size][/font][size=11pt]ISP[/size][font=宋体][size=11pt]缓存这个[/size][/font][size=11pt]URL->IP[/size][font=宋体][size=11pt]映射，这节省访问[/size][/font][size=11pt]DNS[/size][font=宋体][size=11pt]的开销[/size][/font][size=11pt])[/size][font=宋体][size=11pt]，[/size][/font][size=11pt]HTTP GET[/size][font=宋体][size=11pt]请求是发送到[/size][/font][size=11pt]google.com[/size][font=宋体][size=11pt]服务器上，它返回[/size][/font][size=11pt]HTML[/size][font=宋体][size=11pt]格式的[/size][/font][size=11pt]google.com[/size][font=宋体][size=11pt]网页。[/size][/font]
[size=11pt]A2[/size][font=宋体][size=11pt]：[/size][/font][size=11pt]Google[/size][font=宋体][size=11pt]的[/size][/font][size=11pt]DNS[/size][font=宋体][size=11pt]服务器进行负载平衡，让用户能够最快地访问[/size][/font][size=11pt]Google[/size][font=宋体][size=11pt]的内容。实现这靠发送用户一群没有重载的[/size][/font][size=11pt]IP[/size][font=宋体][size=11pt]地址，并在地理上接近他们。每群有几千台服务器，并由该进群中的硬件在被连接到的集群进一步负载平衡，以发送请求到最少负载的网络服务器。[/size][/font]
[size=11pt]Q[/size][font=宋体][size=11pt]：[/size][/font][size=11pt]N[/size][font=宋体][size=11pt]线程[/size][/font][size=11pt].. n[/size][font=宋体][size=11pt]资源[/size][/font][size=11pt]..[/size][font=宋体][size=11pt]你使用什么协议以确保不会发生死锁？[/size][/font]
[size=11pt]A1[/size][font=宋体][size=11pt]：避免死锁用锁级别，每个线程将有不同的级别，高级别线程将能锁低级别线程而不是相反。[/size][/font]
[size=11pt]A2[/size][font=宋体][size=11pt]：避免一个时间有多余一个的锁。[/size][/font]
[size=11pt]A3[/size][font=宋体][size=11pt]：获得锁总是以同一次序。[/size][/font][size=11pt]A4[/size][font=宋体][size=11pt]：收缩同步段。[/size][/font]
[size=11pt]Q[/size][font=宋体][size=11pt]：你可以得到一个应用程序源码，当它运行时就会崩溃。在一个调试器中运行[/size][/font][size=11pt]10[/size][font=宋体][size=11pt]次后，你发现在同一点它不再崩溃。该程序是单线程并只使用[/size][/font][size=11pt]C[/size][font=宋体][size=11pt]标准库。什么编程错误会导致这个崩溃？你如何测试每一个？[/size][/font]
[size=11pt]A1[/size][font=宋体][size=11pt]：它将需要耗费时间或者随机数或者它做了记忆中讨厌的事或者它在[/size][/font][size=11pt]Windows[/size][font=宋体][size=11pt]下运行。[/size][/font]
[size=11pt]A2[/size][font=宋体][size=11pt]：可能在代码中有多条递归，它们导致一个堆栈溢出，导致“超出内存”异常。[/size][/font]
[size=11pt]A3[/size][font=宋体][size=11pt]：可能的原因可能是一个未初始化的指针[/size][/font][size=11pt]/[/size][font=宋体][size=11pt]变量被用。[/size][/font]
[size=11pt]Q[/size][font=宋体][size=11pt]：这是一个代码片段，如何使得该代码抛出[/size][/font][size=11pt]ArrayIndexOutOfBounds[/size][font=宋体][size=11pt]异常？[/size][/font]
[size=11pt]private static String[] list = null;[/size]
[size=11pt]public static String[] getArray(size) {[/size]
[size=11pt]list= new String[size];[/size]
[size=11pt]for (int i = 0; i < size; i++) {[/size]
[size=11pt]list[i] = "a" + i[/size]
[size=11pt]}[/size]
[size=11pt]return list;[/size]
[size=11pt]}[/size]
[size=11pt]A[/size][font=宋体][size=11pt]：如果两个线程并行执行还用值[/size][/font][size=11pt]10[/size][font=宋体][size=11pt]和[/size][/font][size=11pt]7[/size][font=宋体][size=11pt]调用这个方法，第一个线程将创建[/size][/font][size=11pt]10[/size][font=宋体][size=11pt]维数组，然后第二个线程将重新初始化[/size][/font][size=11pt]7[/size][font=宋体][size=11pt]维同样的静态数组，接着第一个线程将运行这个数组从[/size][/font][size=11pt]0[/size][font=宋体][size=11pt]到[/size][/font][size=11pt]9[/size][font=宋体][size=11pt]还放值在里面，然而数组维数现在是[/size][/font][size=11pt]7[/size][font=宋体][size=11pt]于是在[/size][/font][size=11pt]list[7][/size][font=宋体][size=11pt]它将抛出该异常。[/size][/font]
[size=11pt]Q[/size][font=宋体][size=11pt]：写一函数[/size][/font][size=11pt]f(a,b)[/size][font=宋体][size=11pt]，它带有两个字符串参数并返回一串字符，该字符串只包含在两个串中都有的并按照在[/size][/font][size=11pt]a[/size][font=宋体][size=11pt]中的顺序。写一个版本算法复杂度[/size][/font][size=11pt]O(N^2)[/size][font=宋体][size=11pt]和一个[/size][/font][size=11pt]O(N)[/size]
[size=11pt]A[/size][font=宋体][size=11pt]：[/size][/font][size=11pt]private static String match(String a, String b) { [/size]
[size=11pt]String result = ""; [/size]
[size=11pt]Set lettersSet = new HashSet(26); [/size]
[size=11pt]for (int i=0; i[/size]
[size=11pt]lettersSet.add(new Character(b.charAt(i))); [/size]
[size=11pt]} [/size]
[size=11pt]for (int i=0; i[/size]
[size=11pt]if (lettersSet.contains(new Character(a.charAt(i)))) { [/size]
[size=11pt]result=result+a.charAt(i); [/size]
[size=11pt]} [/size]
[size=11pt]} [/size]
[size=11pt]return result; [/size]
[size=11pt]}[/size]
...............................................................................................................
ccweichun 2008-6-16 09:59
需要面试几次，一共就这些题目吗？是全英文吗？牛人？