[合集] google昨晚的笔试题,最后3道
面试笔试9.91K
发信人: fengisan (一个人......), 信区: Job
标 题: [合集] google昨晚的笔试题,最后3道
发信站: 珞珈山水BBS站 (Sat Oct 28 13:06:46 2006), 站内
☆─────────────────────────────────────☆
qinyubin (转向你的方向@E.I.S) 于 (Wed Oct 18 13:51:29 2006) 提到:
写的很快,不过发现自己写的很烂.下面的解法不是我的.
2.1 // search the value on the Binary Search Tree
struct Node
{
Node* left;
Node* right;
int value;
};
Node* Search(Node* root, int value)
{
while(NULL != root && root->value != value)
root = root->value > value ? root->left : root->right;
return root;
}
2.2 //Tribonacci number : T(i) = i (if i = 0, 1, 3); T(i) = T(i-1) + T(i-2) +
T(i-3) (if i > 2)
int Tribonacci(int n)
{
int t[] = {0, 1, 2};
for (; n > 2; --n)
{
t[1] += t[0];
t[2] += t[1];
t[0] = t[1] - t[0];
t[1] = t[2] - t[1];
}
return t[n];
}
一个n个顶点的连通图.
写一个算法,求任意两个点之间是否存在长度为k的通路,通路上可以有重复的点.
写时间和空间复杂度
用matrix multiple, 复杂度是O(N^3logK)
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 13:56:27 2006) 提到:
第3题通路上可以有重复的点?我没看题目上有写这句阿
☆─────────────────────────────────────☆
qinyubin (转向你的方向@E.I.S) 于 (Wed Oct 18 14:01:05 2006) 提到:
通路上可以有重复的点,
恩,我刚发现.没有.
我转的帖子.
☆─────────────────────────────────────☆
dragonflywww (龙飞) 于 (Wed Oct 18 14:15:57 2006) 提到:
最后一题不用乘整个距阵吧
可以做到O(n^2*k)
那个logk怎么来的?
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 14:16:41 2006) 提到:
说下你的算法?目前还不知道最后一题怎么做
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 14:19:18 2006) 提到:
上面那个答案是按2点间路径长可以有回路做的,通路定义应该是不算回路的,
邻接矩阵做的就不对了,另外K应该是常数因子把
☆─────────────────────────────────────☆
dragonflywww (龙飞) 于 (Wed Oct 18 14:25:46 2006) 提到:
用一个bool数组a[n]表示i步可以达到的点
如果求x,y有没有k的路径
初始a[x]=1;其他为0
for(step=0;step {
for(i = 0; i < n; ++i)
{
if(!a[x])continue;
for(j = 0; j < n; ++j)
if(matrix[i][j])b[j] = 1;
}
把b复制到a;
}
最后判断a[y]==1就存在,否则不存在
☆─────────────────────────────────────☆
dragonflywww (龙飞) 于 (Wed Oct 18 14:35:04 2006) 提到:
你搞错概念了
另外k是需要输入的不能算常数因子
☆─────────────────────────────────────☆
Grope (Grope) 于 (Wed Oct 18 23:24:44 2006) 提到:
第2题可以写log(n)的算法
第3题 logk*n^3和k*|e|的算法
☆─────────────────────────────────────☆
Grope (Grope) 于 (Wed Oct 18 23:31:48 2006) 提到:
不对 我刚刚看了题目 你我都搞错了 是求任意的 不是任意给定的
应该矩阵乘法 N^3logK
☆─────────────────────────────────────☆
Grope (Grope) 于 (Thu Oct 19 11:23:26 2006) 提到:
最终发现只要O(n^3)的复杂度
方法都想复杂了
☆─────────────────────────────────────☆
dragonflywww (龙飞) 于 (Thu Oct 19 13:23:17 2006) 提到:
你在哪里看的原始的题目?
求任意和给定的算法思想都一样撒
就距阵的k次方可以log一下
你说的n^3是用floyd?只能求无向图的吧?
标 题: [合集] google昨晚的笔试题,最后3道
发信站: 珞珈山水BBS站 (Sat Oct 28 13:06:46 2006), 站内
☆─────────────────────────────────────☆
qinyubin (转向你的方向@E.I.S) 于 (Wed Oct 18 13:51:29 2006) 提到:
写的很快,不过发现自己写的很烂.下面的解法不是我的.
2.1 // search the value on the Binary Search Tree
struct Node
{
Node* left;
Node* right;
int value;
};
Node* Search(Node* root, int value)
{
while(NULL != root && root->value != value)
root = root->value > value ? root->left : root->right;
return root;
}
2.2 //Tribonacci number : T(i) = i (if i = 0, 1, 3); T(i) = T(i-1) + T(i-2) +
T(i-3) (if i > 2)
int Tribonacci(int n)
{
int t[] = {0, 1, 2};
for (; n > 2; --n)
{
t[1] += t[0];
t[2] += t[1];
t[0] = t[1] - t[0];
t[1] = t[2] - t[1];
}
return t[n];
}
一个n个顶点的连通图.
写一个算法,求任意两个点之间是否存在长度为k的通路,通路上可以有重复的点.
写时间和空间复杂度
用matrix multiple, 复杂度是O(N^3logK)
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 13:56:27 2006) 提到:
第3题通路上可以有重复的点?我没看题目上有写这句阿
☆─────────────────────────────────────☆
qinyubin (转向你的方向@E.I.S) 于 (Wed Oct 18 14:01:05 2006) 提到:
通路上可以有重复的点,
恩,我刚发现.没有.
我转的帖子.
☆─────────────────────────────────────☆
dragonflywww (龙飞) 于 (Wed Oct 18 14:15:57 2006) 提到:
最后一题不用乘整个距阵吧
可以做到O(n^2*k)
那个logk怎么来的?
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 14:16:41 2006) 提到:
说下你的算法?目前还不知道最后一题怎么做
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 14:19:18 2006) 提到:
上面那个答案是按2点间路径长可以有回路做的,通路定义应该是不算回路的,
邻接矩阵做的就不对了,另外K应该是常数因子把
☆─────────────────────────────────────☆
dragonflywww (龙飞) 于 (Wed Oct 18 14:25:46 2006) 提到:
用一个bool数组a[n]表示i步可以达到的点
如果求x,y有没有k的路径
初始a[x]=1;其他为0
for(step=0;step
for(i = 0; i < n; ++i)
{
if(!a[x])continue;
for(j = 0; j < n; ++j)
if(matrix[i][j])b[j] = 1;
}
把b复制到a;
}
最后判断a[y]==1就存在,否则不存在
☆─────────────────────────────────────☆
dragonflywww (龙飞) 于 (Wed Oct 18 14:35:04 2006) 提到:
你搞错概念了
另外k是需要输入的不能算常数因子
☆─────────────────────────────────────☆
Grope (Grope) 于 (Wed Oct 18 23:24:44 2006) 提到:
第2题可以写log(n)的算法
第3题 logk*n^3和k*|e|的算法
☆─────────────────────────────────────☆
Grope (Grope) 于 (Wed Oct 18 23:31:48 2006) 提到:
不对 我刚刚看了题目 你我都搞错了 是求任意的 不是任意给定的
应该矩阵乘法 N^3logK
☆─────────────────────────────────────☆
Grope (Grope) 于 (Thu Oct 19 11:23:26 2006) 提到:
最终发现只要O(n^3)的复杂度
方法都想复杂了
☆─────────────────────────────────────☆
dragonflywww (龙飞) 于 (Thu Oct 19 13:23:17 2006) 提到:
你在哪里看的原始的题目?
求任意和给定的算法思想都一样撒
就距阵的k次方可以log一下
你说的n^3是用floyd?只能求无向图的吧?
-
NEC笔试挂了
下午跨江去了NEC,进去以后我休息了一会,然后就开始笔试了,不过题目确实我很多不会,比如基本的数据传送DMA忘掉了,还有LINUX的文件拷贝等命令……还有实时系统是什么,LINUX/UNIX下面进程如何共享……嘿嘿,都乱写了,后面的也大概随便写写&hellip...
-
招商银行的笔试
2006年12月2日居然迟到了几十分钟,佩服工作人员的时间观念……笔试分为两部分,两个半小时,基础知识类似于公务员题,但添加了专业的内容,注意,还包括主观题;专业的部分就根据不同情况而定了,我们是营销类的,一道案例题。一道可选题,关于宏观经济政策的论述。...
-
思科(CISCO)笔试题目
以下问题来源于网络收集,感谢网友们的笔试经验分享!第一类:1.为什么"ethic"对于一个销售人员来说很重要?ethic能起到什么作用?2.假设一个场景:你去见一个客户,同时遇到了你的竞争对手之一,有恰巧有一个机会他离开片刻,把Notebook留在桌上,你有足够的时间去browse,这会使你...
-
中国人寿股份公司笔试试题
中国人寿股份公司笔试试题分为三部分第一部分和第二部分是由北京师范大学的一个心理测试的研究所出的题第一部分类似于公务员考试,包括概念辨析、逻辑推理、图形推理和计算题(图表和小的应用题),比较像公务员考试试题,时间比较紧,总共40题,35分钟第二部分是纯粹的心理...