Microsoft Interview Question


Country: United States




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

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?

private static boolean IsBT(GeneralLinkedList gll) {
        if (gll == null)
            return true;
        if (met_this_node.containsKey(gll)) // cycke
            return false;
        met_this_node.put(gll, true);
        return IsBT(gll.next) && (IsBT(gll.prev));
    }
    private static HashMap<GeneralLinkedList, Boolean> met_this_node;

For DoublyLinkedList;
Assuming that the list is null terminated, all we need to check is that at each node we get:

this.next.prev = this;
this.prev.next = this;

unless "next" or "prev" are null.

private static boolean IsDLL(GeneralLinkedList gll) {
        if (gll == null)
            return true;
        if (met_this_node.containsKey(gll))
            return true;
        
        met_this_node.put(gll, true);      
        if (gll.next != null)
            if (gll.next.prev != gll)
                return false;
        if (gll.prev != null)
            if (gll.prev.next != gll)
                return false;
        return (IsDLL(gll.next) && IsDLL(gll.prev));
    }

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ananth.sadanand December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ehsan December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Miguel Oliveira December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right. What I had in mind was to make sure a node is not visited twice. This means no cycle, but also not any DAC.

- Ehsan December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- LBaralgeen December 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Miguel Oliveira December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ananth Sadanand December 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Miguel Oliveira December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ananth.sadanand December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Miguel Oliveira December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ananth.sadanand December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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"

- Miguel Oliveira December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Miguel Oliveira December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- confused_banda December 17, 2013 | 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