Google笔试题

Google面试题1.下面哪项不是链表优于数组的特点？A.方便删除B.方便插入C.长度可变D.存储空间小2.T(n)=25T(n/5)+n*n的时间复杂度？3.有一幢100层高的大楼，给你两个完全相同的玻璃围棋子。假设从某一层开始，丢下玻璃棋子就会破碎。那么怎么利用手中的两颗棋子，用一种什么样的最优策略，知道这个临界的层高呢？____________________________________________________________________[07.5.21]Google实习生招聘笔试题目发信站:华南木棉BBS(TueMay2209:40:402007),转信一、选择题1、定义{1,2,...n}*{1,2,...n}上的等价关系~(a,b)~(c,d)当且仅当a+b=c+d。定义集合A(a,b)={(x,y)|(x,y)~(a,b)},那么{1,2,...n}*{1,2,...n}上不同集合的数量为()A、nB、2*n-1C、2*nD、n*n2、下面一段代码的输出是()inta,b;int*x,*y;x=&a;y=&b;*x=10;*y=*x;x=y;*x=20;couta''bendl;A、1020B、2010C、1010D、20203、下面一段代码的输出结果是()voidf(char*c,chard){*c=*c+1;d=d+1;coutcd;}voidmain(){chara='A',b='a';f(&b,a);coutabendl;}A、BaBaB、aBaBC、AbAbD、bBAb4、若二叉搜索树有三个节点，对应于三个不同的值A、B、C，这样的二叉搜索树共有多少种可能的构造？()A、1B、2C、3D、4E、55、假设把整数关键码K散列到有N个槽的散列表，以下哪些散列函数是好的散列函数？()1)h(k)=k/N;2)h(k)=1;3)h(k)=kmodN;4)h(k)=(k+Random(N))modN,Random(N)返回一个0到N-1的整数A、1)B、2)C、3)D、4)E、3)和4)6、有如下递归函数f(n)，其时间复杂度为()intf(intn){intsum=0;for(inti=0;in;i++)sum=sum+i;returnf(n/2)+f((n+1)/2)+sum;}A、O(n)B、O(nlongn)C、O(n^2)D、O(n^(3/2))7、进程从拥塞状态变为就绪状态是发生在()A、分配给进程的时间片用完B、进程等待的事件发生C、进程被调度程序选中D、进程等待某一事件8、如果有多个中断同时发生，系统将根据中断优先级响应优先级最高的中断请求。若要调整中断事件的响应次序，可以利用()A、中断向量B、中断嵌套C、中断响应D、中断屏蔽9、在编译原理里，上下文无关文法和正则文法的描述能力为()A、上下文无关文法更强B、正则文法更强C、两者相当D、无法比较10、IP数据报分片的重组通常发生在以下哪个位置()A、源主机B、目的主机C、路由器D、以太网交换机二、程序设计与算法1、通常在数学中一元n次多项式可表示成如下的形式：Pn(x)=a0+a1*x+a2*x^2+...+an*x^n(1)请设计一套接口用以表示和操作一元n次多项式(2)根据上述设计实现一元n次多项式的加法运算(3)根据上述设计实现一元n次多项式的乘法运算2、给定A、B两个等长的数组，A和B中的数相同，但是顺序不同，现在只能取A中某数和B中某数进行比较只能知道大或者小或者相等，怎么将A和B中相同的数配对？分析你的算法的时间复杂度。解释算法即可，不必写代码。三、1、你做过的最有创意的软件项目是什么？请简单描述一下。2、这个创意有没有被人使用？____________________________________________________________________google笔试大全！超全呀！今年10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa》、《今日物理》等几本专业杂志上刊登了一份“Google实验室能力倾向测试”的试卷，开头蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观，并成为我们其中一员”。有兴趣的人可以做完了邮寄给Google公司，也许会得到一个工作机会呢。1、解答下面的隐藏等式，其中的M和E的值可以互换，但不允许第一位是0：=DOTCOM2、用一个俳句(一种日本短诗，每句有一个与季节有关的词)来建立模型，借此预测网络搜索流量的季节性变化；3、11211211111221下一行是什么？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、假设在n进制下，下面的等式成立，n值是（）567*456=150216a、9b、10c、12d、182、文法G:S-uvSvu|w所识别的语言是：（）a、uvw*vub、（uvwvu）*c、uv(uv)*wvu(vu)*d、(uv)*w(vu)*3、如下程序段输出是：（）charstr[][10]={Hello,Google};char*p=str[0];countstrlen(p10);a、0b、5c、6d、104、cnt=0while(x!=1){cnt=cnt1;if(x&1==0)x=x/2;elsex=3*x1;}countcntend1;当n=11时，输出：（）a、12b、13c、14d、155、写一段程序判定一个有向图G中节点w是否从节点v可达。（假如G中存在一条从v至w的路径就说节点w是从v可达的）。以下算法是用C写成的，在boolReachable函数中，你可以写出自己的算法。classGraph{public:intNumberOfNodes();//返回节点的总数boolHasEdge(intu,intv);//u,v是节点个数，从零开始依次递增，当有一条从u到v的边时，返回true}；boolReachable(Graph&G,intv,intw){//请写入你的算法}6、给定一棵所有边的长度均为整数的树，现要求延长其中某些边，使得从根到任意节点的路径长度相等。问满足要求的树的边长度之和最小是多少?请写出你的算法，并分析时间复杂度。欢迎回复，给出你的解答。____________________________________________________________________从没有找工作经历的我今天参加了Google的笔试，本来还自我感觉良好呢，谁知道考题那是嗷嗷不会啊。考的几乎都是算法，指针非凡的多，不过时间太久不用了都忘记了，数据结构的也不少，考了队列，还有一些编译原理的题，关于表达式的；三道大题第一个还蛮简单，是向双向列表插入一个节点，第二个问题比较恶心，判定A字符串中的各个字符数目是否不大于B字符串中的各个字符数目，由于没时间了就没写完，第三题更是相当及其以及非凡的恶心，找到整数数组中满足A*B=C的元素，而且要更优的，算了半天的时间复杂度还是没写出来。还是忙该忙的事吧，眼看期末考试了，不能挂课，加油！！！____________________________________________________________________不过google的题目确实出的很好，看似简单，但需要扎实的基本功和一定的熟练程度，后边的算法设计更需要一些技巧。十几道选择，4个算法，100分钟。走出考场忽然有种恍惚的感觉，碰到一个哥们儿一起拼车回学校，路上聊起找工作的事情都是颇有感慨，今天的笔试他说是“过把瘾就死”。可能吧！____________________________________________________________________google笔试,据说小题都对就进入面试zz1、两个二进制数的异或结果2、递归函数最终会结束，那么这个函数一定（不定项选择）：1.使用了局部变量2.有一个分支不调用自身3.使用了全局变量或者使用了一个或多个参数3、以下函数的结果？intcal(intx){if(x==0)return0;elsereturnx+cal(x-1);}4、以下程序的结果？voidfoo(int*a,int*b){*a=*a+*b;*b=*a-*b;*a=*a-*b;}voidmain(){inta=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