var _gaq = _gaq || []; _gaq.push(['_setAccount', 'UA-333696-1']); _gaq.push(['_trackPageview']); _gaq.push(['_trackPageLoadTime']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })();
  • 2008年01月20日

    Google面试题集

    分类:

    原文:2 Egg ProblemGoogle Interview Questions Part 1Part 2Part 3Part 4Part 5Part 6Part 7Part 8Part 9

     

    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:在C中你如何调整比特来找出一个机器内存内的堆栈向上或向下增长?

    A:初始化一个局部变量,用这个局部变量调用另一项功能。查看那项功能的地址并比较,如果该功能的局部变量更高了,堆栈远离地址位0增长;如果该功能的局部变量更低了,堆栈向地址位0增长。

     

    Q:哪些比特在TPC/IP三个包中是握手?

    A:它是SYNSYN+ACKACK。源想发送数据到目的地,第一步它发送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:快速乘法(Karatsuba)算法是什么?

    A:它的算法是处理N位的两个大正数相乘,算法复杂度O(N^2)。思想主要是将乘法转化为加法来计算以减少计算复杂度。

     

    Q:告诉我当你输入www.google.com进入网页浏览器时发生什么

    A1:解释DNS通过UPD端口53的运作等等,IP地址由DNS返回(有时ISP缓存这个URL->IP映射,这节省访问DNS的开销)HTTP GET请求是发送到google.com服务器上,它返回HTML格式的google.com网页。

    A2GoogleDNS服务器进行负载平衡,让用户能够最快地访问Google的内容。实现这靠发送用户一群没有重载的IP地址,并在地理上接近他们。每群有几千台服务器,并由该进群中的硬件在被连接到的集群进一步负载平衡,以发送请求到最少负载的网络服务器。

     

    QN线程.. 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[i] = "a" + i

    }

    return list;

    }

    A:如果两个线程并行执行还用值107调用这个方法,第一个线程将创建10维数组,然后第二个线程将重新初始化7维同样的静态数组,接着第一个线程将运行这个数组从09还放值在里面,然而数组维数现在是7于是在list[7]它将抛出该异常。

     

    Q:写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序。写一个版本算法复杂度O(N^2)和一个O(N)

    Aprivate 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;

    }

     

    Q:

    1

    1 1

    2 1

    1 2 1 1

    1 1 1 2 2 1 下一个数是什么?

    序列的下一个数是什么10, 9, 60, 90, 70, 66, ?

    A) 96

    B) 1000000000000000000000000000000000\

    0000000000000000000000000000000000\

    000000000000000000000000000000000

    C) Either of the above

    D) None of the above

    A:第一个问题的答案:

    one

    one one (上一行有一次数字)

    two ones (上一行有两次数字1)

    one two one one

    one one one two two ones

    three ones two twos one one(3 1 2 2 1 1)

    第二个问题的答案:

    ten, nine, sixty, ninety, seventy, sixty-six,

    每个数比前面的数多一个字母,103个字母,94个字母等。

    既然sixty-six(66)8个字母下个数字需要有9个字母,它就是ninety-six(96)

     

    Q:有8块石头它们彼此相似除了一个比其它更重。为找出它,给你一个天平。找出最重的石头需要最少的称量次数是多少?

    A:划分石头成子集象(3,3,2)。使用天平去称量(3,3),如果该天平保持平衡,则重的是在剩下的2个中,再次使用天平从这2个中来找出那个重(总计称量2次)。如果天平不平衡在称量(3,3), 选石头子集比另一边更重的,把它分成子集(1,1,1),使用天平称量首先的2个,若保持平衡,剩下的石头则是更重的,否则高翘那边的就是更重的(总计称量2次)。 

     

    Q: 只给你二个鸡蛋,你能上100层楼,你想知道鸡蛋的硬度。鸡蛋可能很硬或很脆弱,如果鸡蛋从第m层掉下而没破裂,而从第m+1层掉下就破裂了,那么这个鸡蛋的硬度就是m。你需要找出这个m和在最坏情况下最少试验次数。(经典鸡蛋问题)

    A: 计算机学生可能会首先用第一个鸡蛋做二分搜索(O(logN))再用第二个递增做线性搜索(O(N)),最后必将用线性搜索结束因为用第二个鸡蛋时你无法确定最高一层。因此,问题变为如何使用第一个鸡蛋来减少线性搜索。

    于是如果第一个蛋破裂在最高点我们要扔x-1次并且我们必须从x层高扔第一个蛋。现在如果第一个蛋的第一次扔没有破裂,如果第一个蛋在第二次扔破了我们要扔x-2次第二个蛋。假如16是答案,我需要扔16次才能找到答案。来验证一下是否可以从16层开始扔,首先从16层扔如果它破裂了,我们尝试所有其下的楼层从115;如果没破我们还能扔15次,于是我们将从32(16+15+1)再扔。原因是如果它在32层破裂我们能尝试其下所有楼层从1731最坏扔第二个蛋14次(总共能扔16次了)。如果32层并没破,我们还剩下能扔13次,依此类推得:

    1 + 15 16 如果它在16层破裂,从115层最坏扔15次第二个蛋

    1 + 14 31 如果它在31层破裂,从1730层最坏扔14次第二个蛋

    1 + 13 45.....

    1 + 12 58

    1 + 11 70

    1 + 10 81

    1 + 9  91

    1 + 8  100 在最后我们能轻易地做到因为我们有足够多扔的次数来完成任务

    从上表我们能看到最佳的一个在最后一步将需要0次线性搜索。

    能把上述规律写为: (1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.

    1+p=q上述式子变为q(q+1)/2>=100,100解答得到q=14

    扔第一个蛋从层1427395060697784909599100直到它破裂,再开始扔第二个蛋。最坏情况只需14次。

    分享到: