Hey
Below is a solution. Hope it works.
Let 'n' be the size of the array we have.
max = min = array(n-1)
flag=1;
for(i=(n-2) to 0)
{
if(array(i)<array(i+1))
{
if(min < array(i))
{
flag = 0;
break;
}
else
{
min = array(i);
}
}
else
{
if(min > array(i))
{
flag = 0;
break;
}
else
{
max = array(i);
}
}
}
flag?printf("yes"):printf("no");
On Fri, Dec 30, 2011 at 1:21 PM, top coder <[email protected]> wrote:
> Input : You have been given a sequence of integers.
> Now without actually constructing BST from the given sequence of
> integers (assuming the sequence is pre-order) determine if each node
> of BST has single child (either left or right but not both).
> Output : YES if given integer sequence corresponds to such a BST.
> otherwise say NO.
>
> Ex. Say NO for 16,10,8,9,29,27,22.
> Say YES for 10,19,17,14,15,16
>
> I know the algo O(N^2) as follows:
> For every node in array(traverse from left to right),
> all the other nodes must be less or all the nodes must be greater
> than it.
>
> But interviewer is expecting O(N). Any ideas?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
regards
Apoorve Mohan
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
