[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3830|回复: 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

使用道具 举报

全球28万学生4.7分推荐
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 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-25 02:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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