1. 异或
1^1=0
0^0=0
1^0=1
0^1=1
2. 斐波那契数列(Fibonacci)
3.存储空间上不具有优势
4. 由“主定理”
T(n)=25T(n/5) + n
2
a=25 b=5 f(n)=n
2
log
ba=2
将n
logba与f(n)比较： 相等
则时间复杂度为O(n
2logn)
1.
2.
3
#include <iostream>
#include <limits>
using namespace std;
int foo(int arr[], int n)
{
int max = numeric_limits<int>::min();
//cout << max << "\n";
for(int i = 0; i < n; i++)
{
int product = 1;
for(int j =0; j < n; j++)
{
if(j != i )
product *= arr[j];
}
max = product > max ? product : max;
}
return max;
}
int main()
{
int arr[4] = { -1, -5, 2, 3};
cout << foo(arr, 4) << "\n";
return 0;
}
时间复杂度分析:
总共的操作步骤 n*{[n+(n-1)]+1}=2n2
时间复杂度为O(n2)
空间复杂度为O(1) 4*sizeof(int)
改进算法：
Google笔试集锦
Google笔试集锦
选择题+三道算法题
选择题没什么难的 最后一道考的数据库使用什么存储结构不会做。。
算法题
第一题没什么好说
第二题可破
Google笔试集锦
Google笔试集锦
选择题+三道算法题
选择题没什么难的 最后一道考的数据库使用什么存储结构不会做。。
算法题
第一题没什么好说
第二题可破坏一个数组A[0..N-1]的条件下使用最少的内存判断是否存在相同的元素
我的做法是堆排序 时间O(NlogN) 空间O(1) 复杂度上来看应该最优了
第三题已知每个点的父节点，求这棵树的最大独立集
用递归求解 类似动态规划 但是不存在重叠子状态 经典算法问题了
预处理每个节点的子节点存在一张表里
时间O(N）空间O(N）
大家做的结果是这样吗？
发信站: 饮水思源 (2006年10月11日03:06:04 星期三), 站内信件
开章明义，我是个废人，上来积攒rp了。
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
现在后悔只选了北京和上海的SWE了。
不过反正……也不指望了。。。
笔试题目：9道单选+3道问答
时间：100分钟
我做的是B卷。
单选题：
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
2，不记得了。。也是不需要思考的题目。。
3，大概是如下的函数：
int someFunc(int x){
if (x == 0)
return 0;
else
return x + someFunc(x - 1);
}
问这个计算的是什么。。。
4，不记得了。。不需要思考吧。。
5，不记得了。。不需要思考吧。。
6，参见2，4，5。。
7，似乎需要思考一下。。
8，问链表结构和数组相比的优势不包括哪项，
包括：
插入的时间
删除的时间
存储空间
剩下两个不记得了。。
9，如下函数：
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
问T(n)随n的增长。
选项大概是这样的：
O(n^2)，O(n^2logn)等等的。。
问答：
1，写两个N*N的矩阵的乘法，给出了C的格式，你可以选择你喜欢的语言去写。。
int* multi(int* a1, int* a2, int N){
}
2，寻找一个单向链表的中项，如果存在两个则返回前一个。给出了C的格式，同样你可
以选择。。。。
struct {
Node* next;
int value;
} Node;
Node* someFunc(Node* head){
}
3，给一个长度为n的整数数组，只允许用乘法不允许用除法，计算任意(n-1)个数的组合
乘积中最大的一组。。。写出算法的时空复杂度。
ps：怀疑这道题目出错啦。。虽然我也做错了。。。。。。
一些补充：
1，问答的第一题是google上学期 intern的大题原题；
2，google很喜欢考链表，无论intern的面试以及两次的笔试都有这样的题目；
3，google一般大题第三道都是写算法的时空复杂度；
4，选择题基本上偏简单，但是要做得准确率高似乎并不那么容易；
5，根据传言，小道消息，人云亦云以及以讹传讹，google的高速审卷政策来源于审卷时
以选择题为主，如果你全对啦，那么恭喜你pass啦；如果你错了好几道，那么下次努力
吧，如果还有下次。。。大题基本是做参考的。。。
6，选择题很多记不清了，因为一遍做下来的，回去随便扫了两眼。。。加上过了这几个
小时，记不得了。希望大家补充修正以及修改。。。
7，google会在11号开始3天内发面试通知，据小道消息等等，有四轮面试。bless大家~~
输入a_1, a_2, ..., a_n, b_1, b_2, ..., b_n，如何在O(n)的时间，用O(1)的空间，
将这个序列顺序改为a_1, b_1, ..., a_n, b_n。
这个问题在瀚海星云上跟出了好几十的跟帖，看看大家有没有什么好的解法！！！
晚上是google的校园宣讲会
先前并没有投简历，但是还是奔了去
google的hrjj看起来仿佛没有ibm的那么动人，但却很亲切
五点半左右开始，开始前那个hrjj放了些google员工自己拍的mv，
比较有意思
之后是一个做技术的男生如数家珍的介绍google做的东西
之所以称为“男生”主要感觉他很学生气。。。讲话并没有那些很商业的调度气氛的东西
很理想主义，呵呵，虽然听的很多人打瞌睡
他总是说google是个很理想主义的公司，虽然为了生存不得不做一些商业化的事情，但是，google做很多事情都是因为认为觉得有做的价值并且要做好，所以有了googleprint,googleearth,等等
不过，google仿佛是一个需要聪明人的公司，接下来的笔试应证了这一点
内容很少，甚至简单，选择题可能是送分的，大概10来道，并不难，算些东西，还有一点点程序方面的基础概念，后面是三个算法设计题。
第一个，深拷贝一个二叉树。我不明白这道题的动机是什么，我最后很搓得用了递归，虽然明知道这样很耗，可是实在想不起来非递归算法怎么个写法了。
第二个，把输入数组随机分配到一个新的数组上，每个数都完全对应一个随机的位置，当然，随即产生函数是提供了的。这个题我想了很久，冲突的时候怎么办？散列？但是那样还是随机的吗？
第三个，很ft。居然是C语言的一个作业题。N个人排成圈，从第一个人开始，去掉，隔一个人，去掉下一个，以此类推，要求出最后出局的那个人的位置。并且，要求分析算法的时间、空间复杂度。我感觉这个题表面简单，实际对算法的优化要求很高。一个是空间复杂度，一个是时间复杂度，只是不知道做到什么程度算是极好。
仿佛这种类型的考试，大家差不多都能答完，只是如何才能与众不同却让人伤脑筋
回来后对google的印象变得很好，至少感觉他们真的是需要人，而不是一个螺丝钉。。。
昨天，参加了Google春季实习工程师的招聘笔试。这是进入大学以来参加的第一次笔试。
可以说，这次笔试也让我更明确了我的学习方向。学习什么技能不重要，重要的是要有扎实基础，数据结构，c++语言等，都要扎实的掌握，不可有丝毫的马虎。于是，渐渐开始后悔了，后悔自己对基础知识没有学好，却又一天到晚想着要学什么什么东西，这真是丢了西瓜捡了芝麻，一点便宜都没有占到啊。
还记得昨天的笔试，第一题是有关位操作的，很简单。接下来两题是讲const指针的，这便是我的一个薄弱点，以前一直都没有学好。首先，constchar*p="abcde"，那么，p指向的内容是不可变得，即不能改变*p的值，但是，p却是可变的，即可以这么操作：p=“12345”，或者p=newchar[10]，等等；另外，char*constp="abcde"，则表示这是一个指针常量，即p不能指向另外的地址，但是，p指向的内容是可以改变的；还有一个就是常量指针常量，constchar*constp，它是指向常量的常量指针，若初始化的时候，p指向的是一个变量，那么，不能用指针操作来改变变量的值，例如：inta=0;constint*constp=&a;*p=1;//这句或是错误的，但是，可以直接给变量赋值，即a=1；是可以的。
接下来几题涉及了算法分析的一些东西，然后是涉及语法分析的正则表达式什么的，这个因为没学过编译，也就不太懂了。接下来是考了抖动。什么是抖动？所谓抖动，主要是由于页面交换过于频繁，而导致时间浪费太多的现象。特别的，在虚拟内存技术下，若工作集大小选的不合适的话，就会有频繁的换入换出，而我们知道，硬盘的读写是需要花费大量时间的，这样，就导致了某进程等待的时间比实际运行的时间多的多。
接下来的大题是编程题和算法题，前两题都挺简单的，第一题要求完成双向链表的添加结点，第二题要求比较两字符串的字符出现频率；第三题是个算法题，基本意思很简单，但是，要找到一个好的算法却需要一定的思考能力，具体题目已经记不太清了。
总之，这次笔试，虽然说从一开始所抱的心态就是见识见识，没有奢求什么，只是想走出这个温暖的象牙塔，走到外面这个花花世界来看看情形。一切都需放开。走了一遭才发现，不要总往高处看，基础扎实了，才能造起巴比伦塔。
1.写程序判断是否字符串A里每个字符在A中出现的次数都大于在字符串B中出现的次数。
注：此题我是对每个字符出现的次数分别统计，然后比较。重复的字符重复统计比较，所以效率很低。不知有什么好的改进方法？
2.对一个数组S，求其中满足要求的最大元素C。要求C满足等式C=A*B，其中A、B也是数组S中的元素。请用能想到的最优算法，分析时间和空间复杂度。（用语言描述算法，不用写程序）
注：这个题我当时做的方法在时间上要用o(n^3)，事后想出了个o(n^2logn)的方法。不知有没有更好的方法。
传说中有人说：google笔试很变态，题目希奇古怪；google题目比较基础简单。
终于得于一见。
晚上干完活才去，到的时候已经7点左右。在二教已经没有空余座位，无赖多等了20多分钟才安排了一个新的教室。
发题，答卷。
整体感觉就是比较基础，没有什么很难的题目，除最后一题目以外。
选择题目9个，比较基础。
第一题，相对比较简单，递归
第二题，基本是看是否对函数效率是否有概念。似乎也跟动态规划的记录法有点相似之处。
最后一题目回想起来实在惭愧，其实还是题目没有怎么读懂。嗨！
以下是科苑上，看到的解法。惭愧惭愧
第一和第二应该是不错的选择！
特别是第二种方法！
发信人:oasis(绿洲),信区:SISE2004702
标题:笔试最后一题想到的几种解法
发信站:BBS科苑星空站(WedOct1803:24:342006),站内
反正也晚了，干脆再折腾一会儿。
题目：n个点组成的无向图，对于任意给出的两点，判断其是否有长度为K的通路。
分析：无向图是允许有环存在的，也允许两点间有多条边，长度为K是指从一个点
移动到相邻点这样过程的次数。比如AB两点相邻，那么A-B-A-B就是长度为3的通路。
解法一：直接利用图论中的一个定理，邻接矩阵U的K次方后所得矩阵的(i,j)元素
即为原无向图中i,j两点之间长度为K的通路数量。因此复杂度只需要对U^K分析。
由于U^2的时间复杂度为O(n^3)，（这里使用了传统矩阵乘法，不过即使用strassan
方法也依然是O(n^(2+e))，其中0小技巧，不需要去依次的乘，否则的话需要K-1次矩阵乘法，可以从U^2，算出U^4，
依此类推，因此总的时间复杂度为O(n^3*lgK)。空间复杂度不细述O(n^2)。
评论一：细心的人会注意到这样的解法其实比题目的要求要强，因为题目中只是要
求出任意给定的两点间K通路数目，而上述做法，则是把所有的两点组合都求出来
了。因此还应该存在着改进的算法在O(n^2)这个时间复杂度级别。
解法二：这是看水木上一个网友的解法，我重写成下面这样：设所给的两点为A、B。
那么首先把A的所有相邻点全部放入U集合中，接着对之前放入U中的点i分别求出其相
邻点，并将它们放入U中（而原先的点i本身则从集合中事先去除）。这样做过K次后，
看队列中是否有B点。若有则表明存在着长度为K的通路。由于每次寻找邻接点的次数
不超过n^2，而要进行K次，因此时间复杂度为O(n^2*K)，空间复杂度为O(n)。
评论二：和解法一相比，从n^3*lgK变为了n^2*K，也就是n*lgK与K之间的差别，若n=k
的话，也就说明后者比前者快了lgK倍。
解法三：从A到B利用深度优先遍历，找出每一条AB间的路径，其中没有点重复经过。
对每一条这样的路径进行分析：
若长度>K，该路径不可能满足；
若长度=K，则已满足；
若长度一次加一）。若无环，则看K-当前路径长度，若该值为偶数，则可以在该路径上的某两
个邻接点上来回的重复走从而满足要求（每来回走一次加二）。其他情况，无法满足。
由上得到算法的时间和空间复杂度均为O(n^2)，
评论三：时间复杂度很可能不是O(n^2)，因为从A到B上找出每一条AB间的简单路径，由
于存在着重复边和环的情况，多半就不是简单的深度遍历的O(n^2)了，具体是多少我也
说不清。笔试里我用的这个方法，现在感觉挺玄。。。
『2006-10-17』
今晚Google笔试，也是本人的“处女笔”，人山人海啊，开始Google技术总监宣讲时，有位义愤填膺的老兄，抓住提问时间，强烈指责Google搜索不了“南京大屠杀”等“不公正”现象。唉，勇气和爱国主义情感可嘉啊，只可惜为什么不弄清情况就跑来乱说话呢？
笔试的人数比Google预想的多出2-3倍，题目不是很难，似乎都是计算机专业的基础课。不过可惜，我不是计算机专业的，很多题目只是凭自己编程经验写的，估计希望不会太大。但是心情还不错，因为本来就没有抱太大希望，而且Google笔试尚且不是很难，就不必对其他公司笔试有太大心里压力了。
有几道题目给出来，喜欢C的来看看：
int main()
{const char* p = "12345";
const char **q = &p;
*q = "abcde";
const char *s = ++p;
p = "XYZWVU";
printf("%c\n", *++s);
}
求输出结果。
---------------------------------------------
最后一道题：
n个节点的无向图，判断任意两点之间是否有长度为K的通路。写出算法思路，并给出你的算法的时间和空间复杂度。
--------------------------------------------
上面一题答案“c”，因为p是指向常量的指针，但P本身可以变化；下面一题据说是离散数学教程中的经典题型，我没有上过，只想到深度遍历的方法。
google的魅力就不用词语形容了,从晚上的人气就可见一斑.准点赶到教七,却发现门口已经被人群给赌了,google的工作人员一个劲地劝大家别进去了,理由是"为了安全":).也好,不用听开复同学的唠叨.回教三的路上,一打打的人迎面而来,熟悉的,陌生的,本校的,外校的.我彷佛到了麦加,穿梭在朝圣的人流中. 但是念佛的人多,成佛的却是寥寥.晚上肯定有四位数的申请者,不过能有多少人登上幸运的快车呢?能突破个位数吗?所谓千军万马过独木桥,找工作,挺残酷!
于我,去参加笔试,更多是一种体验.选择google,权当是我对这家伟大的公司的一点敬意吧!
在软件上,我这样的水平,恐怕连菜鸟也谈不上.那么硬件呢?光学呢?我的竞争力在哪里?不能不说,对于找工作,我是有所恐惧的.现在的选择,也许不过是种逃避.
昨天,zhengzheng说他改变主意,准备工作了,一起走的兄弟,又少了一个.今天,simon说在犹豫是否调整申请的方向,因为他想以后还是进公司的.说起,5年的努力是否值得?未来也许只有上帝知道吧!
乘着脑子还清晰,先把笔试题记下:
9个选择题,2个编程,1个算法.选择题,感觉比较基础,不知里面有没有设地雷?反正没啥印象了.
编程1,打印二叉树,实现语言不限,先后也不限.
编程2,给定一个字符串数组,从中找出第一个只出现一次的字母.
算法题,给定一个整数数组,从中切出一个连续片段,保证其元素和最大.求最优算法,分析时间和空间复杂度.
标 题: Google笔经
发信站: 饮水思源 (2006年10月11日03:06:04 星期三), 站内信件
开章明义，我是个废人，上来积攒rp了。
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
现在后悔只选了北京和上海的SWE了。
不过反正……也不指望了。。。
笔试题目：9道单选+3道问答
时间：100分钟
我做的是B卷。
单选题：
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
2，不记得了。。也是不需要思考的题目。。
3，大概是如下的函数：
int someFunc(int x){
if (x == 0)
return 0;
else
return x + someFunc(x - 1);
}
问这个计算的是什么。。。
4，不记得了。。不需要思考吧。。
5，不记得了。。不需要思考吧。。
6，参见2，4，5。。
7，似乎需要思考一下。。
8，问链表结构和数组相比的优势不包括哪项，
包括：
插入的时间
删除的时间
存储空间
剩下两个不记得了。。
9，如下函数：
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
问T(n)随n的增长。
选项大概是这样的：
O(n^2)，O(n^2logn)等等的。。
问答：
1，写两个N*N的矩阵的乘法，给出了C的格式，你可以选择你喜欢的语言去写。。
int* multi(int* a1, int* a2, int N){
}
2，寻找一个单向链表的中项，如果存在两个则返回前一个。给出了C的格式，同样你可
以选择。。。。
struct {
Node* next;
int value;
} Node;
Node* someFunc(Node* head){
}
3，给一个长度为n的整数数组，只允许用乘法不允许用除法，计算任意(n-1)个数的组合
乘积中最大的一组。。。写出算法的时空复杂度。
ps：怀疑这道题目出错啦。。虽然我也做错了。。。。。。
一些补充：
1，问答的第一题是google上学期 intern的大题原题；
2，google很喜欢考链表，无论intern的面试以及两次的笔试都有这样的题目；
3，google一般大题第三道都是写算法的时空复杂度；
4，选择题基本上偏简单，但是要做得准确率高似乎并不那么容易；
5，根据传言，小道消息，人云亦云以及以讹传讹，google的高速审卷政策来源于审卷时
以选择题为主，如果你全对啦，那么恭喜你pass啦；如果你错了好几道，那么下次努力
吧，如果还有下次。。。大题基本是做参考的。。。
6，选择题很多记不清了，因为一遍做下来的，回去随便扫了两眼。。。加上过了这几个
小时，记不得了。希望大家补充修正以及修改。。。
7，google会在11号开始3天内发面试通知，据小道消息等等，有四轮面试。bless大家~~
google brainy test/exam 就是流传甚广的传说中的google 的21道 GLAT 考试了。
10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa》、《今日物理》等几本专业杂志上，刊登了一份"Google实验室能力倾向测试"。
试卷开头，蛊惑地写着"试试看！把答案寄回Google，你有希望去Google总部参观，并成为我们其中一员"。
1. Solve this cryptic equation, realizing of
course that values for M and E could be
interchanged. No leading zeros are allowed.
WWWDOT - GOOGLE = DOTCOM
2. Write a haiku describing possible methods
for predicting search traffic seasonality.
3.
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
What is the next line?
4. You are in a maze of twisty little passages,
all alike. There is a dusty laptop here with a
weak wireless connection. There are dull,
lifeless gnomes strolling about. What dost
thou do?
A) Wander aimlessly, bumping into
obstacles until you are eaten by a grue.
B) Use the laptop as a digging device to
tunnel to the next level.
C) Play MPoRPG until the battery dies
along with your hopes.
D) Use the computer to map the nodes
of the maze and discover an exit path.
E) Email your resume to Google, tell the
lead gnome you quit and find yourself
in whole different world.
5. What’s broken with Unix?
How would you fix it?
6. On your first day at Google, you discover
that your cubicle mate wrote the textbook
you used as a primary resource in your first
year of graduate school. Do you:
A) Fawn obsequiously and ask if you
can have an autograph.
B) Sit perfectly still and use only soft
keystrokes to avoid disturbing her
concentration.
C) Leave her daily offerings of granola
and English toffee from the food bins.
D) Quote your favorite formula from the
textbook and explain how it’s now
your mantra.
E) Show her how example 17b could
have been solved with 34 fewer lines
of code.
7. Which of the following expresses Google□
over-arching philosophy?
A) "I’m feeling lucky"
B) "Don’t be evil"
C) "Oh, I already fixed that"
D) "You should never be more than
50 feet from food"
E) All of the above
8. How many different ways can you color an
icosahedron with one of three colors on
each face?
What colors would you choose?
9. This space left intentionally blank. Please fill it
with something that improves upon emptiness.
10.On an infinite, two-dimensional, rectangular
lattice of 1-ohm resistors, what is the
resistance between two nodes that are a
knight’s move away?
11.It’s 2 PM on a sunny Sunday afternoon in the
Bay Area. You’re minutes from the Pacific
Ocean, redwood forest hiking trails and world
class cultural attractions. What do you do?
12.In your opinion, what is the most beautiful
math equation ever derived?
13. Which of the following is NOT an actual
interest group formed by Google employees?
A. Women’s basketball
B. Buffy fans
C. Cricketeers
D. Nobel winners
E. Wine club
14.What will be the next great improvement in
search technology?
15.What is the optimal size of a project team,
above which additional members do not
contribute productivity equivalent to the
percentage increase in the staff size?
A) 1
B) 3
C) 5
D) 11
E) 24
16.Given a ABC, how would you use only
a compass and straight edge to find a point P
such that s ABP, ACP and BCP have
equal perimeters? (Assume that ABC is
constructed so that a solution does exist.)
17.Consider a function which, for a given whole
number n, returns the number of ones required
when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What
is the next largest n such that f(n)=n?
18.What’s the coolest hack you’ve ever written?
19.’Tis known in refined company, that choosing
K things out of N can be done in ways as
many as choosing N minus K from N: I pick K,
you the remaining.
Find though a cooler bijection, where you show
a knack uncanny, of your choices contain
all K of mine. Oh, for pedantry: let K be no more
than half N.
20.What number comes next in the sequence:
10, 9, 60, 90, 70, 66,?
A)96
B) 1000000000000000000000000000000000
0000000000000000000000000000000000
000000000000000000000000000000000
C) Either of the above
D) None of the above
21.In 29 words or fewer, describe what you
would strive to accomplish if you worked
at Google Labs.
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实验室的贡献。
今年10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa
》、《今日物理》等几本专业杂志上刊登了一份“Google实验室能力倾向测试”的
试卷，开头蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观
，并成为我们其中一员”。有兴趣的人可以做完了邮寄给Google公司，也许会得到
一个工作机会呢。
1、解答下面的隐藏等式，其中的M和E的值可以互换，但不允许第一位是0：
WWWDOT - GOOGLE = DOTCOM
2、用一个俳句(一种日本短诗，每句有一个与季节有关的词)来建立模型，借
此预测网络搜索流量的季节性变化；
3、
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
下一行是什么？
4、你正处于一个全部由崎岖小路构成的迷宫里，手里有一个满是灰尘的笔记
本，可以无线上网，但是信号很弱。与此同时，一些阴森可怕、毫无生气的妖怪在
你身边游荡。你会怎么做呢？
(1)毫无目的的四处游荡，到处碰壁，直到被迷宫里的妖怪吃掉。
(2)用笔记本作为挖掘工具，打穿地面直接进入下一关。
(3)玩网络游戏《魔法骑兵》，直至电池耗尽，你也心灰意冷。
(4)使用笔记本画出迷宫的节点地图，找到出路。
(5)发送简历给Google，告诉主管妖怪你选择退出，随后你就回到现实世界。
5、Unix有何缺陷？你准备如何补救？
6、在Google工作的第一天，你发现身边的同事竟然是研究生一年级课本的作
者，你会：
(1)主动示好并索取签名。
(2)不改变坐姿，但放轻打字声音，避免影响她的工作和思考。
(3)把你每天的麦片和咖啡都留给她享用。
(4)在她所写的书中找到你最喜欢的内容，并告诉她这些内容已经成为你的座
右铭。
7、下列哪句话最贴切的表达了Google的企业文化？
(1)我感到很幸运。
(2)不要干坏事。
(3)哦，我已经解决了那个问题。
(4)你身边50英寸之内，必定能找到食物。
(5)以上皆是。
8、用3种颜色为20面体上色，每个面一种颜色，有多少种组合？你会选择哪些
颜色？
9、下面是故意留出的空白，请将其填满，使之看起来不那么空。
10、用1欧姆的电阻组成无限大的两维矩阵，“象棋跳马步”(“日”字对角点
)两点之间的电阻是多少？
11、现在是星期日下午2点，你正在旧金山著名的湾区。你可以选择去国家公
园的红杉林里徒步旅行，或者参观城市里的文化景观。你会怎么做？
12、你认为最美的数学等式是什么？
13、下列哪个团体没有在Google员工中形成？
(1)女子篮球
(2)淡黄色爱好者
(3)Cricketeers
(4)诺贝尔奖获得者
(5)葡萄酒俱乐部
14、搜索技术的下一个革命性突破是什么？
15、一个项目组由多少人构成才能达到最优规模？也就是说，一旦超过这一数
字，每增加一个成员项目组的平均生产力就会相应下降。
(1)1个
(2)3个
(3)5个
(4)11个
(5)24个
16、给你一个三角形ABC，请用圆规和尺找出点P，保证三角形ABP、ACP和BCP
周长相等。
17、有这样一个函数，对于任意整数n，都能返回写出0到n之间出现“1”的个
数。例如，f（13）=6。请注意f（1）=1，那么下一个能实现f（n）=n的最大数字
是什么？
18、你编写的最酷的黑客程序是什么？
19、在下面的数列中，下一个数字是多少：10, 9, 60, 90, 70, 66,?
(1)96
(2)10的100次方
(3)以上皆是
(4)以上皆不是
20、用少于29个词，描述你能带给Google实验室带来的贡献。(天外)
--
“微软是个公平的公司，这里几乎没有特权。盖茨只是这两年才有了自己的一个停车位。
以前他来晚了没地儿，就得自己到处去找停车位。”
“微软非常强调员工的动手能力。在做新产品发布时，盖茨都能自己动手做演示。他总
是在和工程师作搭档，对自己的产品很熟悉，这样，任何人都糊弄不了他。”
1.单项选择题
1. 下面一段代码的输出是[ ]
void fn( int* b){
(*b)++;
}
int main(){
int a=7;
fn(&a);
cout<<a;
return 0;
}
A.0 B.7 C.8 D.undefined
2. 定义int i,j,*p=&i; 那么下面哪条语句可以完成i=j的赋值[ ]
A.i=*p; B. *p=*&j; C.i=&j; D.I=**p;
3. 用二叉搜索树和哈希表存储相同的数据集,对于以下何种操作,二叉搜索树比哈希表
速度更快?[ ]
A.检索 B. 插入 C.删除 D.更新 E.排序
4. 包含N个几点和M条边的有向带权图G, 边的权为正, 以下操作中不可以在O(N+M)
的时间复杂度内完成的操作是:[ ]
A. 求结点s到结点t之间的最短距离
B. 求距离结点s最近的结点
C. 已知起始结点, 对图G中的结点进行拓扑排序
D. 求图G的最大强连通子图
5. 有如下递归函数f(n),其时间复杂度为[ ]
int f(int n){
if(n==0)
return 0;
if(n==1)
return 1;
return ( 5*f(n-1) - 6*f(n-2));
}
A.O(n) B. O(n^2) C. O(n^3) D. O(2^n)
6. 下面所述步骤中,哪一个不是创建经常所必需有的[ ]
A.由调度程序为进程分配CPU B.建立一个进程控制块
C.为进程分配内存 D.将进程控制块链入就绪队列
7. 在多进程的系统中,为了保证公区变量的完整性,各进程应互斥进入临界区。所谓临
界区是[ ]
A.一个缓冲区 B.一个数据区 C.一个同步机构 D.一段程序
8. 能产生满足如下条件语言的正则表达式是：1.每一个a后至少紧跟两个c; 2.每一个b
后至少紧跟一个c [ ]
A.(acc|bc|c)* B.(acc|bc)* C.(ac|bc)* D.不是正则语言
9. 以下哪项不是RPC（远程过程调用）的特点[ ]
A.速度快 B.降低系统耦合度 C.可以实现异构系统间的协作
10. 有三个桶，容量分别是3升，5升，7升，你只能进行下面的操作：
把一个桶中所有的水倒掉；
把一个桶A中的水倒入桶B，直到桶A空了或者桶B满了；
假设一开始容量为3升和5升的桶是满的，7升的桶是空的，希望通过一系列操作使3个桶
中任意一个中正好有4升水，那么至少需要[ ]次操作。
A.3 B.5 C.7 D.不可能
2. 程序设计与算法
2.1 实现如下编码算法，对于重复2-9次数的字符，用两个数字表示，即NX（其中N为重
复的次数，X为重复的字符，下同），超过九个则先输出9X，然后处理剩下的字符。对于
连续的不重复的字符，则两边加1来封字符串。如果被封的字符串其中有数字为1，则用1
来转义。 示例： AAAAAABCCCC -> 6A1B14C, 12344 -> 11123124。。。（下面的框
架是用C++语言写的。你可以用你熟悉的语言。）
void encode (const char* text, char* dest)
text 为需要编码的字符串，dest表示编码输出的目标空间，而空间足够大
2.2给定一颗有n个结点的二叉树。求它的所有结点数为m的连通子图数目。m<=n分析你的
算法的时间复杂度，解释算法即可，不必写代码。
用:
假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。
现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：
如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。
这规则甚是简单，不过有个问题就是同一个 AB 序列，可能有多个字符串都与之相符，比方说序列“ABA”，就有“acdb”、“cadb”等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的 AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。
嘿嘿，这就是你要解决的问题了。如果不嫌慢的话大可以穷举，不过这种解法拿出来那是显然不好意思和人打招呼的。事实上，如果设 AB 序列的长度为 n ，那么这个问题是可以做到 O(n^3) 的。
1、有两根不均匀分布的香，香烧完的时间是一个小时，你能用什么方法来确定一段15分钟的时间？
答：2根香同时点燃，第一根两头都点燃，第二根只点一头， 第一根点完的时候是半个小时，接着把第二根两头都点燃，第二根点完的时候就是15分钟。
２、一个经理有三个女儿，三个女儿的年龄加起来等于13，三个女儿的年龄乘起来等于经理自己的年龄，有一个下属已知道经理的年龄，但仍不能确定经理三个女儿的年龄，这时经理说只有一个女儿的头发是黑的，然后这个下属就知道了经理三个女儿的年龄。请问三个女儿的年龄分别是多少？为什么？
答：2，2，9， 1岁不可能
3、有三个人去住旅馆，住三间房，每一间房$10元，于是他们一共付给老板$30，第二天，老板觉得三间房只需要$25元就够了于是叫小弟退回$5给三位客人，谁知小弟贪心,只退回每人$1，自己偷偷拿了$2，这样一来便等于那三位客人每人各花了九元，于是三个人一共花了$27，再加上小弟独吞了不$2，总共是$29。可是当初他们三个人一共付出$30那么还有$1呢？
答：没错，三个人付了27块，老板拿了25块，小弟拿了2块
４、有两位盲人，他们都各自买了两对黑袜和两对白袜，八对袜了的布质、大小完全相同，而每对袜了都有一张商标纸连着。两位盲人不小心将八对袜了混在一起。 他们每人怎样才能取回黑袜和白袜各两对呢？
答：不知道，还要仔细想想
５、有一辆火车以每小时15公里的速度离开洛杉矶直奔纽约，另一辆火车以每小时20公里的速度从纽约开往洛杉矶。如果有一只鸟，以30公里每小时的速度和两辆火车同时启动，从洛杉矶出发，碰到另一辆车后返回，依次在两辆火车来回飞行，直到两辆火车相遇，请问，这只小鸟飞行了多长距离？
答：记好两车相遇时间，就是鸟飞行时间，乘以其飞行速度就得到飞行距离。
６、你有两个罐子，50个红色弹球，50个蓝色弹球，随机选出一个罐子，随机选取出一个弹球放入罐子，怎么给红色弹球最大的选中机会？在你的计划中，得到红球的准确几率是多少？
答：不知道，还要仔细想想
７、你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的重量＋1.只称量一次，如何判断哪个罐子的药被污染了？
答：不知道，还要仔细想想
８、你有一桶果冻，其中有黄色，绿色，红色三种，闭上眼睛，抓取两个同种颜色的果冻。抓取多少个就可以确定你肯定有两个同一颜色的果冻？
答：4
９、对一批编号为1～100，全部开关朝上(开)的灯进行以下*作：凡是1的倍数反方向拨一次开关；2的倍数反方向又拨一次开关；3的倍数反方向又拨一次开关……问：最后为关熄状态的灯的编号。
答：不知道，还要仔细想想
１０、想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒上下？
答：人的眼睛是左右对称的
１１、一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
答：3
一、单选
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 ... 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;
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。这样一趟扫描结果也就出来了。
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.
转载请注明出自应届生求职招聘论坛 http://bbs.yingjiesheng.com/,本贴地址:http://bbs.yingjiesheng.com/thread-21638-1-1.html