- 1、本文档共21页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
Google 笔试面经
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 的路径,描述算法即可,不用
实现,分析算法的时间和空间复杂度,尽量优化算法。
文档评论(0)