Google面试题集

xiaoshancom · 发表于 2008-1-20 16:00:06

原文：http://fafeng.blogbus.com/logs/14168877.html
本作品采用知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议授权。

Q：你有一序列数字，其中有些是负数，有些是正数，从该列中找出最大和的子序列，要求算法复杂度O(N)。比如：-5, 20, -4, 10, -18，子列[20, -4, 10]具有最大和26。
A：首先你应该通过序列建立一个新的序列，它值为包含它在内以及之前序列之和。举例来说如果序列为：[-7 12 -5 13 -2]，那么新序列将是：[-7 5 0 13 11]。该子列占有的最大序列和是在新序列中从最小数字索引加1(在这个例中-7(索引0))是最小，于是我们从5(索引1)开始直到该列表中的最大数13(索引3)，于是结果(12, -5, 13)总和20。为何这样行？因为如果我们从它最小数到最大数，这是在总和中最大差异的数字，因而这个数字和将是序列中的最大。

Q：哪些比特在TPC/IP三个包中是握手？
A：它是SYN、SYN+ACK、ACK。源想发送数据到目的地，第一步它发送SYN去问目的地是否它准备好接收数据，然后目的地想去回答它是否准备好接收比特流于是它发送SYN+ACK，然后源需要对该目的地来确认它得到的是请求于是源返回ACK。
TCP是面向连接的而UDP不是。TCP：连接建立->数据传输->连接终止。
发起主机（客户端）发送一个同步(SYN标记设置)包发起一个连接。任何SYN包拥有一个序号，该序号在TCP段头是一个32位区。比如说这个事物的该序号值是x。
其它主机接收数据包，从客户端记录了x的序号，并回复一个应答同步(SYN-ACK)。该应答号在TCP段头是一个32位区，它包含这个主机想要接收(x+1)的随后序号。该主机还发起了一个返回事物，这包含一个带有它自身值为y的发起序号的TCP段
。
发起主机答复以下一个序号(x+1)和一个简单的值为y+1的应答号，它是其它主机的序号值+1。
.............................................

Q：告诉我当你输入www.google.com进入网页浏览器时发生什么
A1：解释DNS通过UPD端口53的运作等等，IP地址由DNS返回(有时ISP缓存这个URL->IP映射，这节省访问DNS的开销)，HTTP GET请求是发送到google.com服务器上，它返回HTML格式的google.com网页。
A2：Google的DNS服务器进行负载平衡，让用户能够最快地访问Google的内容。实现这靠发送用户一群没有重载的IP地址，并在地理上接近他们。每群有几千台服务器，并由该进群中的硬件在被连接到的集群进一步负载平衡，以发送请求到最少负载的网络服务器。

Q：N线程.. n资源..你使用什么协议以确保不会发生死锁？
A1：避免死锁用锁级别，每个线程将有不同的级别，高级别线程将能锁低级别线程而不是相反。
A2：避免一个时间有多余一个的锁。
A3：获得锁总是以同一次序。A4：收缩同步段。

Q：你可以得到一个应用程序源码，当它运行时就会崩溃。在一个调试器中运行10次后，你发现在同一点它不再崩溃。该程序是单线程并只使用C标准库。什么编程错误会导致这个崩溃？你如何测试每一个？
A1：它将需要耗费时间或者随机数或者它做了记忆中讨厌的事或者它在Windows下运行。
A2：可能在代码中有多条递归，它们导致一个堆栈溢出，导致“超出内存”异常。
A3：可能的原因可能是一个未初始化的指针/变量被用。

Q：这是一个代码片段，如何使得该代码抛出ArrayIndexOutOfBounds异常？
private static String[] list = null;
public static String[] getArray(size) {
list= new String[size];
for (int i = 0; i < size; i++) {
list = "a" + i
}
return list;
}
A：如果两个线程并行执行还用值10和7调用这个方法，第一个线程将创建10维数组，然后第二个线程将重新初始化7维同样的静态数组，接着第一个线程将运行这个数组从0到9还放值在里面，然而数组维数现在是7于是在list[7]它将抛出该异常。

Q：写一函数f(a,b)，它带有两个字符串参数并返回一串字符，该字符串只包含在两个串中都有的并按照在a中的顺序。写一个版本算法复杂度O(N^2)和一个O(N)
A：private static String match(String a, String b) {
String result = "";
Set lettersSet = new HashSet(26);

for (int i=0; i
lettersSet.add(new Character(b.charAt(i)));

}

for (int i=0; i
if (lettersSet.contains(new Character(a.charAt(i)))) {
result=result+a.charAt(i);
}
}
return result;
}
...............................................................................................................