提供两道面试题

提供两道面试题

第一题， 给两个排好序的数组，设计一个 function 把他们合成一个排好序的数组。然后，follow up 是 用这个function 设计一个算法 能把一个没有排序的大数组排序。

第二题， 给一个数组，每个元素是一个字符串， 只有英语小写字母， 从每个字串中找出一个 长度最小的 substring 能够唯一代表这个字串 , 不与其他字串的代表 substring  重复。

比如：   ['abcder'  ,  'abcduer'   , 'paqotom' , 'paqiam' ]
解：      ['de' , 'du' , 't', 'qi']

可能有很多解，只要 每个 substring 长度最短， 找到任何一个即可。

umusa2012 发表于 2019-10-28 01:19
根据   “首先在串s的后面加一个特殊字符$, 然后对于的s每一个后缀”：

['abcder'  ,  'abcduer ...

我想到了一个更好的做法。O(nm)

[abc, bd, ac]
construct a new string, suppose #,$ are greater than letter, in this form: abc#bd#ac$
in the following table,
first column denote where the suffix come from
second column is suffix array
third column is the height array
after the arrow is the longest prefix's length from anther string
0        |        abc#bd#ac$                | 0        -> 1
2        |        ac$                             | 1        -> 1
0        |        bc#bd#ac$                  | 0 -> 1
1        |        bd#ac$                        | 1 -> 1
0        |        c#bd#ac$                    | 0 -> 1
2        |        c$                               | 1 -> 1
1        |        d#ac$                         | 0 -> 0
....
strings start with # or $ are omitted bere

for each suffix, find the logest common prefix that is from different string

string 0: abc
1,1,1 ==> answer is 2

string 1: bd
1, 0  ==> asnwer is 1

string 2: ac
1, 1  ==> asnwer is 2

Note that if for a string, the answer is greater than the string's length, which means this string is a substring of another string.
The problem does not define what if this situation happens.

第二道题虽然我没做出来，不过出得真棒

第二题有优化要求吗？

用后缀数组应该可以做。假设一共n个串，每个串的长度最大是m
对每一个list里的每个string都构造对应后缀数组 O(nm)
考虑区分两个串s, t的情况：
首先在串s的后面加一个特殊字符$, 然后对于的s每一个后缀，到t的后缀数组里进行二分查找，可以得到这个后缀需要多长的前缀才能区分s 和 t。
对于所有的t求最大值， 就是这个s的后缀需要的最大长度。再对于所有可能的后缀（除了$）取最小值就可以得到对于s的结果
复杂度应该是O(n m log m)
对每个串都要做一遍，所以总复杂度是 O(n^2 m log m)

rayleigh0328 发表于 2019-10-27 05:48
用后缀数组应该可以做。假设一共n个串，每个串的长度最大是m
对每一个list里的每个string都构造对应后缀数 ...

根据   “首先在串s的后面加一个特殊字符$, 然后对于的s每一个后缀”：

['abcder'  ,  'abcduer'   , 'paqotom' , 'paqiam' ]

'abcder' ：  suffix array：[$r, $er, $der, $cder, $bcder, $abcder]
. 1point3acres'abcduer' ：  suffix array：[$r, $er, $uer, $duer, $cduer, $bcduer, $abcduer]
'paqotom' ：  suffix array：[$m, $om, $tom, $otom, $qotom, $aqotom, $paqotom]
'paqiam' :     suffix array：[$m, $am, $iam, $qiam, $aqiam, $paqiam]

根据  ,  "到t的后缀数组里进行二分查找，可以得到这个后缀需要多长的前缀才能区分s 和 t。"

use binary search to search each suffix in t:

for
    s =  'abcder' : search each of [$r, $er, $der, $cder, $bcder, $abcder]
in
    t   =  'abcduer' ：[$r, $er, $uer, $duer, $cduer, $bcduer, $abcduer]

对于  s = ‘abcder’，  

for "$r", 用字串的长度进行二分查找, 可以在  t 中找到 ‘$r’， 就是说 如果用 ‘r’ 作为代表子串的话， 需要 ‘abcde’ （长度为 6 － 1 = 5） 才能区分 s 和 t ？

同理：
    对于 ‘$er’， 要 ‘abcd’ （长度为 6 － 2 = 4） 才能区分 s 和 t ？
    对于 ‘$der’， 因为在 t 中找不到相同的后缀，所以不需要任何前缀就能区分 s 和 t ？
同理：
    对于 ‘$cder’， 不需要任何前缀就能区分 s 和 t ？
    对于 ‘$bcder’，不需要任何前缀就能区分 s 和 t ？

这样， 根据 ”对于所有的 t 求最大值”， 如何能找到最短子串来代表 s ？

还是不太明白您的算法。

谢谢

谢谢楼主分享。第二题我从没有见过，感觉需要好好想一想。

rayleigh0328 发表于 2019-10-28 23:17
我想到了一个更好的做法。O(nm)

[abc, bd, ac]

谢谢 , 您的算法， 还是有些问题不太懂:

"third column is the height array"

Can you please explain what "height array " is ?

after the arrow is the longest prefix's length from anther string

0        |        abc#bd#ac$                | 0        -> 1
2        |        ac$                             | 1        -> 1
0        |        bc#bd#ac$                  | 0 -> 1
1        |        bd#ac$                        | 1 -> 1
0        |        c#bd#ac$                    | 0 -> 1
2        |        c$                               | 1 -> 1
1        |        d#ac$                         | 0 -> 0
.

What is " longest prefix's length from anther string" ?

for each suffix, find the logest common prefix that is from different string

string 0: abc
1,1,1 ==> answer is 2

string 1: bd
1, 0  ==> asnwer is 1

string 2: ac
1, 1  ==> asnwer is 2

How to get the an answer here  ? Why the answer is 2 for "abc" ?

string 0: abc
1,1,1 ==> answer is 2

Note that if for a string, the answer is greater than the string's length, which means this string is a substring of another string.


Why "this string is a substring of another string." ?

谢谢

umusa2012 发表于 2019-10-30 21:39
谢谢 , 您的算法， 还是有些问题不太懂:

height[i] 表示 sa[i] 和 sa[i-1]的最长公共前缀，height可以在构造出sa以后线性的构造出来。然后询问两个串的最长公共前缀就可以转化成height数组里的range-minimum-query。具体可以参考下面的链接
https://oi-wiki.org/string/sa/
this string is a substring of another string 这句话有点confusing。但是我也不知道怎么更好的描述了，再举个例子吧
arr=[aaaa, ba, c] ==> aaaa#ba#c$
0|aaaa#ba#c$   | inf
0|aaa#ba#c$     | 3   
0|aa#ba#c$      | 2   
0|a#ba#c$        | 1
1|a#c$              | 1
1|ba#c$            | 0
2|c$                  | 0
这里仍然省略了所有#,$开头的串。第一列是这个前缀在arr里面对应的字符串的下表，第二列是suffix array, 第三列是height。对于第一个串aaaa#ba#c$，我们需要再SA中找离它最近的，不属于arr[0]的后缀。所以是从a#c$ 得到1。 而不是 从 aaa#ba#c$得到3。