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

尼玛，这题确实不适合电面
我的做法
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 记下每个字母出现的频率

觉得这个做法挺好~

感觉是一个DFS的题目 说一个大概的想法哈 用一个hashmap来存每一个string最近被存放的位置 其实也就是当前搜索的深度  然后每次从剩下的可选String里面选一个合法的加到结果队列里面去 如果可选集合空了 说明找到了一个合法解 就返回

我的想法是这样的：
1。先统计list中不同元素的个数，假设为u，如果u < minimal distance，则无解
2. 否则按照出现的次数将list中的元素从大到小进行排序，假设排完后为x1，x2，。。。。xn，即x1出现的次数大于x2，x2出现的次数大于x3等。
3. 然后可以构造一组解，x1,x2,......xn,x1,x2....xn,x1,x2...这样排列下去。应该就是符合条件的

我能想的是动态规划。 放到一个二维数组. 横竖每个都是字符。
然后从左上开始，遇到一样的跳过去，并记录。
不一样的swap。

不过目测需要n2

而且这题能电面？？
估计是有很简单的解决方法吧？

RomanC 发表于 2014-3-12 21:38
我的想法是这样的：
1。先统计list中不同元素的个数，假设为u，如果u < minimal distance，则无解
2. 否则 ...

感觉贪心能work， 但感觉不知道怎么证明正确性。

北美农民 发表于 2014-3-13 11:02
感觉贪心能work， 但感觉不知道怎么证明正确性。

我又想了一下，发现我的解法好像是错的。。。

RomanC 发表于 2014-3-12 22:17
我又想了一下，发现我的解法好像是错的。。。

我觉得能work， 你给个反例？

北美农民 发表于 2014-3-13 11:27
我觉得能work， 你给个反例？

比如[A,A,A,A,B,B,C]，最小距离为2，合法的应该是[A,B,A,B,A,C,A]，感觉构造的方法没有我说的那么简单。。。

loop一遍数duplicates, 比如C重复3次，B重复2次，A重复1次， 那么要让所有duplicates的distance尽可能大，必然数组第一个数是C（重复次数最多的），第二个是B，第三个是C， 最后数组一定是C B A C B （因为要确保所有duplicates的distance都尽可能大） 所以如果input > 2 那就是无解。 同样，如果C重复10次，B2次，A一次， 那么数组要确保所有duplicates距离最大，一定要有这种形式：C B A C B CCCCC.... 所以这个case的input>1就无解了。

此算法还没用数学analysis验证，但是直觉上貌似是对的。。如果有错请勿喷。。。 随便猜的