Re: [algogeeks] array question
I think you can use heap. Thanks, Sathaiah On Wed, Jul 21, 2010 at 12:06 PM, divya sweetdivya@gmail.com wrote: Given an array A of N elements, where N approaches infinity, there are S elements in it where SN. WAP to insert an element at A[S] if it does not exist in A[0S-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] a google question
consider these arrays: 10 9 8 5 3 2 1 and 13 12 11 10 9 8 7 form a grid like this: 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 109 8 5 321 7 17 1615 *1210 98* 8 18 1716 *1311 10 9* 9 19 1817 *1412 12 10* 10 20 1918 *1513 12 11* 11 *21 2019* 1614 13 12 12 *22 2120* 1715 14 13 13 *23 2221* 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Till this point it takes constant time. Now the first column of the L formed is sorted. So is the 2nd column. So is the horizonal part of L which is comprized of two sorted arays (20-13) and (21-14). All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the biggest n elements. On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal ankur.mast@gmail.comwrote: this ques was asked by google.. i* could find any gud soln than order n*n -- 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. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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] a google question
im sry the L should look like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 I missed a row in the last mail. On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas topojoy.bis...@gmail.comwrote: consider these arrays: 10 9 8 5 3 2 1 and 13 12 11 10 9 8 7 form a grid like this: 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 109 8 5 321 7 17 1615 *1210 98* 8 18 1716 *1311 10 9* 9 19 1817 *1412 12 10* 10 20 1918 *1513 12 11* 11 *21 2019* 1614 13 12 12 *22 2120* 1715 14 13 13 *23 2221* 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Till this point it takes constant time. Now the first column of the L formed is sorted. So is the 2nd column. So is the horizonal part of L which is comprized of two sorted arays (20-13) and (21-14). All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the biggest n elements. On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal ankur.mast@gmail.com wrote: this ques was asked by google.. i* could find any gud soln than order n*n -- 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. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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] os problem
But you dont need a swap filesystem right? On Thu, Jul 22, 2010 at 8:41 AM, Anand anandut2...@gmail.com wrote: Yes you do need virtual memory even if you have 4GB of RAM. Because if you do not have virtual memory, you could not have uniform addressing. and that prevents you creating the final elf file for each process. B'cos while compiling the program you don;t know the actual physical address your program is going to reside during execution. On Tue, Jul 20, 2010 at 11:46 AM, divya sweetdivya@gmail.com wrote: You have 4GB ram, and at any time you have only 2 processes of 10mb each. so do you need any virtual memory for it? -- 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. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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: Adobe Strings matching Puzzle.
@all:pls make use of KMP algorithm...because knuth morris prat algor On Wed, Jul 21, 2010 at 6:16 PM, anugrah anugrah.agra...@gmail.com wrote: Stack can be used to push the characters of the string A and then popped off while scanning through the string B until there is a difference in the character read from the string B and the one popped off from the stack.. On Jul 20, 4:40 pm, agnibha nath agni.fl...@gmail.com wrote: You can try rabin-carp.. On Jul 20, 4:18 pm, mallesh mallesh...@gmail.com wrote: We are given two strings. A and B. First few letters of A match with Last letters of B. We have to find the longest match in linear time. Example: char * A =This is my first post to this group; char *B= to this group this is my post; Algorithm should return starting position of substring to this group in string A. How do we do this? -Thanks and regards, Mallesh -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Interview Nagarro.................
Hello everybady, my question is:- Find the maximum length Subsequence in the given Array that contains only 0's and 1's elements and condition is that number of 1;s equal to the number of 0's. Ex:- Input:- 10101011100 output:-101010111000 -- 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] interview microsoft............
Qn:-in the given array elements a1a2a3a4..anb1b2b3b4...bnc1c2c3c4cn without take a extra memory how to merge just like? a1b1c1a2b2c2a3b3c3anbncn -- 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] Interview Nagarro.................
algo- traverse the list from the end to find the 1. let the index of last 1 be x. count=0; while(i not equal to x or array_length ) if(a[i]==1)count++; else count--; print the value i++; while(--count) printf(%d,a[i++]); On Thu, Jul 22, 2010 at 5:53 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote: Hello everybady, my question is:- Find the maximum length Subsequence in the given Array that contains only 0's and 1's elements and condition is that number of 1;s equal to the number of 0's. Ex:- Input:- 10101011100 output:-101010111000 -- 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] interview microsoft............
123456789 then interchange middle one of 123 and 456 12 43 56 789 now exchange in pairs except first and last i.e. 24 -42, 35-53 1 42 53 6 789 now treat 14 as single number, 25 as single number ans 36 as single number and again apply this logic 14257 36 89 14 725 836 9 need time to program this, a bit busy... done :) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Jul 22, 2010 at 5:58 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote: Qn:-in the given array elements a1a2a3a4..anb1b2b3b4...bnc1c2c3c4cn without take a extra memory how to merge just like? a1b1c1a2b2c2a3b3c3anbncn -- 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] find k-th maximum in an unsorted array
Write an algo (in less than O(n^2)) to find k-th maximum in an unsorted array of integers. -- 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] find k-th maximum in an unsorted array
you can sort them(in O(n log n)) then find it . this is O(nlog n) or you can use selection problem ,by this you can solve it in O(n) ! look at the chapter Medians and Order Statistics in CLRS book,, --- On Thu, 7/22/10, Tech Id tech.login@gmail.com wrote: From: Tech Id tech.login@gmail.com Subject: [algogeeks] find k-th maximum in an unsorted array To: Algorithm Geeks algogeeks@googlegroups.com Date: Thursday, July 22, 2010, 8:53 PM Write an algo (in less than O(n^2)) to find k-th maximum in an unsorted array of integers. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Get the number of pairs of “ones” in a given integer. Eg: if the integer is 7 (binary: 0111), th en the number of pairs of ones is 2
Get the number of pairs of “ones” in a given integer. Eg: if the integer is 7 (binary: 0111), then the number of pairs of ones is 2 -- 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] Interview Nagarro.................
this can be done in O(n) time and O(n) space: let count = the number of 1s seen so far - the number of 0s seen so far so for each element if it is 1 then count++ and if it is 0 count-- (count is 0 at first ) make a map m[] such that m[i] is null if count was never equal to i else it is the index of the first place where count was equal to i so at each step if m[count] is not null this means that the index we are on - m[count] is a subsequence such that number of 0s and 1s is equal the maximum over length of all such subsequences would be the result here's a code for it note: count can be at least -n and at most n so the size of m must be 2n+1 so i shifted all by n and -1 here means null codepad.org/9zth8Uzl -- 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] Get the number of pairs of “ones ” in a given integer. Eg: if the integer is 7 (binary: 011 1), then the number of pairs of ones is 2
#includestdio.h
main()
{
unsigned num;
int ctr=0;
printf(Enter the number: );
scanf(%d,num);
while(num)
{
if( (num 1) ((num 1) 1) )
{
ctr++;
num=1;
}
else
{
num=1;
}
}
printf(number of pair: %d ,ctr);
}
On Fri, Jul 23, 2010 at 12:39 AM, vijay auvija...@gmail.com wrote:
Get the number of pairs of “ones” in a given integer. Eg: if the
integer is 7 (binary: 0111), then the number of pairs of ones is 2
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
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] You have 2 arrays of integer. You have to write a function, which take an integer as input and returns bool. Example array 1 has {1,5,10} array 2 has {2,5,9}. Func(3) should return t
Assuming that both the array are sorted.
For all elements of array1
Pick up an element from array1.
Subtract that element from the number passed.
The difference you got search that number in second array using binary
search.
If elements found come out of the loop and return 1 else return 0.
I think this approach will take O(nlogn) time.
If the array are not sorted then use linear search. Then this approach will
take O(n^2) time.
On Fri, Jul 23, 2010 at 12:01 AM, vijay auvija...@gmail.com wrote:
You have 2 arrays of integer. You have to write a function, which take
an integer as input and returns bool. Example array 1 has {1,5,10}
array 2 has {2,5,9}. Func(3) should return true, since 1 (from array
1) +2 (from array 2) =3 ( i.e summation of 2 numbers (1 from each
array) is equal to 3). Func(13) should return false
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
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] random clicks
A website has n questions. If you're shown one random question per click, prove that it takes O(n log n) clicks on avg to see all questions. How should I approach this problem. This sounds easy but till now I am not able to get any headway. Any help is appreciated. Thanks. -- 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] Let us be descriptive
Hi All, I am very proud of this group and continuously learn a lot from all the members. But at times, I am not able to make out even the language of the question or the answer. This happens because of grammar and spelling mistakes, steps left in answer description etc etc. As a very humble request, we can make this group much better if the following guidelines are followed: 1) Please spend some time on the language of the question/answer. In the real world, only the solution does not matter. How well it is put forward also matters a lot. If no one can make sense of your text (due to spelling/grammar mistakes also), it will be rejected. However good it is. 2) If possible, please provide 1-2 examples for your question/answer (both). An example makes sure that the reader understands the question. And it also makes sure that the solution provider has tested his algo for at least one case. 3) Please be descriptive. It is much easier to understand english than code. 4) Heading of a message should give hint to the question and then the first message in a discussion should give full details to the problem. Please do not put a giant string in the heading itself which ruins not only that discussion but surrounding ones also. 5) Comments in code are worth gold. They raise the coder's respect a lot in the eyes of code readers. My only interest is to make the posts more fruitful for all of us. Please forgive if anything above sounds bad and do point out the same. Thanks for your time to read above, Techi -- 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] You have 2 arrays of integer. You have to write a function, which take an integer as input and returns bool. Example array 1 has {1,5,10} array 2 has {2,5,9}. Func(3) should return t
Let argument of function Func is k.
Case 1: If at least on of the array is sorted (say array1) then.
For each number in array2, do
1. binary search for (k - array1[i]) in array1
2. if found
return true.
else
return false
case 2: Arrays are not sorted then
1. Sort one array and apply algo for case 1.
Time complexity will be sizeof(unsortedarray)log (sizeofsortedarray).
Regards,
Shafi
On Fri, Jul 23, 2010 at 12:01 AM, vijay auvija...@gmail.com wrote:
You have 2 arrays of integer. You have to write a function, which take
an integer as input and returns bool. Example array 1 has {1,5,10}
array 2 has {2,5,9}. Func(3) should return true, since 1 (from array
1) +2 (from array 2) =3 ( i.e summation of 2 numbers (1 from each
array) is equal to 3). Func(13) should return false
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little longerUS
Army
--
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] find k-th maximum in an unsorted array
You can use algorithim for finding median in unsorted array.
int medianofUnsortedArray(int a[], int low, int high, int rank){
int l, h, pivot;
int temp;
pivot = l = low;
h = high;
if(l=h){
while(lh){
while(a[l] = a[pivot]) l++;
while(a[h] a[pivot]) h--;
temp = a[h];
a[h] = a[l];
a[l] = temp;
}
temp = a[h];
a[h] = a[pivot];
a[pivot] = temp;
}
if(rank h){
medianofUnsortedArray(a,low,h-1,rank);
}else if(rank h){
medianofUnsortedArray(a,h+1,high,rank);
}else{
return a[h];
}
}
/*
1.
pivot = l
a[piv] if(a[pivot]p[l])--h
| |
- - - - - - - - --- - -- - - - - - - - - -
|
l++ -- if(a[pivot]p[l])
2.
l=h
+ - - - - - - - - - - - - - - = - - - - -
3. swap(a[pivot],a[h])
---+
| rank |
= - - - - - - - - # - --- - - + - - - - -
||
+-
*/
On Thu, Jul 22, 2010 at 10:35 PM, jalaj jaiswal
jalaj.jaiswa...@gmail.com wrote:
use selection algorithm
On Thu, Jul 22, 2010 at 9:53 PM, Tech Id tech.login@gmail.com wrote:
Write an algo (in less than O(n^2)) to find k-th maximum in an
unsorted array of integers.
--
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.
--
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little longerUS Army
--
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] find k-th maximum in an unsorted array
make a min heap of first k elements and check if the next coming numbers and update heap accordingly. al last root of heap will give result. O(nlogk-k(k-1)/2) -- 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] find k-th maximum in an unsorted array
hey this question was discussed earlier rite???pls make use of Selection algorithm...i think the worst case is O(n+logn). http://en.wikipedia.org/wiki/Selection_algorithm On Thu, Jul 22, 2010 at 9:53 PM, Tech Id tech.login@gmail.com wrote: Write an algo (in less than O(n^2)) to find k-th maximum in an unsorted array of integers. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
