2014騰訊筆試題目
簡答題：
1、請(qǐng)?jiān)O(shè)計(jì)一個(gè)排隊(duì)系統(tǒng)，能夠讓每個(gè)進(jìn)入隊(duì)伍的用戶都能看到自己在 中所處的位置和變化。隊(duì)伍可能隨時(shí)有人加入和退出，當(dāng)有人退出影響到用戶的位置排名時(shí)需要即時(shí)反饋到用戶。
2、A、B兩個(gè)整數(shù)集合，設(shè)計(jì)一個(gè)算法求他們的交集，盡可能的高效。
(博主能力有限，不是所有題目都會(huì)求解，第1題不是我的擅長，這里貼出來讓大家知道騰訊的考題。我的重點(diǎn)放在第2題上面!)
第2題 題解(個(gè)人見解，僅供參考!)
思路1：排序法
對(duì)集合A和集合B進(jìn)行排序(升序，用快排，平均復(fù)雜度O(N*logN))，設(shè)置兩個(gè)指針p和q，同時(shí)指向集合A和集合B的最小值，不相等的話移動(dòng)*p和*q中較小值的指針，相等的話同時(shí)移動(dòng)指針p和q，并且記下相等的數(shù)字，為交集的`元素之一，依次操作，直到其中一個(gè)集合沒有元素可比較為止。
優(yōu)點(diǎn)：操作簡單，容易實(shí)現(xiàn)。
缺點(diǎn)：使用的排序算法不當(dāng)，會(huì)耗費(fèi)大量的時(shí)間，比如對(duì)排好序的集合使用快排， 時(shí)間復(fù)雜度是O(N2)這種算法是大家都能比較快速想到的辦法，絕大多數(shù)時(shí)間放在了對(duì)集合的排序上，快排的平均復(fù)雜度是O(N*logN)，對(duì)排好序的集合做查找操作，時(shí)間復(fù)雜度為O(N)，當(dāng)然這種算法肯定比遍歷要快多了。
code：
#include
#include
#define M 8
#define N 5
int cmp(const void *a, const void *b)
{
int *x = (int *)a;
int *y = (int *)b;
return (*x) - (*y);
}
int main(void)
{
int A[] = {-1, 2 ,39 ,10, 6, 11, 188, 10};
int B[] = {39 ,8 , 10, 6, -1};
//對(duì)數(shù)組A和數(shù)組B進(jìn)行快排
qsort(A, M, sizeof(int), cmp);
qsort(B, N, sizeof(int), cmp);
//FindIntersection(A, B);
int i = 0, j = 0;
int cnt = 0;
int result[M > N ? M : N];//保存集合的結(jié)果
//設(shè)置i、j索引，分別指向數(shù)組A和B，相等則同時(shí)移動(dòng)，不相等則移動(dòng)較小值的索引
【2014騰訊筆試題目】相關(guān)文章：
騰訊前端筆試題目01-15
騰訊技術(shù)筆試題目01-16
騰訊筆試題目初試11-05
騰訊hr崗位筆試題目09-03
騰訊運(yùn)營的筆試題目01-16
騰訊校招筆試題目12-20
騰訊軟件測(cè)試筆試題目10-23
騰訊人力資源筆試題目07-03
2016年騰訊模擬筆試題目匯總01-15