Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Traverse the nodes in a BFS manner while maintaining a set of visited nodes.
If at any point we encounter a node that has already been visited, the tree is a graph.
class Node<T> {
T val;
List<Node> childNodes;
}
public boolean isGraph( Node<T> n){
if(n == null || n.getChildren() == null){
return false;
}
Queue<Node<T>> nodes = new LinkedList<>();
Set<Node<T>> visitedNodes = new HashSet<>();
nodes.add(n);
visitedNodes.add(n);
Node curr = null;
while(!nodes.isEmpty()){
curr = visitedNodes.remove();
if(curr.getChildren() != null){
for(Node<T> child : curr.getChildren()){
if(visitedNodes.contains(child){
return true;
}else {
visitedNodes.add(child);
nodes.add(child);
}
}
}
}
return false;
}
Assuming you are given all nodes and their immidate decendents, you can just keep track of the parent for each node and check if any node has more than one parent...
class Node
{
public int NodeId {get;set}
public Node[] Decendents {get;set}
}
bool IsGraph(Node[] allNodes)
{
Node[] parent = new Node[allNodes.Length];
for(int i=0;i < allNodes.Length; i++)
{
Node p = allNodes[i];
foreach(Node descNode in p.Decendents)
{
int descIndex = FindNodeIndex(descNode, allNodes);
if(parent[descIndex] == null)
{
parent[descIndex] = p;
}
else
{
//if we reached here, it means a node has multiple parents - so its a graph
return true;
}
}
}
return false;
}
int FindNodeIndex(Node descNode, Node[] allNodes)
{
int idx = -1;
foreach(Node n in allNodes)
{
if(n.NodeId == descNode.NodeId)
{
idx = n.NodeId;
break;
}
}
return idx;
}
Assuming you are given all nodes and their immidate decendents, you can just keep track of the parent for each node and check if any node has more than one parent...
class Node
{
public int NodeId {get;set}
public Node[] Decendents {get;set}
}
bool IsGraph(Node[] allNodes)
{
Node[] parent = new Node[allNodes.Length];
for(int i=0;i < allNodes.Length; i++)
{
Node p = allNodes[i];
foreach(Node descNode in p.Decendents)
{
int descIndex = FindNodeIndex(descNode, allNodes);
if(parent[descIndex] == null)
{
parent[descIndex] = p;
}
else
{
//if we reached here, it means a node has multiple parents - so its a graph
return true;
}
}
}
return false;
}
int FindNodeIndex(Node descNode, Node[] allNodes)
{
int idx = -1;
foreach(Node n in allNodes)
{
if(n.NodeId == descNode.NodeId)
{
idx = n.NodeId;
break;
}
}
return idx;
}
Assuming you are given all nodes and their immidate decendents, you can just keep track of the parent for each node and check if any node has more than one parent...
class Node
{
public int NodeId {get;set}
public Node[] Decendents {get;set}
}
bool IsGraph(Node[] allNodes)
{
Node[] parent = new Node[allNodes.Length];
for(int i=0;i < allNodes.Length; i++)
{
Node p = allNodes[i];
foreach(Node descNode in p.Decendents)
{
int descIndex = FindNodeIndex(descNode, allNodes);
if(parent[descIndex] == null)
{
parent[descIndex] = p;
}
else
{
//if we reached here, it means a node has multiple parents - so its a graph
return true;
}
}
}
return false;
}
int FindNodeIndex(Node descNode, Node[] allNodes)
{
int idx = -1;
foreach(Node n in allNodes)
{
if(n.NodeId == descNode.NodeId)
{
idx = n.NodeId;
break;
}
}
return idx;
}
Assuming you are given all nodes and their immidate decendents, you can just keep track of the parent for each node and check if any node has more than one parent...
class Node
{
public int NodeId {get;set}
public Node[] Decendents {get;set}
}
bool IsGraph(Node[] allNodes)
{
Node[] parent = new Node[allNodes.Length];
for(int i=0;i < allNodes.Length; i++)
{
Node p = allNodes[i];
foreach(Node descNode in p.Decendents)
{
int descIndex = FindNodeIndex(descNode, allNodes);
if(parent[descIndex] == null)
{
parent[descIndex] = p;
}
else
{
//if we reached here, it means a node has multiple parents - so its a graph
return true;
}
}
}
return false;
}
int FindNodeIndex(Node descNode, Node[] allNodes)
{
int idx = -1;
foreach(Node n in allNodes)
{
if(n.NodeId == descNode.NodeId)
{
idx = n.NodeId;
break;
}
}
return idx;
}
This can be checked using BFS algorithm only.
It can be checked in tow ways, one checking the parent count for each node in a graph. In case of tree parent count for each node should not be more than one. Any node having more than one parent will determine it is a graph not tree.
Other way is checking the total number of times all the nodes in a graph has been checked . In case of tree it should not be more than twice of number of vertices.
// Iterative approach , Time complexity O(V+E)
bool Graph::BSF( int startVertex)
{
bool *enqueuedNodeList = new bool[numberOfVertices];
// Default set all vertices as 0
for ( int index = 0; index<numberOfVertices; index++ )
{
enqueuedNodeList[index] = 0;
}
queue<int> Q;
Q.push(startVertex);
enqueuedNodeList[startVertex] = 1; // Because first eelemnt has been pushed into the queue
//int nodeCount = 1; // for the first node as that has been enqueued
while (! Q.empty())
{
int v = Q.front();
Q.pop();
cout<<"Visited:"<<v<<endl;
int visitCount = 0;
for( auto & node : AdjacencyList[v] )
{
//nodeCount++;// Increament node
// Is node already enqued in the Q
if( ! enqueuedNodeList[node] )
{
enqueuedNodeList[node] = 1;
Q.push(node);
}
else
{
// Checking the parent, more than one parent is graph
// Check if visited adjacent node more than one
if (++visitCount == 2 )
{
return false;
}
}
}
}
// Delete explored
delete [] enqueuedNodeList;
/*cout <<"Node Visit Count:"<<nodeCount<<endl;
if ( nodeCount > 2 * numberOfVertices)
{
return false;
}*/
return true; // Its tree
}
@property (strong,nonatomic) NSMutableArray *nodeArray;
- (BOOL)isTree: (Node*)head{
if(nodeArray == nil){
self.nodeArray = [NSMutableArray new];
}
if([self.nodeArray contains: head]){
return NO;
}
else if (!head.right && !head.left){
[self.nodeArray addObject: head];
return YES;
}
else{
[self.nodeArray addObject: head];
return [self isTree: head.left] && [self isTree: head.right];
}
}
Take any node and do a BFS maintain count of the number of visited nodes and a visited array. If any node is visited twice(cycle) return false. After the BFS if count is not equal to the no of nodes return false.
- 511narender March 07, 2017