爱奇艺2018秋季校招hadoop工程师（第三场）

题目

一、单选题

1、以下关于过拟合和欠拟合说法正确的是（ ）

A、过拟合一般表现为偏差较大

B、欠拟合一般表现为方差较大

C、过拟合可以通过减少变量来缓解

D、欠拟合可以通过正则化来解决

2、file文件属性如下：

-rw-r--r-- 1 root root 0 Jun 24 23:12 file

现在需要修改所属用户组为test，下面哪项能够满足要求（）

A、chown test file

B、chown test:test file

C、chmod test file

D、chmod test:test file

3、下面哪个程序负责HDFS的数据存储（）

A、datanode

B、NameNode

C、secondNameNode

D、chmod test:test file

4、下面哪个程序负责HDFS的数据存储（）

A、func(1);

B、func(1,'h',"hehe",NULL);

C、func(1,'n',"hehe");

D、func(1,"nihao");

5、以下算法属于有监督算法的是（ ）

A、LDA（latent dirichlet allocation）

B、PLSA（probabilistic latent semantic analysis）

C、knn

D、SOM(Self-Organizing Maps)

6、某文件系统采用链接存储方式，文件A在磁盘中存放的情况如图所示。

若该文件所在的目录文件已经在内存中，要读取文件块2，需要访问磁盘的次数为（ ）

A、1次

B、2次

C、3次

D、4次

7、以下哪种排序算法在最坏情况下的时间复杂度最小（ ）

A、冒泡排序

B、选择排序

C、归并排序

D、插入排序

8、设栈S初始状态为空。元素1,2,3,4,5,6依次通过栈S，若出栈的顺序为4,6,5,3,2,1，则栈S的容量至少应该为？（）

A、3

B、4

C、5

D、6

9、在Linux系统中，因为某些原因造成了一些进程变成孤儿进程，那么这些孤儿进程会被以下哪一个系统进程接管？（）

A、sshd

B、init

C、top

D、syslogd

10、在Linux系统下，下列哪个命令可以查看曾经登录到此系统的用户清单?（）

A、ps

B、last

C、lastcomm

D、accton

二、编程题

1、一个完整的括号字符串定义规则如下:

(1)、空字符串是完整的。

(2)、如果s是完整的字符串，那么(s)也是完整的。

(3)、如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。

例如，"(()())", ""和"(())()"是完整的括号字符串，"())(", "()(" 和 ")"是不完整的括号字符串。

牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。

2、牛牛选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。 在整个过程中,牛牛会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum.

例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564.

牛牛现在给出一个sum,牛牛想让你求出一个正整数X经过上述过程的结果是sum.

3、牛牛又从生物科研工作者那里获得一个任务,这次牛牛需要帮助科研工作者从DNA序列s中找出最短没有出现在DNA序列s中的DNA片段的长度。

例如:s = AGGTCTA

序列中包含了所有长度为1的('A','C','G','T')片段,但是长度为2的没有全部包含,例如序列中不包含"AA",所以输出2。

三、简答题

1、请列出你所知道的hadoop调度器，并简要说明其工作方法。

参考答案

一、单选题

1~5：CBADC

6~10：CCCBB

二、编程题

1、

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char s[100];
int dp[100][100],i,j,n,k;
int main(){
    scanf("%s",s),n=strlen(s);
    for(i=n-1;i>=0;i--)
        for(j=i;j<n;j++)
            if(i==j) dp[i][j]=1;
            else if(i+1==j){
                if(s[i]=='('&&s[j]==')') dp[i][j]=0;
                else dp[i][j]=2;
            }else{
                dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
                if(s[i]=='('&&s[j]==')')
                    dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
                for(k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
    printf("%d\n",dp[0][n-1]);
}

2、

#include<stdio.h>
long long getSum(long long);
int main(){
   long long sum,l,r,mid;
   //freopen("input.txt","r",stdin);
   scanf("%lld",&sum);
   for(l=0,r=sum;l+1<r;){
       mid=l+(r-l)/2;
       if(getSum(mid)==sum){
           printf("%lld",mid);
           return 0;
       }else if(getSum(mid)<sum) l=mid;
       else r=mid;
   }
   if(getSum(l)==sum) printf("%lld",l);
   else if(getSum(r)==sum) printf("%lld",r);
   else printf("-1");
}
long long getSum(long long x){
   long long sum=0;
   while(x!=0) sum+=x,x/=(long long)10;
   return sum;    
}

3、

import java.util.Scanner;  
public class Main1 {  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        while(sc.hasNext()){  
            String str = sc.next();  
            int Max = 0;             
            for(int i=0;i<str.length();i++){  
                int curMax = getCurMax(str, i);  
                Max = Math.max(Max, curMax);  
            }  
            System.out.println(Max);  
        }  
    }       
    private static int getCurMax(String s,int start){  
        int max = 0;  
        int len = s.length();  
        for(int i=start;i<len;i++){  
            if(s.charAt(i) == 'A' || s.charAt(i) == 'C' || s.charAt(i) == 'T' ||s.charAt(i) == 'G'){  
                max ++;  
            }else{  
                break;  
            }  
        }  
        return max;  
    }   
}  

三、简答题

1、

Fifo schedular：默认，先进先出的原则

Capacity schedular：计算能力调度器，选择占用最小、优先级高的先执行，依此类推。

Fair schedular：公平调度，所有的 job 具有相同的资源。