现在的位置: 首页 > 综合 > 正文

几道简单的面试题

2018年03月16日 ⁄ 综合 ⁄ 共 4953字 ⁄ 字号 评论关闭

1、寻找一个单向链表的倒数第n个节点;

2、二分查找以及二分查找寻找上下界;

3、求交叉链表的第一个交叉节点;

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std ;
struct _link_node{
    int data ;
    struct _link_node *next ;
} ;
struct _link_node* create_linklist(int data[],int len){
    assert(data!=NULL) ;
    struct _link_node *pRoot = (struct _link_node*)malloc(sizeof(struct _link_node)) ;
    //pRoot->next = NULL ;
    struct _link_node *pTmp = pRoot ;
    for(int i=0;i<len;i++){
        pTmp->next=(struct _link_node*)malloc(sizeof(struct _link_node)) ;
        pTmp->next->data = data[i] ;
        pTmp = pTmp->next ;
    }
    pTmp->next = NULL ;
    return pRoot ;
}
struct _link_node* print_link(struct _link_node* pRoot){
    struct _link_node *pTmp = pRoot ;
    while(pTmp->next!=NULL){
        printf("%d,",pTmp->next->data) ;
        pTmp=pTmp->next ;
    }
}
struct _link_node* get_reverse_n(struct _link_node* pRoot,int n){
    assert(pRoot!=NULL) ;
    struct _link_node *pPre = pRoot ;
    struct _link_node *pTail = pRoot ;
    int cnt = 0 ;
    /*使用两个指针,第一个指针比第一个指针先走n步,两个指针再一起移动,
    当先走指针走向末尾时,另外一个指针所指向的位置就是倒数第n个*/
    while(cnt<n){
        if(pPre==NULL){
            return NULL ;
        }
        cnt++ ;
        pPre=pPre->next ;
    }
    while(pPre!=NULL&&pPre->next!=NULL){
        pPre=pPre->next ;
        pTail=pTail->next ;
    }
    return pTail->next ;
}
void PrintMeet(){
    int hour=0 ;
    int minutes=0 ;
    for(int i=1;i<6;i++){//模拟时针每走一小时,角度是30度
        hour+=30 ;
        for(int j=0;j<60;j++){//模拟秒针走,一步角度为6;
            minutes+=6 ;
            if(minutes%360==hour){
                printf("time=%d:%d\n",hour/30,minutes%360/6) ;
            }
        }
    }
}

int binary_search(int array[],int low,int high,int target){
    if(low>high||array[high]<target){//advance abort
        return -1 ;
    }
    int mid = low+((high-low)>>1) ;
    while(low<=high){
        mid = low+((high-low)>>1) ;
        if(array[mid]<target){
            low = mid+1 ;
        }else if(array[mid]>target){
            high = mid-1 ;
        }else{
            return mid ;
        }
    }
    return -1 ;
}
int binary_search1(int array[],int low,int high,int target){
    if(low>high){
        return -1 ;
    }else{
        int mid = low+((high-low)>>1) ;
        if(array[mid]>target){
            high = mid-1 ;
            binary_search1(array,low,high,target) ;
        }else if(array[mid]<target){
            low = mid + 1 ;
            binary_search1(array,low,high,target) ;
        }else{
            return mid ;
        }
    }
}
int binary_find_upper_bound(int array[],int low,int high,int target){
    if(low>high||array[high]<target){//advance abort
        return -1 ;
    }
    int mid =low + ((high-low)>>1) ;
    while(low<high){

        if(array[mid]>target){
            high = mid ;
        }else{
            low = mid+1 ;
        }
        mid = low+((high-low)>>1) ;
    }
    return array[mid] ;
}
int binary_find_lower_bound(int array[],int low,int high,int target){
    if(low>high||array[high]<target){//advance abort
        return -1 ;
    }
    int mid = low+((high-low)>>1) ;
    while(low<high){
        if(array[mid]<target){
            low = mid ;
        }else{
            high=mid-1 ;
        }
        mid = low + ((high-low+1)>>1) ;//note:here we must add 1 to compute mid
    }
    return array[mid] ;
}
int find_first_cross_node(struct _link_node*pFirst, struct _link_node *pSecond){
    assert(pFirst!=NULL&&pSecond!=NULL) ;
    int len_first=0 ;
    int len_second=0 ;
    struct _link_node *pTmp1=pFirst ;
    struct _link_node *pTmp2=pSecond ;

//first compute length of the two link list
    while(pTmp1->next!=NULL){
        pTmp1=pTmp1->next ;
        len_first++ ;
    }
    while(pTmp2->next!=NULL){
        pTmp2=pTmp2->next ;
        len_second++ ;
    }

// if not have cross ,return -1
    if(pTmp1!=pTmp2){//if not cross
        return -1 ;
    }

//compare length of the two link list and difference of two link list length,
//and decide which list should move first
    int b_first_long=len_first>len_second ;
    int diff=b_first_long?(len_first-len_second):(len_second-len_first) ;

//the longer list should move diff steps
    if(b_first_long){
        pTmp1= pFirst ;
        while(diff--){
            pTmp1=pTmp1->next ;
            printf("%d+",diff) ;
        }
        pTmp2 = pSecond ;
    }else{
        pTmp2=pSecond ;
        while(diff--){
            pTmp2=pTmp2->next ;
        }
        pTmp1 = pFirst ;
    }

//compute the last positon and the position = diff + last move
    int location=b_first_long?(len_first-len_second):(len_second-len_first) ;

    while(pTmp1!=pTmp2) {
        pTmp1=pTmp1->next ;
        pTmp2=pTmp2->next ;
        location++ ;
    }
    return location ;
}
void create_cross_linklist(struct _link_node* pFirst, struct _link_node *pSecond,int len1,int len2,int position){
    assert(pFirst!=NULL&&pSecond!=NULL) ;
    struct _link_node *pTmp1 = pFirst ;
    struct _link_node *pTmp2 = pSecond ;
    int cnt = 0;
    if(len1>len2){
        assert((len2+position)<len1) ;
        while(cnt<len2){
            pTmp1 = pTmp1->next ;
            pTmp2 = pTmp2->next ;
            cnt++ ;
        }
        cnt=0;
        while(cnt<position){
            pTmp1=pTmp1->next ;
            cnt++ ;
        }
        pTmp2->next = pTmp1 ;
    }else{
        assert((len1+position)<len2) ;
        while(cnt<len1){
            pTmp1 = pTmp1->next ;
            pTmp2 = pTmp2->next ;
            cnt++ ;
        }
        cnt=0 ;
        while(cnt<position){
            pTmp2 = pTmp2->next ;
            cnt++ ;
        }
        pTmp1->next = pTmp2 ;
    }
}
int main()
{
    int array[]={1,2,3,4,5,6,7,8,9,10,11,12,13,24} ;
    int array1[]={2,3,4,6,1,3} ;
    int len = sizeof(array)/sizeof(array[0]) ;
    int len1 = sizeof(array1)/sizeof(array1[0]) ;

    struct _link_node *pRoot1 = create_linklist(array,len) ;
    struct _link_node *pRoot2 = create_linklist(array1,len1) ;
    create_cross_linklist(pRoot1,pRoot2,len,len1,2) ;
    printf("find first cross_node begin............\n") ;
    printf("len=%d,len1=%d\n",len,len1) ;
    int location = find_first_cross_node(pRoot1,pRoot2) ;
    printf("first cross node at %d position\n",location) ;
    printf("find first cross_node end............\n\n") ;

    printf("binary search bound begin..........\n") ;
    printf("location=%d\n",binary_search1(array,0,len-1,24)) ;
    printf("upperbound=%d\n",binary_find_upper_bound(array,0,len-1,9)) ;
    printf("lowerbound=%d\n",binary_find_lower_bound(array,0,len-1,9)) ;
    printf("binary search bound end..........\n\n") ;

    printf("find reciprocal n node begin..........\n") ;
    struct _link_node *pRoot=create_linklist(array,len) ;
    struct _link_node *pTmp=get_reverse_n(pRoot,3) ;
    printf("data=%d\n",pTmp->data) ;
    printf("find reciprocal n node end..........\n") ;
}

抱歉!评论已关闭.