Re: [algogeeks] a google question
This problem has been discussed before @
http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1aa8cf1ed437/d451cd9468d985f7
I believe, the problem can't be solved in O(n) but only in O(nlog n).
@Divya: Are you sure the interviewer explicitly asked for an O(n) time
algorithm?
On Sun, May 2, 2010 at 1:48 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
@divya You're rite. Post a solution if you have one.
--
Regards,
Vignesh
On 2 May 2010 13:14, divya jain sweetdivya@gmail.com wrote:
@Mohit
according to ur algo if a[1], b[0] has sum greater than a[0],b[1]
then i is incremented i is now 2 so for next iteration u ll compare a[2]
b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever. think
for ths case also.
On 2 May 2010 11:22, mohit ranjan shoonya.mo...@gmail.com wrote:
@Algoose Chase
point taken
Thanks
Mohit Ranjan
Samsung India Software Operations.
On Sat, May 1, 2010 at 8:43 PM, Algoose Chase harishp...@gmail.comwrote:
@mohit
The idea of DP is fine.
When you find the Max i dont think you need to include A[i+1]+B[j+1]
because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1] since
both the lists are sorted in decreasing order.
On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan
shoonya.mo...@gmail.comwrote:
oops
Sorry didn't read properly
last algo was for array sorted in ascending order
for this case, just reverse the process
A[n] and B[n] are two array
loop=n, i=0, j=0;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of first index from both array will
be max
foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using
DP, moving forward
if foo==A[i+1]+B[j]; i++ // only increment A
if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B
if foo==A[i]+B[j+1]; j++ // increment only B
}
Mohit Ranjan
Samsung India Software Operations.
On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan shoonya.mo...@gmail.com
wrote:
Hi Divya,
A[n] and B[n] are two array
loop=n, i=n-1, j=n-1;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of last index from both array will
be max
foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using
DP moving backward
if foo=A[i-1]+B[j]; i-- // only reduce A
if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B
if foo=A[i]+B[j-1]; j-- // reduce only B
}
Time: O(n)
Mohit Ranjan
On Fri, Apr 30, 2010 at 5:35 PM, divya sweetdivya@gmail.comwrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of
such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
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.
--
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.
--
There are two kinds of people. Those who care for others and The others
--
You received this message because you
Re: [algogeeks] Inorder traversal on binary tree
Read about B+ trees. It might help. On Sat, Nov 28, 2009 at 1:53 PM, Nayn nayanish.hi...@gmail.com wrote: Hi, We have to find inorder traversal on a binary tree whose leaf nodes are connected in a singly circular linked list. The tree might not be a complete binary tree. Thanks Nayn -- 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. -- Shishir Mittal Ph: +91 9936 180 121 -- 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: optimum algo for second largest
On Mon, Oct 12, 2009 at 1:29 PM, ankur aggarwal ankur.mast@gmail.comwrote: @shishir can u give the ds data structure used is a binary tree, with each node key being the maximum of its two children's key values. Space complexity of implementation of tournament principle is O(n). how would u save the history part (save the data that was rejected by the highest element in order to get the 2nd highest) extra space will b required.. :( I don't think that the problem statement suggest any constraint in the memory. The only objective is to reduce the number of comparisons to n + ceil(log n) - 2 from (n-1 + n-2) comparisons that would be required in case of a naive algorithm where one first finds the maximum and then finds the maximum of the remaining elements of the array. -- Shishir Mittal Ph: +91 9936 180 121 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: optimum algo for second largest
It has been discussed here http://groups.google.com/group/algogeeks/browse_thread/thread/5a3ccc1bfb4617fa/885438e251ffd330?lnk=gstq=second+highest+element#885438e251ffd330 On Sun, Oct 11, 2009 at 8:21 PM, Manisha pgo...@gmail.com wrote: First find out the largest element and it requires n-1 comparison. Lets say we have 8 elements then we need 7 comparison to decide largest. Imagine the tree structure that you will use to find out largest. 21 15 21 9 15 8 21 2 9 11 15 7 89 21 Notice that second largest will be be smaller than largest and larger than any other item in the list. So it is sure that second largest will loose in comparison with largest. Hence Second largest will be searched only with the items that got compared with largest item. Number of items that got compared with largest is logn(height of tree). logn-1 comparison is needed to find largest among them. Total comparison to find second largest = (n-1) + (logn-1) On Oct 10, 11:52 pm, sankalp sankalpmishr...@gmail.com wrote: can anyone give me algorithm for finding the second largest element in array using tournament method requiring n+logn-2 compariso -- Shishir Mittal Ph: +91 9936 180 121 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: second highest elemt in an aary
On Tue, Sep 29, 2009 at 10:14 AM, harit agarwal agarwalha...@gmail.comwrote: in my codei am doing the same thing the winner is compared to the new player and saved as winner and previous winner is also stored in another variable...so comparisions r same. The problem is your code doesn't provide correct results. Try to dry run the code for some more test cases like ( 4 3 2 1) , ( 3 1 3 2). Refer Introduction to Algorithms, II Ed. (Cormen) Exercise 9.1-1 and the preceding discussion for more info regarding tournament principle. -- Shishir Mittal Ph: +91 9936 180 121 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: second highest elemt in an aary
Here is a pseudo code.
Let the array be A[0..N-1].
Consider array B [0..2*N-2]. This array contains all the elements of the
binary tree formed from the tournament.
h = ceil ( log(N) base 2 ).
p = pow(2,h);
for( i=p-1,k=0; i2N-1 ; i++,k++)
B[i] = A[k];
for(i=p-2, m =N-1; m=k ; m--,i--)
B[i] = A[m];
for(i=p ; i=2N-2 ; i+=2) {
B[i/2 - 1] = max(B[i], B[i-1]);
}
for(i=p/2 ; i=2 ; i=i/2)
{
for ( k = 0;k i ;k+=2)
{
B[ (k+i)/2 -1 ] = max( B[i+k], B[i+k-1]);
}
}
B[0] now contains the largest element.
Total no of comparisons done till now = N-1
Consider array C[0..h-1] . This contains all the candidates for second
largest element.
for(i=0, k=0;i2N-1 ;k++ )
{
if( B[i] == B[2i + 1]) {
C[k] = B[2i+2];
i = 2i+1;
}
else
{
C[k] = B[2i + 1];
i = 2i + 2;
}
}
Now, the largest in the array C can be found in h-1 comparisons.
Total overall comparisons = (N -1) + (h-1), as required.
On Fri, Sep 18, 2009 at 9:54 PM, Nagendra Kumar nagendra@gmail.comwrote:
I want an algo for finding second highest element in n + log n- 2
comparisons.
The algo is first find the highest number and then highest among the
number which get defeated during tournament.
(details in corment).
Can anyone do code implemenation for this one.
Thanks
Nagendra
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: second highest elemt in an aary
Here is a pseudo code.
Let the array be A[0..N-1].
Consider array B [0..2*N-2]. This array contains all the elements of the
binary tree formed from the tournament.
h = ceil ( log(N) base 2 ).
p = pow(2,h);
for( i=p-1,k=0; i2N-1 ; i++,k++)
B[i] = A[k];
for(i=p-2, m =N-1; m=k ; m--,i--)
B[i] = A[m];
for(i=p ; i=2N-2 ; i+=2) {
B[i/2 - 1] = max(B[i], B[i-1]);
}
for(i=p/2 ; i=2 ; i=i/2){
On Fri, Sep 18, 2009 at 9:54 PM, Nagendra Kumar nagendra@gmail.comwrote:
I want an algo for finding second highest element in n + log n- 2
comparisons.
The algo is first find the highest number and then highest among the
number which get defeated during tournament.
(details in corment).
Can anyone do code implemenation for this one.
Thanks
Nagendra
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: second highest elemt in an aary
On Mon, Sep 28, 2009 at 11:56 AM, harit agarwal agarwalha...@gmail.comwrote:
It will take n comparisons.observe this code
The code fails for the input 4 3 2 1.
#includeiostream
using namespace std;
int sec_largest(int ar[],int n)
{
int i,max=-32767,sec_max=0;
for(i=0;in;i++)
{
if(ar[i]max)
{
sec_max=max;
max=ar[i];
}
}
return sec_max;
}
main()
{
int n,i,res;
coutenter number of elements\n;
cinn;
int ar[n];
for(i=0;in;i++)
cinar[i];
res=sec_largest(ar,n);
coutsecond largest number=resendl;
}
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: What algorithm can be used to decide the denomination of notes in an ATM machine?
Let the denominations be D[] = {1000,500,100},
and amount be N.
Let C[] , denotes the count of each denomination.
for ( i=0 ; i 2 ; i++) {
C[i] = (N-1)/D[i] ;
N = N - D[i]*C[i] ;
}
C[2] = N/D[2] ;
For N=4800, C[] = {4, 1, 8}
For N= 2000, C[] = {1, 1, 5}, as required.
Nice observation :) .
PS: Its the Newton who appreciated the falling apple. There aren't many who
really appreciate the happenings from our normal life. [?]
On Sat, Sep 19, 2009 at 11:50 PM, eSKay catchyouraak...@gmail.com wrote:
for example: if I draw 2000, what I get is
1000+500+100+100+100+100+100.
What algorithm can be used to decide how to break up the entered
amount?
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
inline: 329.gif
[algogeeks] Re: Z[n^2]={such that z belongs to X+Y
On Fri, Sep 18, 2009 at 6:20 PM, Mangal Dev Gupta dev.it...@gmail.comwrote:
@mittal
I am not able to understand . How are you updating the C
array?..You didnt tell what will be the updated array after second
element?Please elaborate...
Size of array C is same as that of X, i.e. n.
It contains the indices of array Y, with whom the elements of X are to be
summed and all the values compared to find the minimum.
At mth iteration, the required smallest element corresponding to array Z,
Z[m] = min { X[i] + Y[C[i]] }, 0=in,
The i for which, the minimum occurs, update C[i] = C[i]+1.
In the proposed algorithm, searching for minimum element is done using min
heap.
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Z[n^2]={such that z belongs to X+Y
A correction in the proposed algorithm.
On Tue, Sep 15, 2009 at 1:08 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
*Algorithm.*
1) Corresponding to each element in X, create a node with 2 values, to be
compared indexed of Y, and the corresponding sum.
NODE[i] = {yIndex, sum = X[i] + Y[yIndex]}
*Corresponding to each element in X, create a node with 3 values, xIndex,
corresponding yIndex, and the corresponding sum.
NODE[i] = {xIndex = i, yIndex=0, sum = X[xIndex] + Y[yIndex]}*
2) Form a MinHeap of the nodes.
3) Increment the yIndex of the root node of heap and also the corresponding
sum value.
4) Min Heapify this array of nodes, with key as sum value.
5) Repeat steps 3 and 4, k-2 times.
6) sum value of root node is the required answer.
Space Complexity : O(n),
Time Complexity : O(n + (k-1)logn).
For k = n, Time complexity : O(nlogn).
--
Shishir Mittal
Ph: +91 9936 180 121
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Z[n^2]={such that z belongs to X+Y
Considering a general case of two sorted arrays X[n], Y[m] , n=m and kth
element is requied in the set Z = {x+y, such that x is in X[], y is in
Y[]}, here is an algorithm which takes *O(n + klogn) time and O(n) space.*
So I guess, if k=n, this time complexity is better than O(kn).
*Logic*: Let we are trying to find k smallest elements. Then, at each
iteration i k,* we can at maximum have n options to choose the ith element
*. For e.g.
Let X[3] = {3, 5, 8}
Y[8] = {1, 2, 4, 5, 7, 9, 11, 12}.
And we need to find 8th element.
Initialize an array C[3] = {0,0,0}. C denotes the array indices in array Y,
which are to summed with corresponding elements in X and compared.
So for comparison of 1st element in Z, we have 3 options ( X[0] + Y[0],
X[1]+Y[0], X[2]+Y[0] ). 4 is the answer
Next update the array C = {1,0,0}, now 2nd element is min of ( X[0]+Y[1],
X[1] + Y[0], X[2] + Y[0] ), 5 is the answer.
Continuing similarly, for the 8th element, array C is {4,3,0} so the 8th
element is minimum of ( X[0] + Y[4], X[1]+ Y[3], X[2] + Y[0] ), which is 10.
*Algorithm.*
1) Corresponding to each element in X, create a node with 2 values, to be
compared indexed of Y, and the corresponding sum.
NODE[i] = {yIndex, sum = X[i] + Y[yIndex]}
2) Form a MinHeap of the nodes.
3) Increment the yIndex of the root node of heap and also the corresponding
sum value.
4) Min Heapify this array of nodes, with key as sum value.
5) Repeat steps 3 and 4, k-2 times.
6) sum value of root node is the required answer.
*Space Complexity : O(n),
Time Complexity : O(n + (k-1)logn).*
*For k = n, Time complexity : O(nlogn)*.
However, in the above method, I found out the k smallest elements in Z in
sorted order, even though only the kth element was asked.
Hence, I believe there is still some scope of optimization!
On Fri, Sep 4, 2009 at 10:33 PM, ankur aggarwal ankur.mast@gmail.comwrote:
Find nth smallest inO(n) Given two arrays of length n in sorted order
X[n] Y[n].
Now make another array Z[n^2]={such that z belongs to X+Y}.
AS all possible sum of x+y is there in Z. You have to give the nth smallest
no of Z in O(n) time.
Space complexity : No bound on it. But try to optimize it if possible.
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: addition without using arithmetic operators
On Tue, Sep 8, 2009 at 2:09 AM, ayush chauhan therajput.ay...@gmail.comwrote:
Cud u plz explain the logic behind this?
On Mon, Sep 7, 2009 at 9:44 PM, Gokul spgo...@gmail.com wrote:
you can try this..
int add(int x, int y)
{
if (!x) return y;
else
return add((x y) 1, x ^ y);
}
Lets consider you want to add 34590 and 987387065 in decimal notation.
9 8 7 6 8 7 0 6 5
+ 3 4 5 5 9 0
---
9 8 7 9 2 2 5 5 5 addition of digits neglecting carry
+ 0 0 0 1 1 0 1 0 0 --- represents carry
--
9 8 7 0 3 2 6 5 5
+ 0 0 1 0 0 0 0 0 0
---
9 8 8 0 3 2 6 5 5
+ 0 0 0 0 0 0 0 0 0
So ans is 988032655.
Similarly, In terms of bit representation, for addition of two numbers 'x'
and 'y', (xy)1 represents the carry number and x^y represents the number
neglecting the carry. So for example let the number is 43 14.
x = 43 = 1 0 1 0 1 1
y = 14 = 0 0 1 1 1 0
1 0 1 0 1 1
+ 0 0 1 1 1 0
--
1 0 0 1 0 1 --- x^y
+ 0 1 0 1 0 0 --- (xy)1
--
1 1 0 0 0 1
+ 0 0 1 0 0 0
--
1 1 1 0 0 1
+ 0 0 0 0 0 0
--
hence 43 + 14 = 111001 = 57
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: minimum difference.
Sort the array and find the minimum of difference of adjacent values of the sorted array. Time Complexity : O(nlogn), Space Complexity : O(1) On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal ankur.mast@gmail.comwrote: given a array of length n. find 2 number such that their differnce is minimum. -- Shishir Mittal Ph: +91 9936 180 121 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Median Finding algorithms.
@Nagendra : As earlier told Refer Pg 189, Cormen, an algorithm is given to
find the Kth largest element in O(n) *worst* time complexity.
@Dufus: yeah, am pretty sure that the algorithm I have described results in
K closest elements to median.
For e.g. Let the array be 2 5 7 10 11 14 19 45 121 i.e. n= 9 elements and 5
closest medians are required.
First determine the median in O(n) time using Linear general selection
algorithm - Median of Medians
algorithmhttp://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22by
looking for 5th largest element in the array.
Median = 11.
int compare (int a, int b, int median){
return ( abs(median - a) - abs(median - b)) ;
}
Rest of the task is similar to first finding the (k)th smallest element in
the array
|2-11|, |5-11|, |7-11|, |10-11|, |11-11|, |14-11|, |19-11|, | 45-11|,
|121-11|
i.e. 9, 6, 4, 1, 0, 3, 8, 34, 110
and then partitioning the array around the pivot and returning the first k
elements as the solution.
Storing the above array in O(n) space and then performing the task would
have ease the task but if space is a constraint (constant space), compare
function described above can be used.
Working for constant space,
Using the compare function, let ** the first recursive call SELECT(arr, 0,
8, 5) *for e.g* does partitioning for index 2.
The partitioned array for pivot arr[2] = 7 is
(10, 11, 14) 7 (2, 5, 19, 45, 121) (order of elements in the bracket may
vary depending upon coding).
equivalent to (1, 0, 3,) 4 ( 9, 6, 8, 34, 110) for O(n) space case.
so 7 is the 4th smallest element.
the above calls SELECT (arr, 4, 8, 5 - 4)
which *ultimately* partitions the array into
(10 , 11, 14, 7,) 5 (2, 19, 45, 121)
equivalent to (1, 0, 3, 4,) 6 ( 9, 8, 34, 110) for O(n) space case.
the first 5 elements is the required answer.
Overall worst case time complexity : O(n), space complexity : O(1).
O(n) space simplifies the coding and understanding of the problem.
On Tue, Sep 1, 2009 at 6:04 PM, ankur aggarwal ankur.mast@gmail.comwrote:
@shishir
i could understand
cann u give an example..
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: 1 Trillion integers on hard disk, find the smallest 1 million of them
Build MAX-HEAP for first 1 million integers. For next elements in the array, if ele root node value, replace ele with root node value and apply MAX-HEAPIFY Time Complexity : NlogK , where N is total no of elements and K is the size of heap. Here N is 1 trillion and K is 1 million Space Complexity : O(K) On Tue, Sep 1, 2009 at 6:29 PM, ankur aggarwal ankur.mast@gmail.comwrote: * Q.3: Given a set of 1 Trillion integers on hard disk, find the smallest 1 million of them. You can fit at most 1 million integers in memory at a time. State the fastest solution you can think of. -- Shishir Mittal Ph: +91 9936 180 121 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Median Finding algorithms.
First find the median of the array in O(n) time using *'Linear general
selection algorithm - Median of Medians algorithm '* (
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22)
by finding (n+1)/2 smallest element (for odd n). You can also refer Pg 189,
Introduction of Algorithms , II edition (Cormen) for the algorithm.
Then apply the same algorithm to partition the array by locating the (k+1)th
smallest element. In the corresponding partition function instead of
directly comparing the values at two indexes use a compare function which
compares modulus of difference of the element and the median found ie
int compare (int a, int b, int median){
return ( abs(median - a) - abs(median - b)) ;
}
Overall time complexity : O(n), space complexity : O(1).
On Sun, Aug 30, 2009 at 8:36 PM, Dufus rahul.dev.si...@gmail.com wrote:
Is it acceptable if I
find the median in O(logn) time and then,
Can you elaborate how can we find the median of an unsorted array in O(log
n) time?
find k numbers closest to the median in O(k) space and O(n) time?
_dufus
On Aug 30, 4:38 pm, Nagendra Kumar nagendra@gmail.com wrote:
Given a set S of n distinct numbers and a positive integer k = n.
Determine the k numbers in S that are closest to the median of S.
Find an O(n) algorithm
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: nth number of k bits
Its a bit similar to finding the rank of the word COMPUTER in the
dictionary among the words formed from C,O,M,P,U,T,E,R.
Find maximum r such that (k+r)C(r) n.
This represents the total number of numbers formed from 'r' 0 bits and 'k' 1
bits. Since n is greater, it implies it has an extra 1 bit in its
representation.
The problem reduces to finding [n - (m+r)C(r)] smallest number than can be
formed with (k-1) 1 bits.
here is a recursive function to obtain the result.
int rec(int curr, int n, int k){
int r,j,comb,tmp;
if(n==1)
return curr+((1k) - 1); /* 1st number in the sequence with m bits. */
for(r =1,comb = 1; ; r++)
{
tmp = (comb*(k+r))/r; /* k+rCr = (k+r-1)C(r-1) x (k+r)/r*/
if(tmp == n)
return curr + (1(k+r)) - (1r); /* All the 'k' left most bits
should be 1 and rest 0 */
else if(tmp n)
return rec(curr+(1(k+r-1)), n-comb,k-1);
comb= tmp;
}
}
Call rec(0,n,k) to get the nth number of the series with 'k' bits set.
On Thu, Aug 27, 2009 at 12:28 PM, ankur aggarwal
ankur.mast@gmail.comwrote:
Nth number with K set bits
We are given with k number of set bits (bit=1). We have to find the Nth
number which has k set bits.
for example
k=3
the numbers with k set bits are as follows:
000111 = 7
001011 = 11
001101 = 13
001110 = 14
010011 = 19
010101 = 21
010110 = 22
011001 = 25
011010 = 26
011100 = 28
and so on
we have to find the Nth number in this series...
suggest some method
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: nth number of k bits
There were some errors in my solution.
On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
Its a bit similar to finding the rank of the word COMPUTER in the
dictionary among the words formed from C,O,M,P,U,T,E,R.
Find maximum r such that (k+r)C(r) n.
This represents the total number of numbers formed from 'r' 0 bits and 'k'
1 bits. Since n is greater, it implies it has an extra 1 bit in its
representation.
What I actually meant was Since n is greater than (k+r)C(r), it means that
the (k+r+1)th bit of nth number is 1
The problem reduces to finding [n - (m+r)C(r)]
its [n - (k+r)C(r)]
smallest number than can be formed with (k-1) 1 bits
(and 'r' 0 bits)
To elaborate this critical point. Here is an example.
Let k=4, n=7. i.e. we need to find the 7th number in the series of numbers
with 4 bits set.
Initial call rec(0, 7, 4)
(4+1)C(1) 7 (4+2)C(2)
Hence we get sure that (4+1+1)th bit of nth number is 1.
Req number - 1_ _ _ _ _
now call (0 + 32, 7-5,4-1)
(3+0)C0 2 (3+1)C1
So Req number- 1 0 1_ _ _
call (32 + 8, 2-1, 3-1)
(2+0)C0 = 1, hence last 2 bits should be 1
hence, Req Number - 1 0 1 0 1 1
Hence answer is 43.
.
here is a recursive function to obtain the result.
int rec(int curr, int n, int k){
int r,j,comb,tmp;
if(n==1)
return curr+((1k) - 1); /* 1st number in the sequence with m bits. */
for(r =1,comb = 1; ; r++)
{
tmp = (comb*(k+r))/r; /* k+rCr = (k+r-1)C(r-1) x (k+r)/r*/
if(tmp == n)
return curr + (1(k+r)) - (1r); /* All the 'k' left most bits
should be 1 and rest 0 */
else if(tmp n)
return rec(curr+(1(k+r-1)), n-comb,k-1);
comb= tmp;
}
}
Call rec(0,n,k) to get the nth number of the series with 'k' bits set.
On Thu, Aug 27, 2009 at 12:28 PM, ankur aggarwal ankur.mast@gmail.com
wrote:
Nth number with K set bits
We are given with k number of set bits (bit=1). We have to find the Nth
number which has k set bits.
for example
k=3
the numbers with k set bits are as follows:
000111 = 7
001011 = 11
001101 = 13
001110 = 14
010011 = 19
010101 = 21
010110 = 22
011001 = 25
011010 = 26
011100 = 28
and so on
we have to find the Nth number in this series...
suggest some method
--
Shishir Mittal
Ph: +91 9936 180 121
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
