|
|
给大家出一道某硅谷大公司的算法面试题，并给出解答过程，让大家体验一下如何去面试
算法题案例：
Given an input string and a dictionary of words,
segment the input string into a space-separated
sequence of dictionary words if possible. For
example, if the input string is "applepie" and
dictionary contains a standard set of English words,
then we would return the string "apple pie" as output.
简单说就是给定字典，对无空格的短语切词。这里可以考虑一些情形，你先问面试官：
如果输入的刚好是字典中的一个单词怎么办？（特殊例子）
我是不是只要考虑切成2个单词的情况？（不仅仅2个，但可以从2个开始）
如果输入的根本无法切分呢？（就返回空）
有没有一些单词拼写或者助词缩写形式（如im = i am，如果在字典中没有就不算)
如果可以切分多种合理的词？（返回一种就行）
要不要用一些字典的高级数据结构（trie, heap, suffix tree)（不需要理解）
字典有哪些操作的方式？（就是词的查询）
字典有多大？（正常英语词典，内存足够）
这些问题时帮助你理解和简化题目，也考察出你对算法和数据结构的熟练度。
简单化的方案：
就把它拆成两个词。分别验证前后是否在字典中。这个直接简单，也让面试者心里有底。下面是python的代码实例：
def segment_string(input, dict):
len = len(input)
for i in range(len):
prefix = input[0:i+1]
if prefix in dict:
suffix = input[i+1:]
if suffix in dict:
return prefix + " " + suffix
return ""
下面考虑怎么推广到一般的情况，有种递归的办法，在上面的基础上稍微改动一下
def segment_string(input, dict):
if input in dict: return input
len = len(input)
for i in range(len):
prefix = input[0:i+1]
if prefix in dict:
suffix = input[i+1:]
seg_suffix = segment_string(suffix, dict)
if seg_suffix != '':
return prefix + " " + seg_suffix
return ''
给出解答还要分析复杂度，就是所谓的 大O分析，这种递归的做法很多人不清楚怎么计算，但你可以想象 如果单纯想 字典里面只有一个字符组合a，aa, aaa... 输入也是aaa... 你就发现就是全组合的可能性，答案O(2^N)。
还可以做的更好么？
如果大家清楚动态规划或者memoization，可以进一步节约计算，这是一种空间换时间的技巧，但大家能思考它的复杂度吗？如果我说是O(N^2), 大家有办法去证明吗？
memory = {}
def segment_string(input, dict):
if input in dict: return input
if input in memory: return memory[input]
len = len(input)
for i in range(len):
prefix = input[0:i+1]
if prefix in dict:
suffix = input[i+1:]
seg_suffix = segment_string(suffix, dict)
if seg_suffix != '':
memory[input] = prefix + " " + seg_suffix
return prefix + " " + seg_suffix
memory[input] = ''
return ''
这道题目就展示了不同层次的优化，首先是一道有现实意义的问题，就是做单词自动识别，它也不需要特定领域的知识，当然递归你还是要知道的。在面试过程中，我可以给你一些提示，但最终你走到哪一步，就看你的能力。并且如果你实现了优化解法，我可以继续问当字典大到内存放不下如何？ |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？立即注册
×
|
窥视卡
雷达卡
发表于 2021-7-4 06:46
显身卡