昨天百度笔试题没探讨的吗?

qq376472696qq 2012-09-23 06:56:27
这个应该不需要什么保密的吧。。。

1.线程或数据库死锁的原理?如何避免?

2.面向对象的3个基本要素和5个基本设计原则。

3.windows内存管理机制有哪几种?优缺点?

二、算法题
1.1001个员工羽毛球比赛,单淘汰制,求比几场能比出冠军(代码模拟过程)?

2.100个灯,初始状态亮着,第一次每隔一个灭一个,第二次每隔两个(如果是亮的就灭,反之亮之)。。。依次类推,100次后还剩几个亮着?

3.字符串左移,void *pszStringRotate(char *pszString, int nCharsRotate),比如ABCDEFG,移3位变DEFGABC,要求空间复杂度O(1),时间复杂度O(n)

三、设计(这题记不大清楚了)
要把10W条数据放进内存,每条数据包括一个key(16字节),一个数据1M,6台电脑,每台64g内存,设计一个存储系统要满足7*24小时运行。(有可能会宕机)

话说上学地方偏僻的应届生找工作真心纠结。。。
...全文
8195 95 打赏 收藏 转发到动态 举报
写回复
用AI写文章
95 条回复
切换为时间正序
请发表友善的回复…
发表回复
某笨緢_Jun 2013-08-02
  • 打赏
  • 举报
回复
太强大了~ 看了前面的 感觉就是头脑风暴 很不错 有收获·~
smsgreenlife 2012-10-08
  • 打赏
  • 举报
回复
羽毛球比赛的那个题,如果只求比赛场数,可以这样吧,时间复杂度为logn。

#include <stdlib.h>
#include <stdio.h>

int foo(int num)
{
int i = 1;
int count = 0;
while(i<num)
{
i<<=1;
++count;
}
return count;
}


void main()
{
printf("%d\n", foo(1001));
}
guanchaoyong 2012-10-08
  • 打赏
  • 举报
回复
强悍的面试题 我也就三四十的样子
dyx心心 2012-10-07
  • 打赏
  • 举报
回复
都好基础啊,看来关键还是面试
smsgreenlife 2012-10-07
  • 打赏
  • 举报
回复
发现灯的亮灭与约数的个数的奇偶性有关好像不难吧,但你要证明所有完全平方数的约数个数为奇数,非完全平方数的约数个数为偶数呀!其实只要把一个数分解质因数,然后分析每个质因数的指数的奇偶性就可以了,我想了将近一个小时才证明出来,在考场上肯定是做不出来了!

[Quote=引用 30 楼 的回复:]引用 20 楼 的回复:

灭灯那题,应该就是看每个数的约数的个数,约数是奇数个的都是亮着的,约数是偶数个的都是灭的,这个难道是一个一个的数吗?

我当时也是这么想的,我就把想法写了下,不知道他要问什么
[/Quote]
smillyz 2012-10-06
  • 打赏
  • 举报
回复
都是牛人啊!
俊哥有个blog 2012-10-05
  • 打赏
  • 举报
回复
贴一个别人写的锦标赛排序代码:

#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#define LENGTH 256
int select_max(int* data, int* idx, int n)
{
int i, l, j;
for (i = 0; i < n; idx[i]=i,++i);
for (l = 1; l < n; l <<= 1)
for (i = 0; i + l < n; i += l<<1)
data[idx[i]] > data[idx[i+l]] ? 0 : (idx[i] = idx[i+l]);
return idx[0];
}

void my_sort(int* data, int n)
{
static int idx[LENGTH];
int t;
while (n--)
{
int j = select_max(data, idx, n+1);
t = data[j], data[j] = data[n], data[n] = t;
}
}

int main(int argc, char* argv[])
{
int data[256];
int i;
srand(time(NULL));
for (i = 0; i - 100; ++i)
data[i] = rand()%1000;
my_sort(data, 100);
for (i = 0; i - 100; ++i)
printf("%d\t", data[i]);
return 0;
}
俊哥有个blog 2012-10-05
  • 打赏
  • 举报
回复
[Quote=引用 54 楼 的回复:]

字符串移动

https://github.com/jhlicc/misc/blob/master/shift.c
[/Quote]

你这个方法很不好。

用两个指针分别指向字符串首尾,交换,然后首尾指针向中间移动,再交换...最后可以完成逆序!
guozhixing 2012-10-04
  • 打赏
  • 举报
回复
考了80分的路过。。
Flammable_ice 2012-10-04
  • 打赏
  • 举报
回复
for (int i=j;i<100;i+=j)这行补充解释://第二次每隔两个再做开关(i+=3,第a[0]个是亮的,隔两个也就是第a[3]个进行开关灯,那么i每次加3),以此类推(第98次每隔98个再做开关i+=99,a[99]是第100个灯,那么第99和100次已经跨过第100个灯泡了)(i+=j)那么第一个永远是默认状态亮着的。所以i从第j个开始。(i=j)
Flammable_ice 2012-10-04
  • 打赏
  • 举报
回复
//算法第二题详细解答。

#include <iostream>
using namespace std;
void main()
{
int a[100]={0};//将100个灯泡放入数组中并且初始化为0,0表示灯亮,1表示灯灭
for (int i=0;i<100;i++)//第一次,第偶数个是亮的,第奇数个是灭的。因为数组下标是从0开始的。
{
if (i%2==0)
{
a[i]=0;//第偶数个灯泡置为亮0
}
else if (i%2==1)
{
a[i]=1;//第奇数个灯泡置为灭1
}
}
for (int j=3;j<100;j++)
{
for (int i=j;i<100;i+=j)//第二次每隔两个再做开关(i+=3,第a[0]个是亮的,隔两个也就是第a[3]个进行开关灯,那么i每次加3),以此类推(第98次每隔98个再做开关i+=99,a[99]是第100个灯,那么第99和100次已经跨过第100个灯泡了)(i+=j)那么第一个永远是默认状态亮着的。所以i从第j个开始。(i=j)
{
if (a[i]==0)//如果是亮的,
{
a[i]=1;//就关灯。
}
else if (a[i]==1)//如果是灭的,
{
a[i]=0;//就开灯。
}
}
}
int n=0;//统计亮灯数
for ( i=0;i<100;i++)
{
if (a[i]==0)
{
n++;
}
else if(a[i]==1)
{
cout<<"a["<<i<<"]:"<<i<<endl;//显示第几个最终灯被熄灭。
}
}
cout<<"亮灯数:"<<n<<endl;
}
OnlyKnowCJJ 2012-10-04
  • 打赏
  • 举报
回复
倒是说点有用的好么?[Quote=引用 83 楼 的回复:]

考了80分的路过。。
[/Quote]
slz17 2012-10-03
  • 打赏
  • 举报
回复
字符串左移 没人想过ABCDEFG-》GABCDEF-》FGABCDE-》EFGABCD这么移动? O(4n) 感觉翻转一个字符串就很耗时间了
NucleusCode 2012-10-03
  • 打赏
  • 举报
回复
2.100个灯,初始状态亮着,第一次每隔一个灭一个,第二次每隔两个(如果是亮的就灭,反之亮之)。。。依次类推,100次后还剩几个亮着?

解(一):



#include <stdio.h>
#include <math.h>

#define N 100 //灯的总数

int main(void)
{
int sum = 0;//用来累计熄灭的灯的个数
int i;

for(i = 1; i <= N;i++)
{
if((int)(sqrt(i)) * (int)(sqrt(i)) == i)//如果该灯的编号为完全平方数,则有奇数个约数,处于熄灭状态
{
sum++;
}
}

sum = N - sum;

printf("还剩下%d栈灯亮着\n",sum);

return 0;
}

解(二)(其实就是解一演变):

#include <stdio.h>
#include <math.h>

#define N 100 //灯的总数

int main(void)
{
int sum = 0;//用来累计熄灭的灯的个数
sum = N - int(sqrt(N));
printf("还剩下%d栈灯亮着\n",sum);
return 0;
}


解法:
约数的奇数个数即是灭灯数
而 int (sqrt (N)) 即是N的约数的奇数个数
i = int (sqrt (100))
i 即灭灯数


以前做挑战赛时写的,希望对LZ有帮助.
Arthur_Tina 2012-10-03
  • 打赏
  • 举报
回复
[Quote=引用 67 楼 的回复:]

3.
void *pszStringRotate(char *pszString, int nCharsRotate)
{
if (nCharsRotate >= strlen(pszString))
{
return pszString;
}
else
{
char chTemp = '\0';
for(int i = 0; i < strlen(pszString) - ……
[/Quote]
第一,你可以将nCharsRotate对strlen(pszString)取模,这样你的第一个判断就没有必要,取而代之的是取模后如果为0,则直接返回。
第二,你后面根本就没有做任何有意义的操作,你有测试过吗?
Arthur_Tina 2012-10-03
  • 打赏
  • 举报
回复
字符串翻转的终于被我想出来了。以前没有看到过,一直分析,终于有个结果了。5个设计原则参见GRASP设计原则,通常来说有9个,只需写出5个就行了。
bca861862 2012-10-02
  • 打赏
  • 举报
回复
这个是正确的
[Quote=引用 25 楼 的回复:]

题目是面试官找的,你们一样可以找到答案,百度即可.
[/Quote]
Canvas 2012-09-30
  • 打赏
  • 举报
回复
灯泡问题的话,就考虑奇偶次数,......
Canvas 2012-09-29
  • 打赏
  • 举报
回复
字符串那个,时间复杂度为n和空间复杂度为1的话就用字符串反转的方法
irshinning 2012-09-29
  • 打赏
  • 举报
回复
灭灯的最简单
假设都是从第二盏开始灭。不用管每次回灭哪几盏灯,我只需要知道哪一盏灯必灭就行。
比如:
第一次 我肯定第二盏灯必灭 后面不管
第二次 我肯定第三盏灯必灭 后面不管
。。。
最后只剩一盏灯
加载更多回复(71)

64,266

社区成员

发帖
与我相关
我的任务
社区描述
C++ 语言相关问题讨论,技术干货分享,前沿动态等
c++ 技术论坛(原bbs)
社区管理员
  • C++ 语言社区
  • encoderlee
  • paschen
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
  1. 请不要发布与C++技术无关的贴子
  2. 请不要发布与技术无关的招聘、广告的帖子
  3. 请尽可能的描述清楚你的问题,如果涉及到代码请尽可能的格式化一下

试试用AI创作助手写篇文章吧