f*******h
发帖数: 53 | 1 假设一共100名小朋友参加足球比赛。每个小朋友都有自己最要好的15个好朋友。现在
要求从这100名小朋友中组成10支队伍进行比赛。要求每个小朋友都和自己的好朋友在
一个队中。请问，有什么数据结构和算法来完成此任务。 |
P********l
发帖数: 452 | 2 general idea: Greedy
data structure:
adjacent matrix.
1. each line is for a child, content is a link to one of his friends.
2. an array keeps the number of friends not having a team for a child.
algorithm:
//all child has 15 friends free.
currentChild = any one.
do{
organize 10 children around him to be a team //<- note 1.
children update their free links.
currentChild = one free child with lest free links.
}while( currentChild != null )
note1: can pick 10 children with the lest free links |
c**y
发帖数: 172 | 3 This problem might have no solution.
For example, the 100 children can be divided into two groups such that there
is no link between the two groups. A link represents a friend relationship
between two children. If the numbers of children in the above two groups are
49 and 51, respectively. There is no way to construct such 10 groups, each
containing 10 children.
So any algorithm leading to the final solution should be cable to determine whether
or not there exists a solution to a given collectio |
f*******h
发帖数: 53 | 4 面试的人明确的和我说不是Greedy Algorithm。 |
g*****a
发帖数: 1457 | 5 I think the requirement is every kid at least have one good friend in the
group. Not all other 9 kids need to be his good friends.
there
relationship
are
determine whether
【在 c**y 的大作中提到】
: This problem might have no solution.
: For example, the 100 children can be divided into two groups such that there
: is no link between the two groups. A link represents a friend relationship
: between two children. If the numbers of children in the above two groups are
: 49 and 51, respectively. There is no way to construct such 10 groups, each
: containing 10 children.
: So any algorithm leading to the final solution should be cable to determine whether
: or not there exists a solution to a given collectio
|
l******c
发帖数: 2555 | 6 there might be a solution or not
we can try.
1. sort the children with number of friends,
2, sort each child friends list based on 1
3 . process starting with the child with least friend based on 1, by
selecting the 9 kids with most friends based 2
4 if every kid is put in a group, done;
otherwise, backtrack, ie. change the last selection in 3
when back to the first selection and enum all the posibility for the first
selection, and fail, no solution
【在 f*******h 的大作中提到】
: 面试的人明确的和我说不是Greedy Algorithm。
|
l******c
发帖数: 2555 | 7 if do not require optimization, backtrack is enough, no need sort.
first
【在 l******c 的大作中提到】
: there might be a solution or not
: we can try.
: 1. sort the children with number of friends,
: 2, sort each child friends list based on 1
: 3 . process starting with the child with least friend based on 1, by
: selecting the 9 kids with most friends based 2
: 4 if every kid is put in a group, done;
: otherwise, backtrack, ie. change the last selection in 3
: when back to the first selection and enum all the posibility for the first
: selection, and fail, no solution
|
s*****e
发帖数: 36 | 8 Can we construct a undirected graph and then find a Hamilton path of length
10? |
m*****g
发帖数: 226 | |
a*s
发帖数: 425 | 10 我想这个问题可以分解
假设我们有一种算法可以找n个小朋友中size为10的clique,
那么，就是先找出100个小朋友中，所有size为10的clique,
然后，对应于每个clique,相对应的子问题是在90个小朋友中找size为10的clique,
有点像用recursive列出所有的permutation
【在 f*******h 的大作中提到】
: 假设一共100名小朋友参加足球比赛。每个小朋友都有自己最要好的15个好朋友。现在
: 要求从这100名小朋友中组成10支队伍进行比赛。要求每个小朋友都和自己的好朋友在
: 一个队中。请问，有什么数据结构和算法来完成此任务。
|
f*******h
发帖数: 53 | 11 感觉没那么复杂。当时面试的人说我的Greedy Algorithm不行，给我五分钟的时间想其
他方法（包括写pseudocode）。所以应该是比较简单的题。 |
l******c
发帖数: 2555 | 12 normal backtrack recursive, like maze problem
【在 f*******h 的大作中提到】
: 感觉没那么复杂。当时面试的人说我的Greedy Algorithm不行，给我五分钟的时间想其
: 他方法（包括写pseudocode）。所以应该是比较简单的题。
|
