din算法面试题？ - 求职招聘网

一、din算法面试题？

主要是聊基础算法知识和代码题。

二、cam算法工程师和智能研发工程师哪个职业好？

我认为算法工程师好些因为现在软件工程师超多，做1个软件有很多软件辅助，非常简单(比如:VB 傻瓜都会)。

再说你做1个软件不到1个月就会落后别人，你想象以前好多软件，现在都不用了! 而算法工程师全靠能力，思维，很难学习，但学会的你不仅可以编软件，还可以搞黑客，如果你是学生，你参加了这种竞赛可以保送上大学,免费出国!

三、研发助理怎么转成研发工程师？

研发助理与研发工程师相比，缺少的是实践经验或项目经验，自然要经过岁月的历练才能转成研发工程师

四、算法工程师工资，算法工程师工资很高吗？

算法工程师各种待遇按工作时间，资历，等不同，差异很大，基本从4500元到15000元不等。

五、鹅厂面试题，英语单词拼写检查算法？

又到安利Python的时间，最终代码不超过30行（优化前），加上优化也不过40行。

第一步. 构造Trie（用dict登记结点信息和维持子结点集合）：

-- 思路：对词典中的每个单词，逐词逐字母拓展Trie，单词完结处的结点用None标识。

def make_trie(words):
    trie = {}
    for word in words:
        t = trie
        for c in word:
            if c not in t: t[c] = {}
            t = t[c]
        t[None] = None
    return trie

第二步. 容错查找（容错数为tol）：

-- 思路：实质上是对Trie的深度优先搜索，每一步加深时就消耗目标词的一个字母。当搜索到达某个结点时，分为不消耗容错数和消耗容错数的情形，继续搜索直到目标词为空。搜索过程中，用path记录搜索路径，该路径即为一个词典中存在的词，作为纠错的参考。

-- 最终结果即为诸多搜索停止位置的结点路径的并集。

def check_fuzzy(trie, word, path='', tol=1):
    if word == '':
        return {path} if None in trie else set()
    else:
        p0 = set()
        if word[0] in trie:
            p0 = check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
        p1 = set()
        if tol > 0:
            for k in trie:
                if k is not None and k != word[0]:
                    p1.update(check_fuzzy(trie[k], word[1:], path+k, tol-1))
        return p0 | p1

简单测试代码 ------

构造Trie：

words = ['hello', 'hela', 'dome']
t = make_trie(words)

In [11]: t
Out[11]: 
{'d': {'o': {'m': {'e': {'$': {}}}}},
 'h': {'e': {'l': {'a': {'$': {}}, 'l': {'o': {'$': {}}}}}}}

容错查找：

In [50]: check_fuzzy(t, 'hellu', tol=0)
Out[50]: {}

In [51]: check_fuzzy(t, 'hellu', tol=1)
Out[51]: {'hello'}

In [52]: check_fuzzy(t, 'healu', tol=1)
Out[52]: {}

In [53]: check_fuzzy(t, 'healu', tol=2)
Out[53]: {'hello'}

似乎靠谱~

---------------------------分--割--线--------------------------------------

以上是基于Trie的approach，另外的approach可以参看@黄振童鞋推荐Peter Norvig即P神的How to Write a Spelling Corrector

虽然我已有意无意模仿P神的代码风格，但每次看到P神的源码还是立马跪...

话说word[1:]这种表达方式其实是有渊源的，相信有的童鞋对(cdr word)早已烂熟于心...（呵呵

------------------------分-----割-----线-----二--------------------------------------

回归正题.....有童鞋说可不可以增加新的容错条件，比如增删字母，我大致对v2方法作了点拓展，得到下面的v3版本。

拓展的关键在于递归的终止，即每一次递归调用必须对参数进行有效缩减，要么是参数word，要么是参数tol~

def check_fuzzy(trie, word, path='', tol=1):
    if tol < 0:
        return set()
    elif word == '':
        results = set()
        if None in trie:
            results.add(path)
        # 增加词尾字母
        for k in trie:
            if k is not None:
                results |= check_fuzzy(trie[k], '', path+k, tol-1)
        return results
    else:
        results = set()
        # 首字母匹配
        if word[0] in trie:
            results |= check_fuzzy(trie[word[0]], word[1:], path + word[0], tol)
        # 分情形继续搜索（相当于保留待探索的回溯分支）
        for k in trie:
            if k is not None and k != word[0]:
                # 用可能正确的字母置换首字母
                results |= check_fuzzy(trie[k], word[1:], path+k, tol-1)
                # 插入可能正确的字母作为首字母
                results |= check_fuzzy(trie[k], word, path+k, tol-1)
        # 跳过余词首字母
        results |= check_fuzzy(trie, word[1:], path, tol-1)
        # 交换原词头两个字母
        if len(word) > 1:
            results |= check_fuzzy(trie, word[1]+word[0]+word[2:], path, tol-1)
        return results

好像还是没有过30行……注释不算（

本答案的算法只在追求极致简洁的表达，概括问题的大致思路。至于实际应用的话可能需要很多Adaption和Tuning，包括基于统计和学习得到一些词语校正的bias。我猜测这些拓展都可以反映到Trie的结点构造上面，比如在结点处附加一个概率值，通过这个概率值来影响搜索倾向；也可能反映到更多的搜索分支的控制参数上面，比如增加一些更有脑洞的搜索分支。（更细节的问题这里就不深入了逃

----------------------------------分-割-线-三----------------------------------------

童鞋们可能会关心时间和空间复杂度的问题，因为上述这种优（cu）雅（bao）的写法会导致产生的集合对象呈指数级增加，集合的合并操作时间也指数级增加，还使得gc不堪重负。而且，我们并不希望搜索算法一下就把所有结果枚举出来（消耗的时间亦太昂贵），有可能我们只需要搜索结果的集合中前三个结果，如果不满意再搜索三个，诸如此类...

那肿么办呢？................是时候祭出yield小魔杖了ﾟ ∀ﾟ)ノ

下述版本姑且称之为lazy，看上去和v3很像（其实它俩在语义上是几乎等同的

def check_lazy(trie, word, path='', tol=1):
    if tol < 0:
        pass
    elif word == '':
        if None in trie:
            yield path
        # 增加词尾字母
        for k in trie:
            if k is not None:
                yield from check_lazy(trie[k], '', path + k, tol - 1)
    else:
        if word[0] in trie:
            # 首字母匹配成功
            yield from check_lazy(trie[word[0]], word[1:], path+word[0], tol)
        # 分情形继续搜索（相当于保留待探索的回溯分支）
        for k in trie:
            if k is not None and k != word[0]:
                # 用可能正确的字母置换首字母
                yield from check_lazy(trie[k], word[1:], path+k, tol-1)
                # 插入可能正确的字母作为首字母
                yield from check_lazy(trie[k], word, path+k, tol-1)
        # 跳过余词首字母
        yield from check_lazy(trie, word[1:], path, tol-1)
        # 交换原词头两个字母
        if len(word) > 1:
            yield from check_lazy(trie, word[1]+word[0]+word[2:], path, tol-1)

不借助任何容器对象，我们近乎声明式地使用递归子序列拼接成了一个序列。

[新手注释] yield是什么意思呢？就是程序暂停在这里了，返回给你一个结果，然后当你调用next的时候，它从暂停的位置继续走，直到有下个结果然后再暂停。要理解yield，你得先理解yield... Nonono，你得先理解iter函数和next函数，然后再深入理解for循环，具体内容童鞋们可以看官方文档。而yield from x即相当于for y in x: yield y。

给刚认识yield的童鞋一个小科普，顺便回忆一下组合数C(n,m)的定义即

C(n, m) = C(n-1, m-1) + C(n-1, m)

如果我们把C视为根据n和m确定的集合，加号视为并集，利用下面这个generator我们可以懒惰地逐步获取所有组合元素：

def combinations(seq, m):
    if m > len(seq):
        raise ValueError('Cannot choose more than sequence has.')
    elif m == 0:
        yield ()
    elif m == len(seq):
        yield tuple(seq)
    else:
        for p in combinations(seq[1:], m-1):
            yield (seq[0],) + p
        yield from combinations(seq[1:], m)

for combi in combinations('abcde', 2): 
    print(combi)

可以看到，generator结构精准地反映了集合运算的特征，而且蕴含了对元素进行映射的逻辑，可读性非常强。

OK，代码到此为止。利用next函数，我们可以懒惰地获取查找结果。

In [54]: words = ['hell', 'hello', 'hela', 'helmut', 'dome']

In [55]: t = make_trie(words)

In [57]: c = check_lazy(t, 'hell')

In [58]: next(c)
Out[58]: 'hell'

In [59]: next(c)
Out[59]: 'hello'

In [60]: next(c)
Out[60]: 'hela'

话说回来，lazy的一个问题在于我们不能提前预测并剔除重复的元素。你可以采用一个小利器decorator，修饰一个generator，保证结果不重复。

from functools import wraps

def uniq(func):
    @wraps(func)
    def _func(*a, **kw): 
        seen = set()
        it = func(*a, **kw)
        while 1: 
            x = next(it) 
            if x not in seen:
                yield x
                seen.add(x) 
    return _func

这个url打开的文件包含常用英语词汇，可以用来测试代码：

In [10]: import urllib

In [11]: f = urllib.request.urlopen("https://raw.githubusercontent.com/eneko/data-repository/master/data/words.txt")

# 去除换行符
In [12]: t = make_trie(line.decode().strip() for line in f.readlines())

In [13]: f.close()

----------------------分-割-线-四-----------------------------

最后的最后，Python中递归是很昂贵的，但是递归的优势在于描述问题。为了追求极致性能，我们可以把递归转成迭代，把去除重复的逻辑直接代入进来，于是有了这个v4版本：

from collections import deque

def check_iter(trie, word, tol=1):
    seen = set()
    q = deque([(trie, word, '', tol)])
    while q:
        trie, word, path, tol = q.popleft()
        if word == '':
            if None in trie:
                if path not in seen:
                    seen.add(path)
                    yield path
            if tol > 0:
                for k in trie:
                    if k is not None:
                        q.appendleft((trie[k], '', path+k, tol-1))
        else:
            if word[0] in trie:
                q.appendleft((trie[word[0]], word[1:], path+word[0], tol))
            if tol > 0:
                for k in trie.keys():
                    if k is not None and k != word[0]:
                        q.append((trie[k], word[1:], path+k, tol-1))
                        q.append((trie[k], word, path+k, tol-1))
                q.append((trie, word[1:], path, tol-1))
                if len(word) > 1:
                    q.append((trie, word[1]+word[0]+word[2:], path, tol-1))

可以看到，转为迭代方式后我们仍然可以最大程度保留递归风格的程序形状，但也提供了更强的灵活性（对于递归，相当于我们只能用栈来实现这个q）。基于这种迭代程序的结构，如果你有词频数据，可以用该数据维持一个最优堆q，甚至可以是根据上下文自动调整词频的动态堆，维持高频词汇在堆顶，为词语修正节省不少性能。这里就不深入了。

【可选的一步】我们在对单词进行纠正的时候往往倾向于认为首字母是无误的，利用这个现象可以减轻不少搜索压力，花费的时间可以少数倍。

def check_head_fixed(trie, word, tol=1):
    for p in check_lazy(trie[word[0]], word[1:], tol=tol):
        yield word[0] + p

最终我们简单地benchmark一下：

In [18]: list(check_head_fixed(trie, 'misella', tol=2))
Out[18]:
['micellar',
 'malella',
 'mesilla',
 'morella',
 'mysell',
 'micelle',
 'milla',
 'misally',
 'mistell',
 'miserly']

In [19]: %timeit list(check_head_fixed(trie, 'misella', tol=2))
1.52 ms ± 2.84 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

在Win10的i7上可以在两毫秒左右返回所有结果，可以说令人满意。

六、音频工程师面试题？

因为最近都参加了好几家公司的音频算法工程师面试主要总结一下

1.自我介绍

2.会根据你自我介绍的内容针对性的提问

3.讲一下AEC都有哪些步骤

4.讲一下自适应滤波的原理

5.NLP的步骤

6.噪声估计的方法有几种

七、自控工程师面试题？

面试题各公司不尽相同。一般而言，都会考一些最基础的东西，来看你学的扎不扎实。

比如，我经历过的面试题里，最经常遇到的就是画出星三角接线图。相信专业人员都会知道，但真的让你在纸上画出来，你真的能完全无误的画好吗？

再就是最基础的PLC小功能程序编写，很常见的小程序，如果，写不出来，那么被录用的机会很小。

八、研发工程师简称？

工程师。

研发工程师　指从事某种行业,对某种不存在的事物进行系统的研究和开发并具有一定经验的专业工作者,或者对已经存在的事物进行改进以达到优化目的的专业工作者。

电器研发工程师主要是负责电器产品的开发与设计，包括电器产品的模具设计、生产图纸的绘制以及新产品的样机生产，电器产品加工工艺的的改进和编制，电器产品的检验标准的编制。

九、研发工程师待遇？

待遇非常不错

工程师是负责一个产品，一个工程，一个工厂的技术负责人。研发工程师是负责一个单位新产品开发，更新，拓展的工程技术人员，他的工资一般高于其他人，大约月薪20000元左右。

十、算法工程师简称？

答：算法工程师简称是cuda。

利用算法处理事物的人

算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法工程师就是利用算法处理事物的人。

顶一下

(0)

踩一下

(0)

相关评论

我要评论: 用户名: 验证码:

上一篇：返回栏目