程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 騰訊面試題，騰訊試題

騰訊面試題，騰訊試題

編輯：C++入門知識

騰訊面試題，騰訊試題

1、請定義一個宏，比較兩個數a、b的大小，不能使用大於、小於、if語句
2、如何輸出源文件的標題和目前執行行的行數
3、兩個數相乘，小數點後位數沒有限制，請寫一個高精度算法
4、寫一個病毒
5、有A、B、C、D四個人，要在夜裡過一座橋。他們通過這座橋分別需要耗時1、2、5、10分鐘，只有一支手電，並且同時最多只能兩個人一起過橋。請問，如何安排，能夠在17分鐘內這四個人都過橋？

2008年騰訊招聘
選擇題 (60)
c/c++ os linux 方面的基礎知識 c的Sizeof函數有好幾個 !
程序填空 (40)
1.(20) 4空 x5
不使用額外空間,將 A,B兩鏈表的元素交叉歸並
2.(20) 4空 x5
MFC 將樹序列化轉存在數組或鏈表中 !

1, 計算 a^b << 2 (運算符優先級問題 )

2 根據先序中序求後序

3 a[3][4]哪個不能表示 a[1][1]: *(&a[0][0]) *(*(a+1)+1) *(&a[1]+1) *(&a[0][0]+4)

4 for(int i...)
for(int j...)
printf(i,j);
printf(j)
會出現什麼問題

5 for(i=0;i<10;++i,sum+=i);的運行結果

6 10個數順序插入查找二叉樹，元素62的比較次數

7 10個數放入模10hash鏈表，最大長度是多少

8 fun((exp1,exp2),(exp3,exp4,exp5))有幾個實參

9 希爾冒泡快速插入哪個平均速度最快

10 二分查找是順序存儲鏈存儲按value有序中的哪些

11 順序查找的平均時間

12 *p=NULL *p=new char[100] sizeof(p)各為多少

13 頻繁的插入刪除操作使用什麼結構比較合適，鏈表還是數組

14 enum的聲明方式

15 1-20的兩個數把和告訴A,積告訴B，A說不知道是多少，

B也說不知道，這時A說我知道了，B接著說我也知道了，問這兩個數是多少

大題：

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的聲明

4 有關系 s(sno,sname) c(cno,cname) sc(sno,cno,grade)
1 問上課程 "db"的學生 no
2 成績最高的學生號
3 每科大於90分的人數主要是c/c++、數據結構、操作系統等方面的基礎知識。好像有sizeof、樹等選擇題。填空題是補充完整程序。附加題有寫算法的、編程的、數據庫sql語句查詢的。還有一張開放性問題。請定義一個宏，比較兩個數a、b的大小，不能使用大於、小於、if語句 #define Max(a,b) ( a/b)?a:b
如何輸出源文件的標題和目前執行行的行數 int line = __LINE__; char *file = __FILE__; cout<<"file name is "<<(file)<<",line is "<<line<<endl; 兩個數相乘，小數點後位數沒有限制，請寫一個高精度算法
寫一個病毒 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>

using
namespace
 std;

int
 main()

 
int
 n;

 cin>>n;

 
int
 i;

 
int
 **Matr=
new
int
*[n];
//
動態分配二維數組

 
for
(i=
0
;i<n;++i)

       Matr[ i ]=
new
int
[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 ];

return
1
;

騰訊的一道面試題 :( 與百度相似 , 可惜昨天百度死在這方面了 )//// 在一個文件中有 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，這樣後面輸出定位時就可以直接跳過這個值段了，因為題目僅僅要求輸出一個，這樣可以大大減少後面對標志數值的遍歷步驟。
理論上值段的劃分有一定的算法可以快速的實現，比如利用位運算直接定位值段對應值進行計算。騰訊面試題 : 有1到10w這10w個數，去除2個並打亂次序，如何找出那兩個數。（不准用位圖！！）位圖解決: 位圖的方法如下
假設待處理數組為 A[10w-2]
定義一個數組B[10w],這裡假設B中每個元素占用1比特,並初始化為全 0
for(i=0;i <10w-2;i++)
{
B[ A[i] ]=1
}
那麼B中不為零的元素即為缺少的數據
這種方法的效率非常高，是計算機中最常用的算法之一其它方法:     求和以及平方和可以得到結果，不過可能求平方和運算量比較大（用64位int不會溢出）騰訊面試題 : 騰訊服務器每秒有2w個QQ號同時上線，找出5min內重新登入的qq號並打印出來。解答: 第二題如果空間足夠大,可以定義一個大的數組
a[qq號],初始為零,然後這個qq號登陸了就a[qq號 ]++
最後統計大於等於2的QQ號
這個用空間來代替時間第二個題目，有不成熟的想法。
2w x 300s
所以用 6,000,000 個桶。刪除超時的算法後面說，所以平均桶的大小是 1 。
假設 qq 號碼一共有 10^10 個，所以每個桶裝的 q 號碼是 10^10 / (6 * 10^6) 個，這個是插入時候的最壞效率（插入同一個桶的時候是順序查找插入位置的）。
qq的節點結構和上面大家討論的基本一樣，增加一個指針指向輸出列表，後面說。
struct QQstruct {
   num_type    qqnum;
   timestamp   last_logon_time;
   QQstruct    *pre;
   QQstruct    *next;
   OutPutList *out;     // 用於 free 節點的時候，順便更新一下輸出列表。
}

另外增加兩個指針列表。
第一個大小 300 的循環鏈表，自帶一個指向 QQStruct 的域，循環存 300 秒內的qq指針。時間一過
就 free 掉，所以保證所有桶占用的空間在 2w X 300 以內。
第二個是輸出列表，就是存放題目需要輸出的節點。
如果登陸的用戶，5分鐘內完全沒有重復的話，每秒 free 掉 2w 個節點。
不過在 free 的時候，要判斷一下時間是不是真的超時，因為把節點入桶的時候，遇到重復的，會更
新一下最後登陸的時間。當然啦，這個時候，要把這個 qq 號碼放到需要輸出的列表裡面。

騰訊的後台開發的面試

名企面試最看中的七點關鍵能力

找到一份理想的工作是大學畢業生們最大的心願，而進入那些知名的大企業更是廣大畢業生的夢想。如何應付這些企業的面試成為了畢業生們最為關注的話題。

這些名企的面試往往有一定的程序，絕非草草而就。因此，一定要有所准備才能“百戰不殆”。而要在面試前得到有關信息，常常采用的有這樣幾個方法：1.充分利用人際關系，與近年進入該企業工作的師兄師姐溝通，以預測面試題目的方向；2.查詢該企業的資料，深入了解該企業的企業文化特點，聯系當前情況，自己預測考題；3.利用網絡資源，登錄該企業網站，查詢相關信息及面試題目。從目前的情況來看，最普遍也最為有效的方式，仍然是向往屆畢業生咨詢相關信息。

面試題往往與各公司的企業文化和重點關注的東西有密切的關系，我們可以做出如下總結：

*忠誠度：面臨跳槽，企業往往會看重應聘學生對忠誠度的看法。尤其是一些國有大型企業，更為重視員工的忠誠度。在近日康佳集團的招聘中，面試官就提出了“請分析職業技能和忠誠度哪個對企業更重要”的問題。

*實踐能力：在注重學生學習成績的同時，相當多的企業非常重視應聘者的實踐經歷。例如通用電氣（中國）有限公司（GE）就表示他們要招聘的絕不是簡單的“學習機器”，在校期間實習、兼職、家教的經驗都是積累社會經驗的好機會，這都應該受到企業的重視。

*團隊協作精神：經營規模宏大的名企往往非常重視員工的團隊協作精神。例如聯想集團人力資源部的有關負責人就表示，該公司尤其歡迎具有團隊協作精神的應聘者。

*創新精神：對於大型企業來說，離開了不斷的創新，就等於失去了生命力，因此應聘者是否具有創新精神也是重點要考查的。如聯想集團在面試中就十分重視應聘者的創新精神和能力。

*對企業文化的認可程度：企業在招聘過程中常常會考慮到員工是否能夠認可和適應該企業的價值觀和企業文化，這將決定員工是否能夠很好地為企業服務。例如SONY公司在招聘過程中把員工能否適應日本文化尤其是索尼的企業文化作為重點考核內容。通用電氣有限公司在招聘中也要看學生是否喜歡、是否認同GE的價值觀，即“堅持誠信、注重業績、渴望變革”。

*人際交往能力和良好的溝通能力：如SONY把人際溝通能力作為重點考核內容，而畢博管理咨詢有限公司人力資源部的經理則透露，畢博在招聘過程中非常重視學生的溝通技巧，因為作為未來的咨詢師，應聘者一定要具有與客戶溝通、協調的能力。

*對新知識新能力的求知態度和學習能力：一位企業負責人表示，應屆畢業生往往不具備直接進行業務操作的能力，基本上都要經過系統的培訓，所以學習能力和求知欲應該是重點考查的內容。很多企業都堅持這一原則。通用電氣的公關總監表示，公司不是很在乎應屆生與公司要求之間的差距，因為他們對於自己的培訓體系非常自信，只要有強烈的求知欲和學習能力一定可以通過系統的培訓脫穎而出，因此在面試中這兩項考核十分關鍵。此外，UT斯達康、歐萊雅、安永……都表示是否具備良好的學習能力和強烈的求知欲是企業十分重視的。