x***i
发帖数: 64 | 1 刚店面完，口头答应recommand onsite, 不知最终如何
先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
over the phone
题目大概是这样
social network, billions id, every id has about 100 friends roughly, what is
max connections between any two ppls. write algorithm to return min
connections between two ids: int min_connection(id1, id2)
you can call following functions
expand(id) return friends list of id
expandall(list) return friends union of all the ids in the list
intersection(list1, list2) return intersection
removeintersection(list1, list2) | k*j
发帖数: 153 | 2 cong!!
他家到底freeze hiring了没啊
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| r*******y
发帖数: 1081 | 3 connection means a path from one people to another people ?
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| x****1
发帖数: 118 | 4 赞！
他家这种类型的题目貌似很多，应该好好准备。
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| d***n
发帖数: 65 | 5 Could you define what is max connections and min connections? | a**********2
发帖数: 340 | 6 这题是不是就是dfs找所有路径
所有路径removeintersection就是最多连接，
最短路径就是最少连接
intersection用来判重，expandall用来添加已访问的节点
瞎猜一下，题目是不是不允许用其他数据结构，只能用list？ | x***i
发帖数: 64 | 7 刚店面完，口头答应recommand onsite, 不知最终如何
先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
over the phone
题目大概是这样
social network, billions id, every id has about 100 friends roughly, what is
max connections between any two ppls. write algorithm to return min
connections between two ids: int min_connection(id1, id2)
you can call following functions
expand(id) return friends list of id
expandall(list) return friends union of all the ids in the list
intersection(list1, list2) return intersection
removeintersection(list1, list2) | k*j
发帖数: 153 | 8 cong!!
他家到底freeze hiring了没啊
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| r*******y
发帖数: 1081 | 9 connection means a path from one people to another people ?
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| x****1
发帖数: 118 | 10 赞！
他家这种类型的题目貌似很多，应该好好准备。
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| | | d***n
发帖数: 65 | 11 Could you define what is max connections and min connections? | H***e
发帖数: 476 | 12 min 和 max connection是如何定义的阿？
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| q****x
发帖数: 7404 | 13 what is max connection and what is min?
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| q****x
发帖数: 7404 | 14 貌似打开了。
【在 k*j 的大作中提到】
: cong!!
: 他家到底freeze hiring了没啊
:
: read
: is
| s******n
发帖数: 3946 | 15 呵呵，看不懂什么是max/min connection | i*******e
发帖数: 240 | 16 max connection = longest path?
If so, how about this one? lg 100 based (10^9) = 4.5? Very rough estimation.
So max connection = 5. Not tight bound, any other suggestion?
For min connection, shorted path should work. Scalability is likely to be the main concern. | k***t
发帖数: 276 | 17 Isn't finding the longest path in a graph an NP-Complete problem?
read
is
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| c*****n
发帖数: 96 | 18
read
is
Any idea how to solve this problem ? Thanks.
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| c*****n
发帖数: 96 | 19
read
is
Any idea how to solve this problem ? Thanks.
【在 x***i 的大作中提到】
: 刚店面完，口头答应recommand onsite, 不知最终如何
: 先聊天，took about 15 minutes.. 然后上题, 先问思路和算法，然后写pcode, read
: over the phone
: 题目大概是这样
: social network, billions id, every id has about 100 friends roughly, what is
: max connections between any two ppls. write algorithm to return min
: connections between two ids: int min_connection(id1, id2)
: you can call following functions
: expand(id) return friends list of id
: expandall(list) return friends union of all the ids in the list
| c**********e
发帖数: 2007 | 20 Min use dijkstra? You can stop the algorithm as soon as the target is out of
the heap. | | | l****o
发帖数: 43 | 21 mark, waiting for clarification | b***u
发帖数: 12010 | 22 longest path 不是npc么？
estimation.
the main concern.
【在 i*******e 的大作中提到】
: max connection = longest path?
: If so, how about this one? lg 100 based (10^9) = 4.5? Very rough estimation.
: So max connection = 5. Not tight bound, any other suggestion?
: For min connection, shorted path should work. Scalability is likely to be the main concern.
| g**u
发帖数: 504 | 23 If "longest path" means the diameter of the network, i.e., the largest one
of those shortest path between any pair of nodes, then we can calculate it
in O(mn), here m is the number of edges. Thus, it's O(n^2).
【在 b***u 的大作中提到】
: longest path 不是npc么？
:
: estimation.
: the main concern.
|
|
