@apoorve say the input is 9 8.. I think it will fail...
Secondly, i see that max is not being used.... On Dec 31, 8:19 pm, Apoorve Mohan <[email protected]> wrote: > 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.
