y****3
发帖数: 825 | 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***s
发帖数: 487 | 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*******s
发帖数: 182 | 3 This is a graph question. Use BFS. | h****n
发帖数: 1093 | 4 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]);
}
}
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****0
发帖数: 2 | | y****3
发帖数: 825 | 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**********5
发帖数: 7881 | 7 有一次去中国公司面试， 被问到这题， 我说就是connected component， DFS， BFS
， union find 都可以
然后面试元， 一个猥琐男， 就是死活不让我写， 说union find 太复杂， 你能30分
钟写完啊， 我说可以啊
然后他还是死活不让我写， 说你这个太复杂。。 再想想。。
I AM NOT MAKING THIS SHIT UP!!!! |
|
