一个面试题 -- restore database - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 一个面试题 -- restore database

相关主题
● 面试题总结(2) - Two/Three pointers	● 算法面试题
● 印度哥哥羞辱我（一道面试题）	● Walmart Lab onsite求指导
● xor cipher面试题求解	● 一道onsite面试题
● 问个关于set的题	● 请教一道面试题
● 面试题都做出来了，但还是悲剧了。。	● Glassdoor上面看到一道F家最近的面试题，来讨论一下？
● 一个面试题	● Facebook 电面
● 问个面试题，加些小抱怨	● 说一说我的看法
● 问个google面试题	● [我也攒RP]新鲜出炉的Google面试

相关话题的讨论汇总
话题: host话题: copy话题: database话题: restore话题: 面试题

进入JobHunting版参与讨论

(共1页)

n*******w
发帖数: 687

一个distributed database，各个host上都只保留了所有数据的一个subset。
现在要在每个host上restore所有数据。也就是对于每个host，把missing的数据从其它
host copy过来。至于选哪一个host，没有要求。
assume 所有host上数据的union就是整个database。
input是
host 1: 1 3 5
host 2: 2 3 4
host 3: 1 2 4 5 6
一种可能的output是
copy 2 from host 2 to 1
copy 4 from host 2 to 1
copy 6 from host 3 to 1
copy 1 from host 1 to 2
copy 5 from host 3 to 2
copy 6 from host 3 to 2
copy 3 from host 1 to 3
所有input要从stdin输入。
跟上一题同样的，最难的不在算法，而是短时间内写出code编译运行出正确结果。这题
可能还需要点数据结构。

q****x
发帖数: 7404

输入不对吧？应该是1 1 3 5，然后第一个代表host id。
另外有空行吗？
这个题可以扩展：
1.假设每个机器只能一次和一台机器通信，数据集大小一致，找最快复制方案。
2.去掉数据集大小一致假设，求最快。
3.加机器之间通信速度，求最快。

【在 n*******w 的大作中提到】

: 一个distributed database，各个host上都只保留了所有数据的一个subset。
: 现在要在每个host上restore所有数据。也就是对于每个host，把missing的数据从其它
: host copy过来。至于选哪一个host，没有要求。
: assume 所有host上数据的union就是整个database。
: input是
: host 1: 1 3 5
: host 2: 2 3 4
: host 3: 1 2 4 5 6
: 一种可能的output是
: copy 2 from host 2 to 1

(共1页)

进入JobHunting版参与讨论

相关主题
● [我也攒RP]新鲜出炉的Google面试	● 面试题都做出来了，但还是悲剧了。。
● 几道关于数据结构的面试题。	● 一个面试题
● 问两道Google面试题	● 问个面试题，加些小抱怨
● 说说Google的电面，求bless	● 问个google面试题
● 面试题总结(2) - Two/Three pointers	● 算法面试题
● 印度哥哥羞辱我（一道面试题）	● Walmart Lab onsite求指导
● xor cipher面试题求解	● 一道onsite面试题
● 问个关于set的题	● 请教一道面试题

相关话题的讨论汇总
话题: host话题: copy话题: database话题: restore话题: 面试题

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天