面试题杂项

<span style="font-family: Arial, Helvetica, sans-serif;">1,9月6日，网新恒天2014校园招聘笔试编程题  已知memcpy的函数为： void* memcpy(void *dest , const void* src , size_t count)其中dest是目的指针，src是源指针。不调用c++/c的memcpy库函数，请编写memcpy。</span>

<span style="font-family: Arial, Helvetica, sans-serif;">  点评：老题，参考答案如下void* memcpy(void *dst, const void *src, size_t count)     </span>

{      
    //安全检查  
    assert( (dst != NULL) && (src != NULL) );      
  
    unsigned char *pdst = (unsigned char *)dst;      
    const unsigned char *psrc = (const unsigned char *)src;      
  
    //防止内存重复  
    assert(!(psrc<=pdst && pdst<psrc+count));      
    assert(!(pdst<=psrc && psrc<pdst+count));      
  
    while(count--)      
    {      
       *pdst = *psrc;      
        pdst++;      
        psrc++;      
    }      
    return dst;      
}

2,9月9日，迅雷2014校招笔试编程题：
已知集合A和B的元素分别用不含头结点的单链表存储，函数difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。
链表结点的结构类型定义如下：

struct node  
{  
    int elem;  
    node* next;  
};  
  
void difference(node** LA , node* LB)  
{  
    node *pa , *pb , *pre , *q;  
    pre = NULL;  
    pa = *LA;                              //1  
    while(pa)
    {
        pb = LB;  
        while(pb && pa->elem != pb->elem)  //2  
            pb = pb->next;  
        if(pb)                             //3  
        {  
            if(!pre)  
                *LA = pa->next;            //4  
            else  
                pre->next = pa->next;      //5  
            q = pa;  
            pa = pa->next;  
            free(q);
        }  
        else  
        {  
            pre = pa;                      //6  
            pa = pa->next;  
        }  
    }  
}

3. 9月10日，美团网2014校招研发笔试哈尔滨站
1、链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现。

//对上述方案4的改写。    
void my_rotate(char *begin, char *mid, char *end)    
{       
    int n = end - begin;       
    int k = mid - begin;       
    int d = gcd(n, k);       
    int i, j;       
    for (i = 0; i < d; i ++)       
    {       
        int tmp = begin[i];       
        int last = i;       
            
        //i+k为i右移k的位置，%n是当i+k>n时从左重新开始。    
        for (j = (i + k) % n; j != i; j = (j + k) % n)    //多谢laocpp指正。       
        {       
            begin[last] = begin[j];           
            last = j;       
        }           
        begin[last] = tmp;       
    }       
}

对上述程序的解释：关于第二个for循环中，j初始化为（i+k）%n，程序注释中已经说了，i+k为i右移k的位置，%n是当i+k>n时从左重新开始。为什么要这么做呢?很简单，n个数的数组不管循环左移多少位，用上述程序的方法一共需要交换n次。当i+k>=n时i+k表示的位置在数组中不存在了，所以又从左边开始的(i+k)%n是下一个交换的位置。

char * invert(char *start, char *end)    
{       
    char tmp, *ptmp = start;        
    while (start != NULL && end != NULL && start < end)      
   {       
        tmp = *start;       
        *start = *end;          
        *end = tmp;         
         start ++;       
         end --;     
     }    
    return ptmp;    
}    
  
char *left(char *s, int pos)   //pos为要旋转的字符个数，或长度，下面主函数测试中，pos=3。    
{    
    int len = strlen(s);    
    invert(s, s + (pos - 1));  //如上，X->X^T，即 abc->cba    
    invert(s + pos, s + (len - 1)); //如上，Y->Y^T，即 def->fed    
    invert(s, s + (len - 1));  //如上，整个翻转，(X^TY^T)^T=YX，即 cbafed->defabc。    
    return s;    
}