How to find unique IP address from the following IP list? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

How to find unique IP address from the following IP list?

How to find unique IP address from the following IP list?# JobHunting - 待字闺中

y*32016-05-23 07:05

1 楼

IP1=IP2,
IP3=IP2,
IP4=IP3,
IP5=IP6.
Unique IP should be IP1 and IP5. This is from Microsoft.
How to use hash table solve this problem by C/C++?

q*s2016-05-23 07:05

2 楼

not sure about how to use hashtable for it. try this:
1, set id of ip1 to ip6, addres:{1,2,3,4,5,6}
2, loop through the list, if (ip_a == ip_b) address[ip_b] = address[ip_a]
e.g. got {1,1,1,1,5,5} in the end
3, count the distinct numbers, that is 2 in this case.

f*s2016-05-23 07:05

3 楼

This is a graph question. Use BFS.

h*n2016-05-23 07:05

4 楼

void dfs(unordered_map>& graph, unordered_mapint>& visit, string ip)
{
visit[ip] = 1;
for(int i = 0; i < graph[ip].size(); i++)
{
if(visit[graph[ip][i]] == 0)
{
dfs(graph, visit, graph[ip][i]);
}
}
visit[ip] = 2;
}
vector get_unique_ips(vector ip_pairs)
{
unordered_map> graph;
unordered_map>::iterator it;
unordered_map visit;
vector res;
for(int i = 0; i < ip_pairs.size(); i++)
{
string ip_1 = ip_pairs[i].substr(0, ip_pairs[i].find("=="));
string ip_2 = ip_pairs[i].substr(ip_pairs[i].find("==") + 2);
graph[ip_1].push_back(ip_2);
graph[ip_2].push_back(ip_1);
}

for(it = graph.begin(); it != graph.end(); it++)
{
visit[it->first] = 0;
}
for(it = graph.begin(); it != graph.end(); it++)
{
if(visit[it->first]==0)
{
dfs(graph, visit, it->first);
res.push_back(it->first);
}
}
return res;
}
int main()
{
vector ip_pairs;
ip_pairs.push_back("IP1==IP2");
ip_pairs.push_back("IP3==IP2");
ip_pairs.push_back("IP4==IP3");
ip_pairs.push_back("IP5==IP6");
get_unique_ips(ip_pairs);
return 0;
}

【在 y****3 的大作中提到】

: IP1=IP2,
: IP3=IP2,
: IP4=IP3,
: IP5=IP6.
: Unique IP should be IP1 and IP5. This is from Microsoft.
: How to use hash table solve this problem by C/C++?

z*02016-05-23 07:05

5 楼

union find也行吧

y*32016-05-23 07:05

6 楼

Thx. It is cool to use temporary/permanent mark in this way.
Just read someone provide Python code based on Hash map, but don't
understand it at all...

string,

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

: void dfs(unordered_map>& graph, unordered_map: int>& visit, string ip)
: {
: visit[ip] = 1;
: for(int i = 0; i < graph[ip].size(); i++)
: {
: if(visit[graph[ip][i]] == 0)
: {
: dfs(graph, visit, graph[ip][i]);
: }

b*52016-05-23 07:05

7 楼

有一次去中国公司面试，被问到这题，我说就是connected component， DFS， BFS
， union find 都可以
然后面试元，一个猥琐男，就是死活不让我写，说union find 太复杂，你能30分
钟写完啊，我说可以啊
然后他还是死活不让我写，说你这个太复杂。。再想想。。
I AM NOT MAKING THIS SHIT UP!!!!