[algogeeks] remove redundantt parenthesis
write a program to remove redundantt parenthesis from an expression eg input ((a+b)) output a+b input a+(b*c) output a+b*c inputa*(b+c) output a*(b+c) -- 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: DP
Using standard Dynamic Programing logic:
http://codepad.org/IwBTor4F
On Thu, Oct 7, 2010 at 8:43 PM, Gene wrote:
> Nice problem. Let N_1, N_2, ... N_n be the values of the N notes.
> Let F(i,j) be the maximum possible score the current player can get
> using only notes i through j. Then
>
> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) )
>
> This is saying that the current player always makes the choice that
> minimizes B the best score that the other player can achieve. When we
> know that choice, the best _we_ can do is the sum of all the available
> notes minus B.
>
> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j)
> where i > j.
>
> For example, suppose we have notes 3 7 2 1 . The answer we want is
> F(1,4).
>
> Initially we have
> F(1,1) = 3
> F(2,2) = 7
> F(3,3) = 2
> F(4,4) = 1
>
> Now we can compute
> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7).
> F(2,3) = 9 - min(F(3,3), F(2,2)) = 9 - min(2,7) = 7 (pick N_2=7).
> F(3,4) = 3 - min(F(4,4), F(3,3)) = 3 - min(1,2) = 2 (pick N_3=2).
> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care).
> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7).
> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1).
>
>
> On Oct 7, 8:14 pm, Anand wrote:
> > Given a row of notes (with specified values), two players play a game. At
> > each turn, any player can pick a note from any of the two ends. How will
> the
> > first player maximize his score? Both players will play optimally.
>
> --
> 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.
Re: [algogeeks] Find push/pop/min or max in O(1)
yes i too think now that it should work..but on every push/pop we will need
to update the other two stacks also which can be done in constant time..
On Fri, Oct 8, 2010 at 12:58 AM, tech rascal wrote:
> I think saurabh gupta is rite.if v take 2 extra stacks ...1 for min and
> 1 for max, thn some space wud b saved.
> for the above example .max_stack wud b-
>
> >top
> 45 56 66 76 44343
>
> and min_stack wud b-
>
> --->top
> 45 22 3 2 -999
>
> so, here v need 2 save only 5 elements in max_stack, 5 elements in
> min_stack and 15 elements in full_stack ( acc 2 above example only), hence
> total=25 elements..othrwise if u do it by taking only 1 stack thn u
> need space for ..15X3 (45)elements.
>
> tell me if I am wrong..
>
> On Thu, Oct 7, 2010 at 11:49 PM, saurabh singh wrote:
>
>> Sorry but I have still not got the solution u have tried to propose here.
>> Firstly the space complexity remain O(n) only what I said.
>>
>> To understand thing u said better lets take an example of stack with
>> following entries
>>
>> --->top
>> 45 22 56 44 55 3 2 4 -999 4 2 45 66 76 44343
>>
>> how will your second stack look like and how will the push/pop/min/max
>> will work here ?
>>
>>
>>
>> On Thu, Oct 7, 2010 at 11:33 PM, Saurabh Gupta <
>> saurabhgupta1...@gmail.com> wrote:
>>
>>>
>>>
>>> On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh wrote:
>>>
elaborate plz
>>>
>>>
>>> For every new element in stack, you need thrice of space to store the min
>>> and max elements also. This has the effect that at state of stack, you can
>>> get the min and max till that point. Instead of this, maintaining a new
>>> stack for min elements would be much more efficient in terms of memory since
>>> in that all the number of elements would be lesser than the main one.
>>>
>>> so, basically in your solution, the size of object will be three times
>>> bigger than the data type which can hold the number otherwise.
>>>
>>>
On Tue, Oct 5, 2010 at 9:42 AM, Saurabh Gupta <
saurabhgupta1...@gmail.com> wrote:
> In this method, the extra memory is used. In fact, maintaining a
> separate stack of min and max would consume lesser memory than this.
>
> On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh <
> saurabh.n...@gmail.com> wrote:
>
>> You will just need to see what is min and max available on the current
>> top before push. in case of pop u dnt need to do anything...
>>
>> consider this array imp of stack
>> each array index is stored with this object : {data, min_till_here,
>> max_till_here}
>>
>> ->Top
>> [{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}]
>>
>>
>>
>> So if u push say 20 then at top u see whats max and min till now.
>> since curr min (-6) is smaller than 20 so min remains unaffected and
>> since
>> curr max (9) is smaller than 20 so curr max becomes 20. Hence the object
>> at
>> top in stack looks like {20,-6,20}
>>
>>
>> On Wed, Sep 29, 2010 at 10:18 PM, albert theboss <
>> alberttheb...@gmail.com> wrote:
>>
>>>
>>> when we pop out something
>>> we need to find the max min again if max or min is popped out...
>>> this ll take again O(n) to find max and min
>>>
>>> Correct me if am wrong
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> Thanks & Regards,
>> Saurabh
>>
>> --
>> 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.
>
--
Thanks & Regards,
Saurabh
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send em
[algogeeks] Re: DP
Nice problem. Let N_1, N_2, ... N_n be the values of the N notes.
Let F(i,j) be the maximum possible score the current player can get
using only notes i through j. Then
F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) )
This is saying that the current player always makes the choice that
minimizes B the best score that the other player can achieve. When we
know that choice, the best _we_ can do is the sum of all the available
notes minus B.
The base case is F(k,k) = N_k, and we are unconcerned with F(i,j)
where i > j.
For example, suppose we have notes 3 7 2 1 . The answer we want is
F(1,4).
Initially we have
F(1,1) = 3
F(2,2) = 7
F(3,3) = 2
F(4,4) = 1
Now we can compute
F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7).
F(2,3) = 9 - min(F(3,3), F(2,2)) = 9 - min(2,7) = 7 (pick N_2=7).
F(3,4) = 3 - min(F(4,4), F(3,3)) = 3 - min(1,2) = 2 (pick N_3=2).
F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care).
F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7).
F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1).
On Oct 7, 8:14 pm, Anand wrote:
> Given a row of notes (with specified values), two players play a game. At
> each turn, any player can pick a note from any of the two ends. How will the
> first player maximize his score? Both players will play optimally.
--
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] DP
Only from either of the two ends. On Thu, Oct 7, 2010 at 6:05 PM, sharad kumar wrote: > is he allowed to pick only from end?? > > > > On Fri, Oct 8, 2010 at 5:44 AM, Anand wrote: > >> Given a row of notes (with specified values), two players play a game. At >> each turn, any player can pick a note from any of the two ends. How will the >> first player maximize his score? Both players will play optimally. >> >> -- >> 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. >> > > > > -- > 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. > -- 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] DP
is he allowed to pick only from end?? On Fri, Oct 8, 2010 at 5:44 AM, Anand wrote: > Given a row of notes (with specified values), two players play a game. At > each turn, any player can pick a note from any of the two ends. How will the > first player maximize his score? Both players will play optimally. > > -- > 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. > -- 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] DP
Given a row of notes (with specified values), two players play a game. At each turn, any player can pick a note from any of the two ends. How will the first player maximize his score? Both players will play optimally. -- 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: arrays
Is there O(n) solution available for it?
On Tue, Sep 28, 2010 at 7:19 AM, Nishant Agarwal <
nishant.agarwa...@gmail.com> wrote:
> #include
> #include
> int main()
> {
> int a[20],i,n,max,t,j,k;
> printf("Enter the no. of elements\n");
> scanf("%d",&n);
> for(i=0;i scanf("%d",&a[i]);
> for(i=0;i {
> j=n-1;
> max=0;
> k=i;
> while(i {
> if(a[j]=max)
> {
> max=a[j];
> k=j;
> j--;
> }
> else
> j--;
> }
> t=a[i];
> a[i]=a[k];
> a[k]=t;
> }
> for(i=0;i printf("%d\t",a[i]);
> return 0;
>
> }
>
> On Tue, Sep 28, 2010 at 3:43 AM, Chi wrote:
>
>> Move-To-The-Front.
>>
>> On Sep 27, 11:58 pm, Anand wrote:
>> > Given an array of integers, for each index i, you have to swap the
>> value at
>> > i with the first value smaller than A[ i ] that comes after index i
>>
>> --
>> 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.
Re: [algogeeks] Find push/pop/min or max in O(1)
I think saurabh gupta is rite.if v take 2 extra stacks ...1 for min and
1 for max, thn some space wud b saved.
for the above example .max_stack wud b-
>top
45 56 66 76 44343
and min_stack wud b-
--->top
45 22 3 2 -999
so, here v need 2 save only 5 elements in max_stack, 5 elements in min_stack
and 15 elements in full_stack ( acc 2 above example only), hence total=25
elements..othrwise if u do it by taking only 1 stack thn u need
space for ..15X3 (45)elements.
tell me if I am wrong..
On Thu, Oct 7, 2010 at 11:49 PM, saurabh singh wrote:
> Sorry but I have still not got the solution u have tried to propose here.
> Firstly the space complexity remain O(n) only what I said.
>
> To understand thing u said better lets take an example of stack with
> following entries
>
> --->top
> 45 22 56 44 55 3 2 4 -999 4 2 45 66 76 44343
>
> how will your second stack look like and how will the push/pop/min/max will
> work here ?
>
>
>
> On Thu, Oct 7, 2010 at 11:33 PM, Saurabh Gupta > wrote:
>
>>
>>
>> On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh wrote:
>>
>>> elaborate plz
>>
>>
>> For every new element in stack, you need thrice of space to store the min
>> and max elements also. This has the effect that at state of stack, you can
>> get the min and max till that point. Instead of this, maintaining a new
>> stack for min elements would be much more efficient in terms of memory since
>> in that all the number of elements would be lesser than the main one.
>>
>> so, basically in your solution, the size of object will be three times
>> bigger than the data type which can hold the number otherwise.
>>
>>
>>>
>>> On Tue, Oct 5, 2010 at 9:42 AM, Saurabh Gupta <
>>> saurabhgupta1...@gmail.com> wrote:
>>>
In this method, the extra memory is used. In fact, maintaining a
separate stack of min and max would consume lesser memory than this.
On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh >>> > wrote:
> You will just need to see what is min and max available on the current
> top before push. in case of pop u dnt need to do anything...
>
> consider this array imp of stack
> each array index is stored with this object : {data, min_till_here,
> max_till_here}
>
> ->Top
> [{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}]
>
>
>
> So if u push say 20 then at top u see whats max and min till now. since
> curr min (-6) is smaller than 20 so min remains unaffected and since curr
> max (9) is smaller than 20 so curr max becomes 20. Hence the object at top
> in stack looks like {20,-6,20}
>
>
> On Wed, Sep 29, 2010 at 10:18 PM, albert theboss <
> alberttheb...@gmail.com> wrote:
>
>>
>> when we pop out something
>> we need to find the max min again if max or min is popped out...
>> this ll take again O(n) to find max and min
>>
>> Correct me if am wrong
>>
>> --
>> 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.
>>
>
>
>
> --
> Thanks & Regards,
> Saurabh
>
> --
> 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.
>>>
>>>
>>>
>>> --
>>> Thanks & Regards,
>>> Saurabh
>>>
>>> --
>>> 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 unsu
[algogeeks] plz clear my basics
hi, can anybody plz tell me how to find the space and time complexity of an algorithm in better and short way with example? and how we find that which approach should be applied to a problem so that we will get its optimized solution with less complexity? -- 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] Fwd:
-- Forwarded message -- From: Christi Massey Date: Thu, Sep 30, 2010 at 9:54 AM Subject: To: algogeeks@googlegroups.com Q.Can you give the optimal solution to the knapsack instances n=7, m=15,(p1,p2..p7) = (10,5,15,7,6,18,3) and (w1,w2.w7)=(2,3,5,7,1,4,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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Fwd:
-- Forwarded message -- From: Christi Massey Date: Thu, Sep 30, 2010 at 9:03 AM Subject: To: algogeeks@googlegroups.com Q.Assume you have an array A[1:n] of n elements.A majority element of a is any element occuring in more than n/2 positions(so if n=6 or n=7, any majority element will occur in at least 4 positions).assume that elements cannot be ordered or sorted, but can be compared for equality.(you might think of elements as chips ,and there is a tester that can be used to determine whether or not chips are identical) Design an efficient algorithm to find a majority element in A(or determine that no majority element exists). May this problem be design in O(n) time?if yes,how? -- 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 push/pop/min or max in O(1)
Sorry but I have still not got the solution u have tried to propose here.
Firstly the space complexity remain O(n) only what I said.
To understand thing u said better lets take an example of stack with
following entries
--->top
45 22 56 44 55 3 2 4 -999 4 2 45 66 76 44343
how will your second stack look like and how will the push/pop/min/max will
work here ?
On Thu, Oct 7, 2010 at 11:33 PM, Saurabh Gupta
wrote:
>
>
> On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh wrote:
>
>> elaborate plz
>
>
> For every new element in stack, you need thrice of space to store the min
> and max elements also. This has the effect that at state of stack, you can
> get the min and max till that point. Instead of this, maintaining a new
> stack for min elements would be much more efficient in terms of memory since
> in that all the number of elements would be lesser than the main one.
>
> so, basically in your solution, the size of object will be three times
> bigger than the data type which can hold the number otherwise.
>
>
>>
>> On Tue, Oct 5, 2010 at 9:42 AM, Saurabh Gupta > > wrote:
>>
>>> In this method, the extra memory is used. In fact, maintaining a separate
>>> stack of min and max would consume lesser memory than this.
>>>
>>> On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh
>>> wrote:
>>>
You will just need to see what is min and max available on the current
top before push. in case of pop u dnt need to do anything...
consider this array imp of stack
each array index is stored with this object : {data, min_till_here,
max_till_here}
->Top
[{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}]
So if u push say 20 then at top u see whats max and min till now. since
curr min (-6) is smaller than 20 so min remains unaffected and since curr
max (9) is smaller than 20 so curr max becomes 20. Hence the object at top
in stack looks like {20,-6,20}
On Wed, Sep 29, 2010 at 10:18 PM, albert theboss <
alberttheb...@gmail.com> wrote:
>
> when we pop out something
> we need to find the max min again if max or min is popped out...
> this ll take again O(n) to find max and min
>
> Correct me if am wrong
>
> --
> 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.
>
--
Thanks & Regards,
Saurabh
--
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.
>>>
>>
>>
>>
>> --
>> Thanks & Regards,
>> Saurabh
>>
>> --
>> 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.
>
--
Thanks & Regards,
Saurabh
--
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 push/pop/min or max in O(1)
On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh wrote:
> elaborate plz
For every new element in stack, you need thrice of space to store the min
and max elements also. This has the effect that at state of stack, you can
get the min and max till that point. Instead of this, maintaining a new
stack for min elements would be much more efficient in terms of memory since
in that all the number of elements would be lesser than the main one.
so, basically in your solution, the size of object will be three times
bigger than the data type which can hold the number otherwise.
>
> On Tue, Oct 5, 2010 at 9:42 AM, Saurabh Gupta
> wrote:
>
>> In this method, the extra memory is used. In fact, maintaining a separate
>> stack of min and max would consume lesser memory than this.
>>
>> On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh
>> wrote:
>>
>>> You will just need to see what is min and max available on the current
>>> top before push. in case of pop u dnt need to do anything...
>>>
>>> consider this array imp of stack
>>> each array index is stored with this object : {data, min_till_here,
>>> max_till_here}
>>>
>>> ->Top
>>> [{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}]
>>>
>>>
>>>
>>> So if u push say 20 then at top u see whats max and min till now. since
>>> curr min (-6) is smaller than 20 so min remains unaffected and since curr
>>> max (9) is smaller than 20 so curr max becomes 20. Hence the object at top
>>> in stack looks like {20,-6,20}
>>>
>>>
>>> On Wed, Sep 29, 2010 at 10:18 PM, albert theboss <
>>> alberttheb...@gmail.com> wrote:
>>>
when we pop out something
we need to find the max min again if max or min is popped out...
this ll take again O(n) to find max and min
Correct me if am wrong
--
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.
>>>
>>>
>>>
>>> --
>>> Thanks & Regards,
>>> Saurabh
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> Thanks & Regards,
> Saurabh
>
> --
> 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] Re: Google Question: Find kth largest of sum of elements in 2 array
A -> 5, 4, 2, 1 B -> 6, 5, 4, 2, M -> <6,b>,<5,a>,<5,b>,<4,a>,<4,a>,<2,a>,<2,a>,<1,a> x=6b, find the index of B[1]=5 in A, which is 0. so 1 big number. k=1 x=5a, find the index of A[1]=4 in B, which is 3. so there are 2 more, k=3 . . . In the case if k=2 is asked, we know that k=2 can be found when a=5, then simply find the the first largest pair to get the 3rd. if you find the index by binary search then its logn or logm to search, doing it for n numbers i A takes mlogn, and for B it is nlogm. I hope it helps to get the main idea, there are details I am avoiding. (don't want to waste too much time on this) On Oct 7, 5:07 pm, sourav wrote: > @Ercan > > I am not clear about your approach. It is clear than you are creating > a single list of numbers which is a merge of numbers from both array > such that final list / array is also decreasing. This can be done in > O(m+n). > > But what after that? Will be great if you can give some more detail. > > Thanks > Sourav > > On Oct 7, 5:30 am, Gönenç Ercan wrote: > > > > > merge the A and B in a queue in sorted order. find the following > > number (next in original array a_i+1) of the largest number (next in > > queue a_i) execute binary search in the other array (B), the index > > returned from binary search (even if its not in the array) gives the > > number of sums greater than the next greatest in A, a_i+1. so; we know > > the number of pairs; > > > (a_i , b_j) where b_j > a_i+1 > > > if you know one of the numbers then the other can be found easily. I > > think this is O(nlogm + mlogn) > > > On Oct 7, 2:16 am, Gönenç Ercan wrote: > > > > A -> 5, 4, 2, 1 > > > B -> 6, 5, 4, 2, 1 > > > > k = 3, > > > > ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the > > > algorithm below give 8 (a=2, b=6)? > > > > On Oct 6, 9:06 pm, ligerdave wrote: > > > > > use pointers and lengths of two arrays. depends on what K is, if K> > > > > m*n/2, you reverse the pointers. therefore, the worst case is either > > > > O(m) when length of m is shorter or O(n) when length of n is > > > > shorter, > > > > > make the pointers pointing to the first elements in both arrays. > > > > > A) > > > > 4,3,2,2,1 > > > > ^ > > > > > B) > > > > 5,3,2,1 > > > > ^ > > > > > compare them to find out which one is larger, here 5 is larger than 4. > > > > by definition, you know 5 would be bigger than any elements in array > > > > A, and sum of 5 with kth element of array A (here, kth <= A.length) > > > > will be the one(kth largest sum(a+b) overall) you are looking for. > > > > > if k>A.length, shift the pointer of B one number to the right and > > > > repeat the same process. > > > > > like i said, if the k> m*n/2, start from small > > > > > On Oct 6, 6:34 am, sourav wrote: > > > > > > you are given 2 arrays sorted in decreasing order of size m and n > > > > > respectively. > > > > > > Input: a number k <= m*n and >= 1 > > > > > > Output: the kth largest sum(a+b) possible. where > > > > > a (any element from array 1) > > > > > b (any element from array 2) > > > > > > The Brute force approach will take O(n*n). can anyone find a better > > > > > logic. thnkx in advance. -- 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: linked lists
use pointer. shift to left if one more leading char has been found. any unmatched char resets the pointer to first char once you went through the entire list(first one), the pointer on the second list tells you where to concatenate that gives you O(n) where n is the length of first list On Oct 7, 3:52 am, snehal jain wrote: > There are two linked list, both containing a character in each node. > > If one linked list contain characters o x e n c and second contain > characters e n c a r t a then the final linked list should contain o x > e n c a r t a i.e. if the end of one list is same as the start of > second then those characters should come only once. > > can we do it in O(n+m) where n and m are the length of list. both are > singly link list. -- 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: partition of digraph
If anyone interested to help here is a full question Thank you http://cstheory.stackexchange.com/questions/1944/digraph-partitioning-to-subgraphs On Oct 4, 6:55 pm, Yakov wrote: > Hello > For the digrah G(V,E),I have to find all the sub graphs so that that > every subgraph will include k=(sqrt(|V|)) leaves > Do you have idea for algorithm? > Thank you very much -- 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] linked lists
sorry bt d ques is not clear
if first linked list has (a b h g r t s g h) nodes and second linked list
has (g r t h s w e r t ) then what should b d result??
On Thu, Oct 7, 2010 at 7:48 PM, neeraj agarwal
wrote:
> 0for this
>
> i will search the first element of seconnd list in the first list,
> when i get it i will make the next of that element in first list to the
> next of that element in second list.
>
>
> for example
> l1={a,b,c,d}
> l2={c,d,e,f}
> here i will search first element of l2 in l1 here it is 'c'
> then i will replace next of 'c' in first list to next of 'c' in list l2...
> now l3 ={a,b,c,d,e,f}
>
> my comlexity is 0(length of list l1).
>
> -neeraj
>
> --
> 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.
Re: [algogeeks] Do This
Wouldn't the address of the fourth pointer be the link pointer in the current 3rd element. On Wed, Oct 6, 2010 at 10:44 PM, shoban babu wrote: > In a linked list how to insert an element at 3rd position given a pointer > to 4th position. > > -- > Shoban babu.B > M.E.,CSA, > IISc. > > -- > 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] Re: Google Question: Find kth largest of sum of elements in 2 array
@Ercan I am not clear about your approach. It is clear than you are creating a single list of numbers which is a merge of numbers from both array such that final list / array is also decreasing. This can be done in O(m+n). But what after that? Will be great if you can give some more detail. Thanks Sourav On Oct 7, 5:30 am, Gönenç Ercan wrote: > merge the A and B in a queue in sorted order. find the following > number (next in original array a_i+1) of the largest number (next in > queue a_i) execute binary search in the other array (B), the index > returned from binary search (even if its not in the array) gives the > number of sums greater than the next greatest in A, a_i+1. so; we know > the number of pairs; > > (a_i , b_j) where b_j > a_i+1 > > if you know one of the numbers then the other can be found easily. I > think this is O(nlogm + mlogn) > > On Oct 7, 2:16 am, Gönenç Ercan wrote: > > > A -> 5, 4, 2, 1 > > B -> 6, 5, 4, 2, 1 > > > k = 3, > > > ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the > > algorithm below give 8 (a=2, b=6)? > > > On Oct 6, 9:06 pm, ligerdave wrote: > > > > use pointers and lengths of two arrays. depends on what K is, if K> > > > m*n/2, you reverse the pointers. therefore, the worst case is either > > > O(m) when length of m is shorter or O(n) when length of n is > > > shorter, > > > > make the pointers pointing to the first elements in both arrays. > > > > A) > > > 4,3,2,2,1 > > > ^ > > > > B) > > > 5,3,2,1 > > > ^ > > > > compare them to find out which one is larger, here 5 is larger than 4. > > > by definition, you know 5 would be bigger than any elements in array > > > A, and sum of 5 with kth element of array A (here, kth <= A.length) > > > will be the one(kth largest sum(a+b) overall) you are looking for. > > > > if k>A.length, shift the pointer of B one number to the right and > > > repeat the same process. > > > > like i said, if the k> m*n/2, start from small > > > > On Oct 6, 6:34 am, sourav wrote: > > > > > you are given 2 arrays sorted in decreasing order of size m and n > > > > respectively. > > > > > Input: a number k <= m*n and >= 1 > > > > > Output: the kth largest sum(a+b) possible. where > > > > a (any element from array 1) > > > > b (any element from array 2) > > > > > The Brute force approach will take O(n*n). can anyone find a better > > > > logic. thnkx in advance. -- 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: Google Question: Find kth largest of sum of elements in 2 array
@lingerdave If you get the larget element from the 2 arrays A -> 5, 4, 2, 1 B -> 6, 5, 4, 2, say 6, do not underestimate the next element in A. The difference between the first two elements in A may be less and 2nd element in A may be string enough to make itself plus an element in B greater than first element in A plus kth element in B. More so if elements in B are very small after first few. for example see example A-> 100, 99, B-> 50,9,2,1,1 Here A[i] + B[1} is largest but A[2]+B[1] is much larger than A[2]+B[2]. Sourav On Oct 7, 6:22 pm, ligerdave wrote: > @ Ercan, > > yes, you were right. i forgot about that. > anyway, that's the idea. you would need to move pointers on both, > depends on which is bigger. for loop w/ i<=k, when the loop stops, you > have the pointers pointing at the numbers you wanted > > On Oct 6, 7:16 pm, Gönenç Ercan wrote: > > > A -> 5, 4, 2, 1 > > B -> 6, 5, 4, 2, 1 > > > k = 3, > > > ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the > > algorithm below give 8 (a=2, b=6)? > > > On Oct 6, 9:06 pm, ligerdave wrote: > > > > use pointers and lengths of two arrays. depends on what K is, if K> > > > m*n/2, you reverse the pointers. therefore, the worst case is either > > > O(m) when length of m is shorter or O(n) when length of n is > > > shorter, > > > > make the pointers pointing to the first elements in both arrays. > > > > A) > > > 4,3,2,2,1 > > > ^ > > > > B) > > > 5,3,2,1 > > > ^ > > > > compare them to find out which one is larger, here 5 is larger than 4. > > > by definition, you know 5 would be bigger than any elements in array > > > A, and sum of 5 with kth element of array A (here, kth <= A.length) > > > will be the one(kth largest sum(a+b) overall) you are looking for. > > > > if k>A.length, shift the pointer of B one number to the right and > > > repeat the same process. > > > > like i said, if the k> m*n/2, start from small > > > > On Oct 6, 6:34 am, sourav wrote: > > > > > you are given 2 arrays sorted in decreasing order of size m and n > > > > respectively. > > > > > Input: a number k <= m*n and >= 1 > > > > > Output: the kth largest sum(a+b) possible. where > > > > a (any element from array 1) > > > > b (any element from array 2) > > > > > The Brute force approach will take O(n*n). can anyone find a better > > > > logic. thnkx in advance. -- 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] linked lists
0for this
i will search the first element of seconnd list in the first list,
when i get it i will make the next of that element in first list to the
next of that element in second list.
for example
l1={a,b,c,d}
l2={c,d,e,f}
here i will search first element of l2 in l1 here it is 'c'
then i will replace next of 'c' in first list to next of 'c' in list l2...
now l3 ={a,b,c,d,e,f}
my comlexity is 0(length of list l1).
-neeraj
--
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: wiki issue on dijkstra's algorithm
anyone here? On Oct 6, 10:47 am, ligerdave wrote: > so i was reading http://en.wikipedia.org/wiki/ > Dijkstra's_algorithm">wiki on dijkstra's algorithm for finding > shortest path. i dont think article specifically define the > requirements of the graph in order to make the algorithm working > properly.(unless i missed something?) > > for instance, in the graph below, the shortest path from 1to1 should > be 1>7>2>1. however, by following dijkstra's, you would get 1>4>9>1 > because compared to 7, 4 is smallest among all direct vertices. > > 1 > / \ > 2 9 > | | > 7 4 > \ / > 1 > > anyone knows the requirements, especially the ration of #of edges to > #of vertices? -- 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: Google Question: Find kth largest of sum of elements in 2 array
@ Ercan, yes, you were right. i forgot about that. anyway, that's the idea. you would need to move pointers on both, depends on which is bigger. for loop w/ i<=k, when the loop stops, you have the pointers pointing at the numbers you wanted On Oct 6, 7:16 pm, Gönenç Ercan wrote: > A -> 5, 4, 2, 1 > B -> 6, 5, 4, 2, 1 > > k = 3, > > ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the > algorithm below give 8 (a=2, b=6)? > > On Oct 6, 9:06 pm, ligerdave wrote: > > > > > use pointers and lengths of two arrays. depends on what K is, if K> > > m*n/2, you reverse the pointers. therefore, the worst case is either > > O(m) when length of m is shorter or O(n) when length of n is > > shorter, > > > make the pointers pointing to the first elements in both arrays. > > > A) > > 4,3,2,2,1 > > ^ > > > B) > > 5,3,2,1 > > ^ > > > compare them to find out which one is larger, here 5 is larger than 4. > > by definition, you know 5 would be bigger than any elements in array > > A, and sum of 5 with kth element of array A (here, kth <= A.length) > > will be the one(kth largest sum(a+b) overall) you are looking for. > > > if k>A.length, shift the pointer of B one number to the right and > > repeat the same process. > > > like i said, if the k> m*n/2, start from small > > > On Oct 6, 6:34 am, sourav wrote: > > > > you are given 2 arrays sorted in decreasing order of size m and n > > > respectively. > > > > Input: a number k <= m*n and >= 1 > > > > Output: the kth largest sum(a+b) possible. where > > > a (any element from array 1) > > > b (any element from array 2) > > > > The Brute force approach will take O(n*n). can anyone find a better > > > logic. thnkx in advance. -- 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: Largest Rectangle in a binary Matrix:
AFAIK there is an O(n^3) solution to this problem. anybody with a O(n^2) or O(n) solution?? Mukesh Gupta Delhi College of Engineering On Thu, Oct 7, 2010 at 3:32 PM, tech rascal wrote: > can u plz xplain?? > > > On Thu, Oct 7, 2010 at 2:32 PM, Chi wrote: > >> Travers the matrix in z-curve or hilbert-curve. This is a heuristic >> algo. Thus you can find largest square matrix. >> >> On Oct 7, 10:39 am, malli wrote: >> > Largest Rectangle in a Matrix: >> > >> > Given an n by n matrix with zeros and ones, find the largest sub- >> > matrix full of ones in linear time. I was told that a solution with >> > O(n) time complexity exists. If there are n^2 elements in a n X n >> > matrix how does a linear solution exist? >> >> -- >> 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.
Re: [algogeeks] Re: Do This
@tech.
OK.
The person asked to insert the node at 3rd position and given a pointer to
4th position.
If you go by the objective of question,
e.g 3-->4--->5>7.
I am starting as index 0(which is key value 3 in this case)
I have given a pointer to node having key value 7.I have to insert 6(new
node).
i will do the following.
Insert after given node pointer.
3>4>5->7->6.
after swapping it would become.
3->4->5-->6-->7.
So for client who is using my class function for inserting a node in front
of node(which is not possible in our example),doesn't care how i inserted
his node in my list,but once he iterate his list , he will find his node
first instead of node for which pointer is given in question.
I know we can't do that, but if you go by the objective of question,why
would some one insert a node in front of some other node,he might want to
access it first,so i did the same thing here.
He can access his node as he has inserted his node at 3rd place,but actually
his node is at 4th place.
I hope it will clear your doubt.
Rahul.
On Thu, Oct 7, 2010 at 4:10 PM, tech rascal wrote:
>@Rahul: u r rite dat swapping can b done wid only 1 pointer and a
> variable. But evn doin insertion n swapping won't solve d problem bcoz new
> element is to b inserted at 3rd position bt acc 2 ur method new element
> wud come at 4th position. so, I think its not possible 2 do this in a single
> linked list since v don't evn knw whr d head is n can't use more
> pointers.
>
> On Thu, Oct 7, 2010 at 1:53 PM, rahul wrote:
>
>> @Akarsh.
>>
>> for inserting only,we need a new node and it is not possible without
>> having new pointer(we have to ref. the new node with some pointer.) once
>> insertion complete, we left with one pointer which point to old node.
>> swapping can be done with 1 pointer only,if nodes are adjacent(in this
>> case).
>>
>> Rahul.
>>
>>
>> On Thu, Oct 7, 2010 at 1:05 PM, Akarsh D wrote:
>>
>>> @Rahul : I think the swapping method will work. But still have to use two
>>> pointers.
>>>
>>> On Thu, Oct 7, 2010 at 12:34 AM, sajj wrote:
>>>
In a single linked list its is not at all possible i hope correct me
if im wrong ... with given one pointer and with out knowing where head
is.. even if u know the position of the head it ll help you out for
arriving the solution if and only if it is pointing to any of the
following nodes 1 or 2 or 3
On Oct 6, 10:56 pm, shoban babu wrote:
> @Rahul
> the only one pointer is there and it is pointing to the 4th node
only,, and
> we don't know where the head is points to...
>
> On Wed, Oct 6, 2010 at 11:20 PM, RAHUL KUJUR <
kujurismonu2...@gmail.com>wrote:
>
>
>
> > Take two pointers p and q. Initially p points to head.
>
> > while(p!="given pointer")
> > {
> > p=p->link;
> > q=p;
> > };
>
> > Now you hv pointer at 3rd and 4th position. Now insertion is
simpleHope
> > this will work
>
> > --
> > 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.
>
> --
> Shoban babu.B
> M.E.,CSA,
> IISc.
--
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...@googlegroup
Re: [algogeeks] Re: Do This
@Rahul: u r rite dat swapping can b done wid only 1 pointer and a
variable. But evn doin insertion n swapping won't solve d problem bcoz new
element is to b inserted at 3rd position bt acc 2 ur method new element
wud come at 4th position. so, I think its not possible 2 do this in a single
linked list since v don't evn knw whr d head is n can't use more
pointers.
On Thu, Oct 7, 2010 at 1:53 PM, rahul wrote:
> @Akarsh.
>
> for inserting only,we need a new node and it is not possible without having
> new pointer(we have to ref. the new node with some pointer.) once insertion
> complete, we left with one pointer which point to old node.
> swapping can be done with 1 pointer only,if nodes are adjacent(in this
> case).
>
> Rahul.
>
>
> On Thu, Oct 7, 2010 at 1:05 PM, Akarsh D wrote:
>
>> @Rahul : I think the swapping method will work. But still have to use two
>> pointers.
>>
>> On Thu, Oct 7, 2010 at 12:34 AM, sajj wrote:
>>
>>> In a single linked list its is not at all possible i hope correct me
>>> if im wrong ... with given one pointer and with out knowing where head
>>> is.. even if u know the position of the head it ll help you out for
>>> arriving the solution if and only if it is pointing to any of the
>>> following nodes 1 or 2 or 3
>>>
>>> On Oct 6, 10:56 pm, shoban babu wrote:
>>> > @Rahul
>>> > the only one pointer is there and it is pointing to the 4th node only,,
>>> and
>>> > we don't know where the head is points to...
>>> >
>>> > On Wed, Oct 6, 2010 at 11:20 PM, RAHUL KUJUR <
>>> kujurismonu2...@gmail.com>wrote:
>>> >
>>> >
>>> >
>>> > > Take two pointers p and q. Initially p points to head.
>>> >
>>> > > while(p!="given pointer")
>>> > > {
>>> > > p=p->link;
>>> > > q=p;
>>> > > };
>>> >
>>> > > Now you hv pointer at 3rd and 4th position. Now insertion is
>>> simpleHope
>>> > > this will work
>>> >
>>> > > --
>>> > > 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.
>>> >
>>> > --
>>> > Shoban babu.B
>>> > M.E.,CSA,
>>> > IISc.
>>>
>>> --
>>> 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.
Re: [algogeeks] Re: Largest Rectangle in a binary Matrix:
can u plz xplain?? On Thu, Oct 7, 2010 at 2:32 PM, Chi wrote: > Travers the matrix in z-curve or hilbert-curve. This is a heuristic > algo. Thus you can find largest square matrix. > > On Oct 7, 10:39 am, malli wrote: > > Largest Rectangle in a Matrix: > > > > Given an n by n matrix with zeros and ones, find the largest sub- > > matrix full of ones in linear time. I was told that a solution with > > O(n) time complexity exists. If there are n^2 elements in a n X n > > matrix how does a linear solution exist? > > -- > 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] Re: Largest Rectangle in a binary Matrix:
Travers the matrix in z-curve or hilbert-curve. This is a heuristic algo. Thus you can find largest square matrix. On Oct 7, 10:39 am, malli wrote: > Largest Rectangle in a Matrix: > > Given an n by n matrix with zeros and ones, find the largest sub- > matrix full of ones in linear time. I was told that a solution with > O(n) time complexity exists. If there are n^2 elements in a n X n > matrix how does a linear solution exist? -- 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] Birds on wire
An interesting puzzle. Assume size of each bird to be negligibly small. Please provide your answers with analysis. Take a wire stretched between two posts, and have a large number of birds land on it at random. Take a bucket of yellow paint, and for each bird, paint the interval from it to its closest neighbour. The question is: what proportion of the wire will be painted. More strictly: as the number of birds goes to infinity, what is the limit of the expected value of the proportion of painted wire, assuming a uniform probability distribution of birds on the wire. -- 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: All numbers in Array repeat twice except two
@mahesh Gupta
Nice solution. Thank you. You have explained it well.
On Oct 4, 5:01 pm, Mukesh Gupta wrote:
> The problem could be solved using xor logic. First take xor of all the
> elements .Doing that we get a value which is xor of the two non repeating
> elements(as xor of similar values is 0). Now xor of two non repeating
> numbers contains bits set at those places where the two numbers differ. Now
> if we take any set bit of our result and again xor all those values of set
> where that bit is set we get first non-repeating value. Taking xor of all
> those values where that bit is not set gives the another non-repeating
> number..
> For ex
> let a[]={2,3,4,3,2,6}
>
> xor of all values=0010
> Now we need to get any set bit. We can extract the rightmost set bit of any
> number n by taking ( n & ~(n-1))
>
> Here 2nd bit is the rightmost set bit.
>
> Now when we take xor of all values where 2nd bit is set(this could be done
> as (a[i] & 0010) , we get 6
> Taking xor of all values where 2nd bit is not set yields 4.
>
> Mukesh Gupta
> Delhi College of Engineering
>
>
>
> On Mon, Oct 4, 2010 at 3:17 PM, malli wrote:
> > I have an array. All numbers in the array repeat twice except two
> > numbers which repeat only once. All the numbers are placed randomly.
> > Goal is to find out efficiently the two numbers that have not
> > repeated with O(1) extra memory. Expecting linear solution.
>
> > --
> > 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.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Largest Rectangle in a binary Matrix:
Largest Rectangle in a Matrix: Given an n by n matrix with zeros and ones, find the largest sub- matrix full of ones in linear time. I was told that a solution with O(n) time complexity exists. If there are n^2 elements in a n X n matrix how does a linear solution exist? -- 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] linked lists
How about merge sort. On Thu, Oct 7, 2010 at 1:22 PM, snehal jain wrote: > There are two linked list, both containing a character in each node. > > If one linked list contain characters o x e n c and second contain > characters e n c a r t a then the final linked list should contain o x > e n c a r t ai.e. if the end of one list is same as the start of > second then those characters should come only once. > > can we do it in O(n+m) where n and m are the length of list. both are > singly link list. > > -- > 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.
Re: [algogeeks] Re: Do This
@Akarsh.
for inserting only,we need a new node and it is not possible without having
new pointer(we have to ref. the new node with some pointer.) once insertion
complete, we left with one pointer which point to old node.
swapping can be done with 1 pointer only,if nodes are adjacent(in this
case).
Rahul.
On Thu, Oct 7, 2010 at 1:05 PM, Akarsh D wrote:
> @Rahul : I think the swapping method will work. But still have to use two
> pointers.
>
> On Thu, Oct 7, 2010 at 12:34 AM, sajj wrote:
>
>> In a single linked list its is not at all possible i hope correct me
>> if im wrong ... with given one pointer and with out knowing where head
>> is.. even if u know the position of the head it ll help you out for
>> arriving the solution if and only if it is pointing to any of the
>> following nodes 1 or 2 or 3
>>
>> On Oct 6, 10:56 pm, shoban babu wrote:
>> > @Rahul
>> > the only one pointer is there and it is pointing to the 4th node only,,
>> and
>> > we don't know where the head is points to...
>> >
>> > On Wed, Oct 6, 2010 at 11:20 PM, RAHUL KUJUR > >wrote:
>> >
>> >
>> >
>> > > Take two pointers p and q. Initially p points to head.
>> >
>> > > while(p!="given pointer")
>> > > {
>> > > p=p->link;
>> > > q=p;
>> > > };
>> >
>> > > Now you hv pointer at 3rd and 4th position. Now insertion is
>> simpleHope
>> > > this will work
>> >
>> > > --
>> > > 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.
>> >
>> > --
>> > Shoban babu.B
>> > M.E.,CSA,
>> > IISc.
>>
>> --
>> 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.
Re: [algogeeks] Re: Smallest window of K[] in N[]. Best order solution
@prodigy: how is it coming O(nlogk) can u explain??? -- 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] linked lists
There are two linked list, both containing a character in each node. If one linked list contain characters o x e n c and second contain characters e n c a r t a then the final linked list should contain o x e n c a r t ai.e. if the end of one list is same as the start of second then those characters should come only once. can we do it in O(n+m) where n and m are the length of list. both are singly link list. -- 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: Do This
@Rahul : I think the swapping method will work. But still have to use two
pointers.
On Thu, Oct 7, 2010 at 12:34 AM, sajj wrote:
> In a single linked list its is not at all possible i hope correct me
> if im wrong ... with given one pointer and with out knowing where head
> is.. even if u know the position of the head it ll help you out for
> arriving the solution if and only if it is pointing to any of the
> following nodes 1 or 2 or 3
>
> On Oct 6, 10:56 pm, shoban babu wrote:
> > @Rahul
> > the only one pointer is there and it is pointing to the 4th node only,,
> and
> > we don't know where the head is points to...
> >
> > On Wed, Oct 6, 2010 at 11:20 PM, RAHUL KUJUR >wrote:
> >
> >
> >
> > > Take two pointers p and q. Initially p points to head.
> >
> > > while(p!="given pointer")
> > > {
> > > p=p->link;
> > > q=p;
> > > };
> >
> > > Now you hv pointer at 3rd and 4th position. Now insertion is
> simpleHope
> > > this will work
> >
> > > --
> > > 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.
> >
> > --
> > Shoban babu.B
> > M.E.,CSA,
> > IISc.
>
> --
> 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.
