Adobe Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Is the graph Undirected (i.e., adj matrix is symmetric) ?
Maybe we can treat the 0's as edges and invoke regular maximal clique algorithm (which treat's 0's as edges and 1's as nonedges).
Can this be done in greedy approach?
Step 1) Maintain an array of vertices with number of edges incident.
and thus the asnwer consist of all the vertices.
Step 2) Remove the vertex with maximum number of edges incident.
Step 3) Update the array
Step 4) Keep on repeating step 2 and step 3 untill we reach to a stage where the remaing vertices has no edge incident. The remaining vertices are the answer.
People do not answer to his question. He is posting problems from on going codding competitions. Codechef MARCH14/problems/GERALD07.
- Anonymous March 10, 2014