Re: [algogeeks] Google questions
1. Below is a solution of first problem - int SuccessorOfANodeInBST(Node N, int givenNumber) { if(N-rightChild != NULL) return (int) N-rightchild-data; int iNumberFound = 0; Node K = ParentOf(N); Node J = ParentOf(K); while(1) { if(K == J-leftChild) { iNumberFound = (int) J-data; break; } K = J; J = ParentOf(K); } return iNumberFound; } Rajan. On Thu, Dec 9, 2010 at 1:25 PM, Anand anandut2...@gmail.com wrote: You are given a binary tree. and You need to design a function which takes any node from the binary search tree and a number. Function should be able to return next higher number in binary search tree from the given node of binary search tree. Next higher number means : You given a number. you need to find next higher number of that number in a binary search tree if it exist. I hope this makes it clear. On Wed, Dec 8, 2010 at 11:27 PM, sahil gujral gujralsa...@gmail.comwrote: explain the 1st one again On Thu, Dec 9, 2010 at 11:16 AM, Anand anandut2...@gmail.com wrote: One of my friend recently had a telephonic interview and he got two question to program. 1. Given a binary search tree. Write a function which takes any given node from the binary tree and a number. Functin has to return the next highest number of the given number from the binary search tree. 2. You have given a structure which has two member, One which stores the time and other stores the function pointer Your function has to call the function stored in the fuction poitner after the time given in the structure elapses. Design that function? let me know in case if the questions are not clear in any way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google questions
On 09-Dec-2010, at 1:28 PM, rajan goswami wrote: 1. Below is a solution of first problem - int SuccessorOfANodeInBST(Node N, int givenNumber) { if(N-rightChild != NULL) return (int) N-rightchild-data; Why this? The right child might not be the next immediate higher number after givenNumber in the tree. int iNumberFound = 0; Node K = ParentOf(N); Node J = ParentOf(K); while(1) { if(K == J-leftChild) { iNumberFound = (int) J-data; break; } K = J; J = ParentOf(K); } return iNumberFound; } Rajan. On Thu, Dec 9, 2010 at 1:25 PM, Anand anandut2...@gmail.com wrote: You are given a binary tree. and You need to design a function which takes any node from the binary search tree and a number. Function should be able to return next higher number in binary search tree from the given node of binary search tree. Next higher number means : You given a number. you need to find next higher number of that number in a binary search tree if it exist. I hope this makes it clear. On Wed, Dec 8, 2010 at 11:27 PM, sahil gujral gujralsa...@gmail.com wrote: explain the 1st one again On Thu, Dec 9, 2010 at 11:16 AM, Anand anandut2...@gmail.com wrote: One of my friend recently had a telephonic interview and he got two question to program. 1. Given a binary search tree. Write a function which takes any given node from the binary tree and a number. Functin has to return the next highest number of the given number from the binary search tree. 2. You have given a structure which has two member, One which stores the time and other stores the function pointer Your function has to call the function stored in the fuction poitner after the time given in the structure elapses. Design that function? let me know in case if the questions are not clear in any way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Shuaib http://www.bytehood.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Valid Array
O(2n) algo 1st traversal calculate min calculate sx=1^2^.^N where N= no of elements 2nd traversal fx=(A[1]-min+1)^(A[2]-min+1)...^(A[N]-min+1) Now if sx=fx Array is valid otherwise not Array is called Valid if all the numbers appearing in A [1...N] are consecutive numbers. Example: A={5,3,4} is a valid array A={3,7,5,4,6} is a valid array -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google questions
Code for question no.--2 #includestdio.h #includeconio.h #includetime.h struct test{ clock_t endwait; void (*print_ptr)(); }; void print() {printf(\nHello World\n);} void wait ( int seconds ) { struct test *g=(struct test *)malloc(sizeof(struct test)); g-endwait= clock () + seconds * CLOCKS_PER_SEC ; while (clock() g-endwait) {} (g-print_ptr)=print; (*(g-print_ptr))(); } int main(){ int sec; printf(Enter the time after which you want output:); scanf(%d,sec); wait(sec); getch(); return; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: The best multiply matrix algorithms ?
Dave, thank You very much for yours information. Really, I want to know a theorical big-O algorithm, mainly to interact with sparce matrix. We see every day a new technic computation growing world information, but I not seen a new and revolutionary multiply matrix algorithm that take less than O(n^2). Maby this not will exists, but how can we use a parallel programming skills to better to make that rotine ? Is this what I should like to know. 2010/12/8 Dave dave_and_da...@juno.com: Are you interested in actual computation speed or are you interested in theoretical big-O speed? If you want the fastest computation for a specific, reasonable-sized problem with no particular structure (i.e., non-sparse), then using the ordinary matrix multiply algorithm that is coded the best will probably beat any theoretically-faster algorithm. You probably will find the fastest matrix-multiplication code in one of the sets of the so-called Basic Linear Algebra Subprograms (BLAS). Check out http://www.netlib.org/blas/faq.html, and especially 5) therein: http://www.netlib.org/blas/faq.html#5. Dave On Dec 8, 6:09 am, Luciano Junior luciano@gmail.com wrote: What is best multiply matrix algorithm for: -multiply a n x n matrix by another n x n matrix -multiply a m x n matrix by a n x p matrix I need a best performance cpu algorithm. Note: it can use a parallel programming concept. Thankfully. Luciano. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Luciano Soares Pinheiro Jr. Analista desenvolvedor Sr. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Largest rectangle in a binary matrix
@juver++ : Could you please elaborate your answer a little ... ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Valid Array
Algo: In first traverse find the min and the max values. if (max-min) not equals (N-1) return false In next traverse map each in a hashtable of size N where index=key-min. Now in case of collision return false return true -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Valid Array
@jai yeah, it can be done using count sort logic but that will take O(n) extra space which can be avoided by using XOR. On Fri, Dec 10, 2010 at 3:34 AM, jai gupta sayhelloto...@gmail.com wrote: Algo: In first traverse find the min and the max values. if (max-min) not equals (N-1) return false In next traverse map each in a hashtable of size N where index=key-min. Now in case of collision return false return true -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Valid Array
I got the correct answer: If it is a valid array, sum of all elements in the array = value calculated using arithmetic progression formula In this case Sum of arithmetic progression = (n/2)[2*a+(n-1)*d} where a = min of the array n = number of elements d = 1 If this value is equal to sum of all the elements in the array then it is a valid array On Dec 10, 6:44 am, ADITYA KUMAR aditya...@gmail.com wrote: @jai yeah, it can be done using count sort logic but that will take O(n) extra space which can be avoided by using XOR. On Fri, Dec 10, 2010 at 3:34 AM, jai gupta sayhelloto...@gmail.com wrote: Algo: In first traverse find the min and the max values. if (max-min) not equals (N-1) return false In next traverse map each in a hashtable of size N where index=key-min. Now in case of collision return false return true -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Valid Array
prims check for this case [1,1,4,4] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Valid Array
my bad The solution i quoted works only in case of no repititions. Aditya solution is correct On Dec 10, 9:23 am, mo...@ismu mohan...@gmail.com wrote: prims check for this case [1,1,4,4] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Valid Array
i did nt get this xor part in adithya solution check if this works array is valid if satisfy 2 conditions 1.max-min=n-1 2.there should be no repeatations first one can be done in O(n) for second check 1xor2xor...xorn=(a[1]-min+1)xor(a[2]-min+1)xor.. if both are equal there are no repeatations -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
997 is a prime number, so the calculation must be (1!+2!+...+996!) mod 997 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
@Dave I like this. use mem just O(1) , my algo use O(N). Thxx haxxpop -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: program for evaluation of remainders
@jai gupta why is this work?? I think it just calculates (N+1)! %n haxxpop -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.