歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

騰訊2014軟件開發筆試題目

騰訊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

Copyright © Linux教程網 All Rights Reserved