Re: [algogeeks] Re: SUN Microsystem Question
@Dave, I think you meant* *MIN** Heap here? On Fri, Dec 24, 2010 at 6:46 PM, Dave dave_and_da...@juno.com wrote: @Bittu: Using the first 10 numbers, build a max heap. Then add each number into the 11th array position (always the 11th position) and perform the up-heap operation. At the end of the input, discard the 11th number in the heap. The remaining numbers will be the 10 maximum. O(n log k) where n = the number of items in the list and k = the number of maximum items you want. Dave On Dec 24, 3:32 am, bittu shashank7andr...@gmail.com wrote: You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That ...what is Time space Complexcity of Algorithm that you will usethen optrmize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyt eof memory may be reuqired so that should be avoided. Regards Shashank Mani Narayan Birla Instute of Technology,Mesra -- 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] Re: SUN Microsystem Question
@Dave, you are right. MAX Heap is correct for your always 11th position removal logic. . Satya On Fri, Dec 24, 2010 at 9:45 PM, Satya satya...@gmail.com wrote: @Dave, I think you meant* *MIN** Heap here? On Fri, Dec 24, 2010 at 6:46 PM, Dave dave_and_da...@juno.com wrote: @Bittu: Using the first 10 numbers, build a max heap. Then add each number into the 11th array position (always the 11th position) and perform the up-heap operation. At the end of the input, discard the 11th number in the heap. The remaining numbers will be the 10 maximum. O(n log k) where n = the number of items in the list and k = the number of maximum items you want. Dave On Dec 24, 3:32 am, bittu shashank7andr...@gmail.com wrote: You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That ...what is Time space Complexcity of Algorithm that you will usethen optrmize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyt eof memory may be reuqired so that should be avoided. Regards Shashank Mani Narayan Birla Instute of Technology,Mesra -- 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] Re: spy in the city
counter-agent can ask each person, did they know X( X is always him the counter agent). N-1 max questions. On Sun, Dec 19, 2010 at 8:16 PM, 王大东 dadongk...@gmail.com wrote: some conditions must be missed,I think. On Sun, Dec 19, 2010 at 10:40 PM, juver++ avpostni...@gmail.com wrote: It looks like this is a homework question. If no, send link to the original problem. -- 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. -- What are we to be? -- 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] BST sort
u need to write a recursive function. All leaf nodes in complete BST are from n/2+1n. n/2+1 element will be the beginning element(least left child) for our resultant sorted array. U can get the parent of the element by doing the floor(n/2/+1), get the right child of the parent by 2*(floor(n/2/+1))+1, do it recursively for its parent and so ... on till the parent index is 0 . Satya On Fri, Aug 6, 2010 at 3:37 PM, sharad kumar aryansmit3...@gmail.comwrote: perform inorder traversal...and store it in same array... On Thu, Aug 5, 2010 at 7:10 PM, AlgoBoy manjunath.n...@gmail.com wrote: sort a BST represented like an array...(similar to representation of HEAP) -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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] BST sort
typo! floor(n/2/+1) == floor((n/2/+1)/2) . Satya On Fri, Aug 6, 2010 at 5:27 PM, Satya satya...@gmail.com wrote: u need to write a recursive function. All leaf nodes in complete BST are from n/2+1n. n/2+1 element will be the beginning element(least left child) for our resultant sorted array. U can get the parent of the element by doing the floor(n/2/+1), get the right child of the parent by 2*(floor(n/2/+1))+1, do it recursively for its parent and so ... on till the parent index is 0 . Satya On Fri, Aug 6, 2010 at 3:37 PM, sharad kumar aryansmit3...@gmail.comwrote: perform inorder traversal...and store it in same array... On Thu, Aug 5, 2010 at 7:10 PM, AlgoBoy manjunath.n...@gmail.com wrote: sort a BST represented like an array...(similar to representation of HEAP) -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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] ipc
I think pipes are fastest as the other end process will be trying to read the from fds always(waiting for the input). semaphores,monitors all these need certain condition to meet so that they get ++/-- , notify. Signal's can be masked!!. . Satya On Wed, Jul 7, 2010 at 8:13 AM, sharad kumar sharad20073...@gmail.comwrote: @harit why pipes are fastest...plzz explain a bit -- 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] adobe problem---array
not to complicate the question, if it is sorted, then its simple!! . Satya On Wed, Jul 7, 2010 at 3:05 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: you have misinterpreted the questn.. 1 simply means 1 occurences we have to do this inplace On Wed, Jul 7, 2010 at 10:37 AM, Ashish Goel ashg...@gmail.com wrote: i thought the same way, but in this case 4 is being repeated twice, but is not nullified it is ctually getting nullified, but it is indeed contributing to bit 2 so how do i rule out 4 here? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 7, 2010 at 10:17 AM, Anand anandut2...@gmail.com wrote: if we xor all elements of the array, then the element which are repeated twice and multiple of two gets nullify and what left is the number which got repeated once and thrice. if we can find the number which got repeated once, then we can xor that number from the total xor value to get the element which got repeated thrice. On Tue, Jul 6, 2010 at 9:37 PM, Ashish Goel ashg...@gmail.com wrote: can i take this as a sample array? 1,1,2,2,3,3,4,4,4,5,5,5,5 or 1,2,3,4,4,5,5,5 ideally a bit map would suffice for identification of repeating numbers, but the memory requirements shoot up 0001 0010 0011 0100 0100 0101 0101 0101 xor result = 0101, how to proceed further..?? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jul 5, 2010 at 7:18 PM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times. can xor do something here ?? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT 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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT 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.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
See below links. Most of web applications(facebook,classmates) use memcached to speed up their sites. memcached uses hashing. http://memcached.org/ http://www.facebook.com/note.php?note_id=39391378919 http://memcached.org/http://en.wikipedia.org/wiki/Memcached . Satya On Fri, Jul 2, 2010 at 11:46 PM, sharad sharad20073...@gmail.com wrote: [1] Design a layer in front of a system which cache the last n requests and the responses to them from the system. what data structure would you use to implement the cache in the later to support following operations. [a] When a request comes look it up in the cache and if it hits then return the response from here and do not pass the request to the system [b] If the request is not found in the cache then pass it on to the system [c] Since cache can only store the last n requests, Insert the n+1th request in the cache and delete one of the older requests from the cache The objective is to achieve all the three operations in O(1). -- 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] Re: Array Problem
This problem seems to be finding the maxdiff in an array. int maxdiff ( int A[], int n ) { // write your code here int max_diff = A[1] - A[0]; int min_element = A[0]; int i; for(i = 1; i n; i++) { if(A[i] - min_element max_diff) max_diff = A[i] - min_element; if(A[i] min_element) min_element = A[i]; } if(max_diff 0) max_diff = 0; return max_diff; } . Satya On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote: i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- 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.
[algogeeks] Largest even length palindrome in a string!!
Hi, How to find largest palindrome, which is even in length in a string. Complexity should be lessthan O(n^2). Ex;- abacbbcababac - Given string. 'abacbbcaba' - is the largest even length palindrome. Thanks, Satya -- 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: help me with finding the time complexcity
since your input is of fixed size, your algorithm always runs in constant time. If the # of students and # of courses are variable, the algorithm is O(n^2). satya. On 5/28/07, sl7fat [EMAIL PROTECTED] wrote: hi i have an algorthim code and i have to find the time complixcity of the code so can you plz help me ASAP the code is written done ,, # include iostream.h void main() { int a[10][4]= {{ 16,17,19,13}, {18,14,15,19}, {18,20,20,19}, {13,14,15,10}, {20,17,19,19}, {18,13,18,19}, {18,10,15,12}, {12,14,15,11}, {12,16,17,18}, {18,11,15,10}} ; int i,j,max,min; float avg,sum; for(i=0;i10;i++) { for(j=0;j4;j++) { cout a[i][j] ; } cout \n; } for(i=0;i4;i++) { max= a[0][i]; min= a[0][i]; sum=0; for(j=1;j10;j++) { sum= sum+a[j][i]; if(a[j][i]max) max=a[j][i]; if(a[j][i]min) min=a[j][i]; } avg= sum/10; cout The average Grade for Exam i+1 is: avg\n; cout The minimum Grade for Exam i+1 is: min\n; cout The maximum Grade for Exam i+1 is: max\n\n; } for(i=0;i10;i++) { min= a[i][0]; sum=0; for(j=0;j4;j++) { sum= sum+a[i][j]; if ( mina[i][j]) min= a[i][j]; } sum= sum-min; cout The summation of the best 3 grades for student No i +1 is: sum\n; } } thanx alot :D -- ...what's remarkable, is that atoms have assembled into entities which are somehow able to ponder their origins. -- http://cs.uic.edu/~spopuri --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---