2012校园招聘笔试第一站（创新工场）

------------------------------------------

本文为本人原创，欢迎转载!

转载请注明出处:snowboy.blog.chinaunix.net

雪夜流星

------------------------------------------

n年没笔试了，9月16号迎来了笔试第一站，试卷分为两部分，第一部分是选择题，第二部分是综合题。选择题依稀记得有个arp的功能（把ip地址转换为mac地址），下面贴一下综合题。

 

1.找出一个序列中的最长递减子序列，如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}；代码实现如下：

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

#define MAX_LEN 255

/*****************************************************************************************

*功能描述：找出一个序列中的最长递减子序列，如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}

*传入参数：str：源数组首地址， len:数组的长度

*传出参数：str：递减子序列的数组首地址，传入参数和传出参数空间复用，降低空间复杂度

*返回值： 递减子序列的数组首地址

 ****************************************************************************************/
char *substring(char *str, int len)
{
    char b[MAX_LEN] = {0};//定义数组长度必须为常量，不能为变量或者只读变量
    int i, j, k=0, tmp;

    if ((str == NULL)||(len <1))
    {
        return NULL;
    }

    for (i=0; i<len; i++)
    {
        tmp = str[i];
        for (j=i+1; j<len; j++)//遍历当前元素后面的所有元素，如果有比当前元素大的则退出循环
        {
            if (str[i] <= str[j])
            {
                break;
            }
        }
        if (j == len)//循环正常结束，即后面没有比当前数要大的，将其则放入新数组中
        {
            b[k] = tmp;
            k++;
        }
    }
    b[k] = '\0';//最后将新数组赋结束符

    strcpy(str, b);//将新数组元素拷贝到源数组中，复用空间

    return str;
}

int main(void)
{
    char a[10] = "954325432";
    char *b;
    b = substring(a, 10);
    printf("b:%s\n", b);

    return 0;
}

2.将两个有序链表合并成为一个有序链表（附带测试程序）

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

typedef struct node
{
    int data;
    struct node *next;
}link;

/*****************************************************************

*功能描述：合并两个带头结点的有序链表使其仍然有序

*传入参数：head1，head2：两个有序链表

*传出参数：无

*返回值： 合并后的有序链表的头指针

 ****************************************************************/
link *mergelist(link *head1, link *head2)
{
    link *pa = NULL;
    link *pb = NULL;
    link *pc = NULL;
    link *head3 = NULL;

    pa = head1->next;
    pb = head2->next;
    head3 = pc = head1;

    while ((pa != NULL) && (pb != NULL))
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa; pc = pa; pa = pa->next;
        }
        else
        {
            pc->next = pb; pc = pb; pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;//插入剩余段
    free(head2);

    return head3;
}

/*创建带头结点的链表*/
link *creat(void)
{
    link *head = NULL;
    link *tail = NULL;
    link *cur = NULL;
    int x;

    head = (link *)malloc(sizeof(link));

    if(!head)
    {
        printf("malloc error\n");
        exit(1);
    }

    tail = head;

    while(1)
    {

        printf("please input data:");
        scanf("%d", &x);
        if(x <= 0)
        {
            break;
        }

        cur = (link *)malloc(sizeof(link));

        if(!cur)
        {
            printf("malloc error\n");
            exit(1);
        }

        cur->data = x;
        cur->next = NULL;
        tail->next = cur;
        tail = cur;
    }
    printf("creat list success\n");

    return head;
}

/*打印带头结点的链表*/
void printl(link * head)
{
    link *p = NULL;

    if(!head)
    {
        return;
    }

    for(p=head->next; p; p=p->next)
    {
        printf("%d ", p->data);
    }

    printf("\n");

    return;
}

int main(void)
{
    link *head1, *head2, *head3;
    head1 = creat();
    head2 = creat();
    printl(head1);
    printl(head2);
    head3 = mergelist(head1, head2);
    printl(head3);

    return 0;
}

小结：这个公司招的人少，笔试的人却很多，僧多粥少，准备迎接下一站，希望后面的路会更顺利。