TME2021-QQ音乐暑期实习-自然语言处理

TME2021-QQ音乐暑期实习-自然语言处理一面：

算法题（40分钟）：

1． 输入一个字符串，长度 >=6 内容包含0-9， 请从中取出6个数字，组成 -时-分-秒，输出最大时间，如果无法组成有效的时间，输出无效。 例如 输入“0012345”输出： 23时54 分10秒

方法：暴力：
获得数组的全排列

class Solution:
    def largestTimeFromDigits(self,arr):

        arr = [int(x) for x in arr]
        ans = -1
        for i in range(len(arr)):

            for j in range(len(arr)):

                if i != j:

                    for k in range(len(arr)):

                        if k != i and k != j:

                            for q in range(len(arr)):

                                if q!=k and q!=i and q!=j:

                                    for w in range(len(arr)):

                                        if w!=q and w!=k and w!=i and w!=j:

                                            for l in range(len(arr)):
                                                if l!=w and l!=k and l!=q  and l!=j and l!=I:

                                                    A = arr[i] * 10 + arr[j]
                                                    B = arr[k] * 10 + arr[q]
                                                    C = arr[w] * 10 + arr[l]

                                                    if 0 <= A <= 23 and 0 <= B <= 59 and 0<=C<=59:
                                                        ans = max(ans, A *60*60 + B*60 +C)

        if ans == -1:
            return ""
        else:

            return "{:02}:{:02}:{:02}".format(ans //3600, ans//60%60,ans%60)


time = Solution
print(time.largestTimeFromDigits(time,"0051234519"))
# 输出23:59:54

2 按给定词典分割字符串
给定一个词典文件和一个字符串，要求将字符串按照词典分割， 没有在词典里面匹配的字符按照单个字符输出。
词典文件 a.txt
内容 ：
hello
word
给定字符串文件 b.txt
hellohhword
输出： hello h h word

方法：
1、字典树，匹配每个字符
2、分词操作的最大前项匹配、最大后项匹配，双向匹配
3、segword
4、leetcode-139. 单词拆分

# 字典文件
#a_worddict = ['hello','word',"abc","ced"]
# 字符串
#b_word ="hellohhwordhfkdhhabcced"

a_worddict = []
f = open("a.txt")
for line in f.readlines():
    a_worddict.append(line.replace("\n",""))

# 字符串读取
f = open("b.txt")
b_word = f.read()

def dictTree(a_worddict):
    dict = {}

    for s in a_worddict:
        p=dict

        for sub_s in s:

            if sub_s in p:
                p=sub_s
            else:
                p[sub_s]={}
                p=p[sub_s]

    return dict

def splitword(b_word,dictTree):

    i,j=0,0
    list = []
    p=dictTree
    k=0
    while k<len(b_word):

        s=b_word[k]

        if s not in p and i!=j:
            list.append(b_word[i:j])
            p = dictTree
            i = j

        if s in p:
            j+=1
            p=p[s]

        else:
            list.append(b_word[k:k+1])
            p = dictTree
            j+=1
            I=j

        k+=1


    list.append(b_word[i:j])
    print(list)


dict = dictTree(a_worddict)
splitword(b_word,dict)
# ['hello', 'h', 'h', 'word', 'h', 'f', 'k', 'd', 'h', 'h', 'abc', 'ced']

面试：

1、自我介绍
2、介绍一个项目？
3、glove和word2vec的区别？
4、word2vec两种方法的区别，优势？
5、word2vec的改进？
6、focal loss函数，focal loss函数缺点？
7、欠采样了解？
8、样本不平衡问题？
9、bert模型结构介绍？
10、layer正规化和batch正规化区别。为什么不全用batch正规化？
11、crf介绍一下，crf的输入？
12、crf的损失函数？

TME2021-QQ音乐暑期实习-自然语言处理二面：

算法题：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
candidates = [2,3,6,7], target = 7,
[
[7],
[2,2,3]
]

简单回溯

def findSum(List,target):

    res = []

    def dfs(arr,path):

        if sum(path)>target:
            return

        if sum(path)==target:

            path.sort()
            if path in res:
                return
            res.append(list(path))

        for i in range(len(arr)):

            path.append(arr[I])
            dfs(arr,path)
            path.pop()

        pass

    dfs(List,[])

    print(res)

findSum([2,3,5],8)

2、给定一个字符串以及一个词典（key为词，value为词对应的类型），从字符串中找出词表中出现的词并用其对应的类型模板替代，输出所有可能的序列
e.g. text='请给我来一下那个周杰伦晴天'
word_dict={"给我来":"track","来一下":"track","一下":"track","周杰":"singer","杰伦":"singer","周杰伦":"singer","晴天":"track"}
结果 = [‘请 track track 那个singer track’，’请给我 track 那个 singer伦 track’ ...]

def replacePatten(text,word_dict):

    res = []
    n=len(text)
        
        # 采用dfs，基于树结构深度搜索
    def dfs(text,path,pos):

        if pos==n:
            if path in res:
                return
            res.append(list(path))
            return

        # 遍历当前位置至下一个位置，
        while pos<len(text):
            flag = 0
            Min = len(text)
            
            # 最大后项匹配，从后往前匹配
            for j in range(len(text),pos,-1):
                if text[pos:j] in word_dict:
                    flag=1
                    Min = j
                    path.append(word_dict[text[pos:j]])
                    dfs(text,path,j)
                    path.pop()
                        
                        # 如果没有一个匹配成功，则必定是单个词
            if flag==0:
                path.append(text[pos:pos+1])
                dfs(text, path, pos+1)
                path.pop()
                        
                        # 查看当前pos到最小的匹配中，有没嵌套模版；例如 “周杰伦” 中的“杰伦，它的起始位置在嵌套内
            else:
                                # 新建模版sub_path，不然会影响其他搜索的结果TVT
                sub_path = list(path)
                for i in range(pos+1,Min):
                    for j in range(len(text),i,-1):
                        if text[i:j] in word_dict:
                                                        
                                                        # 找到嵌套匹配，例如“周杰伦” 中的“杰伦，
                                                        # 补齐前面的字符，”周“
                            for k in range(pos,i):
                                sub_path.append(text[k:k+1])
                                                        
                                                        # 替换杰伦为模版
                            sub_path.append(word_dict[text[i:j]])
                            # 继续搜索
                            dfs(text, sub_path, j)
                            # 删除模版
                            sub_path.pop()
                            # 删除补全
                            for k in range(pos,i):
                                sub_path.pop()

                        # 剪枝，因为剩下的都没有匹配了（pos+1:最后）。面试时绷得太紧，这一步没想出来，导致输出无用结果。
            break

    dfs(text,[],0)
    print(res)
    print(len(res))

    pass

text='请给我来一下那个周杰伦晴天'
word_dict={"给我来":"track","来一下":"track","一下":"track","周杰":"singer","杰伦":"singer","周杰伦":"singer","晴天":"track"}
replacePatten(text,word_dict)


结果输出：
[
   ['请', 'track', 'track', '那', '个', 'singer', 'track'],
   ['请', 'track', 'track', '那', '个', 'singer', '伦', 'track'],
   ['请', 'track', 'track', '那', '个', '周', 'singer', 'track'], 
   ['请', '给', '我', 'track', '那', '个', 'singer', 'track'], 
   ['请', '给', '我', 'track', '那', '个', 'singer', '伦', 'track'], 
   ['请', '给', '我', 'track', '那', '个', '周', 'singer', 'track']
]

图片

1、自我介绍
2、为什么bert里的transformer要用的是multi-head attention？
3、multi-head头数和任务之间有什么关系？这个参数应该怎么设置会好一些？
4、transformer如何做并行化？
5、为什么bert引入attention机制？
6、Bert的缺点在哪？
7、针对这个问题，后面一些优化的Bert做了哪些改进。例如Roberta或xlnet？
8、介绍一下，隐马尔可夫，CRF，维特比算法？
9、隐马尔可夫和CRF比较？
10、介绍一些维特比算法？
11、介绍一下集成学习和xgboost的区别和优缺点；GBDT和XGboost的区别？xgboost为什么能做二阶展开？
12、bagging方法
13、你这边介绍一下随机森林（最特别，最典型的bagging方法），如何投票？加权投票？
14、softmax有什么优缺点？

15、你这边有什么问题？

• 3、实习生需要什么能力，能胜任这份工作呢？

  学习能力，快速上手能力