# 群聯考古題
## 群聯三題

## Q1

/* 給一個int a[20]已排序的陣列，請寫一個function(a, size)能印出0~500的數字，
   且不包含a陣列內的元素，請用最少的時間和空間複雜度完成 */
void function(int* a, int size) 
{
    int* ptr = a;
    for (int i = 0; i <= 500; i++) 
    {
        if (*ptr == i) 
            ptr++;
        else
            printf("%d", i); 
    }
}

## Q2

/*給一個int a[20]已排序的陣列，請寫一個function(a, size, b) 能依照參數b(b = 0~4)別印出該區間的數字，
  且不包含a陣列內的元素，例如 b =0, 印出0~99 b = 1, 印出100~199 */
void function(int *a, int size, int b)
{
    int *ptr = a;
    int i;

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

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

## Q3: 情境題

/*給予一個 structure 
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"  */

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");

            // check condtion 2
            next_entry = ListArray[found_entry].NextPtr;
            if (ListArray[next_entry].DataH << 16 + ListArray[next_entry].DataL >
                DATA_A << 16 + DATA_B)
                break;
        }
        // update entry
        pre_entry = found_entry;
        found_entry = ListArray[found_entry].NextPtr;
    }
}

## binary serach

int binsearch(int* arr, int k, int n) {
  int left = 0, right = n;
  while (left <= right) {
    int mid = (left+right)/2;
    if (arr[mid] > k) {       // 往左半部找
      right = mid - 1;
    }
    else if (arr[mid] < k) {  // 往右半部找
      left = mid + 1;
    }
    else
      return mid;
  }
  return -1; // not found
}

## 給一個unsigned short, 問換算成16進制後四個值是否相同? 若是回傳1,否則回傳0

int isHexEqaul(unsigned short input) {     // input = 0xAAAA;
    unsigned short input;
    unsigned short hex[4]; // 0xFFFF ==> 0000 0000 0000 0000
    int is_eqaul;

    hex[0] = (input & 0xF000) >> 12;
    hex[1] = (input & 0x0F00) >> 8;
    hex[2] = (input & 0x00F0) >> 4;
    hex[3] = input & 0x000F;

    is_eqaul = ((hex[0] == hex[1]) && (hex[1] == hex[2]) && (hex[2] == hex[3]));
    return is_eqaul;
}

## 求一個數的最高位1在第幾位

int main()
{
    unsigned int a = 0x65; // 0110 0101
    unsigned int test_bit = 128; // 1000 0000
    int count = 7;  // sizeof(unsigned int)*8   == 該data type的bit數
    while (((a & test_bit) >> count) != 1) {
        count--;
        test_bit >>= 1;
    }
    printf("hightest bit is %d th bit\n", count);
    
    return 0;
}

## 最大公因數 遞迴寫法

int gcd(int x, int y) { // x > y
    if (y == 0)  /* 餘 0，除數 x 即為最大公因數 */
        return x;
    else
        return gcd(y, x % y);  /* 前一步驟的除數為被除數，餘數為除數 */
}

## 字串反轉 (Reverse String)

void swap(char* a, char* b) {
    char t = *a;
    *a = *b;
    *b = t;
}

void reverseString(char* s, int sSize){
    if (s == NULL) return NULL;
    int j = sSize - 1;
    for (int i = 0; i < sSize/2; i++) {
        swap( &s[i], &s[j] );
        j--;
    }
}

## quick sort

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
int Partition(int *arr, int front, int end){
    int pivot = arr[end];
    int i = front -1;
    for (int j = front; j < end; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    i++;
    swap(&arr[i], &arr[end]);
    return i;
}
void QuickSort(int *arr, int front, int end){
    if (front < end) {
        int pivot = Partition(arr, front, end);
        QuickSort(arr, front, pivot - 1);
        QuickSort(arr, pivot + 1, end);
    }
}