阿里面试 Coding 测试回顾

1. 数组交集求解

求两个无序数组的交集，例如a={1,5,2,4,2}, b={2,7,2,8},结束为{2,2}.
可见，该问题有多种解法，其中线性时间复杂度的解法应该是使用hash table求解。这里没有要求复杂度。我直接使用了python 简单完成。

#!/usr/bin/python 2.7
# @author liuzhiqiang
# @date 2018-01-25
# @email lucien@pku.edu.cn

from collections import Counter

# main function
def main():
    '''
    :return: 0
    '''
    nums1 = [1,2,5,3,2,4]
    nums2 = [2,7,8,2]
    dict1 = Counter(nums1)
    dict2 = Counter(nums2)
    set3 = set(nums1) & set(nums2)
    lists = []
    for i in set3:
        min_count = min(dict1[i], dict2[2])
        lists += [i] * min_count
    print lists
    return 0

if __name__ == '__main__':
    main()

2. 字符串中连续最频繁子串求解

求一个字符串中连续出现的次数最多的子串。例如字符串“abababc”,最多连续出现的为ab，连续出现三次。该类题目用到了后缀数组这个数据结构。

#!/usr/bin/python 2.7
# @author liuzhiqiang
# @date 2018-01-25
# @email lucien@pku.edu.cn
import sys

# To obtain substr and max count
def find_substr(string):
    '''
    :param string:
    :return: max_count, substr
    '''
    max_count = 0  # max count
    substr_len = 0  # the length of sub string
    addr = 0   # the address index of sub string
    length = len(string)

    suffix_arr = [string[i:] for i in range(length)]  # create suffix array

    for i in range(1, (length + 1)/2 + 1):
        j = 0
        while j + i <= length - 1:
            k = j
            temp_count = 1
            while k + i <= length - 1 and suffix_arr[k][:i] == suffix_arr[k + i][:i]:
                temp_count += 1
                k += i
            if temp_count > max_count:
                max_count = temp_count
                substr_len = i
                addr = k
            j += i
    substr = suffix_arr[addr][:substr_len]
    return max_count, substr

# main function
def main():
    '''
    :return: 0
    '''
    # string = 'skykykykykysky'
    string = sys.stdin.readline()
    max_count, substr = find_substr(string)
    print 'max_count: %d, substr: %s' % (max_count, substr)
    return 0

if __name__ == '__main__':
    main()