Adobe Interview Question for Software Development Managers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

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:

#pragma once
#include "Problem.h"
#include <list>
#include <iostream> 
using namespace std;

class Edge
{
public:
	int vertex_1, vertex_2;
	Edge(int v1, int v2) : vertex_1(v1), vertex_2(v2)
	{
	}
	Edge() : vertex_1(0), vertex_2(0)
	{
	}

};

class PerfectMatch :
	public Problem
{
public:
	static const int FALSE_INCORRECT_EDGE_NUMBER = -1;
	static const int FALSE_NOT_PERFECTLY_MATCHED = -2;
	static const int TRUE_PERFECT_MATCH = 0;
	static const int FALSE_INCORRECT_VERTEX_NUMBER = -3;
	static const int FALSE_UNMATCHED_VERTICES = -4;

	PerfectMatch() : vertices(0), edges(0)
	{
	}

	~PerfectMatch()
	{
	}
	/** Solving the problem */
	void SetGraph(list<int>* vertices_, list<Edge>* edges_)
	{
		vertices = vertices_;
		edges = edges_;
	}
	int Solve() 
	{
		int n_vertices = vertices->size();
		int n_edges = edges->size();
		// If it is a perfect match, then we should have two vertices per edge
		if ((n_edges << 1) != n_vertices)
			return FALSE_INCORRECT_EDGE_NUMBER;
		if (n_vertices % 2 == 1)
			return FALSE_INCORRECT_VERTEX_NUMBER;

		bool* encountered = new bool[n_vertices];
		for (int i = 0; i < n_vertices; i++) encountered[i] = false;
		int counted_vetices = 0;
		for (const auto& e : *edges) 
		{			
			if (encountered[e.vertex_1] || encountered[e.vertex_2])
				return FALSE_NOT_PERFECTLY_MATCHED;			
			encountered[e.vertex_1] = true;
			encountered[e.vertex_2] = true;
			counted_vetices += 2;
		}
		delete[] encountered;
		if (counted_vetices != n_vertices)
			return FALSE_UNMATCHED_VERTICES;
		return TRUE_PERFECT_MATCH;
	}

	void Result()
	{
		int result = Solve();
		switch (result)
		{
		case TRUE_PERFECT_MATCH:
			cout << "Perfect Match!" << endl;
			break;
		default:
			cout << "Not a Perfect Match!" << endl;
		}
	}
	
	list<int>* vertices;
	list<Edge>* edges;
};

Code to test three graphs:

#include "PerfectMatch.h"
#include <set>
#include <list>
using namespace std;

int main(int argc, _TCHAR* argv[])
{
	list<int> vertices{ { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } };
	list<Edge> edges{ { Edge(0, 1), Edge(2, 3), Edge(4, 5), Edge(6, 7), Edge(8, 9) } };
	list<Edge> bad_edges{ { Edge(0, 1), Edge(2, 3), Edge(2, 1), Edge(6, 7), Edge(8, 9) } };
	list<Edge> insuff_edges{ { Edge(0, 1), Edge(2, 3) } };
	PerfectMatch pf;
	pf.SetGraph(&vertices, &edges);
	pf.Result();
	pf.SetGraph(&vertices, &bad_edges);
	pf.Result();
	pf.SetGraph(&vertices, &insuff_edges);
	pf.Result();
	fgetc(stdin);
}

Output:

Perfect Match!
Not a Perfect Match!
Not a Perfect Match!

- Ehsan January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ehsan Their can be multiple edges also in the graph and initially graph need not have all vertices with degree 1.I need to tell can their be perfect matching in a graph after removal of some of its edges.

- justhack4fun688 January 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

a question from an online coding competition....wth

- kira January 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Which one? Reference please

- godzilla January 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Another question from running codding competition:
codechef.com/JAN14/problems/SEAGRP
Someone is cheating.

- Anonymous January 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

All you need it is to check that each column in adjacency matrix has exactly one non zero element.

- glebstepanov1992 January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you are wrong.Consider the undirected graph with 4 vertices and 6 edges say (1,2),(1,3),(1,4),(2,3),(2,4),(3,4) .According to u it dont haveperfect matching.But in actual it has.

- justhack4fun688 January 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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

- SK January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- SK January 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- justhack4fun688 January 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@justhack4fun688: So question is like: Given a graph G, is it possible to get a perfect matching out of this Graph?
Did I get the question right?

- SK January 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Try Hopcraft or edmonds Maximum matching Algorithm to get the maximum matching and then check whether that matching is perfect

- NoobCoder January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think by "perfect matching" you mean "bipartite matching" ? If no then degree of "1" does not make sense.

- godzilla January 04, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More