can any 1 suggest an algo without global vars pls
On Sat, Aug 20, 2011 at 1:29 PM, Abhishek Yadav <[email protected]>wrote: > yes you are right thanks for correcting me, there would be 3 canditates. > > > On Sat, Aug 20, 2011 at 1:28 PM, Kunal Patil <[email protected]> wrote: > >> @Abhishek: >> Its not always that you reach a leaf through the node. >> But still your logic seems correct. >> There would be 3 candidates for minimum: >> -->predecessor >> -->current node >> -->successor. >> >> On Sat, Aug 20, 2011 at 1:13 PM, Abhishek Yadav < >> [email protected]> wrote: >> >>> No your solution is correct too....its just that in your solution number >>> of comparisons done with the original number are more, while in my solution >>> they get down to 2. otherwise complexities of both the solution would be >>> O(log n). >>> I am stressing on no. of comparisons because in these kind of questions >>> where we do compare something no. of comparisons matters. >>> for example when we talk about finding largest and second largest in an >>> array, we do try to minimize number of comparisons. >>> >>> Otherwise your solution is correct no doubt. >>> >>> >>> On Sat, Aug 20, 2011 at 12:59 PM, Dipankar Patro <[email protected]>wrote: >>> >>>> is there anything wrong in my algo? >>>> do tell me. >>>> >>>> >>>> On 20 August 2011 12:56, Abhishek Yadav <[email protected]>wrote: >>>> >>>>> Hey i tried it now and got to another solution >>>>> O(log n) solution: >>>>> 1. try searching for the number , if found,return the node, otherwise, >>>>> you will ultimately reach a leaf node say 'nd' >>>>> 2. Now the two candidates for the answer would be >>>>> 1. TreeSuccessor(nd) 2. TreePredecessor(nd) >>>>> Now compare the original number with these two and minimum would be the >>>>> answer. >>>>> >>>>> (TreeSuccessor and TreePredecessor are the next and previous node resp. >>>>> in the Inorder traversal of the tree.) >>>>> >>>>> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro >>>>> <[email protected]>wrote: >>>>> >>>>>> why traverse the whole tree? >>>>>> >>>>>> at each root keep the difference in a min_diff and min_ele. >>>>>> if the entered value is less root then move to left or right. >>>>>> repeat above two until whole tree is checked or min_diff becomes 0. >>>>>> >>>>>> pseudo code: >>>>>> >>>>>> min_diff = INF; // global variables >>>>>> min_ele = 0; >>>>>> >>>>>> find_min_diff(node *root, int num) >>>>>> { >>>>>> >>>>>> if (root == null) >>>>>> return; >>>>>> >>>>>> // update the difference >>>>>> if(abs(root->val - num) < min_diff) >>>>>> { >>>>>> min_diff = abs(root->val - num); >>>>>> min_ele = root->val; >>>>>> } >>>>>> if ( min_diff == 0) >>>>>> return; // search is over >>>>>> >>>>>> // proceed to next element in tree which might be closer to the num >>>>>> if ( num < root-> val) >>>>>> find_min_ele(root->left, num); >>>>>> else >>>>>> find_min_ele(root->right, num); >>>>>> } >>>>>> >>>>>> ^^ Complexity : O(logn) >>>>>> >>>>>> On 20 August 2011 12:36, Abhishek Yadav >>>>>> <[email protected]>wrote: >>>>>> >>>>>>> yes, the interviewer said that there is a solution in O(log n) >>>>>>> >>>>>>> >>>>>>> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan < >>>>>>> [email protected]> wrote: >>>>>>> >>>>>>>> ur traversing the tree once so it shud be o(n).does the question >>>>>>>> demand 0(logn) ? >>>>>>>> >>>>>>>> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav < >>>>>>>> [email protected]> wrote: >>>>>>>> >>>>>>>>> what would be the complexity of your solution O(n) or O(log n)..? >>>>>>>>> >>>>>>>>> On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan < >>>>>>>>> [email protected]> wrote: >>>>>>>>> >>>>>>>>>> traverse bst inorder and each time u encounter a node find the >>>>>>>>>> difference between the element and given element in question . if the >>>>>>>>>> absolute difference is minimum after traversing the tree that is the >>>>>>>>>> element >>>>>>>>>> . u can getback the element using another element which keeps sign >>>>>>>>>> of the >>>>>>>>>> element so that original element can be obtained from diff >>>>>>>>>> >>>>>>>>>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav < >>>>>>>>>> [email protected]> wrote: >>>>>>>>>> >>>>>>>>>>> Given a BST and a number, Find the closest node to that number in >>>>>>>>>>> the >>>>>>>>>>> BST. Give an algorithm for that. >>>>>>>>>>> Let there be binary search tree having nodes with values >>>>>>>>>>> 12,34,64,23,64,25,76,6 and the number given is 28, then the >>>>>>>>>>> answer >>>>>>>>>>> would be 25 as it is the closest node. >>>>>>>>>>> >>>>>>>>>>> -- >>>>>>>>>>> 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. >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> 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. >>>>>>>>>> >>>>>>>>> >>>>>>>>> -- >>>>>>>>> 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. >>>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> 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. >>>>>>>> >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> >>>>>> ___________________________________________________________________________________________________________ >>>>>> >>>>>> Please do not print this e-mail until urgent requirement. Go Green!! >>>>>> Save Papers <=> Save Trees >>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> >>>> ___________________________________________________________________________________________________________ >>>> >>>> Please do not print this e-mail until urgent requirement. Go Green!! >>>> Save Papers <=> Save Trees >>>> >>>> -- >>>> 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. >>>> >>> >>> -- >>> 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. >>> >> >> -- >> 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. >> > > -- > 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. > -- 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.
