@Apoorva.. I think i misread your code at the beginning ( apart from the typo) If i m not wrong then you have a taken a bottom up approach to solve the problem using the range concept.. Wherein the code that i posted is a top down approach..
Great .. :) On 31 Dec, 21:30, Apoorve Mohan <[email protected]> wrote: > Hey > > It was a typo error. > > here it goes.. > > 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(max > array(i)) > { > flag = 0; > break; > } > else > { > max = array(i); > } > } > > } > > flag?printf("yes"):printf("no" > ); > > > > > > > > > > On Sat, Dec 31, 2011 at 9:20 PM, Lucifer <[email protected]> wrote: > > @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. > > -- > 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.
