由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - hackercup出结果了
相关主题
面试题求解NYC金融公司招Java码工
其实投行里面撑门面的都是白人精英BinaryTree to DoublyLinkedList
BST合并的面试题Tableau is for sale now?
发面经攒人品求blessFacebook Hacker Cup
这里有BOA的人吗?这个怎么弄?
Looking for Part-time Office Manager - Hina Group U.S.‏彭博 面试题
3 Secrets No-One Ever Revealed About Investment Bank Careers zz问一道 Interviewstreet 上的题 (JAVA)
h1被雷求助Interview street上的一题求助
相关话题的讨论汇总
话题: case话题: company话题: hierarchy话题: mergers话题: president
进入JobHunting版参与讨论
1 (共1页)
p*****2
发帖数: 21240
1
大家查查吧。谁进了下一轮吱一声呀。
i******r
发帖数: 793
2
看不到题目,谁贴个题目来看看吧
B******5
发帖数: 4676
3
这么快。。。
我一个好友进前100了。。。
p*****2
发帖数: 21240
4

牛呀。

【在 B******5 的大作中提到】
: 这么快。。。
: 我一个好友进前100了。。。

y**********u
发帖数: 6366
5
我全挂。。。

【在 p*****2 的大作中提到】
:
: 牛呀。

l*****a
发帖数: 14598
6
看来大牛又晋级了
admire

【在 p*****2 的大作中提到】
: 大家查查吧。谁进了下一轮吱一声呀。
p*****2
发帖数: 21240
7

我全挂了too。成都如果全挂我更没戏了。

【在 l*****a 的大作中提到】
: 看来大牛又晋级了
: admire

l*****a
发帖数: 14598
8
share 一下题目,大家讨论一下吧

【在 p*****2 的大作中提到】
:
: 我全挂了too。成都如果全挂我更没戏了。

p*****2
发帖数: 21240
9

In a certain business sector there are currently N small companies, each
having just a single employee. These employees are numbered 1 through N.
The business sector is about to be transformed into a monopoly. This will
happen through a series of mergers, until there is only one company. A
single merger involves two companies. In a merger, the president of one
company becomes the direct report of the president of the other company,
preserving the rest of the hierarchies of both companies.
You will be given the descriptions of all mergers. Depending on how they are
performed (which of the two presidents involved becomes the president of
the new company), the hierarchy can of the final company can take different
shapes. We want the hierarchy of the final company to be as shallow as
possible. The task is to find the smallest possible number of levels in the
final hierarchy.
There is also a limit D on the number of direct reports any employee can
have. Because of this limit, there may be only one way to accomplish a
certain merger, or it might even be impossible. However, there will always
be some way to accomplish all the mergers.
Input
The first line contains the number of test cases T.
Each test case starts with a blank line. The next line contains two integers
, N and D.
Each of the following N-1 lines describes a single merger, with two integers
between 1 and N. These are the employees whose companies are merging. The
two employees will never already be part of the same company.
The mergers must be performed in the order in which they are given.
Constraints
5 ≤ T ≤ 20
2 ≤ N ≤ 30000
1 ≤ D ≤ 5000
The input test cases will be such that it is possible to accomplish all
mergers.
Output
For each of the test cases numbered in order from 1 to T, output "Case #i: "
followed by a single integer, the smallest number of levels in the final
hierarchy.
Examples
In the first example, we have N=3 and D=2. The first merger happens between
the companies of employees 1 and 2. In the resulting company we can have
employee 1 as the president with 2 as his report, or vice versa. Next this
company merges with the company of employee 3. If we have employee 3 become
the president, the hierarchy will be a chain 3-1-2 or 3-2-1. If 1 or 2
become the president, that president will have the other two employees as
direct reports. This last hierarchy has two levels.
Example inputExample output
5
3 2
1 2
1 3
3 1
1 2
1 3
4 2
4 2
2 1
3 2
5 2
5 2
4 5
2 1
3 1
6 3
6 1
4 2
1 4
5 6
3 6
Case #1: 2
Case #2: 3
Case #3: 3
Case #4: 3
Case #5: 4

【在 l*****a 的大作中提到】
: share 一下题目,大家讨论一下吧
p*****2
发帖数: 21240
10
我觉得上边这道还算是有思路的。不过我们几个人都做错了。
i******r
发帖数: 793
11
并查集
l******c
发帖数: 2555
12
Similar google interview questions

are
different

【在 p*****2 的大作中提到】
: 我觉得上边这道还算是有思路的。不过我们几个人都做错了。
a********m
发帖数: 15480
13
牛!

【在 B******5 的大作中提到】
: 这么快。。。
: 我一个好友进前100了。。。

h*****s
发帖数: 29
14
UnionFind + DP

are
different

【在 p*****2 的大作中提到】
: 我觉得上边这道还算是有思路的。不过我们几个人都做错了。
1 (共1页)
进入JobHunting版参与讨论
相关主题
Interview street上的一题求助这里有BOA的人吗?
求教EA一道面试题Looking for Part-time Office Manager - Hina Group U.S.‏
问个面试题3 Secrets No-One Ever Revealed About Investment Bank Careers zz
stable rearrange an integer array with + and -h1被雷求助
面试题求解NYC金融公司招Java码工
其实投行里面撑门面的都是白人精英BinaryTree to DoublyLinkedList
BST合并的面试题Tableau is for sale now?
发面经攒人品求blessFacebook Hacker Cup
相关话题的讨论汇总
话题: case话题: company话题: hierarchy话题: mergers话题: president