提供两道面试题, 想找到最优解

提供两道面试题 , 想找到最优解
第一题， 给两个排好序的数组，设计一个 function 把他们合成一个排好序的数组。然后，follow up 是 用这个function 设计一个算法 能把一个没有排序的大数组排序。

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

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

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

umusa2012 发表于 2019-10-27 19:03
如果是 merge sort， 就不需要用那个已经建好的  function, right ?

需要的，mergesort的思路是先分成两部分，然后对两部分排序，然后不就变成了最开始的情况，两个排好序的数组，然后用这个函数merge

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

请问第二个为什么是du不是u，同理第四个不是i？是找到最短的还是成立即可呢？

huangbingyu 发表于 2019-11-2 00:14
请问第二个为什么是du不是u，同理第四个不是i？是找到最短的还是成立即可呢？

他是说要找到最短的，所以我觉得第二个应该是u，第四个应该是i

第一题解是merge sort吗？

第二题 有点像huffman coding。。

zwj102030 发表于 2019/10/28 02:25:20
第一题解是merge sort吗？

我也觉得就是mergesort

yayafuture 发表于 2019-10-28 04:37
我也觉得就是mergesort

如果是 merge sort， 就不需要用那个已经建好的  function, right ?

第二道题，出得很棒。力扣有类似的题目吗？

第二题有什么好的解法吗？楼主当时是怎么做的

yayafuture 发表于 2019-10-28 09:38
需要的，mergesort的思路是先分成两部分，然后对两部分排序，然后不就变成了最开始 ...

同意哈哈