Re: [algogeeks] MS interview
What should be the answer to above questions...? On Sat, Sep 17, 2011 at 5:01 AM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: Memory management has following things.. 1.Relocation To maintain the free pages and when a page is to be swapped, we have to add that page into free page list .. For this ,if we maintain a bool array which is equal to # pages in RAM,it gives whether it is free or not .. 2.Protection If ours is strict paging , then this is easy task to implement ... any way we have the fixed page size ... In segmentation , we maintain length of the segment..we can achieve protection... 3.Sharing for each page if we maintain the list of users this page has been given permission (either read or write) 4.Logical Organization 5.Physical Organization On Thu, Sep 15, 2011 at 2:06 PM, teja bala pawanjalsa.t...@gmail.comwrote: 13. Propose an algo/data struct for memory manager. 14. Propose and algo/data struct for timer manager. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: Closest ancestor of two nodes
this solution works if parent pointer is given. 1. Start moving up from both the nodes (if two nodes become equal, fine this is the common ancestor) till you reach the root node and in between count the number of nodes you covered in their path for both the nodes. Say 7 for node A and 10 for node B. 2. Now from B (longer path node) move up 3 (10-7) nodes. 3. now start moving up from B's new position and from A. Wherever they meet is the common ancestor. On Sat, Sep 3, 2011 at 11:13 AM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: For BST it is easy ...it can be find in O(logn) time .. when ever we find that the direction we are searching for x and y are different, that node is the common ancestor ...no need to find either x or y where the nodes are... what about binary tree ? how do we search an element in binary tree efficiently ? On Sat, Sep 3, 2011 at 12:44 AM, rajul jain rajuljain...@gmail.comwrote: @anika this solution only works for BST On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain anika.jai...@gmail.comwrote: node *common_ancestor(node *root, node **prev, int x,int y) { if(root-a==x || root-a==y) return *prev; else if(root-a x root-a y) { prev=root; return common_ancestor(root-l,prev, x,y); } else if(root-a x root-a y) { prev=root; return common_ancestor(root-r,prev, x,y); } else { prev=root; return *prev; } } with call as node *prev=NULL; common_ancestor(root,prev,x,y); On Sun, Aug 14, 2011 at 10:08 PM, Yasir yasir@gmail.com wrote: Guys, How about the below mentioned implementation? The only assumptions is that nodes should exist in the tree. (will fail if one node exists and another doesn't) static Node LCA(Node root, int d1, int d2){ if(root==null) return root; if(root.left!=null ( root.left.data == d1 || root.left.data==d2 ) ) // both nodes exists in left sub-tree return root; if(root.right!=null ( root.right.data == d1 || root.right.data==d2) ) // both nodes exists in right sub-tree return root; Node ltree = LCA(root.left, d1, d2); //check recursively in left subtree Node rtree = LCA(root.right, d1, d2);// check recursively in right subtree if(ltree!=null rtree!=null)// One node in left another in right return root; return (ltree==null)?rtree:ltree; } Just to mention that, closest ancestor of 54 OR 49 would be 3 in the following tree: 3 \ 4 /\ 5 8 / 9 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Pattern Matching
Implement a function that receive a string S and a pattern containing wild characters ( * and ? only) in string P. Function return true if S matches the pattern P. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] print level by level withoust recursion
can we use loops or GOTO statements On Wed, Aug 31, 2011 at 10:03 PM, manish kapur manishkapur.n...@gmail.comwrote: Given a binary Tree and a node pointer extra in a tree. print all the node level by level. You cannot use any Stack ,recursion and queue. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Help ! - Explain Sscanf
so what should be the correct question after writing % specifier. On Tue, Aug 30, 2011 at 11:48 PM, Sanjay Rajpal srn...@gmail.com wrote: yes % has to be there. Sanju :) On Tue, Aug 30, 2011 at 11:12 AM, sukran dhawan sukrandha...@gmail.comwrote: yes conversion specifier missing i think On Tue, Aug 30, 2011 at 11:37 PM, SANDEEP CHUGH sandeep.aa...@gmail.comwrote: but sanjay in the ques it is *c*cd shudn't there be a % before that ?? On Tue, Aug 30, 2011 at 11:22 PM, Sanjay Rajpal srn...@gmail.comwrote: Run the following program : main() { int a,b; scanf(%d %*d,a,b); printf(\na= %d, b=%d,a,b); } now see the values of a and b, and post the result here. Sanju :) On Tue, Aug 30, 2011 at 10:46 AM, sukran dhawan sukrandha...@gmail.com wrote: i don think so.can u brief it ? On Tue, Aug 30, 2011 at 10:45 PM, Sanjay Rajpal srn...@gmail.comwrote: only year gets scanned here, * suppresses assignment of day and month. Sanju :) On Tue, Aug 30, 2011 at 9:08 AM, sukran dhawan sukrandha...@gmail.com wrote: sscanf is similar to scanf except that input is read from string rather than keyboard or i/o *c -supression character.it reads character and discards it.doesnt store it anywhere On Tue, Aug 30, 2011 at 9:32 PM, Mani Bharathi manibharat...@gmail.com wrote: char*str=11/1/1999; sscanf(str,*c*cd,month,day,year); -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/60kR7ykKiksJ. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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: elitmus test
can you share some DI questionsurgent On Sun, Aug 28, 2011 at 3:37 PM, Aditya Virmani virmanisadi...@gmail.comwrote: focus on quant di...verbal wud be easy...as in our college, thr were two papers, on which had gud level of quant qns...qns were nt tough to crack, but involved calculations which may take gud amt of time...like thr was 1 qn: find the sum of first 1234 terms in the series 121221222112. its easy but calculations may be high if u dun do it wit sum trick, second paper had tougher DI but pretty easy quant...so u hav to manage ur time well... On Sun, Aug 28, 2011 at 1:00 AM, prasanna rockslife2...@gmail.com wrote: thanks...:) hope someone adds some more questions..:) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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: Adding Two no without using any operator...??
Very nice solution sourabh. On Sun, Aug 28, 2011 at 9:52 PM, Dave dave_and_da...@juno.com wrote: @Shravanthi: Write a and b in binary, and then apply the bitwise exclusive-or to them and you will see why. Dave On Aug 28, 9:24 am, Shravanthi U M shravanthium...@gmail.com wrote: if we give a=10, b=5 we get a^b=15 but wen a=10,b=7 we get a^b=13 why s it so,..??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: Intersection of characters
@Don: Can you please explain the 3rd for loop.the working of if statement??? On Thu, Aug 25, 2011 at 11:02 PM, Don dondod...@gmail.com wrote: Sure. It uses a hash table to keep track of which characters occur in each file. The hash table is 256 bits initialized to zero. When it encounters a character in file 1 it sets the corresponding bit in the hash table. It does that by taking the 3 low order bits as the index to the hash table. Those bits will fall in the range 0..7. The high order bits, obtained by shifting the character right 3 bits, will give a value in the range 0..32. We shift a bit into that location and use bitwise or to set the bit in the hash table. We do that for both files. The final for loop checks each character to determine if its bit is set in both hash tables. If so, it occurs in both places and we output that character. The code would be somewhat simpler if I didn't try to use every bit in the hash table. It would take 512 bytes of memory instead of 512 bits. int main(int argc, char *argv[]) { FILE *f1 = fopen(argv[1],r); FILE *f2 = fopen(argv[2],r); char hash1[256] = {0}; char hash2[256] = {0}; char ch; while((ch=getc(f1)) != EOF) hash1[ch] = 1; while((ch=getc(f2)) != EOF) hash2[ch] = 1; for(ch = 0; ch 256; ++ch) if (hash1[ch] hash2[ch]) printf(%c, ch); return 0; } Don On Aug 25, 11:42 am, Shrey Choudhary choudharyshre...@gmail.com wrote: @Don.. Can you briefly explain the program? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] C Trick
@Anup: i think priyanka's solution would work for 3 and -2 On Wed, Aug 24, 2011 at 10:05 PM, *$* gopi.komand...@gmail.com wrote: oops! yes I was trying to find whether that number is negative or positive by shifting the highest bit to oth location... that is a typo error.. Thanks for pointing out! On Wed, Aug 24, 2011 at 7:32 PM, vikas singh shyguy1...@gmail.com wrote: On Tue, Aug 23, 2011 at 7:50 PM, *$* gopi.komand...@gmail.com wrote: int a,b; int c=a-b; c=c31; c=c31; // hope you're trying for this. ;) int x =c0x01; a=a-x*c; Thx, --Gopi On Tue, Aug 23, 2011 at 7:32 PM, Sanjay Rajpal srn...@gmail.com wrote: @teja : use of comparison operator is not allowed. Sanju :) On Tue, Aug 23, 2011 at 6:42 AM, teja bala pawanjalsa.t...@gmail.comwrote: int a,b,c; c=(ab)?a:b; print(c); On Tue, Aug 23, 2011 at 6:37 PM, Abhishek Yadav algowithabhis...@gmail.com wrote: Write a method which finds the maximum of two numbers You should not use if-else or any other comparison operator. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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. -- Thx, --Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks and Regards VIKAS SINGH MCA- final year NIT DURGAPUR email: vikas.singh1...@gmail.com shyguy1...@gmail.com http://smrit.wordpress.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thx, --Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: C dot
Moreover they also asked what is .NET as if they heard it for the first timecome on...can you believe it...!!! On Tue, Aug 23, 2011 at 4:18 PM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: yeah..the interview was total nakli :D .. they always..take the toppers.. :) i mean..among the top ten who are sitting.. @Sachin:- they also asked , what is Drishti ? :D On Tue, Aug 23, 2011 at 1:54 PM, Sanjay Rajpal srn...@gmail.com wrote: 7.7 LPA @ NIT Kurukshetra. Sanju :) On Mon, Aug 22, 2011 at 10:47 PM, siddharam suresh siddharam@gmail.com wrote: how much they are offering ? Thank you, Siddharam On Tue, Aug 23, 2011 at 11:12 AM, ranjith kumar v.ranjithcar...@gmail.com wrote: They shortlist candidates based on cgpa and select the highest cgpa candidate. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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. -- *Dheeraj Sharma* Comp Engg. NIT Kurukshetra +91 8950264227 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] C Trick
Write a method which finds the maximum of two numbers You should not use if-else or any other comparison operator. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Adobe Interview - 20/08/2011
@vikas: can you please put some light over interval graph to solve this problem or provide some useful links?? On Mon, Aug 22, 2011 at 6:47 PM, Decipher ankurseth...@gmail.com wrote: @vikas - Can u post ur answer using segment trees ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ssVg6dOuXiUJ. To post to this group, send email to algogeeks@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 algogeeks@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] c++
But if you try making a copy constructor of your own and check whether it is called or not.it does not. On Sun, Aug 21, 2011 at 12:21 PM, Sanjay Rajpal srn...@gmail.com wrote: I think it will not be an error. This is because X() will create a temporary object, and when the object is returned in the function calling it, then default copy constructor will do bitwise copy of data members in the calling function. Correct me if m wrong. On 8/20/11, sachin sabbarwal algowithsac...@gmail.com wrote: class X() { X() { } X fun() { return X(); //error or what?? because constructor never returns anything so what this return statement will receive after executing x() and what it will return?? } }; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Sanju :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] c++
The code is correct..return X will make a temporary object and for that a constructor and corresponding destructor will be called and that object is returned. On Sun, Aug 21, 2011 at 12:24 PM, Puneet Chawla puneetchawla...@gmail.comwrote: It will show error On Sun, Aug 21, 2011 at 12:21 PM, Sanjay Rajpal srn...@gmail.com wrote: I think it will not be an error. This is because X() will create a temporary object, and when the object is returned in the function calling it, then default copy constructor will do bitwise copy of data members in the calling function. Correct me if m wrong. On 8/20/11, sachin sabbarwal algowithsac...@gmail.com wrote: class X() { X() { } X fun() { return X(); //error or what?? because constructor never returns anything so what this return statement will receive after executing x() and what it will return?? } }; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Sanju :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- With regards Puneet Chawla Computer Engineering Student NIT Kurukshetra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] c++
what are you trying to say?...can you please explain? On Sun, Aug 21, 2011 at 1:35 PM, JAIDEV YADAV jaid...@gmail.com wrote: try to use X b = a ; b.fun() ; On Sun, Aug 21, 2011 at 1:33 PM, Abhishek Yadav algowithabhis...@gmail.com wrote: ok...may be i forgot , can you please tell me correct code for the copy constructor..? On Sun, Aug 21, 2011 at 1:31 PM, JAIDEV YADAV jaid...@gmail.com wrote: dude u haven't used copy constructor properly .. check it out again ... you are not copying actually ... thats it ... On Sun, Aug 21, 2011 at 12:53 PM, Abhishek Yadav algowithabhis...@gmail.com wrote: Check this code: the thing i couldn't understand is when the object is being returned neither the copy constructor is being called nor the assignment operator overload is calledthen how the object is being copied into b. i don't think default copy constructor should be called if i have made our own copy constructor??? #includeiostream using namespace std; #includeconio.h class X { public: int num; X(int a) { num=a; cout\n constructor; } X(const X t) { this-num=t.num; cout\nCopy ; } X operator=(const X t) { this-num =t.num; cout\n Assigment ; return t; } X fun() { cout\nin fun; return X(7); } ~X() { cout\ndestruct ; } }; int main() { { X a(1); X b=a.fun(); cout\n\nb.num; } getch(); } On Sun, Aug 21, 2011 at 12:33 PM, Abhishek Yadav algowithabhis...@gmail.com wrote: The code is correct..return X will make a temporary object and for that a constructor and corresponding destructor will be called and that object is returned. On Sun, Aug 21, 2011 at 12:24 PM, Puneet Chawla puneetchawla...@gmail.com wrote: It will show error On Sun, Aug 21, 2011 at 12:21 PM, Sanjay Rajpal srn...@gmail.comwrote: I think it will not be an error. This is because X() will create a temporary object, and when the object is returned in the function calling it, then default copy constructor will do bitwise copy of data members in the calling function. Correct me if m wrong. On 8/20/11, sachin sabbarwal algowithsac...@gmail.com wrote: class X() { X() { } X fun() { return X(); //error or what?? because constructor never returns anything so what this return statement will receive after executing x() and what it will return?? } }; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Sanju :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- With regards Puneet Chawla Computer Engineering Student NIT Kurukshetra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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. -- JaiDev Yadav (National Yoga Champion) Computer Engg. Dept. National Institute of Technology Kurukshetra,Haryana -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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. -- JaiDev Yadav (National Yoga Champion) Computer Engg. Dept. National Institute of Technology Kurukshetra,Haryana -- You received this message because you are subscribed
Re: [algogeeks] c++
@jagannath: no its not i am totally confused. On Sun, Aug 21, 2011 at 5:57 PM, priya ramesh love.for.programm...@gmail.com wrote: it is not an error. check this code: I compiled it #includeiostream using namespace std; class X { public: X() { } }; main(){ } X fun() { return X(); } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] c++
@Thayumanavar: thanks for the link On Sun, Aug 21, 2011 at 10:33 PM, Thayumanavar S thayum...@gmail.comwrote: folks during temporary object creation constructor is called right..but constructor is called here only 2 times.. According to me,either copy constructor and constructor should have been called 2 times both or constructor 4 times ..but its neither of them...paradox http://en.wikipedia.org/wiki/Return_value_optimization thayumanavar s -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.
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 algogeeks@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 Question:Given a BST and a number, Find the closest node to that number in the BST.
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 sukrandha...@gmail.comwrote: 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 algowithabhis...@gmail.com 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 algogeeks@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 algogeeks@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 algogeeks@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 Question:Given a BST and a number, Find the closest node to that number in the BST.
yes, the interviewer said that there is a solution in O(log n) On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan sukrandha...@gmail.comwrote: 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 algowithabhis...@gmail.com 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 sukrandha...@gmail.comwrote: 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 algowithabhis...@gmail.com 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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 Question:Given a BST and a number, Find the closest node to that number in the BST.
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 dip10c...@gmail.comwrote: 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 algowithabhis...@gmail.comwrote: yes, the interviewer said that there is a solution in O(log n) On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan sukrandha...@gmail.comwrote: 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 algowithabhis...@gmail.com 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 sukrandha...@gmail.com 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 algowithabhis...@gmail.com 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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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. -- ___ 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 algogeeks@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
Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.
No your solution is correct tooits 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 dip10c...@gmail.comwrote: is there anything wrong in my algo? do tell me. On 20 August 2011 12:56, Abhishek Yadav algowithabhis...@gmail.comwrote: 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 dip10c...@gmail.comwrote: 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 algowithabhis...@gmail.comwrote: yes, the interviewer said that there is a solution in O(log n) On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan sukrandha...@gmail.com 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 algowithabhis...@gmail.com 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 sukrandha...@gmail.com 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 algowithabhis...@gmail.com 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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group
Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.
yes you are right thanks for correcting me, there would be 3 canditates. On Sat, Aug 20, 2011 at 1:28 PM, Kunal Patil kp101...@gmail.com 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 algowithabhis...@gmail.com wrote: No your solution is correct tooits 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 dip10c...@gmail.comwrote: is there anything wrong in my algo? do tell me. On 20 August 2011 12:56, Abhishek Yadav algowithabhis...@gmail.comwrote: 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 dip10c...@gmail.comwrote: 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 algowithabhis...@gmail.comwrote: yes, the interviewer said that there is a solution in O(log n) On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan sukrandha...@gmail.com 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 algowithabhis...@gmail.com 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 sukrandha...@gmail.com 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 algowithabhis...@gmail.com 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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@googlegroups.com. To unsubscribe from this group
Re: [algogeeks] Challenge
yah this is a good approach...but one thing in worst case it would be m^2 instead of n^2 On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal srn...@gmail.com wrote: Yes, thats right. I think we can do the following also : Lets us assume rows are sorted in increasing order. start from first row say i. Traverse the array from the end of the row towards the beginning till 0 occurs say at position j. now proceed to the next row i+1, check the value at i+1,j if it is 0, go to next row i+2,j else if its 1, then go to left till 0 occurs and store that index of 0 and follow to the next row. In the worst case, it will be O(n^2), but in general its a good approach i guess. what do u say guys ? Average Case O(m+n) ? Sanju :) On Sat, Aug 20, 2011 at 2:47 AM, shady sinv...@gmail.com wrote: binary search on every row which will give solution in O(m*(logn)) On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal srn...@gmail.com wrote: Sorry I forgot to mention that. Sanju :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 Question:Given a BST and a number, Find the closest node to that number in the BST.
@atul yes sure why not... On Sat, Aug 20, 2011 at 1:39 PM, Naman Mahor naman.ma...@gmail.com wrote: i think there will be three candidate.. 1. TreeSuccessor(nd) 2. TreePredecessor(nd) 3. nd it self. On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav algowithabhis...@gmail.com 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 dip10c...@gmail.comwrote: 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 algowithabhis...@gmail.comwrote: yes, the interviewer said that there is a solution in O(log n) On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan sukrandha...@gmail.com 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 algowithabhis...@gmail.com 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 sukrandha...@gmail.com 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 algowithabhis...@gmail.com 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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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. -- ___ 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 algogeeks@googlegroups.com
Re: [algogeeks] query.. amazon question
Its the same as we do merge sort where we merge the two sorted array into one which will require an extra array.. Is there any algorithm for inplace mergesort...? On Fri, Aug 19, 2011 at 2:09 PM, sagar pareek sagarpar...@gmail.com wrote: Can be done in O(n) time but it will need O(n) space too take another array of same length then its code will be for( i=0,j=0,k=n/2+1 ;i=n/2kn; ) { if(arr[i]arr[k]) new[j++]=arr[k++]; else new[j++]=arr[i++]; } if(kn) { while(i=n/2) new[j++]=arr[i++] } else { while(jn) new[j++]=arr[k++] } On Fri, Aug 19, 2011 at 12:40 AM, *$* gopi.komand...@gmail.com wrote: Sort an array of n positive integers containing n/2 sorted integers in first and second-half? in O(n) time complexity .. and space complexity should be constant -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Abhishek Yadav Comp Engg. NIT Kurukshetra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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]
Hey try queue instead of stack On Fri, Aug 19, 2011 at 9:47 PM, sagar pareek sagarpar...@gmail.com wrote: traverse the list and print only odd numbers and if even number encounter store it in a stack and later on print it On Fri, Aug 19, 2011 at 9:29 PM, sukran dhawan sukrandha...@gmail.comwrote: There is a Circular Singly Linked List with n nodes having sorted values from 1 to n. Need to print the odd and even numbers in groups in a single traversal. Eg. Input: 1-2-3-4-5-6-1 Output: {Any combination of Odd Nos} {Any combination of Even Nos} Eg. 1 3 5 6 4 2. write a program for same? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: array question
Thats right...by doing xor this can't be done...hey sanjay please reconsider your answer. On Aug 17, 2:05 pm, sukran dhawan sukrandha...@gmail.com wrote: when u xor nos with odd number of times we will get back the same no.only even occurences will give 0.question is to find the no with even occurence.how will you find that no? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- You wreceived this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.- 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 algogeeks@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.