2012Hulu校园招聘笔试题

一、填空

侧重逻辑思维，没有语言、具体技术考察，大部分属于组合数学、算法。比较基本的知识点有二元树节点树、最小生成树、Hash函数常用方法等。

二、编程题

1、正整数剖分

2、AOE关键路径

3、二元树前序、中序求后序

4、大整数加

//正整数剖分

#include <stdio.h>

int func(int n, int k, int max)

{

    int min = (int)((n+k-)/k);

    if(k==)

        return ;

    int count = ;

    for(int i=min;i<max;i++){

        count += func(n-i, k-, max-i);

    }

    return count;

}

int main()

{

    int ans;

    int i = ;

    //ans = func(10, 3, 10);

    ans = func(, , );

    printf("%d\n", ans);

    return ;

}

//AOE

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void AOE(int adj[][], int n)

{

    int *e = (int*)malloc(sizeof(int)*n);

    int *l = (int*)malloc(sizeof(int)*n);

    e[]=;

    for(int i=;i<n;i++){

        int max = ;

        for(int j=;j<i;j++){

            if(adj[j][i]!= && adj[j][i]+e[j]>max){

                max = adj[j][i] + e[j];

            }

        }

        e[i]=max;

    }

    l[n-]=e[n-];

    for(int i=n-;i>=;i--){

        int min = ;

        for(int j=n-;j>i;j--){

            if(adj[i][j]!= && l[j]-adj[i][j]<min){

                min = l[j]-adj[i][j];

            }

        }

        l[i]=min;

    }

    for(int i=;i<n;i++){

        if(e[i]==l[i])

            printf("%d\t", i+);

    }

    printf("\n");

    free(e);

    free(l);

}

int main()

{

    const int size = ;

    int adj[size][size];

    memset(adj, , sizeof(int)*size*size);

    adj[][] = , adj[][]=, adj[][]=;

    adj[][] = , adj[][]=, adj[][]=;

    adj[][] = , adj[][]=, adj[][]=;

    adj[][] = , adj[][]=;

    AOE(adj, size);

    return ;

}

//二元树前序、中序打印后序

#include <stdio.h>

#include <cstring>

#include <stack>

using namespace std;

void dumpPost(const char* pre, const char* mid)

{

    int n = strlen(pre);

    if(n==){

        printf("%c\t", pre[]);

        return;

    }

    int i;

    for(i=;i<n;i++){

        if(mid[i]==pre[])

            break;

    }

    char lpre[i], lmid[n-i-];

    char rpre[i], rmid[n-i-];

    memcpy(lpre, pre+, sizeof(char)*i);

    memcpy(lmid, mid, sizeof(char)*i);

    memcpy(rpre, pre+i+, sizeof(char)*(n-i-));

    memcpy(rmid, mid+i+, sizeof(char)*(n-i-));

    lpre[i] = lmid[i] = '\0';

    rpre[n-i-] = rmid[n-i-] = '\0';

    dumpPost(lpre, lmid);

    dumpPost(rpre, rmid);

    printf("%c\t", pre[]);

}

int main()

{

    const char* preOrder = "ABDEC";

    const char* midOrder = "DBEAC";

    const char* postOrder = "DEBCA";

    dumpPost(preOrder, midOrder);

    printf("\n");

    return ;

}

//大整数运算

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void strrev(char* s)

{

    int i=-;

    while(s[++i]!='\0');

    for(int j=;j<i/;j++){

        char tmp = s[j];

        s[j] = s[i-j-];

        s[i-j-]=tmp;

    }

}

void Add(const char*str1, const char* str2, char* ans)

{

    int l1, l2, l;

    l1 = strlen(str1);

    l2 = strlen(str2);

    l = l1>l2 ? l1 : l2;

    char* s1 = (char*)malloc(sizeof(char)*(l1+));

    char* s2 = (char*)malloc(sizeof(char)*(l2+));

    memcpy(s1,str1,(l1+)*sizeof(char));

    memcpy(s2,str2,(l2+)*sizeof(char));

    strrev(s1);

    strrev(s2);

    int i;

    int sum, carry;

    i=sum=carry=;

    while(i<l){

        char a = i<l1?s1[i]:'';

        char b = i<l2?s2[i]:'';

        sum = a-''+b-'' + carry;

        ans[i] = sum %  + '';

        carry = sum / ;

        i++;

    }

    if(carry!=)

        ans[i++]=carry+'';

    ans[i]='\0';

    strrev(ans);

    free(s1);

    free(s2);

}

void Mul(const char*str1, const char* str2, char* ans)

{

    int l1, l2, l;

    l1 = strlen(str1);

    l2 = strlen(str2);

    l = l1 + l2;

    ans[]='\0';

    char* s1 = (char*)malloc(sizeof(char)*(l1+));

    char* s2 = (char*)malloc(sizeof(char)*(l2+));

    memcpy(s1,str1,(l1+)*sizeof(char));

    memcpy(s2,str2,(l2+)*sizeof(char));

    strrev(s1);

    strrev(s2);

    char* tmp = (char*)malloc(sizeof(char)*(l1+));

    int s, carry;

    s = carry = ;

    for(int i=;i<l2;i++){

        int j;

        for(int j=;j<i;j++)

            tmp[j]='';

        for(j=;j<l1;j++){

            s = (s1[j]-'')*(s2[i]-'')+carry;

            tmp[i+j]=s%+'';

            carry=s/;

        }

        if(carry!=)

            tmp[i+j++]=carry+'';

        tmp[i+j]='\0';

        strrev(ans);

        strrev(tmp);

        Add(ans,tmp, ans);

        strrev(ans);

    }

    strrev(ans);

}

int main()

{

    const char a[] = "";

    const char b[] = "";

    char c[];

    Add(a,b,c);

    printf("a+b=%s\n", c);

    Mul(a,b,c);

    printf("a*b=%s\n", c);

    return ;

}