Adobe Interview Question
Software Development ManagersCountry: United States
Interview Type: In-Person
All you need it is to check that each column in adjacency matrix has exactly one non zero element.
@justhack4fun688
If you say that degree of node is 1, it means that there will be only 1 edge on that node, but in your example, there will be 3 edges on each node.
By your given definition of perfect matching, there should be 1 edge only.
glebstepanov1992 is right. But @glebstepanov1992: graph is not given in form of adjacency matrix and we dont need to create a adjacency matrix.
perfectMatch(vector<int>V, vector< pair<int,int> E>)
1) create map<int, bool>
2) For each vector element, add entry into map and make is false.
3) for each edge, check if incident node of edge are marked false in map if yes then mark them true. If any of them is marked true, then there is no perfect match.
4) If all edges pass successfully, then we will check map, if there is any node which is false, if yes then again there is no perfect match. As this node has 0 incident edge.
5) If we reach here there is a perfect match
void perfectmatch (vector<int> V, vector< pair<int,int> > E)
{
vector<int>::iterator vit;
map<int, bool> vmap;
for (vit=V.begin(); vit!=V.end(); vit++)
{
vmap[*vit] = false;
}
vector< pair<int,int> >::iterator pairit;
for (pairit=E.begin(); pairit!=E.end(); pairit++)
{
int first = pairit->first;
int second = pairit->second;
cout << "pair: " << first << " " << second << endl;
if (vmap[first] == false)
{
vmap[first] = true;
}
else
{
cout << "Not A Perfect Match: Culprit Edge " << pairit->first << "," << pairit->second << endl;
vmap.clear();
return;
}
if (vmap[second] == false)
{
vmap[second] = true;
}
else
{
cout << "Not A Perfect Match: Culprit Edge " << pairit->first << "," << pairit->second << endl;
vmap.clear();
return;
}
}
map<int, bool>::iterator mapit;
for (mapit=vmap.begin(); mapit!=vmap.end(); mapit++)
{
if (mapit->second == false)
{
cout << "Not A Perfect Match: Culprit Vetex:" << mapit->first << endl;
return;
}
}
cout << "Perfect Match" << endl;
}
@saurabh So finding perfect matching itself means that can we delete some edges from our given graph so that each node has degree 1.I need to find this in short
If all vertices are supposed to be of degree "1", then you must have exactly "n_vertices / 2" edges. That is the first thing to check.
Then, prepare an array of boolean for the vertices checked. Read through all edges and for each edge, mark off two vertices. If a vertex has already been marked off, return false.
Otherwise, return true.
Main Algorithm:
Code to test three graphs:
Output:
- Ehsan January 04, 2014