Re: [algogeeks] Re: a google question
@Algoose : No, it is not necessary that first n elements must contain A[0]
or B[0]. For e.g.
A = {40,30,15,10}
B = {40,30,15,10}
Required 4 largest values = {40+40, 40+30, 40+30, 30+30}.
@Satish:
A very nice algorithm provided by you.
Complexity Analysis for the algorithm provided by you:
Creation of max-heap of n elements = O(n).
Time to add a new element to the heap after extracting the maximum - O(log
n)
Overall Complexity = O(n log n)
Regards,
Shishir
On Sun, May 2, 2010 at 10:52 PM, Satish wrote:
> This problem can be simplified to a variation of merge part of merge
> sort algorithm.
>
> - Break the set S having n^2 values into n individual arrays of length
> n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn].
> - One can observe that each Si has entries which are themselves sorted
> within Si.
> - Perform merge of S1, S2,..Sn where take the largest values of each
> Si, and create a heap of these individual max values.
> - In each step, return the max value from heap and then add the next
> max value from the Si that had the current max value and add it in the
> max-heap.
> - Repeat this step n times and then exit.
>
> Time: O(n).
>
> Satish
>
> On May 2, 5:41 pm, Algoose Chase wrote:
> > Hi
> >
> > will this work ?
> >
> > since we need Set S with n pairs of largest values , any such pair within
> > the set would (always) contain A[0] or B[0] because they maximize the
> value
> > of the pair.
> >
> > so
> >
> > // code snippet
> > typedef std::vector Pairs;
> >
> > Pairs.push(A[0],B[0])
> > int i = 1; // index for ListA
> > int j = 1; // index for list B
> > count = 1;
> > while( count <= n)
> > {
> > if( A[0] + B[j] > B[0] + A[i] )
> > {
> > Pairs.push(A[0],B[j])
> > j++;
> > }
> > else
> > {
> > Pairs.Add(A[i],B[0])
> > i++;
> > }
> > count++;
> >
> > }
> >
> > since there are n items in both the lists, j and i wont go beyond n in
> the
> > while loop
> >
> >
--
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
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 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 wrote:
>>
>>> @Algoose Chase
>>>
>>> point taken
>>> Thanks
>>>
>>>
>>> Mohit Ranjan
>>> Samsung India Software Operations.
>>>
>>>
>>> On Sat, May 1, 2010 at 8:43 PM, Algoose Chase wrote:
>>>
@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
wrote:
> 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(loop>0) // 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 > wrote:
>
>> Hi Divya,
>>
>>
>> A[n] and B[n] are two array
>>
>> loop=n, i=n-1, j=n-1;
>>
>> while(loop>0) // 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 wrote:
>>
>>> 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.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.
>
--
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.
>>>
>>
>> --
>> You received this message because you are subscribed
Re: [algogeeks] Inorder traversal on binary tree
Read about B+ trees. It might help. On Sat, Nov 28, 2009 at 1:53 PM, Nayn 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.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 wrote:
> @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=gst&q=second+highest+element#885438e251ffd330 On Sun, Oct 11, 2009 at 8:21 PM, Manisha 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 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 wrote: > 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
On Mon, Sep 28, 2009 at 11:56 AM, harit agarwal wrote:
> It will take n comparisons.observe this code
>
>
> The code fails for the input 4 3 2 1.
> #include
> using namespace std;
> int sec_largest(int ar[],int n)
> {
> int i,max=-32767,sec_max=0;
> for(i=0;i {
> if(ar[i]>max)
> {
> sec_max=max;
> max=ar[i];
> }
> }
> return sec_max;
> }
> main()
> {
> int n,i,res;
> cout<<"enter number of elements\n";
> cin>>n;
> int ar[n];
> for(i=0;i cin>>ar[i];
> res=sec_largest(ar,n);
> cout<<"second largest number="<
> }
>
>
> >
>
--
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; i<2N-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 wrote:
>
> 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; i<2N-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;i<2N-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 wrote:
>
> 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: 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 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
-~--~~~~--~~--~--~---
<>
[algogeeks] Re: Z[n^2]={such that z belongs to X+Y
On Fri, Sep 18, 2009 at 6:20 PM, Mangal Dev Gupta wrote:
> @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<=ihttp://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 wrote:
> 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: 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.com>wrote:
>
>
> *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: addition without using arithmetic operators
On Tue, Sep 8, 2009 at 2:09 AM, ayush chauhan wrote:
> Cud u plz explain the logic behind this?
On Mon, Sep 7, 2009 at 9:44 PM, Gokul 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', (x&y)<<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 ---> (x&y)<<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: 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
algorithm"<http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22>by
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 wrote:
> @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 wrote: > > * 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: 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 wrote: > 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.
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 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 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
There were some errors in my solution.
On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal <1987.shis...@gmail.com>wrote:
> 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+((1< 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)) - (1< 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 > 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
-~--~~~~--~~--~--~---
[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+((1< 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
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
--~--~-~--~~~---~--~~
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: can any body help me in writing a C program find the reverse any given matrix
det(A) ! = 0 , for inverse to exist. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Finding cycles in a Linked List
@Kapil How do you intend to do a BFS in a linked list (its not a Bin Tree i suppose or a graph) @Pramod Can you please detail as to what does your program do? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: find pair in O(N)
Why do you want both the pairs to be printed? I guess the problem's originality is only in finding unique pairs summing to a particular number, so there's no point in printing repeating pairs. Besides, even if you want to do that, daizi's code can be altered quite simply to print repeating pairs. I guess you already are aware of the changes required in there. ~Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Insertion in a binary tree.
Thanks Narvi, for the idea. A simple counter at the start of the tree insertion keeping track of the strength of the tree, would be all that is required. ~Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Insertion in a binary tree.
@Karas Can you please take some time to brief us about the algo of your program. Thanks, ~Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Insertion in a binary tree.
Well, I was aware of BFS solution , but am looking for something more elegant than this. Does, any other method exist to do this. Thanks for your reply anyways ~Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Insertion in a binary tree.
Hi, I am looking for a method for left to right insertion in a binary tree( mind it, its not BST am talking about). A simple binary tree where every root has not more than two childs and the insertion is always done starting from the leftmost side of any given node. 13 / \ 27 54 / \ / \ 23 42 For eg in the above case the next node should be inserted as the left most child of 54. Let me know if there's any doubt regarding the question. ~Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Given an array of size n of 0 and 1 only sort it in linear time.
Errata: Should be j in place of i in the condition statement of the for
loop.
and arr[j]=0 should come before arr[i]=0;
Here's the correct code.
void sort(int arr[])
{
for(int i = 0, j = 0; jhttp://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Given an array of size n of 0 and 1 only sort it in linear time.
void sort(int arr[])
{
for(int i = 0, j = 0; ihttp://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: How to Sort a Stack in ascending order
I think the best possible thing is to do an insertion sort(using another stack)/bubble sort. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: frequent substring
sorry ! didn't get that. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: find pair in O(N)
Good one. -Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Assignment: Print reverse order
1.) For printing the integer in reverse order.
#include
main()
{
int i;
scanf("%d",&i);
while(i!=0)
{printf("%d",i%10);
i=(i-(i%10))/10;
}
getch();
}
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: check string A and B isPermutation ?
HI, how do you intend to use hash ( as in which hash function) to check if the hash keys generated for both A and B are equal. Thanks, Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Array subsequence of sum N.
.>>A consecutive series in the array? Is this really what you are looking for? I guess that's what I mentioned in my problem statement. Besides can u please brief me about your algo, i cant get it. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Array subsequence of sum N.
Given an array of integers and a number N, find if there exists a consecutive series of numbers in this array which sum up to N. Regards, Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
Well the formula works only for the corner end points as starting and ending node and that too on the diagonal ends. Its not a general formula for any set of starting/ending nodes. @Dhyanesh I think the problem clearly states that the nodes can only be traversed once i.e. no repetition. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
There's a small error in my formula. The formula holds for a NxM grid (N horizontal and M vertical lines) where N= n+1 and M = m+1, which essentially boils down to C(N+M-2, N-1) = C(N+M-2,M-1). This should work fine. -Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Subset with largest sum
Yes, am sorry, its infact the continous sub-sequence which I missed in the question. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Subset with largest sum
Hi, This is a standard MS interview question. Give an O(n) algorithm to find the subset of an array A[n] with largest sum. Anticipating a healthy and useful discussion on this. Thanks, Shishir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
For a nxm grid of nodes the no of possible paths between the two nodes each of them at a corner of the grid and under the constraint that a node should not be repeated is given by (n+m) C n = (n+m)!/(m!n!) = (n+m) C m. Is this what you are looking 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
