Google电面题，List中的duplicate最小距离

fyt227 发表于 2014-3-14 07:19
前面楼的反例，输入[A,A,A,A,B,B,C]，最小距离为2，
输出是[A,B,A,B,A,C,A]
你这个好像不行

好像理解错了，我认为可以。

1. A,B,C
2. A,B,A,B,C
3. A,B,A,B,A,C
4. A,B,A,B,A,C,A
楼主，求google面试注意事项？

这个值需要判断出现次数最多的那个数就行。最多的排的下，其他的就都可以。

尼玛，这题确实不适合电面
我的做法
1.先iterate list， 用hashmap 记下每个字母出现的频率
2.以频率 sort hashmap， 最高频率的在前面， 低频率的在后面
3.把一个list 分成多个buckets， 每个buckets的容量是 minimal distance， 最后一个bucket容量可能小于 minimal distance
4.按频率顺序， 把字母均匀的分配到每个bucket里， 如果某个字母出现的频率大于bucket的数量， return err
5.把buckets合起来，组成一个大的list，就是答案

python code 在此

def minDistanceList(A, d):
        length = len(A)
        freq_map = dict()
        for a in A:
                if a in freq_map:
                        freq_map[a] += 1
                else:
                        freq_map[a] = 1
        freq_list = []
        for a in freq_map:
                freq_list.append((freq_map[a], a))
        freq_list.sort(key = lambda x: x[0], reverse = True)
        buckets_cnt = length/d + (length%d>0)
        buckets = [[] for i in range(buckets_cnt)]
        bucket_idx = 0
        for s in freq_list:
                n = s[0]
                a = s[1]
                if n > buckets_cnt:
                        return None
                for i in range(n):
                        buckets[bucket_idx].append(a)
                        bucket_idx += 1
                        if bucket_idx==buckets_cnt:
                                bucket_idx = 0
        res = []
        for bucket in buckets:
                res += bucket
        return res
   
print minDistanceList(['A','A','A','A','B','B','C'], 2)
print minDistanceList(['A','B','B'], 2)
print minDistanceList(['A','B','B'], 1)
print minDistanceList(['A','B','B'], 3)

########################
results：

['A', 'B', 'A', 'B', 'A', 'C', 'A']
['B', 'A', 'B']
['B', 'B', 'A']
None

a5554794 发表于 2015-3-12 08:05
尼玛，这题确实不适合电面
我的做法
1.先iterate list， 用hashmap 记下每个字母出现的频率

觉得这个做法挺好~