20220412百度笔试—机器学习/数据挖掘/自然语言

一、选择题30道（60分）

考察内容涉及：数据结构、熟悉C++、概率论、线性代数、离散数学、计算机网络、操作系统和机器学习。

一些主题：

• 用于多分类任务的激活函数：Softmax
  
• TCP首部的确认号字段ACK
  
• GMM-HMM模型
  
• 朴素贝叶斯模型
  
• 特征向量
  
• SGD随机梯度下降法
  
• 随机森林算法
  
• 强连通图：n个顶点，最多有n*(n-1)条边；最少有n条边
  
• 红黑树的高度
  
• 完成二叉树的高度
  
• 最长公共前缀
  
• 冒泡排序中的比较次数
  
• C4.5使用的属性划分标准：信息增益率
  

二、问答题1道（20分）

在离线训练点击率预估模型的过程中，验证集的AUC显著提高，但上线后效果不佳，分析其原因。

我的答案：

在离线训练点击率预估模型的过程中，题目中只提到了验证集的AUC显著提高，没有提及训练集的AUC效果如何，故从以下方面分析上线后排序效果差：
1.模型训练次数太少，泛化能力差。
2.模型过拟合：此种情况下，模型过度拟合了训练集数据的特征，导致实际使用中效果差，泛化能力差。
3.用于训练的数据过少，模型特征提取能力差，导致实际使用效果差。
4.训练集和验证集不具备代表性，或者训练数据集中的噪声影响了模型的训练。
5.所训练的模型不适合该类问题，模型设计过于复杂或者过于简单，应更换其他模型尝试解决该类问题。

三、系统设计题1道（30分）

产品还没上线，设计一个音乐引擎推荐系统，有30万首候选歌曲，无用户数据。

四、编程题2道（40分）

1. 小明最近经常会思考一些关于整数的问题。今天他想到这么一个问题： 现在有n个整数，其中有些整数相同，也有一些整数不相同。首先需要找出其中出现次数最多的整数，如果出现次数最多的整数不唯一，则找出其中值最大的整数，记为M；然后再找出其中出现次数最少的整数，如果出现次数最少的整数不唯一，则找出其中值最小的整数，记为N；最后计算M和N的差，即输出(M-N)。 请你编写一个程序帮助小明解决这个问题。
   

# 样例输入
10
1 2 1 3 5 4 2 1 3 3
# 输出
-1
# 解释：1和3出现了3次，M为3；4和5出现了1次，N为4.M-N=-1

#通过率：100%
import collections
if __name__ == "__main__":
    # n个整数
    n = int(input().strip())
    line = input().strip().split()
    nums = [int(num) for num in line]
    count = collections.Counter(nums)
    ans = sorted(count.items(), key=lambda x: (x[1], x[0]))
    print(ans)
    M = ans[-1][0]
    N = ans[0][0]
    print(M - N)

1. 小Pa无意之间得到一个长度为N的序列，但是他喜欢单调递增的序列，他找到了魔法师小Ka，想让他对于任意位置的i通过魔法将Ai变成Bi，请你告诉小Pa最少施展多少次魔法可以变成单调递增的序列，如果不可能请输出 -1。
   

# 样例1
5
1 2 3 4 5
2 3 4 5 6
# 输出
0

# 样例2
6
1 8 3 6 7 5
1 2 3 6 9 7
# 输出
-1

# 样例3
6
1 8 3 6 7 5
1 2 3 6 9 8
2

#通过率：90%
if __name__ == "__main__":
    # 序列长度n
    n = int(input().strip())
    # 序列a
    line = input().strip().split()
    a = [int(num) for num in line]
    # 序列b
    line = input().strip().split()
    b = [int(num) for num in line]
    ans = 0
    i = 0
    count = 0
    while i != n - 1:
        while i < n - 1 and a[i] < a[i + 1]:
            i += 1
        if i == n - 1:
            break
        # 此时a[i]>a[i+1]
        if b[i] < a[i + 1]:
            a[i] = b[i]
            count += 1
        elif b[i + 1] > a[i]:
            a[i + 1] = b[i + 1]
            count += 1
        else:
            i += 1
    flag = True
    for i in range(n - 1, 0, -1):
        if a[i] < a[i - 1]:
            flag = False
            break
    if not flag:
        count = -1
    print(count)