K*V
发帖数: 192 | 1 your data-center screwed up and know every data center needs to have the
data from the other centers again, what is the most efficient way to copy
data such that every center has it. |
G*********o
发帖数: 2045 | 2 靠，土希格玛好换换题吧
your data-center screwed up and know every data center needs to have the
data from the o........
【在 K*V 的大作中提到】
: your data-center screwed up and know every data center needs to have the
: data from the other centers again, what is the most efficient way to copy
: data such that every center has it.
|
K*V
发帖数: 192 | 3 是的 two sigma 面试题。
更具体的题目是
Write a program to synchronize data sets between data centers using as few
copies as possible.
Example 1:
----------
Input:
4
1 3 4
1 2 3
1 3
1 4 2
One Possible Correct Output:
2 2 1
4 1 2
2 2 3
4 4 3
3 1 4
【在 G*********o 的大作中提到】
: 靠，土希格玛好换换题吧
:
: your data-center screwed up and know every data center needs to have the
: data from the o........
|
k*******d
发帖数: 1340 | 4 说清楚一点吧，Input和Output代表什么。
In practice这是个很复杂的问题，但从你的题目来看这更像是人为构造的算法题，既
然是这样的题目，就要给清楚assumption，让人弄明白到底要做什么
【在 K*V 的大作中提到】
: 是的 two sigma 面试题。
: 更具体的题目是
: Write a program to synchronize data sets between data centers using as few
: copies as possible.
: Example 1:
: ----------
: Input:
: 4
: 1 3 4
: 1 2 3
|
s*****u
发帖数: 164 | 5 Oh no! Disaster has struck some of ACME's redundant data centers. The
administrators have managed to restore backups, but some data sets are
still missing from some data centers. Fortunately, every data set can be
found at least once in one or more of the data centers. However, before
ACME can resume normal operations, it needs to ensure that each data
center has a copy of every data set.
Your goal is to help ACME resume normal operations by writing a program
to synchronize data sets between data centers using as few copies as
possible.
Input:
------
The first line of input will contain an integer between 0 and 999999
inclusive, representing the number of data centers.
Following that will be one line of input for each data center. Each
line will contain an integer representing the number of data sets at
that data center, followed by a space and space-separated list of data
set ids currently present at that data center. Data set ids are each
an integer between 1 and 999999, inclusive. Each line will be at most
999 characters long.
Data set ids are not necessarily consecutive. The list of data sets
will not be in any particular order.
Output:
-------
The program must output an optimal data set copy strategy to ensure that
every data center has a copy of every data set. Output one line for every
copy instruction.
A copy instruction is of the form , where
is the data set id, is the index of the data center
the data set will be copied from (1 = the first data center), and
is the index of the data center to copy the data set to.
When there are no more copy instructions, the program must output the
word "done" on a line by itself.
There is often more than one correct output with minimal number of
operations for a given input, and any output that satisfies the
requirements is valid.
Constraints:
------------
The code you submit must take input from stdin and produce output to
stdout as specified above. No other output is permitted. You can
assume the input will be valid. In the examples below, the text
"Input:" and "Output:" (or "One Possible Correct Output:") are not
part of the output, and neither are the blank lines.
Example 1:
----------
Input:
4
3 1 3 4
3 1 2 3
2 1 3
3 1 4 2
One Possible Correct Output:
2 2 1
4 1 2
2 2 3
4 4 3
3 1 4
done
Example 2:
----------
Input:
2
2 1 2
2 2 1
Output:
done
Example 3:
----------
Input:
3
5 1 3 4 5 7
2 1 3
1 2
One Possible Correct Output:
2 3 2
2 3 1
1 1 3
4 1 2
5 1 3
5 3 2
4 2 3
3 1 3
7 1 2
7 1 3
done |
P****d
发帖数: 369 | |
p****a
发帖数: 4829 | 7 这属于quant的范畴吗？怎么看着是码工的题？
【在 K*V 的大作中提到】
: 是的 two sigma 面试题。
: 更具体的题目是
: Write a program to synchronize data sets between data centers using as few
: copies as possible.
: Example 1:
: ----------
: Input:
: 4
: 1 3 4
: 1 2 3
|
J*****n
发帖数: 4859 | 8 都般到高层建筑了,还出这种刮风下雨的题。真没长进。 |
