部分騰訊筆試題(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位置為１，處理完40G個數后，對500M的內存遍歷，找出一個bit為0的位，輸出對應的整數就是未出現的。
算法流程：
１）分配５００ＭＢ內存buf，初始化為０
２）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，這樣后面輸出定位時就可以直接跳過這個值段了，因為題目僅僅要求輸出一個，這樣可以大大減少后面對標志數值的遍歷步驟。
理論上值段的劃分有一定的算法可以快速的實現，比如利用位運算直接定位值段對應值進行計算。