Amazon Interview Question
Country: Singapore
// ZoomBA
emp_list = [ "Mc Grill,Mc,Grill,Karmon",
"Karmon,Zech,Karmon,Joe","Mithun,Try,Mithun,Joe",
"Joe,Top,Joe,","Zara,Aman,Zara,Mc Grill",
"Fizzy,Dude,Fizzy,Mc Grill" ]
def create_node( string ){
fields = string.split( ',' ,-1)
{ 'id' : fields[0] , 'fname' : fields[1] ,
'lname' : fields[2] , 'mgr' : fields[3] , 'children' : set() }
}
def print_node( node_id ){
node = nodes[node_id]
printf( '%s %s\n', node.fname, node.lname )
for ( node.children ){
print_node ($)
}
}
nodes = dict ( emp_list ) -> {
e = create_node( $.o )
[ e.id , e ]
}
root = lfold(nodes, '' ) ->{
node = $.o.value
continue ( empty(node.mgr) ){ $.p = node.id }
parent = nodes[node.mgr]
parent.children += node.id
$.p
}
print_node( root )
@Megha Maheshwari A little clarification is required. Is the goal to print all "First Name, Last Name" of employees, having people with most reports at the bottom?
You need to print the information in the order of reporting...like the guy who has no report to is the top level guy and so he comes first, than there are two guys who report to the top level guy...so they come at the second level and so on. The number to be printed must be as per their level ...I would assume its a case of Breadth First Traversal...what is your opinion?
This is a graph problem which needs topological sorting. Here is the logic:
1. Build a graph by reading each element in the array. Add an edge between reports_to and employee node.
2. If the reports_to field is blank then mark that vertex as the Start vertex
3. Perform a topological search starting with the Start vertex and store the information in an array of lists
4. Print the array of list. Each list in array represents one level.
This is a graph problem which needs topological sorting. Here is the logic:
1. Build a graph by reading each element in the array. Add an edge between reports_to and employee node.
2. If the reports_to field is blank then mark that vertex as the Start vertex
3. Perform a topological search starting with the Start vertex and store the information in an array of lists
4. Print the array of list. Each list in array represents one level.
Here is the c# code:
class Vertex
{
public string Name;
public List<Vertex> ConnectedTo;
public bool Visited;
public string FirstName;
public string LastName;
public Vertex(string VName)
{
Name = VName;
ConnectedTo = new List<Vertex>();
Visited = false;
}
}
public class Graph
{
Dictionary<string, Vertex> AllVertices = new Dictionary<string,Vertex>();
Vertex StartVertex;
void BuildGraph()
{
string[] Values = new[] { "Mc Grill,Mc,Grill,Karmon", "Karmon,Zech,Karmon,Joe", "Mithun,Try,Mithun,Joe", "Joe,Top,Joe,", "Zara,Aman,Zara,Mc Grill", "Fizzy,Dude,Fizzy,Mc Grill" };
for (int i = 0; i < Values.Length; i++)
{
string[] Info = Values[i].Split(',');
Vertex fromV, toV;
if(Info[3].Trim() == "")
{
if (AllVertices.ContainsKey(Info[0]))
toV = AllVertices[Info[0]];
else
{
toV = new Vertex(Info[0]);
AllVertices.Add(Info[0], toV);
}
toV.FirstName = Info[1];
toV.LastName = Info[2];
StartVertex = toV;
continue;
}
if (AllVertices.ContainsKey(Info[0]))
{
fromV = AllVertices[Info[0]];
}
else
{
fromV = new Vertex(Info[0]);
AllVertices.Add(Info[0], fromV);
}
fromV.FirstName = Info[1];
fromV.LastName = Info[2];
if (AllVertices.ContainsKey(Info[3]))
toV = AllVertices[Info[3]];
else
{
toV = new Vertex(Info[0]);
AllVertices.Add(Info[3], toV);
}
toV.ConnectedTo.Add(fromV);
}
}
void TopologicalSortUtil(Vertex V, List<Vertex>[] stkVertex, int Level)
{
V.Visited = true;
foreach (Vertex neighbour in V.ConnectedTo)
{
if (!neighbour.Visited)
TopologicalSortUtil(neighbour, stkVertex, Level+1);
}
if (stkVertex[Level] != null)
stkVertex[Level].Add(V);
else
stkVertex[Level] = new List<Vertex>() { V };
}
void TopologicalSort()
{
List<Vertex>[] stkVertex = new List<Vertex>[5];
TopologicalSortUtil(StartVertex, stkVertex, 0);
for (int i = 0; i < stkVertex.Length; i++ )
{
if (stkVertex[i] != null)
{
foreach (Vertex V in stkVertex[i])
{
Console.WriteLine(i + 1 + ") " + V.FirstName + " " + V.LastName);
}
}
}
}
public Graph()
{
BuildGraph();
TopologicalSort();
}
}
This is a graph problem which needs topological sorting. Here is the logic:
1. Build a graph by reading each element in the array. Add an edge between reports_to and employee node.
2. If the reports_to field is blank then mark that vertex as the Start vertex
3. Perform a topological search starting with the Start vertex and store the information in an array of lists
4. Print the array of list. Each list in array represents one level.
This is a graph problem which needs topological sorting. Here is the logic:
1. Build a graph by reading each element in the array. Add an edge between reports_to and employee node.
2. If the reports_to field is blank then mark that vertex as the Start vertex
3. Perform a topological search starting with the Start vertex and store the information in an array of lists
4. Print the array of list. Each list in array represents one level.
This is a graph problem which needs topological sorting. Here is the logic:
1. Build a graph by reading each element in the array. Add an edge between reports_to and employee node.
2. If the reports_to field is blank then mark that vertex as the Start vertex
3. Perform a topological search starting with the Start vertex and store the information in an array of lists
4. Print the array of list. Each list in array represents one level.
This is a graph problem which needs topological sort. Here is the logic:
- baks November 19, 20151. Build your graph by reading each element in the array. Add an edge between Report_to to the employee
2. Mark the vertex as start vertex if the report_to field is blank
3. Start topological search from start vertex and store each level information in an array of lists
4. Print the array of lists where list at each index of the array is one level
Here is the c# code for this
class Vertex
{
public string Name;
public List<Vertex> ConnectedTo;
public bool Visited;
public string FirstName;
public string LastName;
public Vertex(string VName)
{
Name = VName;
ConnectedTo = new List<Vertex>();
Visited = false;
}
}
public class Graph
{
Dictionary<string, Vertex> AllVertices = new Dictionary<string,Vertex>();
Vertex StartVertex;
void BuildGraph()
{
string[] Values = new[] { "Mc Grill,Mc,Grill,Karmon", "Karmon,Zech,Karmon,Joe", "Mithun,Try,Mithun,Joe", "Joe,Top,Joe,", "Zara,Aman,Zara,Mc Grill", "Fizzy,Dude,Fizzy,Mc Grill" };
for (int i = 0; i < Values.Length; i++)
{
string[] Info = Values[i].Split(',');
Vertex fromV, toV;
if(Info[3].Trim() == "")
{
if (AllVertices.ContainsKey(Info[0]))
toV = AllVertices[Info[0]];
else
{
toV = new Vertex(Info[0]);
AllVertices.Add(Info[0], toV);
}
toV.FirstName = Info[1];
toV.LastName = Info[2];
StartVertex = toV;
continue;
}
if (AllVertices.ContainsKey(Info[0]))
{
fromV = AllVertices[Info[0]];
}
else
{
fromV = new Vertex(Info[0]);
AllVertices.Add(Info[0], fromV);
}
fromV.FirstName = Info[1];
fromV.LastName = Info[2];
if (AllVertices.ContainsKey(Info[3]))
toV = AllVertices[Info[3]];
else
{
toV = new Vertex(Info[0]);
AllVertices.Add(Info[3], toV);
}
toV.ConnectedTo.Add(fromV);
}
}
void TopologicalSortUtil(Vertex V, List<Vertex>[] stkVertex, int Level)
{
V.Visited = true;
foreach (Vertex neighbour in V.ConnectedTo)
{
if (!neighbour.Visited)
TopologicalSortUtil(neighbour, stkVertex, Level+1);
}
if (stkVertex[Level] != null)
stkVertex[Level].Add(V);
else
stkVertex[Level] = new List<Vertex>() { V };
}
void TopologicalSort()
{
List<Vertex>[] stkVertex = new List<Vertex>[5];
TopologicalSortUtil(StartVertex, stkVertex, 0);
for (int i = 0; i < stkVertex.Length; i++ )
{
if (stkVertex[i] != null)
{
foreach (Vertex V in stkVertex[i])
{
Console.WriteLine(i + 1 + ") " + V.FirstName + " " + V.LastName);
}
}
}
}
public Graph()
{
BuildGraph();
TopologicalSort();
}
}