interview

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void Q1(int * a , int size);
void Q2(int * a , int size , int b);
void Q3(unsigned int DATA_A,unsigned int DATA_B);

#define TEST_BENCH_SIZE     20
#define TEST_BENCH_MAX_NUM  500

#define SWAP(x,y,t) ( (t)=(x) , (x)=(y) , (y)=(t) )

// Q3
struct ListNode{
    unsigned int Data_H;
    unsigned int Data_L;
    unsigned int next_ptr;
};

struct ListNode ListArray[500];
#define Null 0xffff
unsigned int listhead=0;

/* Quick Sort */
void QuickSort(int a[],int left,int right)
{
    int pivot,i,j,temp=0;
    if(left < right)
    {
        i = left ; j = right + 1;
        pivot = a[left];
        //printf("init pivot = %d i=%d j=%d\n",pivot,i,j);
        do
        {
            do i++; while(a[i] < pivot && i<right);
            do j--; while(a[j] > pivot && j>left);
           // printf("[i=%d , j=%d]\n",i,j);
            if (i<j) SWAP(a[i],a[j],temp);
           // printAry(a, left,right+1);
        } while (i<j);
        SWAP(a[left],a[j],temp);
        //printAry(a, left, right+1);
        QuickSort(a, left, j-1);
        QuickSort(a, j+1, right);
    }
}

int BinarySearch(int* a,int size,int target){
    int L=0;
    int R=size-1;
    int mid;
    int index=0;
    while(L<R){
        mid=(L+R)/2;
        if(a[mid]==target){
            return mid;
        }
        else if(a[mid]>target){
            R=mid-1;
        }
        else if(a[mid]<target){
            L=mid+1;
        }
    }
    return L;
}

int main()
{
    // Create a sorted array with random
    int test_bench1[TEST_BENCH_SIZE] = {0};

    // Set random seed
    srand(time(NULL));

    // Set data
    printf("Set data\n");
    for(int i = 0 ; i < TEST_BENCH_SIZE ; i++)
    {
        test_bench1[i] = rand( ) % TEST_BENCH_MAX_NUM + 1;
        printf("[%d] %d\n" , i, test_bench1[i]);
    }

    // Sorted
    QuickSort(test_bench1 , 0 , TEST_BENCH_SIZE);

    printf("Sorted data\n");
    for(int i = 0 ; i < TEST_BENCH_SIZE ; i++)
    {
        printf("[%d] %d\n" , i, test_bench1[i]);
    }

    printf("Q1\n");
    Q1(test_bench1 , TEST_BENCH_SIZE);

    printf("Q2\n");
    Q2(test_bench1 , TEST_BENCH_SIZE , 0);

    system("pause");
    return 0;
}

void Q1(int * a , int size)
{
    int x=0,i=0;
    int x_limit = 501;
    for( ; x < x_limit && i < size ; x++)
    {
        if ( x == a[i] )
            i++;
        else
            printf("%d %d %d\n" , x , i , a[i]);
    }

    for( ; x < x_limit  ; x++)
        printf("%d\n" , x);
}

void Q2(int * a , int size , int b)
{
    int lo_bound = b*100;
    int up_bound = (b+1)*100;
    int mid = size / 2;
    int x  = lo_bound;

    int startIdx = BinarySearch(a , size , lo_bound);

    for (int i = startIdx ; x < up_bound && i < size ; x++)
    {
        if ( x == a[i] )
            i++;
        else
            printf("%d %d %d\n" , x , i , a[i]);
    }

    for( ; x < up_bound  ; x++)
        printf("%d\n" , x);
}


void Q3(unsigned int DATA_A,unsigned int DATA_B)
{

    struct ListNode * curNode = &ListArray[listhead];

    for( ; curNode != NULL ; curNode = curNode->next_ptr )
    {
        // Search DATA_A
        if ( curNode->Data_H == DATA_A )
        {
            // If found
            // Search Data_B
            goto FIND_DATA_B;
        }
    }

    goto NOT_FOUND;

    FIND_DATA_B:

    for( ; curNode != NULL ; curNode = curNode->next_ptr )
    {
        if ( curNode->Data_H != DATA_A )
        {
            // If found
            // Search Data_B
            goto NOT_FOUND;
        }

        // Search DATA_B
        if ( curNode->Data_L == DATA_B )
        {
            // If found
            printf("Found data %d %d\n" , DATA_A , DATA_B);
            return;
        }
    }

    NOT_FOUND:

    printf("Not found\n");
}