[面試] 群聯面試前練習：群聯三題

發表於

面試不外乎要準備自介、履歷、工作經驗、白板題、以及碩碖與作品集等等

當然最令人擔心的，當然還是會讓人緊張的白板題

以下會先練習一下網路看到的題目以及想不出來時，探討最後找到的答案

我們立即開始吧！！

知名的「群聯面試三題」

Q1: 給一個int a[20]已排序的陣列，請寫一個function(a, size)能印出0~500的數字，且不包含a陣列內的元素，請用最少的時間和空間複雜度完成。

這個就照著題目的描述寫程式就可以了

1
2
3
4
5
6
7
8
9
10
11
12
/* You may call function through function(a, size) */
void function(int *in, int size)
{
    int *ptr = in;
    int i;
    for (i=0; i<=500; i++) {
        if (*ptr == i)
	    ptr++;
	else
	    printf("%d\n", i);
    }
}

Q2: 給一個int a[20]已排序的陣列，請寫一個function(a, size, b)能依照參數b(b = 0~4)別印出該區間的數字，且不包含a陣列內的元素，例如：

1
2
3
　b = 0, 印出0~99
　b = 1, 印出100~199
　...

請用最少的時間和空間複雜度完成。

這個呢？就還是一樣，照著描述寫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void function(int *a, int size, int b)
{
    int *ptr = a;
    int i;

    while (*ptr < b * 100)
        ptr++;

    if (i=b*100; i<(b+1)*100; i++) {
        if (*ptr == i)
	    ptr++;
	else
	    printf("%d\n", i);
    }
}

Q3: 情境題，給予一個 structure

1
2
3
4
5
6
7
8
struct ListStruct{
    unsigned int DataH;
    unsigned int DataL;
    unsigned int NextPtr;
};
struct ListStruct ListArray[1000];
#define NULL 0xFFFF
unsigned int ListHead = 0;

其中有兩個條件

  • 條件一
    ListArray[Entry1].NextPtr = ListArray[Entry2]
  • 條件二
    ListArray[Entry2].DataH << 16 + ListArray[Entry2].DataL > ListArray[Entry1].DataH << 16 + ListArray[Entry1].DataL

也就是說第一個 index 中的 NextPtr 會只到另一個 index 中的起始位址
再來是另一個 index 中的起始位址的資料內容大小一定大於原起始資料的大小

請寫一個function(unsigned int DATA_A, unsigned int DATA_B)，
能在ListArray中找到符合ListArray[Entry].DataH == Data_A 且 ListArray[Entry].DataL == Data_B
並印出其結果。如果沒有找到的話，印出”no found.”。

okay, 我們根據問題描述，將程式寫出來

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Q3(unsigned int DATA_A, unsigned int DATA_B)
{
    int found_entry = ListHead;
    int pre_entry = NULL;
    int next_entry = NULL;

    while (ListArray[found_entry].NextPtr != NULL) {
        if (ListArray[found_entry].DataH == DATA_A && ListArray[found_entry].DataL == DATA_B) {
	    if (pre_entry == NULL)
	        printf("pre_entry = NULL, found_entry = ListHead\n");
            else
	        printf("pre_entry = %d, found_entry = %d", pre_entry, found_entry);
	    printf("found it\n");

	    next_entry = ListArray[found_entry].NextPtr;
	    if (ListArray[next_entry].DataH << 16 + ListArray[next_entry].DataL >
	        DATA_A << 16 + DATA_B)
		break;
	}

	pre_entry = found_entry;
	found_entry = ListArray[found_entry].NextPtr;
    }

}

其餘在面試中會可能會抽考的題目

Sorting

接下來是 sorting

直接寫 quick sort 好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void QuickSort(int *array, int left, int right)
{
    if (left < right) {
        int i= left-1, j=right+1;
        int mid = info[(left+right)/2].signal_level;

        while (true) {
            while(info[++i].signal_level > mid);
            while(info[--j].signal_level < mid);

            if (i>=j)
                break;

            swap(info, i, j);
        }

        QuickSort(info, left, i-1);
        QuickSort(info, j+1, right);
    }
}

工作經驗中可能會考的內容

Page / Block / Read / Write 等等的概念

想問的問題

  1. PCIE 這麼高速的介面，在傳輸中可能會造成那些影響？

  2. NAND flash 看過有人直接取走的，取走後是不是有辦法透過特殊加解密使得資料無法被竊取？

  3. 公司有給予員工進修的福利嗎？

  4. 群聯這樣的公司，理論上會有許多核心技術取得，公司