Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
I think the questions allows a node to be related to any no of nodes..so loops may occur and hence BFS is not the right way.
Do correct me if i am wrong.
I do not think the loop will be a problem here since we do not search for all level friends. We have a limit to level 3 so even if there is a loop it will loop only once and won't be a big deal.
I think the 3rd degree of connection was just used as an example. The algorithm should work for larger inputs too. See my response to careercup DOT com / question?id=14087784 for an algorithm that's considerably more efficient than BFS.
BFS can be done on a graph that has loops. Just keep track of nodes that you visited before.
Eugene, in your other posts i didn't understand why the algorithm is faster if you search from both the sides. Isn't it still traversing the same tree + additional effort to find the intersection.
@dc360: no, it's not traversing the tree in the same way. Copy and pasting from my other post:
"Think about it this way. If you wanted to find whether two people share a mutual friend, would you 1) do a set intersection on the two people's sets of friends or 2) find all of A's friends, find all the friends of each such friend, and check whether B is in this giant set? Choice 1 is much better."
I think BFS will work since this problem sounds like the shortest path question, and since the length is unit length (i.e., all same weight), Dijkstra's can simply became a BFS. Correct me if I'm wrong.
BFS will work. That doesn't mean it's optimal. The algorithm I'm discussing runs in roughly the square root of the time of BFS.
Eugene is right. Suppose everyone has K friends, that is each node has a degree of K. If the distance between A and B is d, then we have to traverse O(K^d) nodes if we use the traditional BFS traversal. But if we expand the nodes from both sides, then the distance between A and B will halve, so the optimal time is O(K^(d/2)) = O(sqrt(K^d)).
we can apply flyod warshall algorithm ? as it gives min distance between each and every node ?
/*
* File: main.cpp
* Author: vsirohi
*
* Created on August 27, 2012, 5:39 PM
*/
#include <cstdlib>
#include<iostream>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
struct Node {
string Uname;
Node * next;
Node(string );
};
Node::Node(string s1){
Uname= s1;
next = NULL;
}
map<string, Node *> Graph;
void setgraph()
{
Node * node1= new Node("u2");
node1->next = new Node("u4");
Node *node2 = new Node("u1");
node2->next = new Node("u3");
Node *node3 = new Node("u2");
node3->next = new Node("u4");
node3->next->next = new Node("u5");
Node *node4 = new Node("u1");
node4->next =new Node("u3");
Node* node5 = new Node("u3");
Graph["u1"] = node1;
Graph["u2"] = node2;
Graph["u3"] = node3;
Graph["u4"] = node4;
Graph["u4"] = node5;
}
Node * getnode(string s1)
{
return Graph[s1];
}
int getDegree(string s1, string s2)
{
int degree = 1;
queue<string> qu;
vector<string> visited;
qu.push(s1);
visited.push_back(s1);
string noUserLeftAtLevel = "<br>";
qu.push(noUserLeftAtLevel);
while(!qu.empty())
{
string nextFriend = qu.front();
qu.pop();
Node * friendList = getnode(nextFriend);
while(friendList!=NULL)
{
vector<string>::iterator it;
it = visited.begin();
if(find(visited.begin(), visited.end(), friendList->Uname)==visited.end())
{
qu.push(friendList->Uname);
visited.push_back(friendList->Uname);
}
if(friendList->Uname==s2)
{
return degree;
}
friendList = friendList->next;
}
if(qu.front()== noUserLeftAtLevel)
{
qu.pop();
qu.push(noUserLeftAtLevel);
degree++;
}
}
return -1;
}
/*
*
*/
int main(int argc, char** argv) {
setgraph();
int degree;
degree = getDegree("u1", "u5");
cout<<" The degree is "<<degree<<endl;
return 0;
}
The 3rd level degree will look like user1-->user2-->user3-->user4. Lets say on average each user has N(on average N would be less than 1000) friends(just to make it more visible). So if we do simple BFS we go O(N^level) --> in our case we need 3rd level so O(n^3) .
We can make it a bit faster to O(n^ceil(level/2)) here by using O(n^floor(level / 2)) space --> in our case O(n^2) time and O(n) space.
Simple idea here is to start BFS from both ends and meet in the middle. In our case:
1.) we start traversing from user1 in depth cail(3/2) = 2
2.) and from user4 in depth floor(3/2) = 1.
So from 2.) we can hash friends of user4 = O(n) space and check for a matching the user found from 1.) in O(n^2)
This approach will work fine up to level 6 where we can improve O(n^6) to O(n^3) time and space. If it goes higher I think will not be a good idea if we use simple hashing.
Yes. This question has been asked on CareerCup before, and I explained the advantages of this approach. See my post in:
careercup DOT com / question?id=14087784
suppose there are N user, MatrixM of N*N represet the relationship of user(M[i][j] is 1 means user i & user j are friend, M[i][j] is 0 means they are not direct friend but they may be mutual friend) hence to find the degree of connection of user, we have to find the shortest path from userI to userJ using shortest path alorithm
suppose there are N user, MatrixM of N*N represet the relationship of user(M[i][j] is 1 means user i & user j are friend, M[i][j] is 0 means they are not direct friend but they may be mutual friend) hence to find the degree of connection of user, we have to find the shortest path from userI to userJ using shortest path alorithm
Use BFS.
- Anonymous August 09, 2012