騰訊2014軟件開發筆試題目
-----9月21日，騰訊2014軟件開發校招-簡答題-廣州
簡答題：
1、請設計一個排隊系統，能夠讓每個進入隊伍的用戶都能看到自己在 中所處的位置和變化。隊伍可能隨時有人加入和退出，當有人退出影響到用戶的位置排名時需要即時反饋到用戶。
2、A、B兩個整數集合，設計一個算法求他們的交集，盡可能的高效。
（博主能力有限，不是所有題目都會求解，第1題不是我的擅長，這裡貼出來讓大家知道騰訊的考題。我的重點放在第2題上面！）
第2題 題解（個人見解，僅供參考！）
思路1：排序法
對集合A和集合B進行排序（升序，用快排，平均復雜度O(N*logN)），設置兩個指針p和q，同時指向集合A和集合B的最小值，不相等的話移動*p和*q中較小值的指針，相等的話同時移動指針p和q，並且記下相等的數字，為交集的元素之一，依次操作，直到其中一個集合沒有元素可比較為止。
優點：操作簡單，容易實現。
缺點：使用的排序算法不當，會耗費大量的時間，比如對排好序的集合使用快排， 時間復雜度是O(N2)
這種算法是大家都能比較快速想到的辦法，絕大多數時間放在了對集合的排序上，快排的平均復雜度是O(N*logN)，對排好序的集合做查找操作，時間復雜度為O（N），當然這種算法肯定比遍歷要快多了。
code：
#include <stdio.h>
#include <stdlib.h>
#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};
//對數組A和數組B進行快排
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];//保存集合的結果
//設置i、j索引，分別指向數組A和B，相等則同時移動，不相等則移動較小值的索引
while(i < M && j < N)
{
if(A[i] == B[j])
{
result[cnt] = A[i];
i++;
j++;
cnt++;
}
else if(A[i] < B[j])
{
i++;
}
else
{
j++;
}
}
for(i = 0; i < cnt; i++)
{
printf("%4d", result[i]);
}
return 0;
}
接下來請看第2頁精彩內容：http://www.linuxidc.com/Linux/2013-10/90813p2.htm
