《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3616|回复: 27
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
头像被屏蔽
fyt227 发表于 2014-3-13 07:44:36 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽
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 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| fyt227 发表于 2014-3-14 07:09:00 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| fyt227 发表于 2014-3-14 07:18:36 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| fyt227 发表于 2014-3-14 07:18:55 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-25 17:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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