Amazon Interview Question Software Engineer / Developers
Associate or create a class for storing Distributor Center info
Lets call it DistCenter
Class called Edges
{
DistCenter1
DistCenter2
Weight
}
Hashtable indexed by the DistCenter
To store the graph
Create distCenter objects for each distribution center
For each DstCenter object A
Create a HashTable to store Edge objects
If there is an edge from this DistCenter to some other DistCenter B
Create the Edge object
initialize it with weight and the DistCenterObject references/pointers
Add the edge object to the Hashtable or map using DistCenter B as the Key
When done with all edges
Add the DistCenter,Edge Hashtable pair to the HashTable/ HashMap
How to calculate if there is a path or not
Below function will return the list of edges that contains the path information and weight and can be used to print the path with weights
It will return null if there is no path
List of Edges FindPath(DistCenter A ,DistCenter B)
{
Get List of Edges from HashTable for DistCenter A
if (List empty )
return null
else
return findCenter(List Of edges from DistCenter A, DistCenter B)
}
List of Edge findDistCenter(Hashtable of Edges, DistCenter B)
{
edge = HashTable of edges . get (DistCenter B)
if (edge != null )
return new edgeList .Add (edge)
else
for iterate for each edge in hashtable
do
HashTable edges= HashTable of distCenter .get (edge.DistCenter B)
edgeList = findDistCenter(edgeList,DistCenter B)
if (edgeList != null )
return edgeList.Add(iterator.edge)
done
return null
}
Can you explain why a Hash Table is better when we can use depth first search in the graph?
I think we can maintain the graph has an adjacency list. each entry in the adjacency list will have the reference to the node to which an edge exist and also the weight.
Example:
Struct Node{
Node *node;
int weight;
}
so each vertex will have the set of nodes to which it has an edge.
To perform a DFS on the entire graph would take O(m+n) then and you could still identify the path and the total weight of the path.
Do a depth-first search starting at node A and ending at node B.
- Jack February 24, 2006