Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
The solution is a good one. But calling it 'more efficient' is not appropriate. In order to count the number of nodes, you need to determine their uniqueness. You can do it either by sorting ( O(elg(e)) time complexity: e= #of edges) or using a hashtable( O(e) space complexity and O(e) time complexity), which are no way better than using DFS which is of O(1) space complexity and O(e) time complexity(in this case, for a graph where |V| ~ |E|)
@ Erasmus - For DFS, you should know the root node. How you find the root from adjacency list ??
@Vin.....no need for root node.....do dfs from any node...u will able to find whether there is loop or not...for finding loop u have to keep track of visited nodes....once u find node again then loop exist otherwise not....
@Erasmus..how can u do dfs in O(1) space complexity in this case....for dfs u have to construct adjacency list or adjacency matrix from given pairs and also u have to keep track of visited nodes while dfs is running O(V) space
in my method u have to traverse list one time... maintaining hash table for counting unique node... simultaneously count number of edges and we are done
@dhamu.31954
The question says that the input is already given as an adjacency list. In your method, you need an additional hashtable( extra O(e) space ) to find out unique nodes. DFS needs adjacency list, but not your extra hashtable.
@Vin
DFS is a graph algorithm and graphs don't have root nodes. A tree is a graph without cycles and with a distinguished 'root' node.
@Erasmus.....if adjacency list is given then u r right ......but in question he mention List of (parent, child ) ...and after that he write adjacency list.....i think adjacency list is not same as List of (parent, child) pairs
consider following small example
A
/ \
B C
adjacency list is
A->{B C}
and (parent,child) is (A,B),(A,C) {(Parent,Child) pairs}
so for constructing adjacency list from (parent,child )pairs we need hashtablet....
suppose given pairs
(G,H),(B, E),(B,F),(A,B),(A,C),(C,G)......and if we construct tree froms these pairs..then binary tree looks like as following
A
/ \
/ \
B C
/ \ \
E F G
/
H
now look number of edges = No. of nodes - 1(this is the property of binary tree)
now if we add one more edge to this then we get one loop.....so for checking loop
count number of nodes=n
number of edges =given parent child pairs = e
now check
if(e>n-1) then loop exist otherwise not
one more important thing i am assuming every child has only one parent..if has then this method will not work....so for loop detecting we have to do DFS or BFS
In binary tree, no child can have more than one parent.
create a map<child,parent>
while populating this structure, if there is any attempt to assign parent of a node, which already have one, you got cycle.
Tree is a directed acyclic graph. So, there should have only one path from root to any node in the tree. If this property is violated then the graph is not a tree and might have the potential chance for having a loop. We can easily check this by checking number of incoming edges to a node.
1) If a non-root node has more than one incoming edge then loop exists only if the edge is from a child to an ancestor.
2) If the root contains an incoming edge then loop surely exists.
If we have a tree like
a
/ \
b c
/ \
d e
Now assume there is an edge from d to b (d, a). This edge will create a loop according to (2). Now assume an edge from d to b: (d, b). Then there will be a loop according to (1). But if e have an edge from e to c : (e,c) then there exist no loop although the tree is not tree anymore as there are more than one path from root to c.
Since the tree is already given in a graph representation, apply either BFS or DFS. Return true if you encounter a node with 'isVisited' flag is true.
1) If we are given pairs in (parent, child) notation, then lets create a set S.
2 ) For each pair (parent, child) add parent to the set without checking if it is there
3) If child exists in the set then return false (it is a loop, meaning that we previously inserted this node either a parent or someone's child. A child can have only one parent in Binary tree).
4) Else add the child to the set
5) If no loops found - return true
You can do it in O(n) by using hashes.
1. Traverse the tree in any form (preorder, inorder or postorder).
2. For each element in the tree, create an entry in the hash.
3. While inserting, check if the entry already exists or not. If so, you found a loop.
4. If no duplicates found in the complete traversal, loop does not exist
A binary tree has a loop, if a child has more than one parent. So sort the given list with child as the key. Then travese the list to find if there are two adjacent node pair with same child . One more way I could think is to go through the list and create a hash table with child as key to figure out the number of parent the child has.
we can do it more efficiently ..........in case of binary tree....
number of edges in n nodes binary tree is equals to (n - 1)
count number of nodes in binary tree lets say n
and also count number of edges(numbers of parents child pairs given) lets say e
- dhamu.31954 November 27, 2013if(e>n-1) return false else return true