实习题目小结

发表于 | 更新于 | 分类于 | 阅读次数：
百度

百度

数据结构-堆排序

大顶堆:子节点比根节点小。小顶堆：子节点比根节点大。
参考)

  • 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
  • 从最后一个非叶子结点开始，将两个节点信息进行互换，调整子树为正确顺序。继续调整交换节点后的子树结构。
  • 将堆顶元素与末尾元素进行交换，重复以上步骤。

数据结构-普利姆算法&克鲁斯卡尔算法

普利姆算法: 选点法，每次选最近的点构成连通图。
克鲁斯克尔算法: 选边法，每次选择最短边，避免回环，平均时间复杂度为 $O(|E\log |V|)$

机器学习-朴素贝叶斯

贝叶斯计算

编程

  1. 给定一个字符串abab，不断将首字母添加到尾部，可以看出这个过程不同的字符串数量是有限的，请编程实现此问题。对时空复杂度有要求。
    1
    2
    3
    4
    5
    6
    7
    s = input()
    res = []
    for i in range(len(s)):
        s_new = s[i:] + s[:i]
        if  hash(s_new) not in res:
            res.append(hash(s_new))
    print(len(res))

用例: abab 输出 2

  1. 给定源字符串，目标字符串，两个索引值。求源字符串索引值片段内，目标字符串的出现次数。对时空复杂度有要求。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    s = input()
    t = input()
    n = input()

    for i in range(int(n)):
        nums = input().split()
        start = int(nums[0])
        end = int(nums[1])
        sub = s[start-1:end]

        count = 0
        for i in range(len(sub)-len(t)+1):
            print(sub)
            if sub[i:i+len(t)] == t:
                count+=1
        print(count)

用例：

1
2
3
4
5
6
7
8
comeonmandontconconnect
on
5
1 5
1 6
1 23
11 16
11 23

输出0 1 4 2 3

面试

一面

自我介绍，比较详细。

  • 请介绍xgboost 随机森林 GBDT？
  • 编程题1：求一个特别大的数字的质数分解
  • 编程题2：有一个数组，里面有Articial、Guard、Wall。如何分配警卫使其到艺术品的距离最短。(广度优先搜索算法问题Google)
    这些编程题更像是LeetCode风格的，有时候偏向难，代码也不用完成很多，面试官也会提示一两点，比如第一题的循环次数可以减少到根号n。
    最后个人Github成为了加分项。

二面

自我介绍(简短)，依次介绍简历上的项目，论文(当前项目使用了RL，把RL介绍了很多)。
编程题1：最大正向匹配
二面的编程题侧重点与一面的时候不一样，更像是给你算法及思路让你完全把代码一步步写出来。由于没有调整好思路，与面试官来回讨论了多次才对上思路(面试官都说难道还要我给你写出来么~)，最后完成了，不过应该是没一面编程题结果好点，但面试官说看手写的代码还是比较完整的。

机器学习题目：

  • 解释过拟合、欠拟合
  • 常用的激活函数
  • 梯度消失的原因及解决办法
  • 介绍下SVM、核函数的作用及类型

三面

自我介绍，介绍项目，论文(同样针对当前所作的项目论文进行了很多的沟通)
机器学习题目：

  • 对数据添加个相同特征，会对LR有什么影响(权重，拟合效果)

    相同特征的权重会减小，但两个权重和会比之前的权重大。如果在当前维度是线性可分，则扩展到更高维度，更容易可分，即间隔变大，权重变大。

  • 单机如何处理数百亿级特征数量的数百亿级数据(基本没有回答上来，仅提了GPU并行，数据并行，模型并行概念)
  • Sigmoid怎么来的？(两个人思路没有对上，面试官放弃继续追问这个问题了)
  • 信息论解释下LR？

讲解最近看的一篇论文(机器翻译里的Position Network)，讲解下Bert，Transformer。
其它问题：

  • 进程、线程的区别

    进程是cpu资源分配的最小单位，线程是cpu调度的最小单位

  • 虚拟内存与物理内存的区别
  • 三门与羊问题(概率论)
  • 同事不完成任务，你该如何应对
  • 上级给了你不能完成的任务，你如何应对
  • 你与同事的目标不一致如何

总结

百度实习生的招聘还是很满意的，面试是在食堂，和面试官在餐桌一对一，隔一个座位就是另一个面试官和面试人。面试官很亲和，压力不是很大，面试官会对你进行思维引导，交流过程很亲和。一面问题偏技术向，二面偏学术向，详细的介绍了在校项目和论文。三面面试官以你的经历入手，问你一些问题，自己基本就是见招拆招。

阿里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
s = '<[播]放|来>[一|几]<首|曲|个>@{singer}的<歌[曲]|[流行]音乐>'
target = '来几首@{singer}的流行歌曲'

def foo(s, target):
    while s:
        seg = ''
        if s[0] in '<[':
            if s[0] == '<':
                seg = s[s.index('<'):s.index('>')+1]
                s = s[s.index('>')+1:]
                seg = seg[1:-1]
            else:
                seg = s[s.index('['):s.index(']')+1]
                s = s[s.index(']')+1:]
                seg = seg[1:-1]

            seg = seg.split('|')
            lens = len(target)
            for i in seg:
                i.replace('[','')
                i.replace(']','')

                j = 0
                while target[:j+1] in i:
                    j+=1

                if j:
                    target = target[j:]
                    break

            if len(target) == lens: return 0
        else:
            i = 0
            while s[i] == target[i]:
                i+=1

            if i:
                s = s[i:]
                target = target[i:]
            else:
                return 0
    return 1

foo(s, target)

阿里

问题1

自动语音识别（ASR）需要音频和文本的对应数据进行训练，但是通常我们无法直接拿到这样对应好的数据，因此需要一定的方法来构造。假设有一个句子列表1（长度为n），里面是既定的文本，我们要对每个文本构建一段对应的录音。方法是让录音人员一次性完成列表1中的文本的录音，规则是录完一条再录下一条。每条可能不止录一次，因为可能读错或读的不标准，所以对一条文本可再次尝试录音，最多可以再试x次，每次之间有停顿。然后对这个完整音频根据停顿切分成小音频，并对所有小音频进行语音识别（用当前ASR系统，这次识别会不太准）之后，得到列表2，长度最大为(x+1)*n，列表1和列表2都是有序的。现在要求对列表1中的每个元素，找到列表2中对应的元素（即文本相似度最高），使所有项的相似度的和最大（注意每个项的相似度最大不一定相似度的和最大），然后拿列表2中对应元素的音频作为既定文本的对应的录音。在相似度的和最大的基础上，对于既定的文本，我们倾向于选择录音人员最后一次说的比较好的录音，即尽量选择列表2中下标比较大的项。

为了简单起见，文本相似度采用 Jaccard距离进行计算，定义如下：

相似度 = s(i)和s(j)的交集的大小 / s(i)和s(j)的并集的大小，

其中s(i)和s(j)都是上述列表中的字符串，其交集是同时存在于二者中的字符组成的集合，并集是二者所有字符组成的集合。

那么你现在准备好为AI贡献自己的力量了吗？

编译器版本: Python 2.7.6
请使用标准输出(sys.stdout)；已禁用图形、文件、网络、系统相关的操作，如Process , httplib , os；缩进可以使用tab、4个空格或2个空格，但是只能任选其中一种，不能多种混用；如果使用sys.stdin.readline，因为默认会带换行符，所以要strip(‘ ‘)进行截取；建议使用raw_input()
时间限制: 3S (C/C++以外的语言为: 5 S) 内存限制: 128M (C/C++以外的语言为: 640 M)
输入:
输入数据有三行：
第一行是列表1，元素以英文逗号分隔
第二行是列表2，元素以英文逗号分隔
第三行是参数x
输出:
列表1中的每个元素对应列表2中的每个元素的下标，英文逗号分隔。
输入范例:
床前明月光,疑是地上霜,举头望明月,低头思故乡
越光,床前地上霜,大地孤烟直,举头明月,低头是故乡
1
输出范例:
0,1,3,4

问题2

每天都有无数的人跟我厂出品的天猫精灵对话，天猫精灵为人类跟他说的每句话都打上了一个意图标签，一个人的所有对话就是这些意图标签组成的序列，这个序列里面的子序列就是一段对话，意图有查天气、查温度、查股票、放音乐、讲笑话等等。最近天猫精灵灵光一闪，想研究下人类的对话，看看人们都喜欢怎么和它说话，比如有的人喜欢先问天气，再问股票，再让它讲个笑话，再放首歌，有的人喜欢问了天气之后再问空气质量，然后再问下明天的天气，还有的人喜欢先听听歌，然后叫出租车去上班等等。天猫精灵要找出人们普遍的规律，分析出大家一般都喜欢怎么和他说话。那么首先天猫精灵必须先解决一个问题，就是给定两个用户的意图序列，找出相似（编辑距离 <= 阈值）的子意图序列的pair，并且每个子意图序列满足一定的长度要求（长度必须在闭区间 [minSeqLen, maxSeqLen] 内），一个子序列可重复出现在多个pair中。比如如下就是满足长度要求（长度区间 [5, 8]）的两个相似（编辑距离为1，小于等于阈值2）的子意图序列pair：

A： weather, joke, music, stock, joke, joke, news

B： weather, joke, music, stock, joke, joke, texi

那么现在你可以帮天猫精灵完成这个任务吗？

编译器版本: Python 2.7.6
请使用标准输出(sys.stdout)；已禁用图形、文件、网络、系统相关的操作，如Process , httplib , os；缩进可以使用tab、4个空格或2个空格，但是只能任选其中一种，不能多种混用；如果使用sys.stdin.readline，因为默认会带换行符，所以要strip(‘ ‘)进行截取；建议使用raw_input()
时间限制: 3S (C/C++以外的语言为: 5 S) 内存限制: 128M (C/C++以外的语言为: 640 M)
输入:
输入数据包括五行：
第一行：一个数字，编辑距离阈值
第二行：一个数字，最小的序列长度
第三行：一个数字，最大的序列长度
第四行：用户A的意图序列，英文逗号分隔
第五行：用户B的意图序列，英文逗号分隔
输出:
一个数字，满足条件的意图序列的pair的个数
输入范例:
1
3
5
weather,joke,music,stock,joke,news,taxi,temperature,pm2.5
joke,music,news,stock,joke,joke,news,taxi
输出范例:
14