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.

- 511narender March 07, 2017 | Flag Reply
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;
	}
	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;
}

- shinok March 07, 2017 | Flag Reply
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;
}

- Fits March 07, 2017 | Flag Reply
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;
}

- Anonymous March 07, 2017 | Flag Reply
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;
}

- Fitsum March 07, 2017 | Flag Reply
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;
}

- Fits1987 March 07, 2017 | Flag Reply
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
}

- som March 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Legend March 14, 2017 | Flag Reply
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.)

- akki April 20, 2017 | 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