Microsoft Interview Question
Country: United States
The question speaks of a 'random' node so it need not necessarily be a root node in which case your recursion solution does not hold for all possible cases.
It is not relevant. The question mentions two pointers, "next" and "prev" which will point to the right/left children. There is no pointer to the parent. As a result, all we can say is if the "sub-data structure" rooting at the given pointer is a tree.
Also, in the code above I am checking all children and since a HashMap is used, it will say no as soon as a cycle is found.
About the Binary Tree check, I think it gives the correct answer, but just a minor detail: when the node is already contained in the HashMap, it does not necessarily means there's a cycle. Example:
A -> B
A -> C
B -> D
C -> D
D will be revisited twice. It is not a cycle, but this is not a tree, just a DAG, and the code returns false as expected.
with binary tree quite easy - check all parent nodes have no more then two children and data satisfy Binary Tree criteria.
DLL is simple - parents always have one children
For a Doubly linked list:
The next and prev pointers will act just as they should for a doubly linked list.
For a Binary tree:
The next and prev pointers will act as pointers to the left and right child.
Here is my solution:
For a DLL which looks like: pre-input<====>input <====>post-input
Either going foward and back from 'input' OR backward and forward from 'input' should lead to the original node.
For a Binary Tree:
If the node does not form a DLL
AND
If both pointers point to different locations, the input node could represent a node in a binary tree with
atleast one child.
For Neither of the two:
If both the pointers are NULL, then the input node points represents a node which can neither be
a DLL nor a binary tree.
void findWhatNodeForms(Node input)
{
if(input->next->prev == input || input->prev->next == input)
{
// Node is part of a DLL with atleast 2 nodes.
}
else if ( input->next ! = input->prev)
{
// Node forms a binary tree with atleast 1 child node
}
else if (input->next == NULL && input->prev == NULL)
{
// Node does not form either of the two
}
else{}
}
the Binary Tree part is incorrect. A Tree (binary or not) does not have cycles and each node has at most one parent. we need to check that.
the 'input->next ! = input->prev' condition checks if the input node points to two different locations in memory which would mean there is a possibility that it forms a binary tree node. Given a single node, that is the only condition you can check.
The "possibility" part of the question is about using the same structure to represent a DLL, Binary Tree or something else.
Then, the question is very direct "Given a random pointer recognize whether it forms DLL, Binary Tree or none.". Thus, we should traverse from this pointer to its adjacent nodes.
^ That is exactly how I interpreted this question. You can never correctly tell if a node forms a binary tree unless it is a root node in which case we can do a traversal and check for b-tree'ness.
Since it is a random node, we have to look at the 'possibility' that it forms either of the two.
In a real life situation, I presume this would be some optimization over checking the whole tree or list.
Yes, it would have to be a tree rooted on the given node. In my opinion, this does not make much difference.
Interview questions are not set in a "real life" software project. So, unless the interviewer said so in the question, I believe we should treat it as a normal question like "check if a binary tree is a bst"
To check if it is a DLL, we need to traverse the list both forward and backwards and check if the previous and next pointers are correct. Also, if the DLL may be circular (ask the interviewer), we need to detect cycles.
Checking if it is a binary tree is a bit more complex. A Tree does not have cycles. On top of that, we also need to check that each node has at most one parent (otherwise it is just a Directed Acyclic Graph and not a Tree)
As per my understanding, the best way to differentiate Binary tree and DLL is by counting leaf nodes.
In case of DLL there will be only two null values one is at the start and one at the end.
Where as in Binary tree there will be 2^h-1 to 2^h leaf nodes. So by counting the leaf nodes we can solve the problem.
If the given node having two null pointers then we can't say whether it is BT or DLL.
Can this be done for any random pointer?
If there is just one node and it's prev and next are 0 (or NULL) then it can be regarded as both binary tree as well as doubly linked list. Or if input is NULL pointer even then it can be either DLL or BT
curr=random;
if( curr==0 || curr->prev == 0 && curr->next == 0)
return BOTH;
If prev is not null, then keep going to back (traverse prev) until prev is 0, at which set head=curr
for(curr; curr!=0 && curr->prev!=0 && curr->prev!=curr; curr=curr->prev);
head = curr;
now traverse ahead and for ever hop test curr == curr->next->prev, till curr->next == 0
for(flag=1, curr; curr!=0 && curr!=curr->next->prev; curr=curr->next)
{
if( curr == head && flag == 1)
flag=0;
else
return NONE;
}
if( curr == 0 )
return DLL;
else if( isBT(random) )
return BT;
else
return NONE;
if there is a loop then if head is passed twice, then break suggesting loop and it is neither DLL nor BT.
Now for BT its a bit curious, it can as well be a leaf node in which case it will return BOTH, if its not a leaf node then?
Modified DFS can help, if node has already been discovered/ seen in DFS then graph has back edge. Trees don't have back edges.
Keep a hastable of discovered nodes, if next node is in either hash(back-edge), we will have a cycle indicating its not a BT, so return tree. If there're no back edges, its a tree.
boolean isBT(node *random)
{
if( random )
{
/* add in 'discovered' hash table and returns 0, if already exists returns 1 if its already in discovered hash table*/
if( discovered(random) == 0)
{
return isBT(random->next) && isBT(random->prev);
}
return false;
}
return true;
}
Since it is pointer-based, there is a hint at recursive implementation.
For BinaryTree when starting at root, you need to make sure there is no cycle, e.g., when moving down the tree, you can keep a HashMap to make sure new nodes are not being revisited. Another thing which "I did not consider" but could be important is the consistency of values at different nodes, e.g., do we need to have one child value larger, and the other one smaller than current node?
For DoublyLinkedList;
Assuming that the list is null terminated, all we need to check is that at each node we get:
unless "next" or "prev" are null.
In case we are allowing for cycles, you should keep the value of one fixed node somewhere an instead of terminating at "null", terminate when you re-visit this node.
- Ehsan December 16, 2013