爱奇艺秋季校招算法工程师（第一场）-2018年

一、单项选择题

1、当分配给一个进程的页面数增加时，页故障数可能增大也可能变小，下述算法符合这种情况的是（ ）

A、FIFO算法

B、LRU算法

C、Clock算法

D、LFU算法

2、一个提供NAT服务的路由器在转发一个源IP地址为10.0.0.1、目的IP地址为131.12.1.1的IP分组时，可能重写的IP分组首部字段是（ ）

Ⅰ.TTL

Ⅱ.片偏移量

Ⅲ.源IP地址

Ⅳ.目的IP地址

A、仅Ⅰ

B、仅I、Ⅱ

C、仅Ⅰ、Ⅱ、III

D、Ⅰ、Ⅱ、Ⅲ、Ⅳ

3、在深度学习网络中， 以下哪种技术不是主要用来做网络正则化的（提升模型泛化能力）（ ）

A、dropout

B、参数共享

C、Early stopping

D、Pooling

4、[机器学习]以下不属于有监督的词义消歧方法的是（ ）

A、Flip-Flop算法

B、贝叶斯分类器

C、最大熵消歧

D、基于词典的消歧

5、SVM的以下两种模型表达是等价的， 则其中的正则化系数λ和C的关系为（ ）

形式一：

形式二：

A、λ=C

B、λ=1/C

C、λ=C的平方

D、λ=sqrt(C)

6、若前缀表达式为-+a*b-cd/ef，后缀表达式为abcd-*+ef/-，那么对应二叉树的中序遍历序列是（ ）

A、a+c*d-b-e/f

B、a+b*c-d-e/f

C、a+b*d-c-e/f

D、a+e*c-d-b/f

7、对于字符串"ABCDADA"的二进制哈夫曼编码有多少位（ ）

A、11

B、12

C、13

D、14

8、下面关于选择排序说法正确的是（ ）

A、每扫描一遍数组，需要多次交换

B、选择排序是稳定的排序方法,因为时间复杂度是固定的O（n^2）

C、选择排序排序速度一般要比冒泡排序快

D、空间复杂度为O（1）

9、在UML建模中，下列哪个UML的图一般用于描述软件系统的需求（ ）

A、状态图

B、协作图

C、用例图

D、顺序图

10、设置tcp的哪个socket参数会影响了 nagle算法（ ）

A、TCP_MAXSEG

B、TCP_KEEPALIVE

C、TCP_SYNCNT

D、TCP_NODELAY

二、编程题

1、一个合法的括号匹配序列有以下定义:

(1)、空串""是一个合法的括号匹配序列

(2)、如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列

(3)、如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列

(4)、每个合法的括号序列都可以由以上规则生成。

例如: "","()","()()","((()))"都是合法的括号序列

对于一个合法的括号序列我们又有以下定义它的深度:

(1)、空串""的深度是0

(2)、如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y) 3、如果"X"的深度是x,那么字符串"(X)"的深度是x+1

例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

2、牛牛养了n只奶牛,牛牛想给每只奶牛编号,这样就可以轻而易举地分辨它们了。 每个奶牛对于数字都有自己的喜好,第i只奶牛想要一个1和x[i]之间的整数(其中包含1和x[i])。

牛牛需要满足所有奶牛的喜好,请帮助牛牛计算牛牛有多少种给奶牛编号的方法,输出符合要求的编号方法总数。

3、如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串.

牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。

参考答案

一、

1~5：ACDDB

6~10：BCDCD

二、

1、

#include<stdio.h>
#include<stack>
using namespace std;
#define max(a,b) a>b?a:b
int main(){
    char s[100];
    stack<char> stk;
    int i,Max=0;
    for(scanf("%s",s),i=0;s[i]!='\0';i++)
        if(s[i]=='(') stk.push(s[i]),Max=max(Max,stk.size());
        else stk.pop();
    printf("%d",Max);
}

2、

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    int n,i,x,a[100];
    long long res=1,mod=1000000007;
    for(scanf("%d",&n),i=0;i<n;i++) scanf("%d",a+i);
    for(sort(a,a+n),i=0;i<n;i++) res=res%mod*(a[i]-i)%mod;
    printf("%lld",res);
}

3、

import java.util.*;
public class Main {
    public static void main(String[]args){
        Scanner in=new Scanner(System.in);
        String s=in.next();
        if(s.length()==1) System.out.println(0);
        else{
            int res=0,i,n=s.length();
            for(i=0;i+1<n;i++)
                res=Math.max(res,maxLen(s.substring(0,i+1),s.substring(i+1)));
            System.out.println(res);
        }
    }
    public static int maxLen(String a,String b){
        int len1=a.length(),len2=b.length(),i,j;
        int [][]dp=new int[len1+1][len2+1];
        for(i=1;i<=len1;i++)
            for(j=1;j<=len2;j++)
                dp[i][j]=(a.charAt(i-1)==b.charAt(j-1)
                ?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1]));
        return dp[len1][len2]*2;
    }
}