Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
yes could be done by taking struct for each element struct st{int a; //value of elementint i; //index of beaten arrayint beaten[90];//contains all beaten elements beaten by this element }ele[90]; here is the modified code :- http://ideone.com/FqnSq On Mon, Sep 3, 2012 at 8:10 PM, sangeeta goyal sangeeta15...@gmail.comwrote: @Darpan can you implement it without using the multimap and with the same (divide and conquar) approach. On Mon, Sep 3, 2012 at 6:25 PM, Darpan Baweja darpan.bav...@gmail.comwrote: hope this might helps code:- http://ideone.com/mtHem used divide and conquer approach and stored all the beaten elements in the multimap with key is the element which has beaten them with key as winner return maximum element stored in multimap On Mon, Sep 3, 2012 at 3:31 PM, sangeeta goyal sangeeta15...@gmail.comwrote: @bharat is it tournament method?? On Mon, Sep 3, 2012 at 2:34 PM, bharat b bagana.bharatku...@gmail.comwrote: Construct a max-heap -- O(n).. call delete() 2 times .. -- O(logn).. === O(n) time.. On Fri, Aug 31, 2012 at 1:46 AM, Don dondod...@gmail.com wrote: While the list length is more than one Take 2 elements from the head Select the larger of the two If the smaller is greater than the largest beaten by the larger Then set the largest beaten by the larger to the value of the smaller Add the larger to the tail of the list When this completes, you'll have one element containing the largest and second largest values. typedef struct { unsigned int value; unsigned int largestBeaten; } element; unsigned int secondLargest(queueelement elements) { while(elements.length() 1) { element A = elements.dequeue(); element B = elements.dequeue(); if (A.value B.value) swap(A,B); if (A.largestBeaten B.value) A.largestBeaten = B.value; elements.enqueue(A); } return queue.head().largestBeaten; } On Aug 30, 12:53 pm, sangeeta goyal sangeeta15...@gmail.com wrote: @Don can you give the algorithm for the same?? how would you implement it?? On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote: The second largest element is the largest element beaten by the winner. So if you implement a tournament in which each element keeps track of the largest element it has beaten, you'll get the second largest naturally. Don On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote: give the algo or program to find second largest element in a list using tournament method -- 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. -- *DARPAN BAWEJA* *Final year, I.T* *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. -- *DARPAN BAWEJA* *Final year, I.T* *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
Re: [algogeeks] MS Question: Segregrate positive and negative nos in array without changing order
, Bhaskar Kushwaha Student Final year CSE M.N.N.I.T. 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. -- Utsav Sharma, 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. -- regards, Bhaskar Kushwaha Student Final year CSE M.N.N.I.T. 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. -- *DARPAN BAWEJA* *3rd year, I.T* *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 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: Question asked in Amazon online test
i think it can be done in O(n) for each 1, calculate no. of zeros in right and adding all no. of zeros in right of all 1's will give no. of swaps. correct me if i am wrong On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh singhsourab...@gmail.comwrote: @deepika yes, it's giving number of swaps. still Linear time solution would be better :-) On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com wrote: will bubble sort give number of swaps?? I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5 and for the array (0,0,1,0,1,0,1,1)swapcount = 3 -- 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. -- *DARPAN BAWEJA* *3rd year, I.T* *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 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: amazon interview questions
@ashish:- geke is valid as repeated substrings should be immediate. On Wed, Jun 6, 2012 at 1:44 PM, Hassan Monfared hmonfa...@gmail.com wrote: geke is valid. BTW if you changeif(i=len) toif(i0) my code outputs geke is invalid.( what you desired) if geke is invalid regarding to the question, then you can achieve the answer in nLogn by sorting strings :s[0..n-1], s[1..n-1],s[n-1..n-1] and comparing adjacent members. Regards On Wed, Jun 6, 2012 at 11:52 AM, atul anand atul.87fri...@gmail.comwrote: nope geke is valid string.. here is the link from where question was taken http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote: Hassan geke should not be a valid string. The question states which have the same substring following it so here e follows e. There is no precondition that it has to follow immediate. Utsav: can you clarify? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.comwrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.com wrote: for -- 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. -- Regards Lomash Goyal * * -- 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. -- *DARPAN BAWEJA* *3rd year, I.T* *MNNIT Allahabad* -- You received
Re: [algogeeks] Microsoft interview question
@atul:- why we require 1st condition(check sum of the square of arr1 = arr2) ?? On Sun, May 20, 2012 at 1:10 PM, atul anand atul.87fri...@gmail.com wrote: it can be done by doing set of operation on the data. 1) check sum of the square of arr1 = arr2 2) sum of elements of arr1=arr2 3) xoring elements of arr1 and arr2 == 0 if all 3 condition are successful then..permutation found. On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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. -- *DARPAN BAWEJA* *3rd year, I.T* *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 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.