life02

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  197 随笔 :: 3 文章 :: 37 评论 :: 0 Trackbacks

部分腾讯笔试题(2009-10-07 10:21:44)
标签:杂谈   

http://blog.sina.com.cn/s/blog_5dde893c0100fjap.html
1. 1-20的两个数把和告诉A,积告诉B,A说不知道是多少,

B也说不知道,这时A说我知道了,B接着说我也知道了,问这两个数是多少?
答案:2和3

注(本人分析):看了几篇类似的分析,首先我觉得拿出的两个数是不应该重复的,比如不能拿2,2,然而别人分析中没有这么认为。A说不知道,说明由和分解的结果不唯一,而B说不知道也是因为由分解的数不唯一,这时候A说他知道了,我觉得他是把分解的情况做了一个分析,假如分解的情况为x1,x2;y1,y2(如果分解的情况多了的话,我个人认为他不会很快判断出是那个数的),应该有一种情况是x1*x2或者y1*y2的值积分解唯一,而另一个积分解不唯一,因为B说不知道,可以知道答案应该是积分解不唯一的那个,所以A知道了。B在反过来推测,也该得到结论。

在1到20个数中寻找,可以发现2和3满足要求,自我感觉分析有漏洞,智商如此,请高手指点了。

4 如何输出源文件的标题和目前执行行的行数?

答案: printf("The file name: %d\n", __FILE__);

printf("The current line No:%d\n", __LINE__);

ANSI C标准预定义宏:

__LINE__

__FILE__

__DATE__

__TIME__

__STDC__ 当要求程序严格遵循ANSI C标准时该标识符被赋值为1

__cplusplus__ 当编写C++程序时该标识符被定义

7. 希尔 冒泡 快速 插入 哪个平均速度最快?

答案:快速排序nlog2n
快速排序、归并排序和基数排序在不同情况下都是最快最有用的。
8. enum的声明方式

答案:enum 枚举类型名 {

枚举常量1,

枚举常量2,

...

枚举常量n

};

For example:

enum weekday { sunday, monday, tuesday, wednesday, thursday, friday, saturda
y};

enum weekday week_day;//week_day 就是一个枚举类型变量

11. 顺序查找的平均时间

答案:(1+2+3+...+n)/n = (n+1)/2

14.不使用其他变量,交换两个整型a,b的值

答案:x = x+y; y = x-y; x = x-y

还有x=x^y;y=x^y;x=x^y这个更好一些

15. 写出float x 与“零值”比较的if语句。

if(x>=0.000001 && x<=-0.000001)(x不为0的比较)

float: 6位精度

double: 16位精度

2. Internet采用哪种网络协议?该协议的主要层次结构?

答案:TCP/IP协议。应用层、传输层、网络层、数据链路层和物理层。

3. Internet物理地址和IP地址转换采用什么协议?

答案:地址解析协议ARP address resolution protocol

4. IP地址的编码分为哪俩部分?

答案:网络号和主机号。不过是要和“子网掩码”按位与上之后才能区分哪些是网络位
哪些是主机位。

 

大题:

1 把字符串转换为小写,不成功返回NULL,成功返回新串

char* toLower(char* sSrcStr)
{
char* sDest= NULL;
if( __1___)
{
int j;
sLen = strlen(sSrcStr);
sDest = new [_______2_____];
if(*sDest == NULL)
return NULL;
sDest[sLen] = '\0';
while(_____3____)
sDest[sLen] = toLowerChar(sSrcStr[sLen]);
}
return sDest;
}

2 把字符串转换为整数 例如:"-123" -> -123

main()
{
.....
if( *string == '-' )
n = ____1______;
else
n = num(string);
.....
}

int num(char* string)
{
for(;!(*string==0);string++)
{
int k;
k = __2_____;
j = --sLen;
while( __3__)
k = k * 10;
num = num + k;
}
return num;
}

 


附加题:

1 linux下调试core的命令,察看堆栈状态命令
2 写出socks套接字 服务端 客户端通讯程序
3 填空补全程序,按照我的理解是添入:win32调入dll的函数名
查找函数入口的函数名 找到函数的调用形式
把formView加到singledoc的声明 将singledoc加到app的声明


#define Max(a,b) ( a/b)?a:b


写一个病毒
while (1)
       {
              int *p = new int[10000000];
       }

不使用额外空间,将 A,B两链表的元素交叉归并
将树序列化 转存在数组或 链表中
struct st{
int i;
short s;
char c;
};
sizeof(struct st);
答案:8
    char * p1;
    void * p2;
    int *p3;
    char p4[10];
    sizeof(p1...p4) =?
答案:4,4,4,10


二分查找
快速排序
双向链表的删除结点
有12个小球,外形相同,其中一个小球的质量与其他11个不同
给一个天平,问如何用3次把这个小球找出来
并且求出这个小球是比其他的轻还是重
解答:
哈哈,据说这是微软前几年的一个面试题。很经典滴啊!三次一定能求出来,而且能确定是重还是轻。
数据结构的知识还没怎么学透,不过这个题我到是自己研究过,可以分析下。
将12个球分别编号为a1,a2,a3.......a10,a11,a12.
第一步:将12球分开3拨,每拨4个,a1~a4第一拨,记为b1, a5~a6第2拨,记为b2,其余第3拨,记为b3;
第二步:将b1和b2放到天平两盘上,记左盘为c1,右为c2;这时候分两中情况:

1.c1和c2平衡,此时可以确定从a1到a8都是常球;然后把c2拿空,并从c1上拿下a4,从a9到a12四球里随便取三球,假设为a9到a11,放到c2上。此时c1上是a1到a3,c2上是a9到a11。从这里又分三种情况:
      A:天平平衡,很简单,说明没有放上去的a12就是异球,而到此步一共称了两次,所以将a12随便跟11个常球再称一次,也就是第三次,马上就可以确定a12是重还是轻;
      B:若c1上升,则这次称说明异球为a9到a11三球中的一个,而且是比常球重。取下c1所有的球,并将a8放到c1上,将a9取下,比较a8和a11(第三次称),如果平衡则说明从c2上取下的a9是偏重异球,如果不平衡,则偏向哪盘则哪盘里放的就是偏重异球;
      C:若c1下降,说明a9到a11里有一个是偏轻异球。次种情况和B类似,所以接下来的步骤照搬B就是;

2.c1和c2不平衡,这时候又分两种情况,c1上升和c1下降,但是不管哪种情况都能说明a9到a12是常球。这步是解题的关键。也是这个题最妙的地方。
      A:c1上升,此时不能判断异球在哪盘也不能判断是轻还是重。取下c1中的a2到a4三球放一边,将c2中的a5和a6放到c1上,然后将常球a9放到c2上。至此,c1上是a1,a5和a6,c2上是a7,a8和a9。此时又分三中情况:
          1)如果平衡,说明天平上所有的球都是常球,异球在从c1上取下a2到a4中。而且可以断定异球轻重。因为a5到a8都是常球,而第2次称的时候c1是上升的,所以a2到a4里必然有一个轻球。那么第三次称就用来从a2到a4中找到轻球。这很简单,随便拿两球放到c1和c2,平衡则剩余的为要找球,不平衡则哪边低则哪个为要找球;
          2)c1仍然保持上升,则说明要么a1是要找的轻球,要么a7和a8两球中有一个是重球(这步懂吧?好好想想,很简单的。因为a9是常球,而取下的a2到a4肯定也是常球,还可以推出换盘放置的a5和a6也是常球。所以要么a1轻,要么a7或a8重)。至此,还剩一次称的机会。只需把a7和a8放上两盘,平衡则说明a1是要找的偏轻异球,如果不平衡,则哪边高说明哪个是偏重异球;
          3)如果换球称第2次后天平平衡打破,并且c1降低了,这说明异球肯定在换过来的a5和a6两求中,并且异球偏重,否则天平要么平衡要么保持c1上升。确定要找球是偏重之后,将a5和a6放到两盘上称第3次根据哪边高可以判定a5和a6哪个是重球;
      B:第1次称后c1是下降的,此时可以将c1看成c2,其实以后的步骤都同A,所以就不必要再重复叙述了。至此,不管情况如何,用且只用三次就能称出12个外观手感一模一样的小球中有质量不同于其他11球的偏常的球。而且在称的过程中可以判定其是偏轻还是偏重。

给一个奇数阶N幻方,填入数字1,2,3...N*N,使得横竖斜方向上的和都相同
答案:
#include<iostream>
#include<iomanip>
#include<cmath>
usingnamespace std;
int main()
{
 int n;
 cin>>n;
 int i;
 int **Matr=newint*[n];//动态分配二维数组
 for(i=0;i<n;++i)
      Matr[ i ]=newint[n];//动态分配二维数组
 //j=n/2代表首行中间数作为起点,即1所在位置
 int j=n/2,num=1;//初始值
 i=0;
 while(num!=n*n+1)
 {
//往右上角延升,若超出则用%转移到左下角
      Matr[(i%n+n)%n][(j%n+n)%n]=num;
    //斜行的长度和n是相等的,超出则转至下一斜行
    if(num%n==0)
          i++;
   else
      {
          i--;
          j++;
     }
      num++;
 }
 for(i=0;i<n;i++)
 {
      for(j=0;j<n;++j)
         cout<<setw((int)log10(n*n)+4)<<Matr[ i][ j ];//格式控制
      cout<<endl<<endl;//格式控制
 }
for(i=0;i<n;++i)
      delete [ ]Matr[ i ];
return1;
}
腾讯的一道面试题:(与百度相似,可惜昨天百度死在这方面了)////
在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可。
答案:
1, 把整数分成256M段,每段可以用64位整数保存该段数据个数,256M*8 = 2G内存,先清0
2,读10G整数,把整数映射到256M段中,增加相应段的记数
3,扫描256M段的记数,找到中位数的段和中位数的段前面所有段的记数,可以把其他段的内存释放
4,因中位数段的可能整数取值已经比较小(如果是32bit整数,当然如果是64bit整数的话,可以再次分段),对每个整数做一个记数,再读一次10G整数,只读取中位数段对应的整数,并设置记数。
5,对新的记数扫描一次,即可找到中位数。
如果是32bit整数,读10G整数2次,扫描256M记数一次,后一次记数因数量很小,可以忽略不记
(设是32bit整数,按无符号整数处理
整数分成256M段? 整数范围是0 - 2^32 - 1 一共有4G种取值,4G/256M = 16,每16个数算一段 0-15是1段,16-31是一段,...
整数映射到256M段中?如果整数是0-15,则增加第一段记数,如果整数是16-31,则增加第二段记数,...

其实可以不用分256M段,可以分的段数少一写,这样在扫描记数段时会快一些,还能节省一些内存)


腾讯题二:
一个文件中有40亿个整数,每个整数为四个字节,内存为1GB,写出一个算法:求出这个文件里的整数里不包含的一个整数
答:
方法一: 4个字节表示的整数,总共只有2^32约等于4G个可能。
为了简单起见,可以假设都是无符号整数。
分配500MB内存,每一bit代表一个整数,刚好可以表示完4个字节的整数,初始值为0。基本思想每读入一个数,就把它对应的bit位置为1,处理完40G个数后,对500M的内存遍历,找出一个bit为0的位,输出对应的整数就是未出现的。
算法流程:
1)分配500MB内存buf,初始化为0
2)unsigned int x=0x1;
    for each int j in file
    buf=buf ¦x < <j;
    end
(3) for(unsigned int i=0; i <= 0xffffffff; i++)
        if (!(buf & x < <i))
        {
            output(i);
            break;
        }
以上只是针对无符号的,有符号的整数可以依此类推。
方法二:
文件可以分段读啊,这个是O(2n)算法,应该是很快的了,而且空间也允许的。
不过还可以构造更快的方法的,更快的方法主要是针对定位输出的整数优化算法。
思路大概是这样的,把值空间等分成若干个值段,比如值为无符号数,则
00000000H-00000FFFH
00001000H-00001FFFH
......
0000F000H-0000FFFFH
.....
FFFFF000H-FFFFFFFFH
这样可以订立一个规则,在一个值段范围内的数第一次出现时,对应值段指示值Xn=Xn+1,如果该值段的所有整数都出现过,则Xn=1000H,这样后面输出定位时就可以直接跳过这个值段了,因为题目仅仅要求输出一个,这样可以大大减少后面对标志数值的遍历步骤。
理论上值段的划分有一定的算法可以快速的实现,比如利用位运算直接定位值段对应值进行计算。

posted on 2009-10-23 15:00 life02 阅读(1129) 评论(0)  编辑 收藏 引用 所属分类: 笔试

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理