## Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

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.

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

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;
}
Set<Node<T>> visitedNodes = new HashSet<>();
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 {
}
}
}
}
return false;
}``````

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

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

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

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

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

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

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

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

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

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

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

``````@property (strong,nonatomic) NSMutableArray *nodeArray;

if(nodeArray == nil){
self.nodeArray = [NSMutableArray new];
}
return NO;
}
return YES;
}
else{
}
}``````

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

Give a single node and its decedents, then BFS can be used. If a node is already visited then it's not a tree. (To check if the node is already visited either use HashSet or check if the node has a property of state.)

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.

### 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.