发布于 2014-12-19 02:55:32 | 195 次阅读 | 评论: 0 | 来源: 网友投递
腾讯
腾讯控股有限公司（腾迅）是一家民营IT企业，成立于1998年11月29日，总部位于中国广东深圳，是中国最大的互联网综合服务提供商之一，也是中国服务用户最多，最广的互联网企业之一。
本文为大家整理的提供的是一份腾讯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
#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};
//对数组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;
}