筆試(Written Test)是一種與面試對應的測試,是考覈應聘者學識水平的重要工具。這種方法可以有效的測量應聘人的基本知識、專業知識、管理知識、綜合分析能力和文字表達能力等素質及能力的差異。下面是企業筆試題目及答案,請參考!
騰訊筆試題:統計論壇在線人數分佈
求一個論壇的在線人數,假設有一個論壇,其註冊ID有兩億個,每個ID從登陸到退出會向一個日誌文件中記下登陸時間和退出時間,要求寫一個算法統計一天中論壇的用戶在線分佈,取樣粒度爲秒。
一天總共有 3600*24 = 86400秒。
定義一個長度爲86400的整數數組int delta[86400],每個整數對應這一秒的人數變化值,可能爲正也可能爲負。開始時將數組元素都初始化爲0。
然後依次讀入每個用戶的登錄時間和退出時間,將與登錄時間對應的整數值加1,將與退出時間對應的整數值減1。
這樣處理一遍後數組中存儲了每秒中的人數變化情況。
定義另外一個長度爲86400的整數數組int online_num[86400],每個整數對應這一秒的論壇在線人數。
假設一天開始時論壇在線人數爲0,則第1秒的人數online_num[0] = delta[0]。第n+1秒的人數online_num[n] = online_num[n-1] + delta[n]。
這樣我們就獲得了一天中任意時間的在線人數。
騰訊筆試題:從10G個數中找到中數
在一個文件中有 10G 個整數,亂序排列,要求找出中位數。內存限制爲 2G。
不妨假設10G個整數是64bit的。
2G內存可以存放256M個64bit整數。
我們可以將64bit的整數空間平均分成256M個取值範圍,用2G的內存對每個取值範圍內出現整數個數進行統計。這樣遍歷一邊10G整數後,我們便知道中數在那個範圍內出現,以及這個範圍內總共出現了多少個整數。
如果中數所在範圍出現的整數比較少,我們就可以對這個範圍內的整數進行排序,找到中數。如果這個範圍內出現的'整數比較多,我們還可以採用同樣的方法將此範圍再次分成多個更小的範圍(256M=2^28,所以最多需要3次就可以將此範圍縮小到1,也就找到了中數)。
騰訊筆試題:兩個整數集合A和B,求其交集
兩個整數集合A和B,求其交集。
1. 讀取整數集合A中的整數,將讀到的整數插入到map中,並將對應的值設爲1。
2. 讀取整數集合B中的整數,如果該整數在map中並且值爲1,則將此數加入到交集當中,並將在map中的對應值改爲2。
通過更改map中的值,避免了將同樣的值輸出兩次。
騰訊筆試題:找出1到10w中沒有出現的兩個數字
有1到10w這10w個數,去除2個並打亂次序,如何找出那兩個數?
申請10w個bit的空間,每個bit代表一個數字是否出現過。
開始時將這10w個bit都初始化爲0,表示所有數字都沒有出現過。
然後依次讀入已經打亂循序的數字,並將對應的bit設爲1。
當處理完所有數字後,根據爲0的bit得出沒有出現的數字。
首先計算1到10w的和,平方和。
然後計算給定數字的和,平方和。
兩次的到的數字相減,可以得到這兩個數字的和,平方和。
所以我們有
x + y = n
x^2 + y^2 = m
解方程可以得到x和y的值。
騰訊筆試題:需要多少隻小白鼠才能在24小時內找到毒藥
有1000瓶水,其中有一瓶有毒,小白鼠只要嘗一點帶毒的水24小時後就會死亡,至少要多少隻小白鼠才能在24小時時鑑別出那瓶水有毒?
最容易想到的就是用1000只小白鼠,每隻喝一瓶。但顯然這不是最好答案。
既然每隻小白鼠喝一瓶不是最好答案,那就應該每隻小白鼠喝多瓶。那每隻應該喝多少瓶呢?
首先讓我們換種問法,如果有x只小白鼠,那麼24小時內可以從多少瓶水中找出那瓶有毒的?
由於每隻小白鼠都只有死或者活這兩種結果,所以x只小白鼠最大可以表示2^x種結果。如果讓每種結果都對應到某瓶水有毒,那麼也就可以從2^x瓶水中找到有毒的那瓶水。那如何來實現這種對應關係呢?
第一隻小白鼠喝第1到2^(x-1)瓶,第二隻小白鼠喝第1到第2^(x-2)和第2^(x-1)+1到第2^(x-1) + 2^(x-2)瓶....以此類推。
回到此題,總過1000瓶水,所以需要最少10只小白鼠。
騰訊筆試題:根據上排的數填寫下排的數,並滿足要求。
根據上排給出十個數,在其下排填出對應的十個數, 要求下排每個數都是上排對應位置的數在下排出現的次數。上排的數:0,1,2,3,4,5,6,7,8,9。
騰訊筆試題:判斷數字是否出現在40億個數中?
給40億個不重複的unsigned int的整數,沒排過序的,然後再給幾個數,如何快速判斷這幾個數是否在那40億個數當中?
答案:
unsigned int 的取值範圍是0到2^32-1。我們可以申請連續的2^32/8=512M的內存,用每一個bit對應一個unsigned int數字。首先將512M內存都初始化爲0,然後每處理一個數字就將其對應的bit設置爲1。當需要查詢時,直接找到對應bit,看其值是0還是1即 可。
1、請定義一個宏,比較兩個數a、b的大小,不能使用大於、小於、if語句#define Max(a,b) ( a/b)?a:b
2、如何輸出源文件的標題和目前執行行的行數
int line = __LINE__;
char *file = __FILE__;
cout<<"file name is "<<(file)<<",line is "<
3、兩個數相乘,小數點後位數沒有限制,請寫一個高精度算法
4、寫一個病毒
while (1)
{
int *p = new int[10000000];
}
5、不使用額外空間,將 A,B兩鏈表的元素交*歸併
6、將樹序列化 轉存在數組或 鏈表中
struct st{
int i;
short s;
char c;
};
sizeof(struct st);
7、
char * p1;
void * p2;
int p3;
char p4[10];
sizeof(p1...p4) =?
8、
4,4,4,10
二分查找
快速排序
雙向鏈表的刪除結點
面試基本上都是和項目相關的,並當場說幾個程序題的輸出,不能用草稿紙