maverick
BAN USER- 0of 0 votes
AnswersA list contains repeated numbers , all the numbers are repeated odd number of times except one which is repeated even number of time. WAP to find out that number ( which is repeated even number of times).
- maverick in India
( I gave the solution using extra space . He then asked me to give solution without extra space )| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
I started to believe that its number of edges not number of nodes. All the sites or discussions forum saying that its number nodes , seems wrong. Thanks for enlightening us.
For preserving leaf nodes , answer lies in this discussion thread itself . Check out the code posted by “Lucy on October 12, 2012” . It looks correct to me, provide your comment there if you see anything wrong in Lucy’s code so that she would get to know.
This code is very similar to what you are doing , except it preserves leaf nodes which forms diameter.
In case if you get confused looking at Lucy’s code, length is actually the diameter and findDia() function returns height of the root.
While I understand what you are saying , but :
1. I am normally cautious and picky about the word “height” used with Tree. Wikipedia says height of tree with only one node which is root is 0. But I have experienced that people normally perceive it as an empty tree. So I am always careful , while mentioning the height of the tree.
The problem is not with the height definition you have chosen , but the actual problem is it reduces the diameter of tree. ( see below )
2. Check out the diameter of the tree definition (geeksforgeeks.org/archives/5687). It’s not the number of edges but its number of nodes.
Since your focus is to just find two leave nodes which forms the diameter of the tree , it really does not matter what definition you assume for heights and diameter. Your solution is still correct in terms finding two leaf nodes which forms diameter.
But your diameter value seems incorrect to me.
3. It is just an idea and its very much possible. Try modifying your code , you can get the answer and if you cannot please do tell me.
Your concept seems correct to me.
There are few corrections ,I think , would be needed in your pseudo code :
1. You should not return 0 when a node does not have any children.
if n->children == null
return 0;
end-if
This should return 1 , as a node without children has height 1.
Instead, you could also say that -> (f n == null) return 0.
2. Formulae of “dia” seems incorrect . It should be h1+h2+1 i.e. height of left child + height right child + parent which is 1. Am I missing something here ?
One improvement I could see: instead of preserving c1 and c2, you can preserve leaf nodes , and thus avoiding to find leaf nodes at the end i.e. essentially avoiding these two calls.
Node leaf1=bfs(c1); //bfs returns one of the leaf max depth
//from sub-tree at c
Node leaf2=nfs(c2);
Your solution does not work for following input :
1
2 3
4 5
7
9
Root – 1 : left child-2, right child – 3
Node-2 : left child -4, right child -5
Nod-3 : leaf node
Node-4 : leaf node
Node-5 : left child-null, right child-7
Node-7: left child-null , right child-9
Node-9 : leaf node
With your solution Q2 contains only 9 at the end. However the correct answer is 9 and 3 which has the longest path which is 6.
@buckCherry:
It depends on your insertion algorithm.
Assuming root =3 , its right child=4.
3
\
4
Now if you want to insert 3 to this , where your insertion algorithm would insert it ?
1. One solution would be to insert it as a left child of 4
2. Other solution would be to insert it as right child of 3 and then make 4 as a child of 3 ( i.e. 2nd 3 ).
Irrespective of above two solutions, your tree is a valid BST. It satisfies you invariant i.e. all the nodes in the left side of the root should be less than root and all the nodes in the right side of the root should be greater than or equal to root.
I don’t see the reason you are seeing this as an invalid BST . Are you seeing any property of BST not getting satisfied ?
Yes I understood and agreed what you meant to say. I just wanted to clarify because you reply is very specific to this solution code which returns int.
I was just trying to find out what could be that “something similar” and tried to explain on that a bit.
It’s great to have concrete answer of question raised on a concrete solution ,not just conceptual answer.
To : buckCherry's reply on November 06, 2012
Well I believe it should always be part of question on what should function return if no “next big number” found. If not mentioned by interviewer then interviewee should really ask.
If function returns an integer value then there is no question of null. It purely depends on what client code expects and how intelligent client code is. If client is intelligent enough to determine that returned value is equal or less than input number then client code can understand that there isn’t exist next big number in the tree. This is one of the scenario and solution I could think of. But again it depends on what client code really expects, in short what is the exact requirement.
And yes, in terms of finding the next big number code works fine.
You will have to find 3 closest numbers from those sorted lists
This is how this can be done :
1. Take a smallest list – say list-1 ( remaining lists are : list-2, list-3)
2. For each number in list-1 find the closed number in list-2 and list-3 )
3. Step#2 can be done using modified binary search ( if you get exact match then its good or else you get a closest value when searching stops) since list is sorted . – ( time complexity log(n) for each element in list-1 ).
4. With each iteration you would also have to store that closest found values from list-1 and list-2 ( make use of hashmap or some other data structure ).
5. Once this is done , iterate through the hashmap and calculate max(x,y,z) – min(x,y,z) -- whichever results in minimum is the correct answer.
Note : you can avoid using extra storage by making use of 6 variables – 3 for holding current combination (x1,y1,z1) and 3 for holding previous combination(x0,y0,z0) which is also minimum – replace the previous combination with current combination when you find that :
[max(x1,y1,z1)-min(x1,y1,z1) ] < [max(x0,y0,z0)-min(x0,y0,z0) ]
e.g. :
List -1 : 1, 3, 5, 7
List -2 : 2, 4, 6, 8
List -3 : 1, 2, 11, 20
After step#3 you would have : ( format : list-1(list-2,list3) )
1(2,1) , 3(2,2) , 5(4,2), 7(6,11).
In this example we have two answers :
1(2,1) and 3(2,2)
time complexity O(nlogn)
Keep connecting the even nodes and while at the same time remove odd nodes and connect in the reverse way. At the end of traversal you would have two linked list :
1. Even nodes linked list
2. Reversed odd node linked list.
You would need 3 pointers and one temp node variable:
1. Pointer 1 : even -- which would traverse on even nodes only.
2. Pointer 2 : odd -- which would traverse on odd nodes only.
3. Pointer 3 : revHead -- head of reversed odd linked list.
4. Temp variable -- temporarily hold the odd node.
private static void modify(Node head)
{
if(head == null ||head.next == null || head.next.next == null)
{
return ;
}
Node even = head;
Node odd = head.next;
Node revhead = null;
Node temp = null;
while(true)
{
temp = odd;
if(odd.next != null)
{
odd =odd.next.next;
}else
{
break;
}
if(even.next != null)
{
even.next = even.next.next;
even = even.next;
}else
{
break;
}
temp.next = revhead;
revhead = temp;
}
temp.next = revhead;
revhead = temp;
}
One solution ( though it’s a naive one) , but considering memory constraint , it would be ok
a1 a2 a3
b1 b2 b3
i.e. : a1 , a2 , a3 , b1, b2, b3
Steps to be follow :
Remove element column-wise starting from 1st element of next row , shift up the array and then put the element at the end of the array . Do it for all the elements in that column and then move to next column . Repeat this till the last element of the array ( i.e. c5)
e.g. :
a1,a2, a3,b1,b2,b3 – original
a1,a2,a3,b2,b3,b1 –step-1
a1,a3,b2,b3,b1,a2 –step-2
a1,a3,b3,b1,a2,b2–step-3
a1,b3,b1,a2,b2,a3 –step-4
a1, b1,a2,b2,a3,b3 – –step-5 - final result
i.e. :
a1,b1
a2,b2
a3,b3
- maverick November 18, 2012