长理培训真题库
我的
军队文职考试一本通

2011年Google招聘笔试题完整版

2020-07-16 21:30
2011 年 Google 招聘笔试题完整版 一、选择题 (1) 以下哪个字符串不能被正则表达式 a(bc)*d* 匹配到? A. ad B. abcd C. abc D. abccd (2) 在 x86 cpu 中,下面哪种运算速度最慢? A. 加 B. 减 C. 乘 D. 除 (3) 下面程序输出的结果是什么? void main() { bool first=true; int sum =0; int current_value; for(unsigned short i=65535;i>=0;--i ) { if(first) { current_value=65535; sum+=current_value%3; first=false; } else { sum+=-current_value%3; if(current_value<=0) { printf("%d,%d",sum,i); break; } } } } A. 65535, 0 B. 65536, 1 C. 65536, 65535 D. 65536, 0 (4) 书架上有编号为 1-19 的 19 本书,从中拿 5 本,问 5 本编号都不相邻的拿法有多 少种? A. 2002 B. 3003 C. 11628 D. 比 C 大的一个数,具体多少我忘记 了。 (5) 现在有一套房子,价格 200 万,假设房价每年上涨 10%,一个软件工程师每年 固定能赚 40 万。如果他想买这套房子,不贷款,不涨工资,没有其他收入,那么他需要 几年才能攒够钱买这套房子? A. 5 年 B. 7 年 C. 8 年 D. 9 年 E. 永远买不起 (6) 一棵满二叉树,一共有 n 个叶子节点,请问该二叉树一共有多少个节点? A. 2n-1 B. 2n C. n-1 D. n (7) 下列哪种排序方法在最坏情况下的时间复杂度是 nlgn? A. 归并排序 B. 快速排序 C. 冒泡排序 D. 插入排序 (8) 有两个从小到大排好序的数组,长度分别是 N 和 M,将这两个数组合并成一个有 序数组的最小比较次数是:? A min(N,M) B M+N-1 C N+M D max(M,N) (9) 关于 TLB 和 Cache 的说法中,哪个是错的? A. TLB 与 Cache 中保存的数据是不同的 B. TLB miss 后,有可能直接在 Cache 中找到页表内容 C. TLB miss 后会导致程序出错,但是 Cache miss 不会 D TLB 和 Cache 的命中率都与程序的访存模式有关 (10) 关于数据库的说法,哪个是错误的? A. 每个表都必须有主键 B. 跨表查询可能非常慢 C. 数据库不支持多个用户对同一个表进行写操作 D. 多维索引可以用 KD 树实现 二、编程算法题 (1) 编程实现多项式求值: f(n)=a0+ a1*x^1 + a2*x^2 +…+ an*x^n, 函数声明如下:double foo(double x, double *A, int N)。 (2) 现在有 n=2^k 支足球队,编号为 0,1,…,n-1,给出 2 维数组 winner[] [],winner[i][j]表示当编号 i 和 j 的会胜出的队伍的编号,并且没有平局,输入保证 winner[i][j]==winner[j][i],现在给出一个单败淘汰赛的签位一维数组 order[],order[i] 表示第 i 个签位上的队伍的编号,order 保证是 0 到 n-1 的一个排列。返回比赛最后的排 名顺序,同一轮被淘汰的队伍名词并列,并列的队伍之间的顺序任意,要求时间和空间复 杂度尽量的低,将结果写到一维数组 result[]里面即可。 接口定义: c++: void calculate_result(int n,vector> winner,vector order,vector result); 例子: N=4,winner={{0,1,2,3},{1,1,2,1},{2,2,2,3}, {3,1,3,3}},order={0,1,2,3} … (3) KOF 游戏相关,玩过 KOF(拳皇)的人都知道,玩的时候如果按照一定的按键拳皇)的人都知道,玩的时候如果按照一定的按键 次序就会连招,连招的威力很大。现在题目的意思是:每招用一个大写字母表示,如 ABC … Z ,现给定 n 个连招公式:S→T,每个公式的 S 长度都相同,都为 m ,T 的长度为 1 。每个公式都代表一个连招规则,表示如果之前的 m 招为 S,那么可以在后面连出一招 T, 在前 m 招的时候可以随便连,但 m+1 招后就必须遵循连招公式。现在要写一个算法, 计算最长连招的长度;如果可以无限连招,则返回 def 。(拳皇)的人都知道,玩的时候如果按照一定的按键1≤n, m≤100) 这里有一个例子:n=4, m=3,连招公式为: ABC→D,ABC→C,CCA→A,BCC→A。连招公式的意思是:A、B、C 可以连出 C,也 可连出 D,C、C、A 可以连出 A,B、C、A、可以连出 B。这时候可以得到最长连招公式: ABC→C→A→A,即最长连招公式长度为 6 。 题目要求给出算法思想并结合一定的伪码,不需要实现。
温馨提示:如果当前文档预览出现乱码或未能正常浏览,请先下载原文档进行浏览。
2011年Google招聘笔试题完整版 第 1 页

下载提示

1 该文档不包含其他附件(如表格、图纸),本站只保证下载后内容跟在线阅读一样,不确保内容完整性,请务必认真阅读

2 除PDF格式下载后需转换成word才能编辑,其他下载后均可以随意编辑修改

3 有的标题标有”最新”、多篇,实质内容并不相符,下载内容以在线阅读为准,请认真阅读全文再下载

4 该文档为会员上传,版权归上传者负责解释,如若侵犯你的隐私或权利,请联系客服投诉

最近更新

热门排行