Microsoft Interview Question
SDE-2sCountry: United States
this might not be optimal but it works.
take the first element from the partial order and take the projection onto the first coordinate (a, b) -> a. remember a.
continue through the list until you find (x, a), remember x. etc
after you've iterated through the whole set. repeat this process with x until the process doesn't change x. this gives you a minimal element (potentially the minimum).
add this to an array and remove x from the partial ordering (all elements of the form (x, .)). now repeat this process. until the partial ordering is empty.
For topological sort, you need you make sure you work on DAG. if there is any cycle, then there is no solution to this problem.
source = Identify vertex with no incoming edges.
Topological_Sort(source)
perform DFS, if you encounter already visited vertex and if parent is same, set visited parent to visiting vertex.
Do this untill you have no vertex to visit.
Will this work?
public static void topSort(Pair edges[]) throws Exception {
HashMap<Character, ArrayList<Character>> map = new HashMap<Character, ArrayList<Character>>();
for(int i = 0; i < edges.length; i++) {
Pair<Character, Character> edge = edges[i];
Character second = edge.getSecond();
ArrayList<Character> list = null;
list = map.get(edge.getFirst());
if(list == null)
map.put(edge.getFirst(), new ArrayList<Character>());
list = map.get(second);
if(list == null) {
list = new ArrayList<Character>();
map.put(second, list);
}
if(!list.contains(edge.getFirst())) {
list.add(edge.getFirst());
}
}
System.out.println(map.toString());
ValueComparator<Character> comp = new ValueComparator<Character>(map);
TreeMap<Character, ArrayList<Character>> treeMap = new TreeMap<Character, ArrayList<Character>>(comp);
treeMap.putAll(map);
System.out.println(treeMap.toString());
StringBuffer output = new StringBuffer();
for(Iterator<Character> i = treeMap.keySet().iterator(); i.hasNext(); ) {
output.append(i.next()).append(' ');
}
System.out.println("sort Order: " + output.toString());
}
private static class ValueComparator<Character> implements Comparator<Character> {
private Map<Character, ArrayList<Character>> map;
public ValueComparator(Map<Character, ArrayList<Character>> map) {
this.map = map;
}
public int compare(Character arg0, Character arg1) {
ArrayList first = map.get(arg0);
ArrayList second = map.get(arg1);
if(first.size() <= second.size())
return -1;
return 1;
}
}
Algorithm to find out the topological sorted array:
1. find out the source vertice. Let a[][2] stores the edges in the for of a pairs
a[][2] = {
(a,b)
(c,b)
(a,d)
(a,c)
(c,d)
(d,b)
}
First find out a unique id for each vertex and then for each id check whether any of those doesn't appear in 2nd place of the pair. That will be the source vertex (a vertex having only outgoing edges).
2. traverse the graph and find out the weights of all the vertices. To find out the weight add 1 to the weights of already visited vertices. Each edge will have a weight of 1. So
int calculateWeight()
{
weight(v) = 0;
for(each v1 which is predecessor vertex of v)
{
if (v1 has been visited)
{
weight(v) += (1+ weight(v1));
}
else
{
weight(v) += (1+calculateWeight(v1));
}
}
v.visited = true;
return weight(v);
}
3. traverse the graph doing a BFS and calculate weights of each vertex using calculateWeight function.
4. Sort the vertex as per their weights.
5. Print the id /name of each vertex which will print in topologically sorted order.
Here is the actual C++ code:
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <stdlib.h>
using namespace std;
struct Vertex
{
Vertex():
id(-1), name('\0'), weight(-1), visited(false)
{
}
int id;
char name;
int weight;
bool visited;
};
typedef
std::multimap<int, int>
edgeSet;
typedef edgeSet::iterator edgeIterator;
typedef std::map<char, int> vertex_to_id_map_t;
int findSourceVertexId(edgeSet& edges,
int totalVertices);
int calculateWeight(Vertex* source,
Vertex* vertex,
edgeSet& reverseEdges,
Vertex* vertices);
void traverseDagBFS(edgeSet& edges,
edgeSet& reverseEdges,
Vertex* sourceVertex,
Vertex* vertices);
void sortVerticesByWeight(Vertex * vertices,
int totalVertices);
void swap(Vertex& v1, Vertex& v2);
int main()
{
#if 0
char a[][2] = {
{'b','e'},
{'c','e'},
{'b','c'},
{'e','a'},
{'a','d'}
};
#endif
char a[][2] = {
{'a','b'},
{'a','c'},
{'a','d'},
{'c','b'},
{'c','d'},
{'d','b'}
};
vertex_to_id_map_t vertex_to_id_map;
int numEdges = sizeof(a)/sizeof(a[0]);
int id = 0;
for(int i=0;i<numEdges;++i)
{
if (vertex_to_id_map.find(a[i][0]) == vertex_to_id_map.end())
{
vertex_to_id_map.insert(std::make_pair(a[i][0], id++));
}
if (vertex_to_id_map.find(a[i][1]) == vertex_to_id_map.end())
{
vertex_to_id_map.insert(std::make_pair(a[i][1], id++));
}
}
int totalVertices = id;
Vertex* vertices = new Vertex[totalVertices];
std::map<char, int>::iterator iter = vertex_to_id_map.begin();
for(; iter != vertex_to_id_map.end(); ++iter)
{
vertices[iter->second].id = iter->second;
vertices[iter->second].name = iter->first;
cout<<"Vertex = "<<iter->first<<", id = "<<iter->second<<endl;
}
for(int i=0;i<totalVertices;++i)
{
cout<<"Vertex["<<i<<"] = (id,name,weight) = ("
<< vertices[i].id<<","
<< vertices[i].name<<","
<< vertices[i].weight<<")"<<endl;
}
edgeSet edges;
edgeSet reverseEdges;
for(int i=0;i<numEdges;++i)
{
int v1 = vertex_to_id_map[a[i][0]];
int v2 = vertex_to_id_map[a[i][1]];
edges.insert(std::make_pair(v1, v2
));
reverseEdges.insert(std::make_pair(v2,v1));
}
int sourceId = findSourceVertexId(edges, totalVertices);
if (sourceId == -1)
{
cout<<"Invalid source id -1"<<endl;
exit(1);
}
Vertex* sourceVertex = &vertices[sourceId];
traverseDagBFS(edges,
reverseEdges,
sourceVertex,
vertices);
sortVerticesByWeight(vertices, totalVertices);
cout<<"Topological sort is given below"<<endl;
for(int i=0;i<totalVertices;++i)
{
cout<<"("<<vertices[i].name<<","<<vertices[i].weight<<")"<<endl;
}
return 0;
}
void traverseDagBFS(edgeSet& edges,
edgeSet& reverseEdges,
Vertex* sourceVertex,
Vertex* vertices)
{
std::queue<Vertex*> vertexQueue;
vertexQueue.push(sourceVertex);
while(!vertexQueue.empty())
{
Vertex* vertex = vertexQueue.front();
vertexQueue.pop();
if (!vertex->visited)
{
calculateWeight(sourceVertex, vertex, reverseEdges, vertices);
}
if (edges.count(vertex->id) > 0)
{
pair<edgeIterator, edgeIterator> p
= edges.equal_range(vertex->id);
for(edgeIterator it = p.first;
it != p.second;++it)
{
vertexQueue.push(&vertices[it->second]);
}
}
}
}
int calculateWeight(Vertex* source,
Vertex* vertex,
edgeSet& reverseEdges,
Vertex* vertices)
{
if (vertex == source)
{
source->weight = 0;
source->visited = true;
return source->weight;
}
else
{
int weight = 0;
if (reverseEdges.count(vertex->id) > 0)
{
pair<edgeIterator,edgeIterator> p
= reverseEdges.equal_range(vertex->id);
for(edgeIterator it = p.first;
it != p.second;
++it)
{
Vertex* predVertex = &vertices[it->second];
if (predVertex->visited)
{
weight += (1 + predVertex->weight);
}
else
{
weight += (1 + calculateWeight(source,
predVertex,
reverseEdges, vertices));
}
}
}
vertex->visited = true;
vertex->weight = weight;
return vertex->weight;
}
}
int findSourceVertexId(edgeSet& edges,
int totalVertices)
{
int* notSource = new int[totalVertices];
for(int i=0;i<totalVertices;++i)
{
notSource[i] = 0;
}
for(edgeIterator citer = edges.begin();
citer != edges.end();
++citer)
{
notSource[citer->second] = 1;
}
for(int i=0;i<totalVertices;++i)
{
if (!notSource[i])
{
delete[] notSource;
return i;
}
}
delete[] notSource;
return -1;
}
void sortVerticesByWeight(Vertex * vertices,
int totalVertices)
{
for(int i=0;i<totalVertices;++i)
{
bool swapped = false;
for(int j = totalVertices-1; j>i; --j)
{
if (vertices[j].weight < vertices[j-1].weight)
{
swap(vertices[j], vertices[j-1]);
swapped = true;
}
}
if (!swapped)
break;
}
}
void swap(Vertex& v1, Vertex& v2)
{
Vertex temp = v1;
v1 = v2;
v2 = temp;
}
Let the given sets of pair are {(b,e),(c,e),(b,c),(e,a),(a,d)}
- Ravi May 06, 2014step 1 : we count the no. of distinct characters in the set , here it is 5 {a,b,c,d,e}
step 2: take an array A of size 5 i.e char A[5]={'a','b','c','d','e'}
step3: take a matrix of size 5*5 i.e int M[5][5];
step 4: treat M like adjacency matrix , if (b,e) is a pair than put 1 in row no 1 and column no 4 of matrix , do this for every pair rest of elements of matrix should be zero
a b c d e
step 5: a 0 0 0 1 0
b 0 0 1 0 1
c 0 0 0 0 1
d 0 0 0 0 0
e 1 0 0 0 0
M should be look like above
step 6 : if there is 1 in lower tranguler part of matrix than swap the rows than swap the column, here (e,a) is 1 so swap the row no e and row no a after that swap the column no e and column no a, similarly swap the element A[0] and A[4] i.e a and e .
e b c d a
e 0 0 0 0 1
b 1 0 1 0 0
c 1 0 0 0 0
d 0 0 0 0 0
a 0 0 0 1 0
we repeat this process unless there is no 1 in lower tranguler matrix.
step 7: (b,e) is 1 i.e. row no 1 and col no 0 so swap row no 1 with row no 0 and col no 1 with col no 0 .we will get the matrix as
b e c d a
b 0 1 1 0 0
e 0 0 0 0 1
c 0 1 0 0 0
d 0 0 0 0 0
a 0 0 0 1 0
Step 8 : now (c,e) is 1 so swap row c and e (i.e row 2 and row 1) after that swap column 2 and column 1. M will look like
b c e d a
b 0 1 1 0 0
c 0 0 1 0 0
e 0 0 0 0 1
d 0 0 0 0 0
a 0 0 0 1 0
Step 9 : now (a,d) is 1 so swap row a and d after that swap column a and d.
M will be look like
b c e a d
b 0 1 1 0 0
c 0 0 1 0 0
e 0 0 0 1 0
a 0 0 0 0 1
d 0 0 0 0 0
now there is no 1 in lower tranguler matrix so the content of Array A= {b,c,e,a,d} is our solution.