Microsoft Interview Question for SDE-2s


Country: United States




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

Let the given sets of pair are {(b,e),(c,e),(b,c),(e,a),(a,d)}
step 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.

- Ravi May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- jbweimar May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- AlgoAlgae May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

		
	}

- Noobie May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

(a,b)
(c,b)
(a,d)
(a,c)
(c,d)
(d,b)



The tree map should have this for above input.

a
c a
d a,c
b a,c,d

- noobie May 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Won't work if two vertices have same number of predecessors. Need to find distance from root node.

- K May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jeetscoder August 10, 2015 | 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