一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3012|回复: 27
收起左侧

[树/链表/图] Google电面题,List中的duplicate最小距离

[复制链接] |试试Instant~ |关注本帖
fyt227 发表于 2014-3-13 07:44:36 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
google电面fail掉的题:

有个List<String>,里面有duplicates,比如[A,B,B,A,C].现在有另一个input是一个int存放minimal distance。
要求return的list里让duplicate之间的最小距离大于等于输入的minimal distance。


example是
[A, B, B], 2 -> [B, A, B] (2 - 0 >= 2)
[A, B, B], 1 -> (any permutation)
[A, B, B], 3 -> (no solution; throw exception, return error code, etc)


求问怎么做
a5554794 发表于 2015-3-12 08:05:41 | 显示全部楼层
尼玛,这题确实不适合电面
我的做法
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
回复 支持 1 反对 0

使用道具 举报

marstorm08 发表于 2014-3-13 08:21:18 | 显示全部楼层
感觉是一个DFS的题目 说一个大概的想法哈 用一个hashmap来存每一个string最近被存放的位置 其实也就是当前搜索的深度  然后每次从剩下的可选String里面选一个合法的加到结果队列里面去 如果可选集合空了 说明找到了一个合法解 就返回

回复 支持 反对

使用道具 举报

RomanC 发表于 2014-3-13 10:38:26 | 显示全部楼层
我的想法是这样的:
1。先统计list中不同元素的个数,假设为u,如果u < minimal distance,则无解
2. 否则按照出现的次数将list中的元素从大到小进行排序,假设排完后为x1,x2,。。。。xn,即x1出现的次数大于x2,x2出现的次数大于x3等。
3. 然后可以构造一组解,x1,x2,......xn,x1,x2....xn,x1,x2...这样排列下去。应该就是符合条件的
回复 支持 反对

使用道具 举报

readman 发表于 2014-3-13 10:49:04 | 显示全部楼层
我能想的是动态规划。 放到一个二维数组. 横竖每个都是字符。
然后从左上开始,遇到一样的跳过去,并记录。
不一样的swap。

不过目测需要n2
回复 支持 反对

使用道具 举报

readman 发表于 2014-3-13 10:50:36 | 显示全部楼层
而且这题能电面??
估计是有很简单的解决方法吧?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-13 11:02:39 | 显示全部楼层

感觉贪心能work, 但感觉不知道怎么证明正确性。
回复 支持 反对

使用道具 举报

RomanC 发表于 2014-3-13 11:17:04 | 显示全部楼层
北美农民 发表于 2014-3-13 11:02
感觉贪心能work, 但感觉不知道怎么证明正确性。

我又想了一下,发现我的解法好像是错的。。。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-13 11:27:21 | 显示全部楼层
RomanC 发表于 2014-3-12 22:17
我又想了一下,发现我的解法好像是错的。。。

我觉得能work, 你给个反例?
回复 支持 反对

使用道具 举报

RomanC 发表于 2014-3-13 11:51:57 | 显示全部楼层
北美农民 发表于 2014-3-13 11:27
我觉得能work, 你给个反例?

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

使用道具 举报

csgtc 发表于 2014-3-13 12:02:21 | 显示全部楼层
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验证,但是直觉上貌似是对的。。如果有错请勿喷。。。 随便猜的
回复 支持 反对

使用道具 举报

csgtc 发表于 2014-3-13 12:03:00 | 显示全部楼层
csgtc 发表于 2014-3-12 23:02
loop一遍数duplicates, 比如C重复3次,B重复2次,A重复1次, 那么要让所有duplicates的distance尽可能大,必 ...

complexity是O(N)
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-13 12:17:02 | 显示全部楼层
RomanC 发表于 2014-3-12 22:51
比如[A,A,A,A,B,B,C],最小距离为2,合法的应该是[A,B,A,B,A,C,A],感觉构造的方法没有我说的那么简单。。 ...

你这个case显然可以, 频率最多的A隔2个位置能放满, 然后放B, 然后C
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-13 12:17:54 | 显示全部楼层
csgtc 发表于 2014-3-12 23:02
loop一遍数duplicates, 比如C重复3次,B重复2次,A重复1次, 那么要让所有duplicates的distance尽可能大,必 ...

对, 是这个意思, 但感觉没法证明。
回复 支持 反对

使用道具 举报

iveney 发表于 2014-3-14 03:50:53 | 显示全部楼层
应该 greedy 能 work 啊。Count frequency,然后用 min distance 来 assign positions. 注意这里应该先 assign frequency 最多的那个duplicate,因为他们的 bound 最 tight,必须先满足。所以涉及到 sorting,那么应该是 O(n log n).

证明思路:假设有 solution 但是这个方法找不到,也就是在 assign 某个 duplicate x 时,假设重复k次,之前已经assign了 i-1个,所以这个 dup 会被 assign 到 i, i+d, i+2d, ... i+kd,这个方法 fail 说明 for some j < k, i+jd >= n,也就是不够位置放了。那么唯一解决办法就是把他们整体前移,但问题是之前的元素出现次数 >= k,如果先 assign x 那么必然有其他 dup y 无法满足,所以无解,contradiction.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

lixiang.xjtu 发表于 2014-3-14 05:36:03 | 显示全部楼层
本帖最后由 lixiang.xjtu 于 2014-3-14 05:38 编辑

mark 一下,等会儿看
回复 支持 反对

使用道具 举报

花农 发表于 2014-3-14 06:33:51 | 显示全部楼层
搞一个hashtable, 存所有字母出现的frequency,然后根据frequency排序。原来的List扔掉。建立新的list,交替插入,先插入frequency最大的一个,然后第二大的一个结点,。。。第一轮插入所有出现的结点,各自frequency减去1. 然后进行新的一轮,直到所有结点的frequency都为0.
回复 支持 反对

使用道具 举报

 楼主| fyt227 发表于 2014-3-14 07:07:22 | 显示全部楼层
花农 发表于 2014-3-14 06:33
搞一个hashtable, 存所有字母出现的frequency,然后根据frequency排序。原来的List扔掉。建立新的list,交替 ...

感觉能解,不过好像要有好多边界条件判断
回复 支持 反对

使用道具 举报

 楼主| fyt227 发表于 2014-3-14 07:09:00 | 显示全部楼层
readman 发表于 2014-3-13 10:50
而且这题能电面??
估计是有很简单的解决方法吧?

真真就是这么个题,我看到就傻了,google就是这么对我的
回复 支持 反对

使用道具 举报

 楼主| fyt227 发表于 2014-3-14 07:18:36 | 显示全部楼层
RomanC 发表于 2014-3-13 10:38
我的想法是这样的:
1。先统计list中不同元素的个数,假设为u,如果u < minimal distance,则无解
2. 否则 ...

根据你提的那个反例,感觉改一改能work。
把第三步换成x1,x2,..,xk,  x1, x2,....貌似能解
k是最小距离。
不是每组每个不同数都轮一遍,而是只轮到频率最高的数满足最小距离就行?
不知道可不可以
回复 支持 反对

使用道具 举报

 楼主| fyt227 发表于 2014-3-14 07:18:55 | 显示全部楼层
RomanC 发表于 2014-3-13 10:38
我的想法是这样的:
1。先统计list中不同元素的个数,假设为u,如果u < minimal distance,则无解
2. 否则 ...

根据你提的那个反例,感觉改一改能work。
把第三步换成x1,x2,..,xk,  x1, x2,....貌似能解
k是最小距离。
不是每组每个不同数都轮一遍,而是只轮到频率最高的数满足最小距离就行?
不知道可不可以
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 04:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表