Microsoft Interview Question
Country: India
Interview Type: Written Test
we can check using dfs to find whether there is cycle in the tree or not ..there is no point in checking whether it has two sons or not coz the structure of node must be such that it wil be holding two pointers only then only question will make sense
@anonymous.. dude question here is,is the tree binary.. there can be three struct node pointer in tree structure,where the third pointer always points to null(i knw its foolishness,but it is a valid argument).. if u look at the tree in that scenario.. still it will be a binary tree.. so structure on node alone doesn't determines its nature.
Guys this question was asked in NIT rourkela MSIT placement 2nd round.. so pleeezzz dn doubt the question... please write an answer instead of questioning the question...
i think the question wants devlopers to think on how this tree is implemented..
as the q says: there is an implementation in which the tree might have more than 2 childs
so 1 node instead of having 2 childs has an ll or arraylist in which we can put child tree nodes
and then u need to just recursively go through each node and check the no of childs.. thats it )
i hope it helps..
its an open question so even you can suggest some scenario
I think we can get this by applying size of(root)....if it has only left right and data ..it will return 12....considering int size =4 else...it will be 16,20 in case of more than 2 pointers....correct if wrong..
Hey my Java compiler says sizeof is undeclared variable what is up with that?
I tried the above approach in C with the following tree structure
struct Tree {
char [256] name;
uint left_count;
uint right_count;
struct Tree *left;
struct Tree *right;
};
It tells me it is not binary. What am I doing wrong? Should I go back to the basics? Take a course in C again? OMG this question is soooooo tricky....
The question is either incomplete or u need to take ur own assumption that basic structure remain the way we do...to solve it...if there is no such function in java..then try for its implementation...of ur own...
public class Node
{
int value;
List<Node> children;
public:
Node()
{
value = -1;
children = new ArrayList<Node>();
}
List<Node> getChildren()
{
return children;
}
...
};
bool isBinary(Node root)
{
if(root==null) return true;
if(root.getChildren().size() >2) return false;
return isBinary(root.getChild(0)) && isBinary(root.getChild(1));
}
listen asshole... if u dnt knw nythng.. just dont blame ny1.. its a real question of 10 marks asked in written round.. nd u knw wat dumbass.. i gaurantee u cnt answer this one..
@rockstar: You IQ seems to correspond with your typing skills.
The question is missing information and incomplete as written. Challenging someone for an answer to such crap questions just shows you are too stupid to reason with.
@anonymous.. as i said ur an asshole... answer this question if u can,coz its a right question and tricky too... answer was later on said by the interviewer.. and dumbass like u.. were rejected,just coz they said.."incomplete data..."
@rockstar: Abbe chootiye, dumb piece of shit. Stop harping on this crap.
This was in Microsoft India (IDC), which is the sewage tank of Microsoft Redmond. The interviewers there seem to be as dumb as you.
If you think it is tricky and brilliant, post the answer and let the other people judge for themselves.
1)two pointers of the same node point to the same child
- w00ster November 01, 20122)pointers from two different nodes point to a single node
3)a cycle, as was mentioned above
4) Anything else which invalidates the structure
The common pattern i see here is that if you traverse an invalid tree, you'll eventually come across a node that is repeated
Assuming there may be repeated values in the tree, let's assume a node is a unique combination of it's value and left and right pointers
As we traverse the tree, lets store the nodes in a vector. once a new node is found (use anything, depth or breadth first traversal), see if the node already exists in the vector. If it does, its not a tree. If we traverse the entire tree without encountering a repeat, it ought to be a valid binary tree
On second thought, a hash table might be a better option.
With a vector, time complexity will be O(n2). A hash table will probably bring it down to O(n)
Note, I am asuming the structure of a node is the standard value,*left,*right