到google面试 google的21道面试问题

10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa》、《今日物理》等几本专业杂志上，刊登了一份“Google实验室能力倾向测试”。
试卷开头，蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观，并成为我们其中一员”。

我看了这些题目，虽然古怪，但是也不算有困难，有兴趣的人可以做完了邮寄给google公司，也许会得到一个工作机会呢。

注：不要向我要答案。

1.Solvethiscrypticequation,realizingof
coursethatvaluesforMandEcouldbe
interchanged.Noleadingzerosareallowed.

WWWDOT-GOOGLE=DOTCOM

2.Writeahaikudescribingpossiblemethods
forpredictingsearchtrafficseasonality.

3.
1
11
21
1211
111221

Whatisthenextline?

4.Youareinamazeoftwistylittlepassages,
allalike.Thereisadustylaptopherewitha
weakwirelessconnection.Therearedull,
lifelessgnomesstrollingabout.Whatdost
thoudo?

A)Wanderaimlessly,bumpinginto
obstaclesuntilyouareeatenbyagrue.
B)Usethelaptopasadiggingdeviceto
tunneltothenextlevel.
C)PlayMPoRPGuntilthebatterydies
alongwithyourhopes.
D)Usethecomputertomapthenodes
ofthemazeanddiscoveranexitpath.
E)EmailyourresumetoGoogle,tellthe
leadgnomeyouquitandfindyourself
inwholedifferentworld.

5.What'sbrokenwithUnix?
Howwouldyoufixit?

6.OnyourfirstdayatGoogle,youdiscover
thatyourcubiclematewrotethetextbook
youusedasaprimaryresourceinyourfirst
yearofgraduateschool.Doyou:

A)Fawnobsequiouslyandaskifyou
canhaveanautograph.
B)Sitperfectlystillanduseonlysoft
keystrokestoavoiddisturbingher
concentration.
C)Leaveherdailyofferingsofgranola
andEnglishtoffeefromthefoodbins.

D)Quoteyourfavoriteformulafromthe
textbookandexplainhowit'snow
yourmantra.
E)Showherhowexample17bcould
havebeensolvedwith34fewerlines
ofcode.
7.WhichofthefollowingexpressesGoogle□
over-archingphilosophy?

A)"I'mfeelinglucky"
B)"Don'tbeevil"
C)"Oh,Ialreadyfixedthat"
D)"Youshouldneverbemorethan
50feetfromfood"
E)Alloftheabove

8.Howmanydifferentwayscanyoucoloran
icosahedronwithoneofthreecolorson
eachface?

Whatcolorswouldyouchoose?

9.Thisspaceleftintentionallyblank.Pleasefillit
withsomethingthatimprovesuponemptiness.

10.Onaninfinite,two-dimensional,rectangular
latticeof1-ohmresistors,whatisthe
resistancebetweentwonodesthatarea
knight'smoveaway?

11.It's2PMonasunnySundayafternooninthe
BayArea.You'reminutesfromthePacific
Ocean,redwoodforesthikingtrailsandworld
classculturalattractions.Whatdoyoudo?

12.Inyouropinion,whatisthemostbeautiful
mathequationeverderived?

13.WhichofthefollowingisNOTanactual
interestgroupformedbyGoogleemployees?

A.Women'sbasketball
B.Buffyfans
C.Cricketeers
D.Nobelwinners
E.Wineclub

14.Whatwillbethenextgreatimprovementin
searchtechnology?

15.Whatistheoptimalsizeofaprojectteam,
abovewhichadditionalmembersdonot
contributeproductivityequivalenttothe
percentageincreaseinthestaffsize?
A)1
B)3
C)5
D)11
E)24

16.GivenatriangleABC,howwouldyouuseonly
acompassandstraightedgetofindapointP
suchthattrianglesABP,ACPandBCPhave
equalperimeters?(AssumethatABCis
constructedsothatasolutiondoesexist.)

17.Considerafunctionwhich,foragivenwhole
numbern,returnsthenumberofonesrequired
whenwritingoutallnumbersbetween0andn.
Forexample,f(13)=6.Noticethatf(1)=1.What
isthenextlargestnsuchthatf(n)=n?

18.What'sthecoolesthackyou'veeverwritten?

19.'Tisknowninrefinedcompany,thatchoosing
KthingsoutofNcanbedoneinwaysas
manyaschoosingNminusKfromN:IpickK,
youtheremaining.

Findthoughacoolerbijection,whereyoushow
aknackuncanny,ofmakingyourchoicescontain
allKofmine.Oh,forpedantry:letKbenomore
thanhalfN.

20.Whatnumbercomesnextinthesequence:
10,9,60,90,70,66,?

A)96
B)1000000000000000000000000000000000
0000000000000000000000000000000000
000000000000000000000000000000000
C)Eitheroftheabove
D)Noneoftheabove

21.In29wordsorfewer,describewhatyou
wouldstrivetoaccomplishifyouworked
atGoogleLabs.

10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa》、《今日物理》等几本专业杂志上，刊登了一份“Google实验室能力倾向测试”。

试卷开头，蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观，并成为我们其中一员”。

测试只有21个问题。道道刁钻，剑走偏锋。

实打实的数学题，比如“用3种颜色为20面体上色，每个面一种颜色，有多少种组合？你会选择哪3种颜色”。

毫无头绪的主观题：“什么是世上最美的数学方程式？”

和数不清的自由发挥题：“以下空白，填上点好东西”或者“用你的画笔，改变这张考卷的外观”……

全球顶尖高校的BBS上，都流传着这份测试题，和各式各样确定或不确定的答案。

“几天之内，Google总部收到了成千上万份答案。”Google的副总裁艾伦尤斯塔斯说，“其中有很多来自经济学家、教授和高智商人士。他们无意应聘，只想挑战一下自己的能力。”

重金悬赏“金头脑”

Google拨出5万美元基金，等待投出答案的天才程序员。

只要冲到最后一轮淘汰赛，Google就用这笔钱，招待他们去Google加州的“梦幻总部”面试。不入选，也能免费玩一遭，何乐不为。

说到“手面奢侈”，Google当仁不让。

除了善待自个儿的员工，高额分红配股，把他们像托儿所小孩一样照顾，Google每年还在网络上“现金悬赏”，招聘“猎人”编写高难度程序。

去年，“揭皇榜”的程序高手SergioSan鄄cho，用一个小程序，换来1万美元报酬。

这个阿根廷程序员乐开了花，他在公司工作半年，都赚不到这个数字。

Google惯用“整蛊题”

Google上一轮招聘，今年夏天刚结束。

用的也是一道“科学麻瓜”看不懂的“整蛊题”，而且，堂而皇之挂在硅谷各大地铁站上。9月底，3块15米长的米色广告牌上，简简单单刷着“(在‘e’的数列中所能找到的第一个十位数质数).com”，没有公司名也没有任何广告词。

花了几秒钟，路人才明白，这是一道数学题。自然常数e(2.718281828……)的第一个十位数质数，是目标网站的名字。

好奇分子忍不住用Google搜索起答案来，压根儿不晓得这就是Google出的“硬骨头”考题。

不少人后来在规定时间内，登录上了www.7427466391.com。然而，那不是梦寐以求的终点站，Google恶作剧似的，为“高手”们在半山腰设了个休息的小凉亭。

www.7427466391.com里，贴出一条更令人头疼的数学问题，答出这个问题，能得到进入下一个网页的密码。

跑完数学“马拉松”，7500个“幸存者”走入Google实验室网页，成功投出简历。最后，Google只要了50个人。“光以广告而论，Google也算得上高段！”

波士顿一家广告公司的高级副总裁弗里茨库恩分析，“目标人群看到广告后会想，‘这是我的语言，那是冲着我来的’；对其他人而言，广告也使Google的形象大大提升。他们可能会想，‘我是得不到这份工作的了。不过，在那儿工作的人真聪明’。”

Google测试考的就是脑筋

试着证明WWWDOT-GOOGLE=DOTCOM用俳句(一种日本短诗，每句有一个与季节有关的词)来描述各种模型，借此预测网络搜索流量的季节性变化。

你落入一个迷宫，回旋不断的走廊。手里有一台堆满灰尘的手提电脑，可以无线上网。周围，许多无生命的侏儒徘徊走动。这种情况下，你会如何做？

A)无目的地徘徊，不停走入死胡同，然后被迷宫里面的妖怪吃掉。

B)用手提电脑当铲子，打穿地板直接进入游戏下一关。

C)玩网络游戏《魔法奇兵》，直到电池耗尽。

D)利用计算机，找到迷宫的节点，发现准确出路。

E)把你的简历寄给Google，告诉迷宫里领头的妖怪，你要退出游戏。然后，发现你回到了现实世界。

Unix有什么问题？你会如何补救它？

你在Google工作的第一天，发现你同寝室的室友，曾写过一本书。你研究生一年级时，这本书是你最重要的参考资料。你会：A)求他帮你签个名。B)不改坐姿，却放轻打字声音，尽量避免影响他。

C)把你每天吃的麦片和咖啡，留给他吃。

D)引用他那本书中间，你最喜欢的程式，告诉他这则方程给了你多少启发。

E)让他看看，你可以用不到34句语句，完成一个高难度程序。

以下哪个最好地表达了Google的企业文化？

A)“我感觉挺幸运”

B)“别干坏事”

C)“哦，我已经完成了任务”

D)“你身边10米以内，必定能找到食物”


E)以上皆是用1欧姆的电阻，组成无限大的放行点阵，问“象棋跳马步”(“日”字对角点)两点之间的电阻是多少？

下午2点，旧金山著名的湾区。你可以选择去阳光海岸、国家公园的红杉林里徒步旅行，或者参观城市里的文化景观。你会怎么做？

搜索技术的下一个革命性突破是什么？

一个技术研究小组的最优化人员组合是几个人？一旦超过这个数字，每增加一个研究员，平均生产力就会相应下降：A)1B)3C)5D)11E)24三角形ABC，用圆规和尺，找出点P，保证三角形ABP、ACP和BCP周长相等。

你写过最酷的程序是什么？

找出此数列的下一个:10,9,60,90,70,66?A)96B)10的100次方C)A或者BD)以上皆否用少于29个词，描述你能带给Google实验室的贡献。


2007Google笔试题来自浙江大学BBS

一、单选

1、80x86中，十进制数-3用16位二进制数表示为？

2、假定符号-、*、$分别代表减法、乘法和指数运算，且

1)三个运算符优先级顺序是：-最高，*其次，$最低；

2)运算符运算时为左结合。请计算3-2*4$1*2$3的值：

(A)4096，(B)-61，(C)64，(D)-80，(E)512

3、下列伪代码中，参数是引用传递，结果是？

calc(double p, double q, double r){q=q-1.0;r=r+p}
main(){
　　double a = 2.5, b = 9.0;
　　calc(b-a, a, a);
　　print(a);
}
(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.5

4、求输出结果：

int foo(int x, int y){
　　if(x <=0 || y <= 0) return 1;
　　return 3 * foo(x - 1, y / 2);
}
printf("%d\n", foo(3, 5));
(A)81 (B)27 (C)9 (D)3 (E)1

5、下列哪个数据结构在优先队列中被最广泛使用？

(A)堆 (B)数组 (C)双向链表 (D)图 (E)向量

6、以下算法描述了一个在n国元素的双向链表中找到第k个元素的方法（k >= 1且k <= n）：

如果k <= n - k，从链表开始往前进k-1个元素。

否则，从终点出发，往回走n - k个元素。

这个算法的时间代价是？

(A)θ(nlogn) (B)θ(max{k, n - k}) (C)θ(k + (n - k))

(D)θ(max{k, k - n}) (E)θ(min{k, n - k})

7、有一个由10个顶点组成的图，每个顶点有6个度，那么这个图有几条边？

(A)60 (B)30 (C)20 (D)80 (E)90

8、正则表达式L = x*(x|yx+)。下列哪个字符串不符合L

(A)x (B)xyxyx (C)xyx (D)yxx (E)yx

9、为读取一块数据而准备磁盘驱动器的总时间包括

(A)等待时间 (B)寻道时间 (C)传输时间 (D)等待时间加寻道时间

(E)等待时间加寻道时间加传输时间

二、算法

1、打印出一个二叉树的内容。

2、在一个字符串中找到第一个只出现一次的字符。如abaccdeff，输出b。

3、给定一个长度为N的整数数组（元素有正有负），求所有元素之和，最大的一个子数组。分析算法时空复杂度。不必写代码。


附上动态规划做法的答案:

最大子序列

问题：

给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大

例如：整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推，我们就可以得到下面这个算法：

int max_sub(int a[],int size)
{
　　int i,j,v,max=a[0];
　　for(i=0;i<size;i++)
　　{
　　　　v=0;
　　　　for(j=i;j<size;j++)
　　　　{
　　　　　　v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]
　　　　　　　　if(v>max)
　　　　　　　　　max=v;
　　　　}
　　}
　　return max;
}


那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：
int max_sub2(int a[], int size)
{
　　int i,max=0,temp_sum=0;
　　for(i=0;i<size;i++)
　　{
　　　　　　temp_sum+=a[i];
　　　　　　if(temp_sum>max)
　　　　　　　　max=temp_sum;
　　　　　　else if(temp_sum<0)
　　　　　　　　temp_sum=0;
　　}
　　return max;
}


在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum 将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。

--------------------------------------------------------------------

1、 两个二进制数的异或结果

2、 递归函数最终会结束，那么这个函数一定（不定项选择）：

　　1. 使用了局部变量
　　2. 有一个分支不调用自身
　　3. 使用了全局变量或者使用了一个或多个参数


3、以下函数的结果？
int cal(int x)
{
　　　　if(x==0)
return 0;
　　　　else
　　　　　　return x+cal(x-1);
}


4、 以下程序的结果？

void foo(int*a, int* b)
{
　　　　*a = *a+*b;
　　　　*b = *a-*b;
　　　　*a = *a-*b;
}
void main()
{
　　　　int a=1, b=2, c=3;
　　　　foo(&a,&b);
　　　　foo(&b,&c);
　　　　foo(&c,&a);
　　　　printf("%d, %d, %d", a,b,c);
}

5、下面哪项不是链表优于数组的特点？

　　1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小

6、T(n) = 25T(n/5)+n^2的时间复杂度？

7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？

8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？

　　1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)*

9、如何减少换页错误？

　　1. 进程倾向于占用CPU
　　2. 访问局部性（locality of reference）满足进程要求
　　3. 进程倾向于占用I/O
　　4.使用基于最短剩余时间（shortest remaining time）的调度机制
　　5. 减少页大小


10、实现两个N*N矩阵的乘法，矩阵由一维数组表示

11、找到单向链表中间那个元素，如果有两个则取前面一个

12、长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。

------------------------------------------------------------------

Google笔试是没有门槛的。这样说是因为Google根本没有限制笔试的人数，开了N个教室，让N多人参加……不过笔试本身却有门槛，看了题目就知道。

　　本来想上午写写的，但是，嗯，出于攒人品的目的，还是等到现在才写——现在，面试通知已经发过，很显然我又被无视了……OK，那也不错，我也没怎么准备这些东西呢，倒不是说我不重视，而是事情太多……唔，多少算是一种经验了。

　　回来说说昨天的笔试。题目的量并不大，除了几个单选题，剩下就是三个编程或算法题。单选就不说了，考得比较基础，涉及C语言常识、数据结构、文法、操作系统，主要说说大题。

　　大题虽然题型不一，但都有一个重要特点：考递归。精确点说，我每一题都用到了递归。

　　第一个的题目（嗯，记的不是很完整）：
在一棵（排序？）二叉树中搜索指定值，数据结构定义为（唉唉，数据结构的具体名字都不记得了，my god）：
struct Node
{
    Node * lnext;
    Node * rnext;
    int value;
};
函数定义为（情况同上，啥都记不清了）：
Node * search(Node * root, int value)
{
}
实现这个search函数。

用递归，经典的树的遍历，pass先。

第二个的题目：
计算Tribonaci队列（嗯，九成九记错了那个单词……），规则是T(n) = T(n - 1) + T(n - 2) + T(n -3)，其中T(0) = T(1) = 1，T(2) = 2。
函数定义：
int Tribonaci(int n) {
}
备注，不考虑证整数溢出，尽可能优化算法。

　　这一题我一看就知道要考什么，很显然的递归定义，但也是很显然的，这里所谓的优化是指不要重复计算。

　　简单的说，在计算T(n)的时候要用到T(n - 1)、T(n - 2)和T(n - 3)的结果，在计算T(n - 1)的时候也要用到T(n - 2)和T(n - 3)的结果，所以在各项计算的时候必须把以前计算的结果记录下来，去掉重复计算。这里用到的一点小技巧就是要新写一个函数用来做这种事情，嗯，看看我写的代码吧！

/**
  Get the value of T(n - 1), and retrieve the result of
  T(n - 2) and T(n - 3).
  @param[in] n The n in T(n).
  @param[out] mid Value of T(n - 2).
  @param[out] right Value of T(n - 3).
  @return Value of T(n - 1).
*/
int find_trib(int n, int & mid, int & right)
{
    if (3 == n)
    {
        mid = 1;
        right = 1;
        return 2;
    }
    else
    {
        int temp;
        mid = find_trib(n - 1, right, temp);
        return mid + right + temp;
    }
}

/**
  Find value of T(n).
  @param[in] The n in T(n).
  @return Value of T(n).
  @note T(n) = T(n - 1) + T(n - 2) + T(n - 3) (n > 2)
        T(0) = T(1) = 1, T(2) = 2.
*/
int tribonaci(int n)
{
    if (n < 0)
    {
        // Undefined feature.
        return 0;
    }

    if (0 == n || 1 == n)
    {
        return 1;
    }

    if (2 == n)
    {
        return 2;
    }

    int mid, right;
    int left = find_trib(n, mid, right);
    return left + mid + right;
}

　　啊啊，对了，答卷的时候我可没心情写注释……刚才到VC.Net 2003上测试了一下，貌似没有啥问题。唉，看来我多少还是懂一点算法的……

　　第三个的题目：
　　在一个无向图中，寻找是否有一条距离为K的路径，描述算法即可，不用实现，分析算法的时间和空间复杂度，尽量优化算法。

　　OK，这个就是传说中的软肋了………………我也就不把自己的答案写出来了（丢人啊），虽然后来仔细想想，我那个挫挫的方法也能够用……只是效率……

　　That's all.

-----------------------------------------------------------

最大的互联网公司Google的一份面试题集，看看你是否能够回答出来。其中很多问题都是开放式的，正确的解答有许多种，所以在这里就不提供答案了。
几星期前，一个朋友接受了Google公司的面试，他透露了面试中的一些问题。顺便，我把从其他几个曾经面试过的人那里听来的内容也整理在一起。最大的互联网公司Google的一份面试题集，看看你是否能够回答出来。其中很多问题都是开放式的，正确的解答有许多种，所以在这里就不提供答案了。

问题如下：

一辆学校班车里面能装多少个高尔夫球？

你被缩小到只有硬币厚度那么点高（不是压扁，是按比例缩小），然后被扔到一个空的玻璃搅拌器中，搅拌刀片一分钟后就开始转动。你怎么办？

要是让你清洗整个西雅图的所有窗子，你会收取多少费用？

怎么才能识别出电脑的内存堆栈是向上溢出还是向下溢出？

你要向你8岁的侄子解释什么是数据库，请用三句话完成。时钟的指针一天内会重合几次？

你需要从A地去B地，但你不知道能不能到，这时该怎么办？

好比你有一个衣橱，里面塞满了各种衬衫，你会怎么整理这些衬衫，好让你以后找衬衫的时候容易些？

有个小镇有100对夫妇，每个丈夫都在欺骗他的妻子。妻子们都无法识破自己丈夫的谎言，但是她们却能知道其他任何一个男人是否在撒谎。镇上的法律规定不准通奸，妻子一旦证明丈夫不忠就应该立刻杀死他，镇上所有妇女都必须严格遵守这项法律。有一天，镇上的女王宣布，至少有一个丈夫是不忠的。这是怎么发生的呢？

在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就生下一个，直到孩子是男孩为止。这样的国家，男女比例会是多少？

如果在高速公路上30分钟内到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少 （假设为常概率条件下）如果你看到钟的时间是3:15，那一刻时针和分针的夹角是多少？

（肯定不是0度！）4个人晚上要穿过一座索桥回到他们的营地。可惜他们手上只有一支只能再坚持17分钟的手电筒。通过索桥必须要拿着手电，而且索桥每次只能撑得起两个人的份量。这四个人过索桥的速度都不一样，第一个走过索桥需要1分钟，第二个2分钟，第三个5分钟，最慢的那个要10分钟。他们怎样才能在17分钟内全部走过索桥？

你和朋友参加聚会，包括你们两人在内一共有10个人在场。你朋友想跟你打赌，说这里每有一个人生日和你相同，你就给他1元，每有一个人生日和你不同，他给你2元。你会接受么？

全世界有多少个钢琴调音器？

你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。怎样能够用天平仅称两次将那个重一些的球找出来。有5个海盗，按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决，如果多数反对，那他就会被杀死。他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死？（提示：有一个海盗能拿到98%的金币）

你觉得自己有把握去Google工作了么？