2012Hulu校园招聘笔试题

时间:2021-03-16 18:50:07

一、填空

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

二、编程题

1、正整数剖分

2、AOE关键路径

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

4、大整数加

 

//正整数剖分
#include <stdio.h>

int func(int n, int k, int max)
{
int min = (int)((n+k-1)/k);
if(k==1)
return 1;
int count = 0;
for(int i=min;i<max;i++){
count
+= func(n-i, k-1, max-i);
}
return count;
}

int main()
{
int ans;
int i = 10;
//ans = func(10, 3, 10);
ans = func(4, 3, 4);
printf(
"%d\n", ans);

return 0;
}

 

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

void AOE(int adj[][9], int n)
{
int *e = (int*)malloc(sizeof(int)*n);
int *l = (int*)malloc(sizeof(int)*n);
e[
0]=0;
for(int i=1;i<n;i++){
int max = 0;
for(int j=0;j<i;j++){
if(adj[j][i]!=0 && adj[j][i]+e[j]>max){
max
= adj[j][i] + e[j];
}
}
e[i]
=max;
}
l[n
-1]=e[n-1];
for(int i=n-2;i>=0;i--){
int min = 999999;
for(int j=n-1;j>i;j--){
if(adj[i][j]!=0 && l[j]-adj[i][j]<min){
min
= l[j]-adj[i][j];
}
}
l[i]
=min;
}
for(int i=0;i<n;i++){
if(e[i]==l[i])
printf(
"%d\t", i+1);
}
printf(
"\n");
free(e);
free(l);
}
int main()
{
const int size = 9;
int adj[size][size];
memset(adj,
0, sizeof(int)*size*size);
adj[
0][1] = 6, adj[0][2]=4, adj[0][3]=5;
adj[
1][4] = 1, adj[2][4]=1, adj[3][5]=2;
adj[
4][6] = 6, adj[4][7]=5, adj[5][7]=4;
adj[
6][8] = 2, adj[7][8]=4;

AOE(adj, size);

return 0;
}
//二元树前序、中序打印后序
#include <stdio.h>
#include
<cstring>
#include
<stack>
using namespace std;
void dumpPost(const char* pre, const char* mid)
{
int n = strlen(pre);
if(n==1){
printf(
"%c\t", pre[0]);
return;
}
int i;
for(i=0;i<n;i++){
if(mid[i]==pre[0])
break;
}
char lpre[i], lmid[n-i-1];
char rpre[i], rmid[n-i-1];
memcpy(lpre, pre
+1, sizeof(char)*i);
memcpy(lmid, mid,
sizeof(char)*i);
memcpy(rpre, pre
+i+1, sizeof(char)*(n-i-1));
memcpy(rmid, mid
+i+1, sizeof(char)*(n-i-1));
lpre[i]
= lmid[i] = '\0';
rpre[n
-i-1] = rmid[n-i-1] = '\0';
dumpPost(lpre, lmid);
dumpPost(rpre, rmid);
printf(
"%c\t", pre[0]);
}
int main()
{
const char* preOrder = "ABDEC";
const char* midOrder = "DBEAC";
const char* postOrder = "DEBCA";

dumpPost(preOrder, midOrder);
printf(
"\n");

return 0;
}
//大整数运算
#include <stdio.h>
#include
<stdlib.h>
#include
<string.h>

void strrev(char* s)
{
int i=-1;
while(s[++i]!='\0');
for(int j=0;j<i/2;j++){
char tmp = s[j];
s[j]
= s[i-j-1];
s[i
-j-1]=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+1));
char* s2 = (char*)malloc(sizeof(char)*(l2+1));
memcpy(s1,str1,(l1
+1)*sizeof(char));
memcpy(s2,str2,(l2
+1)*sizeof(char));
strrev(s1);
strrev(s2);
int i;
int sum, carry;
i
=sum=carry=0;
while(i<l){
char a = i<l1?s1[i]:'0';
char b = i<l2?s2[i]:'0';
sum
= a-'0'+b-'0' + carry;
ans[i]
= sum % 10 + '0';
carry
= sum / 10;
i
++;
}
if(carry!=0)
ans[i
++]=carry+'0';
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]='\0';
char* s1 = (char*)malloc(sizeof(char)*(l1+1));
char* s2 = (char*)malloc(sizeof(char)*(l2+1));
memcpy(s1,str1,(l1
+1)*sizeof(char));
memcpy(s2,str2,(l2
+1)*sizeof(char));
strrev(s1);
strrev(s2);
char* tmp = (char*)malloc(sizeof(char)*(l1+2));
int s, carry;
s
= carry = 0;
for(int i=0;i<l2;i++){
int j;
for(int j=0;j<i;j++)
tmp[j]
='0';
for(j=0;j<l1;j++){
s
= (s1[j]-'0')*(s2[i]-'0')+carry;
tmp[i
+j]=s%10+'0';
carry
=s/10;
}
if(carry!=0)
tmp[i
+j++]=carry+'0';
tmp[i
+j]='\0';
strrev(ans);
strrev(tmp);
Add(ans,tmp, ans);
strrev(ans);
}
strrev(ans);
}
int main()
{
const char a[] = "12345";
const char b[] = "123";
char c[1024];

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

return 0;
}