Re: [algogeeks] Facebook Question

[Algoose chase]

Yup, it could be O(n^2) in the worst case.

On Wed, Dec 21, 2011 at 1:59 PM, Carol Smith wrote:

> @Algoose, in worst case, this is still O(n^2), ain't it?
>
> On Wed, Dec 21, 2011 at 12:50 PM, Algoose chase wrote:
>
>> Find the distance between each of the points and the origin(0,0) and sort
>> the points based on this distance.
>> Also, divide the points based on which quadrant they belong.  If the
>> difference between their distance(from origin) between 2 points is less and
>> they belong to the same quadrant, then they are likely to be close. So,
>> instead of comparing each point with every other point as in the O(N^2)
>> solution. We can compare a given point only with a subset of points that
>> appear to be close.
>>
>> On Wed, Dec 21, 2011 at 1:00 AM, SAMMM  wrote:
>>
>>> You are given a list of points in the plane, write a program that
>>> outputs each point along with the three other points that are closest
>>> to it. These three points ordered by distance.
>>> The order is less then O(n^2) .
>>>
>>> For example, given a set of points where each line is of the form: ID
>>> x-coordinate y-coordinate
>>>
>>>
>>> 1  0.0  0.0
>>> 2  10.1 -10.1
>>> 3  -12.212.2
>>> 4  38.3 38.3
>>> 5 79.99 179.99
>>>
>>>
>>>
>>> Your program should output:
>>>
>>>
>>> 1 2,3,4
>>> 2 1,3,4
>>> 3 1,2,4
>>> 4 1,2,3
>>> 5 4,3,1
>>>
>>> --
>>> 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?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 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?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 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?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 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?hl=en.

Re: [algogeeks] Facebook Question

[Algoose chase]

Find the distance between each of the points and the origin(0,0) and sort
the points based on this distance.
Also, divide the points based on which quadrant they belong.  If the
difference between their distance(from origin) between 2 points is less and
they belong to the same quadrant, then they are likely to be close. So,
instead of comparing each point with every other point as in the O(N^2)
solution. We can compare a given point only with a subset of points that
appear to be close.

On Wed, Dec 21, 2011 at 1:00 AM, SAMMM  wrote:

> You are given a list of points in the plane, write a program that
> outputs each point along with the three other points that are closest
> to it. These three points ordered by distance.
> The order is less then O(n^2) .
>
> For example, given a set of points where each line is of the form: ID
> x-coordinate y-coordinate
>
>
> 1  0.0  0.0
> 2  10.1 -10.1
> 3  -12.212.2
> 4  38.3 38.3
> 5 79.99 179.99
>
>
>
> Your program should output:
>
>
> 1 2,3,4
> 2 1,3,4
> 3 1,2,4
> 4 1,2,3
> 5 4,3,1
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Re: Interview question

[Algoose chase]

n = x%2 ?

x can be any integer.

On Fri, Dec 2, 2011 at 5:19 PM, Don  wrote:

> (!x || !(x^1))
> !(x>>1)
> !((x|1)-1)
> (x*x)==x
> (x==(x==x))||(x==(x!=x))
>
> etc.
>
> On Nov 29, 9:07 pm, Nitin Garg  wrote:
> > *What are the different ways to say, the value of x can be either a 0 or
> a
> > 1.*
> >
> > --
> > Nitin Garg
> >
> > "Personality can open doors, but only Character can keep them open"
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Re: sort the array

[Algoose chase]

Reverse the 2nd part of the Array so that they are sorted in descending
order.
Then apply bitonic sort

On Wed, Jun 22, 2011 at 2:34 PM, ross  wrote:

> @himanshu: I dont think, the approach works, in present form.
> in place merge sort or  insertion sort is fine.
> Test with,  12 13 19 16 and 0 20 10 14 as 2 parts of the array.
>
> On Jun 22, 8:42 am, Sriganesh Krishnan <2448...@gmail.com> wrote:
> > ya...we can do it in O(n) n time!!!
> > nice question!
> >
> > On Tue, Jun 21, 2011 at 11:01 PM, himanshu kansal <
> >
> >
> >
> >
> >
> >
> >
> > himanshukansal...@gmail.com> wrote:
> > > @anika: yar merge sort vl tk nlogn timeinstead u cn do dt maintain
> two
> > > ptrs one at the beginning and one intitially pointing to middle of the
> > > array...
> > > thn compare the elemnts pointed by them and swap the values if necesary
> nd
> > > incremnt d ptr as u go on...
> > > ths vl tk (n/2)+(n/2)-1 =O(n) time
> > > corrct me if m wrong
> >
> > > On Tue, Jun 21, 2011 at 10:56 PM, Anika Jain  >wrote:
> >
> > >> its like inplace mergesort
> >
> > >> On Tue, Jun 21, 2011 at 10:13 PM, aanchal goyal <
> goyal.aanch...@gmail.com
> > >> > wrote:
> >
> > >>> you have an array of size n where first n/2 is sorted and the sencond
> > >>> half is sorted . You need to sort the entire array inplace
> > >>> Its second modification version is where first part is sorted and
> other
> > >>> is NOT sorted . You need to make entire sorted .
> >
> > >>> --
> > >>> Regards,*
> > >>> Aanchal Goyal*.
> >
> > >>>  --
> > >>> 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?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 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?hl=en.
> >
> > > --
> >
> > >   Regards
> > > Himanshu Kansal
> > >   Msc Comp. sc.
> > > (University of Delhi)
> >
> > >  --
> > > 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?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 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?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 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?hl=en.

Re: [algogeeks] Re: BST+Heap

[Algoose chase]

1. Insert the node(order of insertion is irrelevant) in any order according
to the binary search tree properties.
2. Compare the j value of node with its parent recursively (bottom up) and
then perform rotations to restore the Heap property.

On Thu, Jun 9, 2011 at 12:38 AM, mukesh tiwari  wrote:

> What you explained is the property of Treap data structure . You can
> have a look at wiki [ http://en.wikipedia.org/wiki/Treap ] or you can
> search google for treap.
>
> On Jun 8, 8:15 pm, Akshata Sharma  wrote:
> > A rooted binary tree with keys in its nodes has the binary search tree
> > property (BST property) if, for every node, the keys in its left
> > subtree are smaller than its own key, and the keys in its right
> > subtree are larger than its own key. It has the heap property if, for
> > every node, the keys of its children are all smaller than its own key.
> > You are given a set of n binary tree nodes that each contain an
> > integer i and an integer j. No two i values are equal and no two j
> > values are equal. We must assemble the nodes into a single binary tree
> > where the i values obey the BST property and the j values obey the
> > heap property. If you pay attention only to the second key in each
> > node, the tree looks like a heap, and if you pay attention only to the
> > first key in each node, it looks like a binary search tree.Describe a
> > recursive algorithm for assembling such a tree
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Re: Scheduling

[Algoose chase]

Will this work ?

Order by choosing the last element of the permutation first.

initially Calculate T = Total time of all tasks
and calculate for all i, (T-Ti)*Ci and choose the task with min among them
as last.
To find the next last element , re-calculate T = T-Ti(i being the element
chosen in prev step) and proceed with the same steps as mentioned above.


On Tue, Jun 7, 2011 at 6:43 PM, ross  wrote:

> @Aakash Johari:
> Sorting works fine if all jobs can be completed in a day..
> I have a modification to this question -
> suppose the time to do a job is not one day and is given as Ti for job
> i, then how should one solve it?
>
>
> On Jun 7, 11:58 am, Aakash Johari  wrote:
> > yes, it's correct. simply sort according to their costs (in decreasing
> > order)
> >
> > On Mon, Jun 6, 2011 at 11:52 PM, sunny agrawal  >wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > Sort in decreasing order of Ci ?
> >
> > > On Tue, Jun 7, 2011 at 8:22 AM, aanchal goyal <
> goyal.aanch...@gmail.com>wrote:
> >
> > >> Given n jobs, each ith job has a cost Ci associated with it. The
> waiting
> > >> time for a job i is defined as Ci*Delay, where Delay is the number of
> days
> > >> it takes from the first day to complete a job. Assume each job can be
> > >> completed in 1 day. So, a job started at day 1 will have delay=1, the
> one
> > >> started at day 2 will have delay=2, etc. Order the jobs in such a way
> that
> > >> waiting time is minimum.
> >
> > >> --
> > >> Regards,*
> > >> Aanchal Goyal*.
> >
> > >>  --
> > >> 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?hl=en.
> >
> > > --
> > > Sunny Aggrawal
> > > B-Tech IV year,CSI
> > > Indian Institute Of Technology,Roorkee
> >
> > >  --
> > > 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?hl=en.
> >
> > --
> > -Aakash Johari
> > (IIIT Allahabad)
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to 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?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 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?hl=en.

Re: [algogeeks] SPOJ PROBLEM

[Algoose chase]

Can you explain your code ?

On Thu, Mar 10, 2011 at 10:22 AM, UTKARSH SRIVASTAV  wrote:

> WELL I HAVE DONE THIS PROBLEM .HERE IS THE CODE
> #include
> #include
> using namespace std;
> main()
> {
> long long int t[2][2010],price[2010],r,c,i,j,n;
> scanf("%lld",&n);
> for(i=0;i {
> scanf("%lld",&price[i]);
> }
> for(r=n-1,c=0;r>=0&&c<=n-1;r--,c++)
> {
> for(i=r,j=n-1;i>=0&&j>=c;j--,i--)
>
> t[i&1][j]=max(price[i]*(n+i-j)+t[(i+1)&1][j],price[j]*(n+i-j)+t[i&1][j-1]);
> }
> printf("%lld\n",t[0][n-1]);
> return 0;
> }
>
>
>
> On Wed, Mar 9, 2011 at 5:10 PM, Algoose chase wrote:
>
>> Hi,
>>
>> Any solution other than brute force(exponential growth) for this problem ?
>>
>>
>> On Sun, Mar 6, 2011 at 6:42 PM, UTKARSH SRIVASTAV <
>> usrivastav...@gmail.com> wrote:
>>
>>> can anyone please tell me why i am getting wrong answer for
>>> problem.https://www.spoj.pl/problems/TRT/
>>> .
>>> .
>>> .
>>> MY CODE IS THIS AND TO BE TESTED IN gcc COMPILER
>>>
>>>
>>> #include
>>> double a[2100];
>>> double fun(long long int  m,long long int n,double count)
>>> {
>>>double k,l;
>>>count++;
>>>if(m==n)
>>>{
>>>
>>>return count*a[m];
>>>}
>>>if((k=(fun(m+1,n,count)))>(l=(fun(m,n-1,count
>>>{
>>>
>>>return (count*a[m]+k);
>>>}
>>>else
>>>{
>>>
>>>
>>>return (count*a[n]+l);
>>>}
>>> }
>>> int main()
>>> {
>>>long long int i,m,n;
>>>double ans,c=0;
>>>scanf("%lld",&n);
>>>for(i=1;i<=n;i++)
>>>{
>>>scanf("%lf",&a[i]);
>>>}
>>>m=1;
>>>ans=fun(m,n,c);
>>>printf("%.0lf\n",ans);
>>>return 0;
>>> }
>>>
>>> --
>>> 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?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 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?hl=en.
>>
>
>
>
> --
> UTKARSH SRIVATAV
> CSE-3
> B-TECH 2nd YEAR
> MNNIT ALLAHABAD
>
>  --
> 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?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 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?hl=en.

Re: [algogeeks] SPOJ PROBLEM

[Algoose chase]

Hi,

Any solution other than brute force(exponential growth) for this problem ?


On Sun, Mar 6, 2011 at 6:42 PM, UTKARSH SRIVASTAV
wrote:

> can anyone please tell me why i am getting wrong answer for
> problem.https://www.spoj.pl/problems/TRT/
> .
> .
> .
> MY CODE IS THIS AND TO BE TESTED IN gcc COMPILER
>
>
> #include
> double a[2100];
> double fun(long long int  m,long long int n,double count)
> {
>double k,l;
>count++;
>if(m==n)
>{
>
>return count*a[m];
>}
>if((k=(fun(m+1,n,count)))>(l=(fun(m,n-1,count
>{
>
>return (count*a[m]+k);
>}
>else
>{
>
>
>return (count*a[n]+l);
>}
> }
> int main()
> {
>long long int i,m,n;
>double ans,c=0;
>scanf("%lld",&n);
>for(i=1;i<=n;i++)
>{
>scanf("%lf",&a[i]);
>}
>m=1;
>ans=fun(m,n,c);
>printf("%.0lf\n",ans);
>return 0;
> }
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Re: Meetings puzzle

[Algoose chase]

@Ashish

E(S1) = 0 // S1 is the time we start the first event , so no meetings could
be scheduled by then
E(F1) = 1 // the events are sorted by finish time, so no event could finish
before F1(first event)
Fill the Values E(S1+1) to E(F1-1) to E(S1) which should be 0.

Now if S2 precedes F1. E(S2) will have the value of E(S1) ( which is zero)
if S2 falls after F1, E(S2) will have the value of E(F1) ( which is 1).

E(F2) = Max ( E(s2) + 1  which occurs if S2 Falls after F1 -> the 2
meetings dont overlap
 or E(F1)

For overlapping events E(F1) = E(S2)+1 = 1.
For Non Overlapping Events E(S2) + 1 = 2.

you can try simple examples.


On Wed, Mar 2, 2011 at 9:19 PM, Ashish Goel  wrote:

> How is E(s2) is calculated? Why E(S2)+1
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Wed, Feb 9, 2011 at 5:05 PM, Ujjwal Raj  wrote:
>
>> Input: n meetings
>> A meeting e(i) has start time s(i) and finish time f(i).
>> Sort n events based on there finish time f(i)
>> Say sorted meeting(based on finishing time) are:
>> e1,e2,e3,e4,...en
>>
>> E(t): denotes the maximum no of meetings conducted where 0 <= time <= t.
>>
>> E(f1) = e1
>> E(f2) = max(E(s2) + 1), E(f1));
>> E(f3) = max(E(s3)+1), E(f2));
>>
>> Make array of E based on finishing times.
>> So your array will have values of E at different finishing times
>> f1 E1
>> f2, E2
>> f3 E3
>> f4 E4
>>
>> so E2 means maximum no of events between time >= f2 and < f3.
>>
>> Hope it is now clear.
>>
>>
>> On Wed, Feb 9, 2011 at 12:59 PM, Sachin Agarwal <
>> sachinagarwa...@gmail.com> wrote:
>>
>>> didn't quite get it, can you please elaborate.
>>> thanks
>>>
>>> On Feb 8, 10:38 pm, Ujjwal Raj  wrote:
>>> > Use dynamic programming:
>>> > 1) Sort the events in order of finishing time.
>>> > f1, f2, f3, f4, ... fn
>>> >
>>> > E(fn) = E(sn) + 1;
>>> > Solve the above recursion
>>> > sn is start time of event n
>>> >
>>> > On Wed, Feb 9, 2011 at 11:30 AM, Sachin Agarwal
>>> > wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > Suppose I have a room and I want to schedule meetings in it. You're
>>> > > given a list of meeting start and end times. Find a way to schedule
>>> > > the maximum number of meetings in the room.
>>> >
>>> > > --
>>> > > 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?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 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?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 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?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 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?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 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?hl=en.

Re: [algogeeks] Directory Structure

[Algoose chase]

I think we can build a n-ary tree from the n directory paths that are
already available in the computer and then for each of the m directory paths
we can traverse the tree up until the directory which is already available
in the tree and then count the remaining directories in the path.

1 Question :
Can a test case be like this ?
1 2
/chicken
/chicken/egg
/chicken/egg/chicken
if yes then while processing second of the 2 directories that should be
created, should we consider egg folder is already created while processing
the previous one ?

On Thu, Feb 17, 2011 at 6:23 PM, Akshata Sharma
wrote:

>  On Unix computers, data is stored in directories. There is one root
> directory, and this might have several  directories
> contained inside of it, each with di fferent names. These directories might
> have even more directories contained inside of them,
> and so on.
> A directory is uniquely identified by its name and its parent directory
> (the directory it is directly contained in). This is usually
> encoded in a path, which consists of several  parts each preceded by a
> forward slash ('/'). The final  part is the name of  the
> directory, and everything else gives the path of its parent directory. For
> example, consider the path:   /home/facebook/people
> This refers to the directory with name "people" in the directory described
> by "/home/facebook", which in turn refers to the
> directory with name "facebook" in the directory described by the path
> "/home". In this path, there is only one part, which means it
> refers to the directory with the name "home" in the root directory.
> To create a directory, you can use the mkdir command. You specify a path,
> and then mkdir wi ll  create the directory described by
> that path, but only if the parent directory al ready exists. For example, i
> f you wanted to create the "/home/facebook/people" and
> "/home/facebook/tech" directories from scratch, you would need four
> commands:
>   mkdir /home
>   mkdir /home/facebook
>   mkdir /home/facebook/people
>   mkdir /home/facebook/tech
> Given the full  set of directories already existing on your computer, and a
> set of new directories you want to create if they do not
> already exist, how many mkdir commands do you need to use?
>
> Input The first line of the input gives the number of test cases, T. T test
> cases follow. Each case begins with a line containing two
> integers N and M, separated by a space.
>
> The next N lines each give the path of one directory that already exists on
> your computer. This list will  include every directory
> already on your computer other than the root directory. (The root directory
> is on every computer, so there is no need to l ist it
> explicitly.)
>
> The next M lines each give the path of one directory that you want to
> create.
> Each of the paths in the input is formatted as in the problem statement
> above. Speci fically, a path consists of one or more lower -
> case alpha-numeric strings (i .e., strings containing only the symbols
> 'a'-'z' and '0'-'9'), each preceded by a single forward slash.
> These alpha-numeric strings are never empty.
>
> Output For each test case, output one l ine containing "Case #x: y", where
> x is the case number (starting from 1) and y is the
> number of mkdir you need.
>
> Note: If a directory is listed as being on your computer, then its parent
> directory will  also be listed, unless the parent  is the root
> directory.
>
> INPUT
>
> 2
>
> 1 2
> /chicken
> /chicken/egg
> /chicken
>
> 1 3
> /a
> /a/b
> /a/c
> /b/b
>
> OUTPUT
>
> Case #1: 1
> Case #2: 4
>
>  --
> 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?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 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?hl=en.

Re: [algogeeks] Re: Byte or Bite...Its byte Array

[Algoose chase]

@Jammy
in case of
1X
Since X is the start of a character, thus the preceding byte couldn't the
first byte of the 2-byte character.. So the MSb of the byte preceding X must
be a dont care. So in that case shouldn't we delete 2 bytes preceding X ?



On Thu, Feb 17, 2011 at 12:20 AM, bittu  wrote:

> case 1.
>
> |-|--|
> | 0  | remaining 7 bit|
> |-|--|
> MSB
>
> When Character is represented by 1 Byte
>
> case 2.
>
>
> ||-||-|
> | 1 |  last 7 bit   | dont care | last 7 bit of 2nd
> Byte  |
>
> ||-||-|
> MSB of 1st   MSB of 2nd Byte
>   First Byte   Second Byte
>
> When Character is represented by 1 Byte
>
> Thanks & Regards
> Shashank
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Re: top search queries

[Algoose chase]

Going by the hint given in the problem

Divide the stream into windows and assume that we have enough space to store
all the queries from the stream window in a hash table along frequency
count. Also maintain a global Hash table that will contain the frequency
counts of top n queries seen so far. Make sure that n>>100 .Once the window
is filled with enough queries, merge them into the global hash table. If a
query is already available in the global hash table update the frequency
count.Again this solution cannot be accurate due to limited memory and it
allows for some error. larger the value of n lesser the error proneness.

On Thu, Feb 3, 2011 at 9:51 PM, Srikar  wrote:

> @algoose I see what you are saying. what do you propose? checking out your
> link now...
>
>
>
> On Thu, Feb 3, 2011 at 11:44 AM, Algoose chase wrote:
>
>> @Srikar
>>
>> In your first approach you cant simply ignore the queries that are not
>> present in the heap because you have a stream of queries and you never know
>> if the query that you are about to ignore is going be received frequently or
>> not in future. Your approach is like find the top 100 queries from the
>> stream and keep updating the frequencies of only those queries using heap
>> and hash table. If you have to process some 1,00,000 , with a space for only
>> 100 elements you cant find the frequencies correctly.
>>
>> this is a nice article related to this :
>> http://www.americanscientist.org/issues/pub/the-britney-spears-problem
>>
>>
>>
>> On Tue, Feb 1, 2011 at 8:09 PM, sankalp srivastava <
>> richi.sankalp1...@gmail.com> wrote:
>>
>>> @guy above juver++
>>> The solution , i don't think can get better than this , because you
>>> need to store the querries anyway (at least for the output )
>>>
>>> --
>>> 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?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 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?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 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?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 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?hl=en.

Re: [algogeeks] Re: top search queries

[Algoose chase]

@Srikar

In your first approach you cant simply ignore the queries that are not
present in the heap because you have a stream of queries and you never know
if the query that you are about to ignore is going be received frequently or
not in future. Your approach is like find the top 100 queries from the
stream and keep updating the frequencies of only those queries using heap
and hash table. If you have to process some 1,00,000 , with a space for only
100 elements you cant find the frequencies correctly.

this is a nice article related to this :
http://www.americanscientist.org/issues/pub/the-britney-spears-problem


On Tue, Feb 1, 2011 at 8:09 PM, sankalp srivastava <
richi.sankalp1...@gmail.com> wrote:

> @guy above juver++
> The solution , i don't think can get better than this , because you
> need to store the querries anyway (at least for the output )
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] number of brackets

[Algoose chase]

The DP solution to this problem is very similar DP solution for counting the
number of Dyck words with some additional conditions.

while calculating DP[i][j]  you need to check if i+j equals one from the
list of k values. if yes copy the value from the prev row(i.e DP[i-1][j])
instead of assigning it to DP[i-1][j] + DP[i][j-1] since we can add only an
a  '(' in position i+j and no ')' can be placed there



On Wed, Jan 26, 2011 at 11:07 PM, Avayukth wrote:

> How do we solve the problem http://www.spoj.pl/problems/SQRBR/ using
> dynamic programming?
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Re: Amazon Question

[Algoose chase]

@Ritu,
Right ! I misread you post

On Wed, Jan 26, 2011 at 3:44 PM, Ritu Garg  wrote:

> @Algoose
>
> I said ..*.For every node x,go to the last node in its left subtree and
> mark the right child of that node as x.*
>
> it is to be repeated for all nodes except leaf nodes.
> to apply this approach ,you need to go down the tree.No parent pointers
> required.
> for every node say x whose left sub tree is not null ,go to the largest
> node in left sub-tree say y.
> Set  y->right = x
> y is the last node to be processed in left sub-tree of x hence x is
> successor of y.
>
> On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase wrote:
>
>> @ritu
>> how would you find a successor without extra space if you dont have a
>> parent pointer ?
>> for Instance from the right most node of left subtree to the parent of
>> left subtree(root) ?
>> @Juver++
>> Internal stack does count as extra space !!
>>
>>
>> On Wed, Jan 26, 2011 at 3:02 PM, ritu  wrote:
>>
>>> No,no extra space is needed.
>>> Right children which are NULL pointers are replaced with pointer to
>>> successor.
>>>
>>> On Jan 26, 1:18 pm, nphard nphard  wrote:
>>> > If you convert the given binary tree into right threaded binary tree,
>>> won't
>>> > you be using extra space while doing so? Either the given tree should
>>> > already be right-threaded (or with parent pointers at each node) or
>>> internal
>>> > stack should be allowed for recursion but no extra space usage apart
>>> from
>>> > that.
>>> >
>>> > On Wed, Jan 26, 2011 at 3:04 AM, ritu  wrote:
>>> > > it can be done in O(n) time using right threaded binary tree.
>>> > > 1.Convert the tree to right threaded tree.
>>> > > right threaded tree means every node points to its successor in
>>> > > tree.if right child is not NULL,then it already contains a pointer to
>>> > > its successor Else it needs to filled up as following
>>> > >  a. For every node x,go to the last node in its left subtree and
>>> > > mark the right child of that node as x.
>>> > > It Can be done in O(n) time if tree is a balanced tree.
>>> >
>>> > > 2. Now,Traverse the tree with Inorder Traversal without using
>>> > > additional space(as successor of any node is available O(1) time) and
>>> > > keep track of 5th largest element.
>>> >
>>> > > Regards,
>>> > > Ritu
>>> >
>>> > > On Jan 26, 8:38 am, nphard nphard  wrote:
>>> > > > Theoretically, the internal stack used by recursive functions must
>>> be
>>> > > > considered for space complexity.
>>> >
>>> > > > On Mon, Jan 24, 2011 at 5:40 AM, juver++ 
>>> wrote:
>>> > > > > internal stack != extra space
>>> >
>>> > > > > --
>>> > > > > 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?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 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?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 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?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 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?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 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?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 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?hl=en.

Re: [algogeeks] Re: Amazon Question

[Algoose chase]

@ritu
how would you find a successor without extra space if you dont have a parent
pointer ?
for Instance from the right most node of left subtree to the parent of left
subtree(root) ?
@Juver++
Internal stack does count as extra space !!


On Wed, Jan 26, 2011 at 3:02 PM, ritu  wrote:

> No,no extra space is needed.
> Right children which are NULL pointers are replaced with pointer to
> successor.
>
> On Jan 26, 1:18 pm, nphard nphard  wrote:
> > If you convert the given binary tree into right threaded binary tree,
> won't
> > you be using extra space while doing so? Either the given tree should
> > already be right-threaded (or with parent pointers at each node) or
> internal
> > stack should be allowed for recursion but no extra space usage apart from
> > that.
> >
> > On Wed, Jan 26, 2011 at 3:04 AM, ritu  wrote:
> > > it can be done in O(n) time using right threaded binary tree.
> > > 1.Convert the tree to right threaded tree.
> > > right threaded tree means every node points to its successor in
> > > tree.if right child is not NULL,then it already contains a pointer to
> > > its successor Else it needs to filled up as following
> > >  a. For every node x,go to the last node in its left subtree and
> > > mark the right child of that node as x.
> > > It Can be done in O(n) time if tree is a balanced tree.
> >
> > > 2. Now,Traverse the tree with Inorder Traversal without using
> > > additional space(as successor of any node is available O(1) time) and
> > > keep track of 5th largest element.
> >
> > > Regards,
> > > Ritu
> >
> > > On Jan 26, 8:38 am, nphard nphard  wrote:
> > > > Theoretically, the internal stack used by recursive functions must be
> > > > considered for space complexity.
> >
> > > > On Mon, Jan 24, 2011 at 5:40 AM, juver++ 
> wrote:
> > > > > internal stack != extra space
> >
> > > > > --
> > > > > 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?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 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?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 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?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 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?hl=en.

Re: [algogeeks] Re: Amazon Question

[Algoose chase]

If we shouldn't use recursion at it uses internal stack, then I hope we can
use Morris tree traversal and use a counter to find the 5th max.

On Fri, Jan 21, 2011 at 11:19 PM, juver++  wrote:

> @above yes, posted solution needs parent links.
> Another solution is to process tree in reverse inorder: right subtree,
> root, left subtree and keeping counter k,
> when k is zero return current node
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Distance in a dictionary

[Algoose chase]

To add to what nishaanth mentioned, I think we should also track all the
state transitions so that we can back track and make alternate transitions
if the path that was already taken was later found to be incorrect one which
will not help to reach the given target (with the given set of words).


On Fri, Jan 21, 2011 at 10:09 PM, Manmeet Singh wrote:

> whts complexity for this movegen()
>
>
> On Fri, Jan 21, 2011 at 9:52 PM, nishaanth  wrote:
>
>> Ok lets define the following functions.
>>
>> movegen()- gives the list of next move given the state. This is basically
>> all the 1 distance words given the current word.
>>
>> heuristic()- this gives the number of non-matching characters of the given
>> word with the goal word.
>>
>> Start from start state and expand.
>> Now always choose the move which gives a lesser heuristic valued state.
>> Stop if you reach the goal.
>>
>> You can refer to Russel Norvig book on AI for detailed explanation.
>>
>>
>>
>> Regards,
>>
>> S.Nishaanth,
>> Computer Science and engineering,
>> IIT Madras.
>>
>> --
>> 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?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 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?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 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?hl=en.

Re: [algogeeks] Re: Google Question

[Algoose chase]

hope this works :

#include
#define MAX(A,B) A>B?A:B
#defineMIN(A,B) A=1)
{
cur = arr[k]*factor;
if( cur > max ) //find max among multiples of Arr[k] for k < i
max = cur;
if( cur < prev )
break; // once the decreasing pattern starts its safe to
break out of loop.
k--;
factor++;
prev = cur;
}
arr[i] = MAX(i,max);
}
int result = arr[n];
delete[] arr;
return result;
}


int main()
{
int n;
scanf("%d",&n);
printf("%d\n",FindMaxA(n));
return 0;
}


--



On Fri, Jan 21, 2011 at 11:28 AM, Preetam Purbia
wrote:

> Hi,
>
> I think this method will work
>
Possible Number of A's = N/2(1+R)
> where R=N-(N/2+3)
>
> assuming 11/2 = 5
>
> Thanks
> Preetam
>
>
> On Fri, Jan 21, 2011 at 2:29 AM, Anand  wrote:
>
>> but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
>> resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
>>
>> Try this on a notepad. you will only 15A's
>>
>>
>> On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath wrote:
>>
>>> According to me Nishaanth's solution is incorrect, as let for n =10, your
>>> output : m=16
>>> but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
>>> resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
>>>
>>>
>>> On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d <
>>> abhijith200...@gmail.com> wrote:
>>>
 I think its correct.

 On Jan 19, 9:35 pm, nishaanth  wrote:
 > How about the following dynamic programming solution.
 >
 > Let dp[i] be the max no of As with i keystrokes.
 >
 > dp[i]=max(dp[i-1]+1,2*dp[i-3])
 >
 > dp[N] is the required solution.
 >
 > Correct me if i am wrong.
 >
 >
 >
 > On Wed, Jan 19, 2011 at 9:20 PM, Raj 
 wrote:
 > >http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
 >
 > > On Jan 19, 8:28 pm, bittu  wrote:
 > > > Given
 >
 > > > 1. A
 > > > 2. Ctrl+A
 > > > 3. Ctrl+C
 > > > 4. Ctrl+V
 >
 > > > If you can only press the keyboard for N times (with the above
 four
 > > > keys), please write a program to produce maximum numbers of A. If
 > > > possible, please also print out the sequence of keys.
 >
 > > > So the input parameter is N (No. of keys that you can press), the
 > > > output is M (No. of As that you can produce).
 >
 > > > Thanks & Regards
 > > > Shashank Mani
 >
 > > --
 > > 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?hl=en.
 >
 > --
 > S.Nishaanth,
 > Computer Science and engineering,
 > IIT Madras.

 --
 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?hl=en.


>>>
>>>
>>> --
>>> Regards
>>> Saikat Kumar Debnath
>>> IIIrd year, Computer Science Deptt.,
>>> Delhi Technological University,
>>> (formerly Delhi College of Engineering)
>>> Delhi
>>>
>>>  --
>>> 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?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 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?hl=en.
>>
>
>
>
> --
> Preetam Purbia
> http://twitter.com/preetam_purbia
>
>  --
> 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?hl=en.
>

-- 
You received this message because you

Re: [algogeeks] Re: google mcqs

[Algoose chase]

Pipeline : Choice B : 165 ( this pipeline wastes 20 ns between last 2 stages
for each item )
Scheduling : Choice B
Ram : Choice B
Synchronization : Choice B


On Mon, Jan 17, 2011 at 10:01 AM, Bhavesh agrawal wrote:

>
>
> On Mon, Jan 17, 2011 at 10:00 AM, Bhavesh agrawal 
> wrote:
>
>> sry ,answer is "a"
>
>
>
>> mistakingly written b.
>>
>>
>> On Mon, Jan 17, 2011 at 9:58 AM, Sarma Tangirala <
>> tvssarma.ome...@gmail.com> wrote:
>>
>>> Are larger RAMs faster?
>>>
>>> I am so sure about that.
>>>
>>> Sent from my BlackBerry
>>> --
>>> *From: * Bhavesh agrawal 
>>> *Sender: * algogeeks@googlegroups.com
>>> *Date: *Mon, 17 Jan 2011 09:36:20 +0530
>>> *To: *
>>> *ReplyTo: * algogeeks@googlegroups.com
>>> *Subject: *Re: [algogeeks] Re: google mcqs
>>>
>>> answer is b
>>>
>>> Increasing the RAM of a computer typically improves performance
>>> > > because:
>>> > > a. Virtual memory increases
>>> > > b. Larger RAMs are faster
>>> > > c. Fewer segmentation faults occur
>>> > > d. Fewer page faults occur
>>>
>>>  --
>>> 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?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 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?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 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?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 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?hl=en.

Re: [algogeeks] Re: amazon c questn

[Algoose chase]

@avpostnikov
In my reply I meant TCHAR  ( maybe it doesnt apply to the example given in
the problem)
when your project is being compiled as Unicode, the TCHAR would translate to
wchar_t. If it is being compiled as ANSI/MBCS, it would translated to char
Not always we explicitly use wchar_t.

On Fri, Jan 14, 2011 at 12:44 PM, juver++  wrote:

> @Harish
> You are wrong. It doesn't matter when it is Unicode or ASCII application.
> Size of the char type is ALWAYS 1 byte.
> To use unicode characters introduce wchar_t or something related.
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Re: amazon c questn

[Algoose chase]

Apart from that ,
In Unicode application each char would be 2 bytes in length and its always
advisable to use  malloc(sizeof(char) * 25) which seamlessly works fine in
ASCII application as well.

On Wed, Jan 12, 2011 at 7:20 AM, Kiran K  wrote:

> >p= (char*)malloc(25);
> KK: p should be checked for null after this statment
> >q = (char*)malloc(25);
> KK: q should be checked for null after this statement
>
>
> -Kiran
>
> On Jan 11, 9:44 pm, snehal jain  wrote:
> > what is the wrong in the program?
> >
> > main()
> > {
> > char *p,*q;
> > p=(char *)malloc(25);
> > q=(char *)malloc(25);
> > strcpy(p,"amazon");
> > strcpy(q,"hyd");
> > strcat(p,q);
> > printf("%s"p);
> >
> > }
>
> --
> 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?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 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?hl=en.

Re: [algogeeks] Re: Amazon Intrerview

[Algoose chase]

@Juver++
I am not sure if your input represents a path as asked in the problem.
We typically think of a path within a binary tree as a downward path(from
root to a leaf) thats not spread across different branches.
Of course, if you consider that example as a valid case, then DFS wont work
!


On Sun, Jan 9, 2011 at 9:57 PM, nishaanth  wrote:

> please describe the tree...give an elaborate explanation to your input
>
>
> On Sun, Jan 9, 2011 at 8:02 PM, juver++  wrote:
>
>> x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1
>> cannot be reached while DFS from node 2
>>
>>
>> 
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
>
> --
> 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: Amazon Intrerview

[Algoose chase]

Will this work ?

Find the node x, then the node y within the sub tree rooted at x and then z
within the sub tree rooted at y since they must within a unique path
If any of those searches fails there are no such nodes

On Sun, Jan 9, 2011 at 6:02 AM, Gene  wrote:

> The problem never says that the tree is rooted. So LCA is not
> very relevant.
>
> The path between two nodes in any tree is unique. (Otherwise it has a cycle
> and is not a tree.)  So all that's needed is to search for z starting at x
> (DFS or BFS will work fine).  When you find the unique path, see if it
> contains y.  This is O(n) where n is the number of nodes.
>
> The problem is more interesting if you are allowed to pre-process the tree
> one time in order to build a data structure to support many queries.
>
>
>
> --
> 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: FINDSR in spoj

[Algoose chase]

Brute force :
Have 2 pointers one pointing to last character and other pointing to the
first occurrence of last character. compare the chars at the corresponding
positions and decrement both pointers. when the latter hits -1 increment the
counter and reset it to its original value. if the comparison fails at any
point reset the counter to 1 and find the position of next occurrence of
the  last char in the input string and repeat the process until both the
index reduce to 0.

@Bharath
you need to read a list of input strings terminated by "*" before processing
the strings.
testcase : aaabbbcccddaaabbbcccd

On Tue, Dec 7, 2010 at 12:18 PM, bharath kannan wrote:

> I tried solving that prob..here's my code
>
> #include
> #include
> using namespace std;
> main()
> {
>  string s;
>  cin>>s;
>  while(1)
>  {
>  if(s.size()==1 && s[0]=='*')
>break;
>  int length=1,curr=0,start=0,count=1;
>  for(int i=1;i  {
> if(s[i]!=s[curr] && s[i]!=s[start])
> {
>   curr=0;
>   count=1;
>   length=i+1;
> }
> else if(s[i]!=s[start] && s[i]==s[curr])
> {
>   curr++;
> }
> else if(s[i]==s[start] && s[i]!=s[curr])
> {
>   length=i;
>   curr=0;
>   count=1;
>   i=i-1;
> }
> else if(s[i]==s[start] && s[i]==s[curr])
> {
>if(i%length==0)
>{
> count++;
> curr++;
>}
>else
> curr++;
> }
>  }
>  if(s[s.size()-1]==s[length-1])
>  cout<  else
>  cout<<"1\n";
>  cin>>s;
> }
> }
>
> I am getting WA..anyone pls tel a testcase where the above code
> fails..pls..
>
> Thanks in advance..
>
>
> On Mon, Dec 6, 2010 at 5:44 PM, alexsolo  wrote:
>
>> http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_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.

Re: [algogeeks] Re: Max Heap + Binary Search Tree

[Algoose chase]

To insert a node into a tree with such a property:
First insert the node into the tree using the rules of Binary Search tree
based on Value i .

Now compare Node->j and Node->Parent->j. Depending upon the result of
comparison perform left rotation or right rotation so that the Heap property
is also maintained. Repeat this process until you fully restore the Heap
property.

On Wed, Dec 15, 2010 at 2:54 PM, Prims  wrote:

> Lets assume that the tree node has two keys K1 and K2.
> K1 satisfies the BST property
> K2 satisfies the Max Heap Property.
>
> Our problem is to build a binary tree which satisfies both the
> properties.
> For a maximal heap the root node must be the maximum.
> So we find the node which has the K2 max. And make it as the root
> node.
> Among the remaining nodes, The nodes to the left of the tree will be
> those whose K1 value is less than that of the Root nodes K1. And rest
> will be on the right side of the root. Now again repeat the procedure
> for finding the next left node of root and right node of root using
> the same logic above
>
> On Dec 15, 2:07 pm, snehal jain  wrote:
> > A rooted binary tree with keys in its nodes has the binary search tree
> > property (BST property) if, for every node, the keys in its left
> > subtree are smaller than its own key, and the keys in its right
> > subtree are larger than its own key. It has the heap property if, for
> > every node, the keys of its children are all smaller than its own key.
> > You are given a set of n binary tree nodes that each contain an
> > integer i and an integer j. No two i values are equal and no two j
> > values are equal. We must assemble the nodes into a single binary tree
> > where the i values obey the BST property and the j values obey the
> > heap property. If you pay attention only to the second key in each
> > node, the tree looks like a heap, and if you pay attention only to the
> > first key in each node, it looks like a binary search tree.Describe a
> > recursive algorithm for assembling such a tree
>
> --
> 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: Maximum subarray whose sum is zero

[Algoose chase]

I believe the space complexity should be O(n) since you need to store the
cumulative sum corresponding to each of the elements from the input starting
from the first element.

On Wed, Dec 1, 2010 at 12:04 AM, Prims  wrote:

> I got the solution to use a hash table storing partial sums a[0],
> a[0]+a[1], a[0]+a[1]+a[2], etc. in a hash table, along with i
>
> Whenever a collision happens, then it is the sub array from i to the
> last summand.
>
> This involves O(N) Time complexity but i what is the space complexity
> in this case?
>
> On Nov 30, 10:19 pm, Prims  wrote:
> > There is an unsorted array of positive and negative integers. I need
> > to find out maximum sub array whose sum is zero efficiently.
> >
> > I can able to provide an answer in O(N^2) time complexity with O(N)
> > Space Complexity
> > Can anyone know better than this?
>
> --
> 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 triplets in an integer array A[] which satisfy condition: a[i]^2 + a[j]^2 = a[k]^2

[Algoose chase]

If you store the squares of elements in a hash table, you dont need a binary
search reducing the running time by a factor of log_base2(n)



On Wed, Dec 1, 2010 at 12:50 AM, Akash Agrawal wrote:

> Guys,
>
> I have written a blog post for finding triplets in an integer array A[]
> which satisfy following condition:
>
> a[i]^2 + a[j]^2 = a[k]^2
>
>
> http://tech-queries.blogspot.com/2010/12/finding-triplets-in-integer-array.html
>
> I believe that more optimization are possible. It will be very helpful if
> one can suggest some.
>
>
> Regards,
> Akash Agrawal
> http://tech-queries.blogspot.com/
>
> --
> 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] Dynamic prog.

[Algoose chase]

thats right !
DP must be the best approach to solve it !



On Tue, Nov 30, 2010 at 10:40 PM, Akash Agrawal
wrote:

> In addition to these assumptions, you have also assumed that numbers are
> greater than 1 else * will lower the result.
>
> Regards,
> Akash Agrawal
> http://tech-queries.blogspot.com/
>
>
>
> On Thu, Nov 25, 2010 at 11:18 AM, Algoose chase wrote:
>
>> For this specific case since only 2 operators are used : + , *  and we
>> know that * is the operator that maximizes the value(provided both the
>> operands are not equal to one / none of the operand is zero and also given
>> that operands are +ve ).
>> Doing * operation as late as possible should suffice right ?
>>
>> For Eg: Do all additions in the first pass and do all multiplications in
>> 2nd pass.
>>
>> is there be any case where the above mentioned logic fails ?
>>
>> On Wed, Nov 24, 2010 at 4:07 PM, Amir hossein Shahriari <
>> amir.hossein.shahri...@gmail.com> wrote:
>>
>>> you can  use an algorithm similar to matrix chain multiplication i.e. if
>>> dp[i][j] is the maximum value that you can get with the numbers v_i to v_j
>>> and in order to maximize it find k that maximizes ( dp[i][k]  op_k  dp[k][j]
>>> )
>>> v_i is the ith value and op_k is the kth operator
>>> obviously if i==j : dp[i][j] = v_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.
>

-- 
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] Dynamic prog.

[Algoose chase]

For this specific case since only 2 operators are used : + , *  and we
know that * is the operator that maximizes the value(provided both the
operands are not equal to one / none of the operand is zero and also given
that operands are +ve ).
Doing * operation as late as possible should suffice right ?

For Eg: Do all additions in the first pass and do all multiplications in 2nd
pass.

is there be any case where the above mentioned logic fails ?

On Wed, Nov 24, 2010 at 4:07 PM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:

> you can  use an algorithm similar to matrix chain multiplication i.e. if
> dp[i][j] is the maximum value that you can get with the numbers v_i to v_j
> and in order to maximize it find k that maximizes ( dp[i][k]  op_k  dp[k][j]
> )
> v_i is the ith value and op_k is the kth operator
> obviously if i==j : dp[i][j] = v_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.

Re: [algogeeks] Re: palindrome problem

[Algoose chase]

construct a 2-D array,Arr[strlen][strlen] according to the following rules.

Arr[i][j] = 1 if i = j (they represent string of single char which is
Arr[i], a palindrome by definition)
Arr[i][j] = Invalid  if i > j (only half the table across the leading
diagonal would be filled including the diagonal)

Now if i < j
Arr[i][j] = Arr[i][j-1] + 1 ( if Substring Arr[ij] is a palindrome)
Arr[i][j] = Arr[i][j-1]   ( if Substring Arr[ij] is  not a
palindrome)

Now the Last Column of your table contains the number of palindromes within
a string that starts at index i until the end of the string.
Adding all the values from last column will give you the total number of
substrings within the string that are palindrome.


On Wed, Nov 17, 2010 at 5:49 PM, Arif Ali Saiyed wrote:

> Hi Can you explain following with an example
> "esign an
> e cient al-gorithm to determine the minimum number of palindromes in
> adecomposition for a given string, "
> are you asking to find the longest palindrome ?
> -Arif
>
>
> On Nov 16, 11:51 pm, lichenga2404  wrote:
> > A palindrome is a string which is identical to itself in reverse
> > order. For example
> > \ABAAABA" is a palindrome. Given a string, we'd like to break it up
> > into the small-
> > est possible number of palindromes. Of course, any one-character
> > string is a palindrome
> > so we can always break a length n string into n palindromes. Design an
> > e cient al-
> > gorithm to determine the minimum number of palindromes in a
> > decomposition for a
> > given string, and analyze the running time. You may assume you are
> > given a proce-
> > dure Palindrome(S) which runs in time O(jSj) and returns true if and
> > only if S is a
> > palindrome.
> >
> >   How to solve this problem with the dynamic programming method?
>
> --
> 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] sorting variant

[Algoose chase]

I am not sure if this what you are looking for.

Assuming that the arrays are sorted in ascending order.
Choose one of the 2 arrays as a Reference Array.
for each element element in reference array, do a binary search to find all
elements that are less than the current element in reference and include
them in the result array(and mark the index of the largest among them so
that you dont have to consider them in subsequent searches reducing the
range of binary search) before including the current element from reference.

If there is no element less than the current element in the other array ,
then include that current element and move to the next element in reference
array.



On Sun, Nov 7, 2010 at 3:21 AM, lichenga2404  wrote:

> Suppose we'd like to implement a sorting variant where every element
> is compared only a small number of times.
>  a) devise a divide and conquer algorithm to merge 2 sorted arrays of
> length n , which guarantees that every element is included in at most
> O(log n ) comparisons.
>  b) using this modified merge , prove that Merge-Sort will include
> element in at most O( (log n)^2) comparisons.
>
> --
> 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: Addition Of numbers in SLL

[Algoose chase]

The Solution is pretty straight forward when you long number is represented
in reverse order in linked list.
If the number is not in reverse order, We need an Explicit stack or we must
Use Recursion .

Other way around this is to construct another parallel linked list along
with Sum(linked list) for maintaining the carry information and use multiple
passes until the Carry linked list completely vanishes.
Whenever you find the sum digit , Use sum->digit = (list1->digit +
list2->digit + Carry->next->digit) % 10
Carry->digit =
(list1->digit + list2->digit + Carry->digit) / 10

On Mon, Aug 16, 2010 at 8:03 AM, Ashish Goel  wrote:

>  int add(struct node* pL1, struct node * pl2,int gap/*no of digits in l1
> -no of digits in l2*/)
> { //assumption, # of nodes in L1 is > # of nodes in L2, make sure this
> before calling this, counting nodes is less costlier than reversal
>
>
> if (!(pl1) || !(pl2)) return 0;
>
> if (gap>0)
> {
>  carry = add(pL1->next, pL2, gap-1);
>  carry = (pl1->data+carry)/10;
>  pl1->data =(pl1->data+carry) %10;
>  return carry;
> }
> else
> {
> carry = add(pL1->next, pl2->next, gap -1);
>  carry = (pl1->data+pl2->data+carry)/10;
>  pl1->data =(pl1->data+pl2->data+carry) %10;
>  return carry;
> }
>
> }
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Sun, Aug 15, 2010 at 12:19 PM, Manjunath Manohar <
> manjunath.n...@gmail.com> wrote:
>
>> @Dave..Can u provide a small snippet for ur explanation pls..
>>
>> --
>> 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] minimum window containing charecters

[Algoose chase]

@ Anand, No , It doesnt

Try with String2 = "LH"
String1 = "HELLO".
I think LCS solves a different problem from the one being asked here.

I think we must generate all possible combination of strings  and for each
combination , check if all chars from str2 is present in it.

On Sun, Aug 1, 2010 at 11:54 PM, Anand  wrote:

>
> Even if they are not in the same order still it works
>
> http://codepad.org/jpCUqwpA
>
> 
> On Sun, Aug 1, 2010 at 10:52 AM, srikanth sg wrote:
>
>> dude they dont need to be in the same order ..
>> how are taking care of that
>>
>>
>> On Sun, Aug 1, 2010 at 10:47 AM, Anand  wrote:
>>
>>> Using Dynamic programing(Longest common subsequence logic) we can solve
>>> this problem in O(nm) where n is the length of the first string and m is the
>>> length of second string. Last element of matrix which the length of the
>>> string that matches.
>>>
>>> http://codepad.org/cyiKEMSF
>>>
>>> 
>>>
>>> On Sun, Aug 1, 2010 at 8:13 AM, srikanth sg wrote:
>>>
 plz .. if any one knows dp solution then tell ...


 On Sun, Aug 1, 2010 at 7:31 AM, Ashim Kapoor wrote:

> I am not sure, but can I do this using a suffix trie ? any comments ?
>
>
>
>
> On Sun, Aug 1, 2010 at 2:29 PM, Ashish Goel  wrote:
>
>> solution could be to find the charcter position from both sides for
>> each char of s2
>> then from the 2*n array, find the smallest index from left and largest
>> from right, within these two indexes all chars would be there
>>
>> one case where one of the chars can be missing can be found if a row
>> in this 2-d array remains unmodified
>>
>>
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>>
>> On Sat, Jul 31, 2010 at 10:22 PM, Nikhil Jindal <
>> fundoon...@yahoo.co.in> wrote:
>>
>>> At the moment, I can only think of an O(n^3) algo.
>>> Maybe if you can find a hash function which computes the hash value
>>> depending on the unique characters the string contains, you can reduce 
>>> it to
>>> O(n^2).
>>>
>>>
>>> On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg <
>>> srikanthini...@gmail.com> wrote:
>>>
 given two string , find the minimum  width in string 1 containing
 the
 all characters of string 2 , they may present in different order
 string 1-HELLO
 string 2- LE
 answer-2

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


>>> Please access the attached hyperlink for an important electronic 
>>> communications disclaimer: 
>>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> --
>>>
>>> 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 thi

Re: [algogeeks] algorithm

[Algoose chase]

Add Each number from the stream to a Doubly linked list in sorted fashion

i = 1;
j = 1;
while( stream not empty)
{
   if( i == 1&& j == 1)
   {
 Median = Cur ; /*Create New list with ist Number*/
   }
   Add_Node_In_Sorted_Order(Cur);

   If( If new node is added after median )
   i++;   /*if the current median is 3rd node and new
node is added @ 5th position*/
  bAddedBeforeMedian = False;
   else
   j++;
   bAddedBeforeMedian = true;

   if( i %2 == 1 && !bAddedBeforeMedian)
  Median = median ->next;
   else if (j%2==1 && bAddedBeforeMeidan)
  Median = Median->prev

}
return Median->Data;

At any given point in time Median will point to the median among the numbers
seen so far
-

On Sat, Jul 24, 2010 at 8:02 PM, jalaj jaiswal wrote:

> You are given a stream of numbers which can be positive or negative. You
> are required to provide an operation FIND MEDIAN..which when invoked should
> be able return the median of the numbers in stream (in sorted order) in O(1)
> time.
>
> Eg: 0 1 2 3 4
> Right FIND MEDIAN returns 2 as median
>
> Now input is -2 -4
> So Stream = 0 1 2 3 -2 -2 -4
> Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1
>
> --
> With Regards,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] You have 2 arrays of integer. You have to write a function, which take an integer as input and returns bool. Example array 1 has {1,5,10} array 2 has {2,5,9}. Func(3) should return t

[Algoose chase]

@jalaj

TRY
A:16, 12, 10, 6 ,2
B:11, 10,7, 2, 1
num: 26


On Sat, Jul 24, 2010 at 5:13 AM, jalaj jaiswal wrote:

> Take two pointers both at the start of each array...
> i=0,j=0
> let the size of sorted arrays be m and n
> int func(int num,int m,int n){
> int i=0,j=0;
> while (i   if((num<=a[i])||(num<=a[j])||num<(a[i]+b[j]))
>  return 0;
>   if(num==(a[i]+b[j]))
>   return 1;
>   if(num>a[i]+b[j]){
>   if(a[i]>b[j]) j++;
>   else i++;
>   }
> }
>   return 0;
> }
>
> O(m+n) complexity
> Ps. i'm returning true if the number equals a[i]+b[j] and not just when it
> equals a single element in any array
>
>
>
>
> On Fri, Jul 23, 2010 at 9:22 AM, Shafi Ahmad wrote:
>
>> Let argument of function Func is k.
>> Case 1: If at least on of the array is sorted (say array1) then.
>>   For each number in array2, do
>>1.  binary search  for (k - array1[i]) in array1
>>2. if found
>>return true.
>>else
>>   return false
>> case 2: Arrays are not sorted then
>> 1. Sort one array and apply algo for case 1.
>>
>> Time complexity will be  sizeof(unsortedarray)log (sizeofsortedarray).
>>
>> Regards,
>> Shafi
>> On Fri, Jul 23, 2010 at 12:01 AM, vijay  wrote:
>>
>>> You have 2 arrays of integer. You have to write a function, which take
>>> an integer as input and returns bool. Example array 1 has {1,5,10}
>>> array 2 has {2,5,9}. Func(3) should return true, since 1 (from array
>>> 1) +2 (from array 2) =3 ( i.e summation of 2 numbers (1 from each
>>> array) is equal to 3). Func(13) should return false
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> Regards,
>> Shafi Ahmad
>>
>> The difficult we do immediately, the impossible takes a little
>> longerUS Army
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> With Regards,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
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] Boxes!!!

[Algoose chase]

can we sort the boxes based on their volume in descending order
and start highest volume box to lowest volume box (outer loop)
 -Inner loop start from lowest volume box to highest volume box upto
the box considered in outer loop.

Running time : O(n^2)
On Tue, Jul 20, 2010 at 8:28 PM, Ashish Goel  wrote:

> kindly give an example
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Tue, Jul 20, 2010 at 8:04 AM, siddharth shankar <
> siddharth.shanka...@gmail.com> wrote:
>
>> step :
>>
>> 1. Sorting LBH in decreasing order   first on L than on B and than on
>> H .
>>
>> 2. Now find longest decreasing sub-sequence of array of structures(LBH) .
>>
>> correct me if I m wrong !!!
>>
>>
>> On Sun, Jul 18, 2010 at 11:44 PM, amit  wrote:
>>
>>> Given a lot of cuboid boxes with different length, breadth and height.
>>> We need to find the maximum subset which can fit into each other.
>>>
>>> For example:
>>> If Box 1 has LBH as 7 8 9
>>> If Box 2 has LBH as 5 6 8
>>> If Box 3 has LBH as 5 8 7
>>> If Box 4 has LBH as 4 4 4
>>>
>>> then answer is 1,2,4
>>>
>>> A box can fit into another only and only if all dimensions of that is
>>> less than the bigger box.Rotation of boxes is not possible.
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> siddharth shankar
>>
>>
>>  --
>> 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: center of a tree

[Algoose chase]

Given the collection of nodes that constitute the diameter of the tree, The
node with Max height among them i.e the node thats closest to the root(top
level node) need not necessarily have children with equal height.

For Instance:
If the the top_level_node->left->height  < top_level_node->right->height ,
then find p such that
p = top_level_node->right->height - top_level_node->left->height - 1;
now traverse down p levels to the right along the path that constitutes the
diameter. this node will be the center of the tree.

@gene : you mentioned within brackets "(though not necessarily the overall
maximum)".Did you mean the same as i do  ?

On Sun, Jul 4, 2010 at 2:19 AM, Gene  wrote:

> On Jul 3, 10:14 am, jalaj jaiswal  wrote:
> > give an algo to find center of a tree
> > conter of a tree is midpoint of diameter which is the largest distance
> b/w
> > any two nodes
>
> You can traverse the tree once in O(n) to label each node N with its
> height H(N), which is the maximum distance to any descendent leaf.
>
> Then traverse it again looking for a node C with H(C->left) = H(C-
> >right) and the maximum value of D(C) = 1 + H(C->left) + H(C->right).
> The first condition puts C in the middle of some maximal length path
> (though not necessarily the overall maximum).   The second picks the
> center IF there is only one center.
>
> A tree can also have 2 centers.  For example in the tree
>
> 1 --> 2 --> 3
>  \ --> 4
>
> both 1 and 2 are centers because their radius is 1 in both cases.
> Working out how to handle this case is not hard.
>
> --
> 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: A nice Prob

[Algoose chase]

Algo_F_OF_K(int k)
{
if( k & k-1 == 0 ) // check if its a power of 2
{
f(k) = i  // if ith bit is set in the binary representation of k.
}
else if(  k & k+1 == 0 ) // if all the lower order bits are set in K
{
f(k) = 1;
}
else
{
f(k) = f(j) + 1  // j is the largest number less than k with same
number of 1's set in its binary representation as k.
}
}

@vicky : did you solved it using any recurrence relation (if that can be
applied for this prob) ?

On Fri, Jul 2, 2010 at 12:17 PM, venkat kumar wrote:

>  what is the website having collection of ms questions?
>
>
>
> On Thu, Jul 1, 2010 at 6:48 PM, vicky  wrote:
>
>> Actually i saw a forum of MS questions and same as i wrote was written
>> there. I too was confused but finally came to conclusion as u.
>> Anyways
>>
>> On Jul 1, 5:51 pm, Gene  wrote:
>> > On Jul 1, 6:46 am, vicky  wrote:
>> >
>> > > It took me more time to understand this problem then solving after i
>> > > understood.
>> > > You guys too have a look @ it.::
>> > > Let f(k) = y where k is the y-th number in the increasing sequence of
>> > > non-negative
>> > > integers with the same number of ones in its binary representation as
>> > > y, e.g. f(0) = 1, f(1) => 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2,
>> f(6) = 3
>> > > and so on.
>> > > Given k >= 0, compute f(k).
>> >
>> > There must be a mistake in you problem statement or examples.  It only
>> > makes sense if you change it as follows:
>> >
>> > Let f(k) = y where k is the y-th number in the increasing sequence of
>> > non-negative integers with the same number of ones in its
>> > binary representation as k, <<-- change this from y to k.
>>
>> --
>> 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] a bst

[Algoose Chase]

If the parent Pointer is available we can use

if( node->right->data > node->parent->data || node->right->data <
node->data)  to identify the leaf nodes and use it as one of the recursion
terminating condition in the original Height determining Algorithm.

@Divya, I think u meant node != node->right->left

On Sat, Jun 26, 2010 at 3:54 PM, divya jain wrote:

> yes..
>
> i got the solution traverse till node->right!=node->right->left... at this
> point u ll get height.. rite?
>
>
> On 26 June 2010 11:49, Raj N  wrote:
>
>> @Divya: What will happen when say node->right when you reach the leaves ?
>> Is it equivalent to node->next and node->left = = node->previous in the
>> doubly linked list ?
>>
>>
>> On Tue, Jun 22, 2010 at 4:44 PM, divya  wrote:
>>
>>> a bst is given whose leaf nodes having left as well as right pointers
>>> not pointing to NULL. rather all the leaf nodes are forming a circular
>>> doubly linked list. u have to calculate height of tree.
>>>
>>> --
>>> 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] sum to 0

[Algoose Chase]

@ Amir:
I think you cannot find two numbers in B and C such that their sum is -A[k]
in O(n) in all cases with the logic that you mentioned.

for instance you can try with :
A : 2 7 8 10
B :-2, 0, 1, 9
C: -7 -2 1 3

On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:

> sort all arrays
> for each number in A , A[k]
> find two numbers in B and C such that their sum is -A[k]
> this can be done in O(n) time:
>
> set i at the beginning of B and j at the end of C
> while i=0
>   if ( B[i] + C[j] == -A[k] ) return true
>   if ( B[i] + C[j] < -A[k] ) increase i
>   else decrease j
>
> we have to do this for each element of A so the overall complexity is:
> O(n2) time O(1) space
>
> correct me if I'm wrong
>
> On 6/15/10, sharad kumar  wrote:
> > plzzz comment on this question
> >
> > --
> > 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] Single ordered list

[Algoose Chase]

For multiple ordered lists you can build a single Max heap out of elements
from all this list and Process as its done in heapsort


On Wed, Jun 9, 2010 at 9:14 PM, Rohit Saraf wrote:

> I had answered this question(of multiple lists) 2 or three days back.
> Go into the archive if u wanna see :P
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
>
> On Wed, Jun 9, 2010 at 6:52 PM, Raj N  wrote:
>
>> But what if the same same problem is extended for multiple lists. As the
>> individual lists have already been sorted, is there any efficient way or any
>> other sorting algo which exploits this fact.
>>
>>
>> On Tue, Jun 8, 2010 at 10:56 PM, divya jain wrote:
>>
>>> merging as in merge sort.
>>>
>>> On 8 June 2010 19:59, Raj N  wrote:
>>>
 What is the most efficient way of combining 2 separate ordered list
 into a single ordered 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.
>>>
>>
>>  --
>> 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] isomorphic trees

[Algoose Chase]

The Definition of isomorphic trees given in the first post is incomplete
We say two rooted unordered trees are isomorphic if
1. a tree with a single node (the root) is only isomorphic to a tree with a
single node;
2. two trees with roots A and B, none of which is a single-node tree, are
isomorphic if and only if there is a 1-1 correspondence between the subtrees
of A and the subtrees of B such that corresponding subtrees are isomorphic.

Lets say each node has an additional field that says the number of children
it has.
bool IsIsomorphic(Node* T1,Node* T2)
{
 if( T1 == null && T2 == null ) return true;

 if( T1->numChilderen == T2->numChilderen)
 {
if(IsIsomorphic(( T1->left,T2->left) &&
IsIsoMorphic(T1->right,T2->right)) || (IsIsoMorphic(T1->right,T2->left) &&
IsIsomorphic(T1->left,T2->Right));
 }
 else return false;
}

Correct me if needed !

On Wed, Jun 9, 2010 at 8:29 PM, divya jain  wrote:

> @vadivel and anand
>
> { 1,2,3 } is *isomorphic* to { 1,3,2 }
> { 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 }
> { 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 }
>
> so its nt necessary that right and left will interchange. it may or may
> not. if all right and left are interchanged then it is mirror tree. i think
> ur code is for mirror tree and not isomorphic tree..
>
>
>  --
> 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] Removing extra parentheses in an infix string

[Algoose Chase]

Hi ,

To add to your logic, I hope we must also be checking at the precedence of
the first operator that appears after the closing parenthesis ')' before we
can decided if the parenthesis can be removed or not .


On Thu, Jun 3, 2010 at 11:37 PM, Antony Vincent Pandian.S. <
sant...@gmail.com> wrote:

> If the base logic follows the below rule, it should work.
>
> If any operator within parenthesis is of less precedence to the
> operator before the opening parenthesis, the parenthesis can not be
> removed.
>
> For cases of equal precedence of operators  before parenthesis and
> within parenthesis, transitivity condition should be checked. If
> transitive, parenthesis can be removed else should be retained. Eg:
> parenthesis cannot be removed for division operator while can be
> removed for multiplicative or addition or subtraction operator.
>
> On 6/3/10, Rohit Saraf  wrote:
> > So there is a prob algoose A*(B*C) and a*(b*c+d)
> > i hope you understood
> >
> > --
> > --
> > Rohit Saraf
> > Second Year Undergraduate,
> > Dept. of Computer Science and Engineering
> > IIT Bombay
> > http://www.cse.iitb.ac.in/~rohitfeb14
> >
> > --
> > 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.
> >
> >
>
> --
> Sent from my mobile device
>
> Luv,
> S.Antony Vincent Pandian
>
> --
> 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] Removing extra parentheses in an infix string

[Algoose Chase]

Thats right !!!

On Thu, Jun 3, 2010 at 6:08 PM, Rohit Saraf wrote:

> So there is a prob algoose A*(B*C) and a*(b*c+d)
> i hope you understood
>
> --
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
> --
> 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] Removing extra parentheses in an infix string

[Algoose Chase]

Will this work ?

consider A+(B*C)
have an operator stack to hold the operators. As we scan elements from left
to right,push the operators in operator stack.
when you encounter a '(' , then scan to find the first operator that comes
after '('  (in this case *).
If this operator has a higher precedence than the operator @ top of stack
(in this case +). Then we can safely remove the parenthesis. Else we cant
remove the brackets



On Thu, Jun 3, 2010 at 1:05 PM, divya jain  wrote:

>
>
> 1.calculte the postfix of given expression.
> 2.now remove a particular parenthesis from expression and check if the
> postfix of this expression is equal to the postfix of original expression.
> if yes then the parenthesis we have removed were extra. if no then the
> parenthesis were not exta.
> 3 now remove other parenthesis as step 2 and repeat till u have done this
> for all parenthesis
>
> On 1 June 2010 20:12, Raj N  wrote:
>
>> How to remove extra parentheses in an infix string. For example if it
>> is A+(B*C) parentheses for * is not required as it has higher
>> precedence. Can someone suggest a good routine for this?
>>
>> --
>> 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] Convert a Binary tree into spike.

[Algoose Chase]

Hi ,

We can do Breadth first search but without any additional Memory like Queue.
Since we connect the siblings we can traverse through siblings.
Going from Top to bottom, Each Internal node(non-leaf) must connect its
children. If that internal node has a right sibling then connect the right
most node of internal node with the left most child node of the sibling.
Continue until the sibling node is null. As you towards right remove the
links to its parent. Also save the left most node at each level to traverse
down to next level.



On Thu, May 13, 2010 at 6:57 PM, Jitendra Kushwaha  wrote:

> This can be done with level order traversal of the tree
>
> Algorithm
>
> count = count2 = 0
> 1. Push the root in the queue.
> 2. keep count at each level for root count =1
> 3. while(queue not empty)
> 4.  push all childs of node at the top of queue in queue
> 5.  count2 += (number of childs of node at the top)
> 6.  print the top node of queue and dequeue it
> 7.  count -= 1
> 8.  if (count == 0)
> 9.print newline
> 10.  count = count2
> 11.  count2 = 0
>
>
> any comments are welcomed...
>
> --
> Regards
> Jitendra Kushwaha
> Undergradute Student
> Computer Science & Eng.
> MNNIT, Allahabad
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
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

[Algoose Chase]

OOPs.. sorry

this doesnt work !

On Sun, May 2, 2010 at 6:11 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
>
>
> On Sun, May 2, 2010 at 3:44 PM, Shishir Mittal <1987.shis...@gmail.com>wrote:
>
>> 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 <
>>>>>> shoonya.mo...@gmail.com> 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 <
>>>>>>> shoonya.mo...@gmail.com> wrote:
>>>>>>>
>>>>>>>> Hi Divya,
>>>>>>>>
>>>>>>>>
>>>>>>>> A[n] and B

Re: [algogeeks] a google question

[Algoose Chase]

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


On Sun, May 2, 2010 at 3:44 PM, Shishir Mittal <1987.shis...@gmail.com>wrote:

> 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 <
>>>>>> shoonya.mo...@gmail.com> 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-

Re: [algogeeks] a google question

[Algoose Chase]

@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.

Re: [algogeeks] Build BST from binary tree without extra space

[Algoose Chase]

If you mean to convert the binary tree to binary search tree directly , then


BinarytoBST(Node* root)
{
   if( root == nulll) return;

   BinarytoBST(root->left);
   BinarytoBST(root->right);

   if( root->left )
   Node* NodeL = MAX(root->left);
   if ( root->right )
   Node* NodeR = MIN(root->right);

   if( NodeL->Data > root->data)
   {
   // swap values.
   temp = NodeL->data;
   NodeL->data = root->data;
   root->data = temp;

   BinarytoBST(NodeL);
   }
   if( NodeR->Data <= root->data)
   {
   // swap values.
   temp = NodeR->data;
   NodeR->data = root->data;
   root->data = temp;

   BinarytoBST(NodeR);
   }

--------



On Thu, Apr 29, 2010 at 11:23 AM, Algoose Chase wrote:

> Hi,
>
> How do you define "without extra space" ?
> Doing any order traversal either using recursion or using iteration is
> going to take extra space .
>
> If you are given a binary tree represented by pointers that points to
> children nodes is it possible to do a heap sort without an array ?
>
>
> On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar wrote:
>
>> my choice is build  a min heap .sort the array with heap sort.then find
>> the median of the sorted array and build tree
>>
>>
>> On Wed, Apr 28, 2010 at 10:16 PM, Vivek S wrote:
>>
>>> @Rajesh Patidar
>>>
>>> I think we should do in Post order traversal alone. If we go by
>>> Preorder/Inorder we might lose track of children node that is currently
>>> being inserted into the BST. - correct me if im wrong :)
>>>
>>>
>>> On 28 April 2010 15:30, Rajesh Patidar  wrote:
>>>
>>>> pickup node in any order no matter(pre,post,inorder)  and just one by
>>>> one. start adding the node into bst no need to use extra space u have
>>>> to just ditach the node from binary tree and attach it in bst.
>>>>
>>>> On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra 
>>>> wrote:
>>>> > How to build BST from binary tree in place i.e without extra space ??
>>>> >
>>>> > --
>>>> > 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.
>>>> >
>>>>
>>>>
>>>>
>>>> --
>>>> BL/\CK_D!AMOND
>>>>
>>>> --
>>>> 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.
>>>>
>>>>
>>>
>>>
>>> --
>>> "Reduce, Reuse and Recycle"
>>> Regards,
>>> Vivek.S
>>>
>>> --
>>> 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] Build BST from binary tree without extra space

[Algoose Chase]

Hi,

How do you define "without extra space" ?
Doing any order traversal either using recursion or using iteration is going
to take extra space .

If you are given a binary tree represented by pointers that points to
children nodes is it possible to do a heap sort without an array ?

On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar wrote:

> my choice is build  a min heap .sort the array with heap sort.then find the
> median of the sorted array and build tree
>
>
> On Wed, Apr 28, 2010 at 10:16 PM, Vivek S  wrote:
>
>> @Rajesh Patidar
>>
>> I think we should do in Post order traversal alone. If we go by
>> Preorder/Inorder we might lose track of children node that is currently
>> being inserted into the BST. - correct me if im wrong :)
>>
>>
>> On 28 April 2010 15:30, Rajesh Patidar  wrote:
>>
>>> pickup node in any order no matter(pre,post,inorder)  and just one by
>>> one. start adding the node into bst no need to use extra space u have
>>> to just ditach the node from binary tree and attach it in bst.
>>>
>>> On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra 
>>> wrote:
>>> > How to build BST from binary tree in place i.e without extra space ??
>>> >
>>> > --
>>> > 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.
>>> >
>>>
>>>
>>>
>>> --
>>> BL/\CK_D!AMOND
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> "Reduce, Reuse and Recycle"
>> Regards,
>> Vivek.S
>>
>> --
>> 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] The Mystery Spiral

[Algoose Chase]

I have a logical question about the solution pasted.

The Problem says given N*N numbers filled in a matrix , print the numbers in
spiral .
What the code does is it fills the N*N numbers in spiral in decreasing order
and then prints the matrix contents left to right , top to bottom. Will the
two produce the same results ?
Or I understood the problem incorrectly ?


On Sat, Apr 17, 2010 at 6:53 PM, Chinmay S  wrote:

> *Problem statement:*
> Given a integer N, print N*N numbers in a N x N spiral.
>
> *Detailed problem description:*
> http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/
>
> *Solution:*
> Recently posted the following code.
> http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral-part2/
> (managed to compress it into as few as 99 lines)
>
>  Please comment on *further optimisations*(if any)...
> (any optimisations will do, either size OR performance)
>
> [image: spiralcode.jpg]
>
>  --
> 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 span of Increasing Pair in an array

[Algoose Chase]

Hi all,

How about this ?
set K to the first element i.e Array[0] and set j to the last element i.e
Array[size-1].
Decrement the index j until you find Array[j] > Array[j+1] and increment the
index k until you find Array[k] < Array[k-1] and do this until you find the
conditions met.
Does it solve the original problem ?

Or is it the largest Non decreasing sequence thats been asked in original
problem .


On Wed, Mar 24, 2010 at 1:08 PM, saurabh gupta  wrote:

> Hi Achala,
>
> This fails for:
> 0 1 2000 3 4 5 6
>
> prog's output:
> arr[j]=2000,arr[k]=0,j=2,k=0
>
> correct output should be:
> arr[j]=6,arr[k]=0,j=6,k=0
>
> you seem to be relying on the difference in the 'values' (contents) instead
> of the index span.
>
> On Mon, Mar 22, 2010 at 11:10 PM, achala sharma <3.ach...@gmail.com>wrote:
>
>> One Solution for Largest span in array,I have checked it on many
>> inputs,according to me its working fine
>>
>>
>> void Large_Span(int * arr,int num_elem)
>>
>> {
>>
>>  int j=1,k=0,i,prev_k=0;
>>
>>   for(i=1;i>
>>   {
>>
>> if(arr[i]>arr[i-1])
>>
>> {
>>
>>if((arr[j]-arr[k])<(arr[i]-arr[i-1]))
>>
>>{
>>
>>  if(j>
>>  {
>>
>>   j=i;
>>
>>  }
>>
>>  else if((jarr[i-1])||(j>arr[i] && k>arr[i-1]))
>>
>>  {
>>
>>   j=i;
>>
>>   k=i-1;
>>
>>  }
>>
>>
>>
>>}
>>
>>else if(arr[k]>arr[i-1])
>>
>>{
>>
>>  if(k>
>>  {
>>
>>   prev_k=k;
>>
>>   k=i-1;
>>
>>  }
>>
>>
>>
>>}
>>
>>else if(arr[j]>
>> j=i;
>>
>> }
>>
>>else
>>
>>{
>>
>>if(arr[k]>arr[i])
>>
>>{
>>
>>  if(i>j)
>>
>>  {
>>
>>   prev_k=k;
>>
>>   k=i;
>>
>>  }
>>
>>  else
>>
>>   k=i;
>>
>>}
>>
>>}
>>
>>   }
>>
>>   if(k>j)
>>
>>   {
>>
>>k=prev_k;
>>
>>   }
>>
>> printf("arr[j]=%d,arr[k]=%d,j=%d,k=%d",arr[j],arr[k],j,k);
>>
>> }
>>
>>
>> On Mon, Mar 22, 2010 at 8:28 AM, Manish wrote:
>>
>>> This does not look like a solution for the posted problem.
>>> This fails the test case {2, 7, 6, 0, 100}, where the answer should
>>> have been 4, for k=0 and j=4.
>>>
>>> Manish
>>>
>>> On Mar 20, 1:49 pm, saurabh gupta  wrote:
>>> > This may not be the optimal solution to
>>> > " Given an array of integers A[N], find the maximum value of (j-k) such
>>> > that A[k] <= A[j] & j>k.
>>> > I am looking for a solution with time complexity better than O(N^2)."
>>> >
>>> > this was in response to
>>> > "how u can solve it in o(n)"
>>> > and
>>> > "how to solve this in the claimed  O(N) time."
>>> >
>>> >
>>> >
>>>  > On Sat, Mar 20, 2010 at 9:14 PM, Ralph Boland 
>>> wrote:
>>> >
>>> > > On Mar 15, 10:07 am, saurabh gupta  wrote:
>>> > > > while you scan the array
>>> > > > maintain four indices plus two lengths
>>> > > > two indices and a length mark one sub-array - start,end, length
>>> > > > each such sub-array indicates a non-decreasing sequence,
>>> > > > call them S1 and S2.
>>> >
>>> > > > while one scans, S2 keeps track of incoming elements (curr
>>> sequence)
>>> > > > S1 keeps track of the maximum length (along with indices) so far
>>> (prev
>>> > > > sequence)
>>> > > > as one encounters an element which is less than the previous
>>> element,
>>> > > > this marks the end of S2,
>>> > > > S1 replaces S2 if len S2 > len S1 else S2 starts afresh from this
>>> new
>>> > > > element.
>>> >
>>> > > > In the end if len S2 > len S1 answer = S2
>>> > > > else answer = S1.
>>> >
>>> > > > PS: In the beginning and till one encounters a smaller element
>>>  than the
>>> > > > prev one for the first time, S1 = S2
>>> >
>>> > > I agree that this is a nice algorthithm that solves the
>>> > > largest non decreasing  sequence problem.
>>> > > However, I don't agree that this solves the problem
>>> > > originally posted.
>>> >
>>> > > Regards,
>>> >
>>> > > Ralph Boland
>>> >
>>> > > --
>>> > > 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.
>>> >
>>> > --
>>> > Man goes to doctor. Says he's depressed. Says life seems harsh and
>>> cruel.
>>> > Says he feels all alone in a threatening world where what lies ahead is
>>> > vague and uncertain. Doctor says "Treatment is simple. Great clown
>>> > Pagliacci is in town tonight. Go and see him. That should pick you up."
>>> Man
>>> > bursts into tears. Says "But, doctor...I am Pagliacci."
>>>
>>> --
>>> 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/

Re: [algogeeks] Re: Merge two BST in O(n) time with O(1)

[Algoose Chase]

Hi,

@Asish meena  and Arun :
   I dont think you can simply append a whole tree( BST2) at some
position just because the root of the BST2 is at its correct position.For
instance ,  Lets say you append BST2's Root anywhere within the left subtree
of BST1's Root. But if the right most leaf node of BST2 is greater than the
root of BST1, then the merged tree is no longer a binary search tree. Hence
your approach will not work in all cases.


On Wed, Feb 10, 2010 at 5:12 PM, r_arun  wrote:

> Your algorithm is correct. But
>
> > 3. Remove the children from this place and store them as BST3 and BST4.
>
> This is not required , because trying to merge BST2 with BST1,which is
> equivalent to finding a place to insert a pointer to root of BST2 in
> BST1. Whenever you need a place for a new node, you take a place of a
> existing leaf in BST1 for that new node. So we need not worry about
> children.
>
> Also in a BST there is no configuration for which a new element can
> not be inserted.
>
> So we can just link the pointers and get a merged tree.
>
> --
> 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] string ques

[Algoose Chase]

void FindPattern(string inputstring)
{
  int length = inputstring.length()
  int currentEnd = 1; //end position of the first substring to be searched
  int currentBeg = 0; //begining position of the first substring
  int Result = 0;
  char* Pattern= null;

  while( currentEnd < length-3) // we look for a pattern only until the 3rd
last char
  {
   Pattern = inputstring.substr(currentBeg,CurrentEnd);

   // Search for the pattern within the input string from Next charecter of
CurrentEnd.
   Result = inputstring.find(Pattern, CurrentEnd+1) ;

   // If Pattern Not found , Increase CurrentBeg by 1 char and start search
for next pair of chars
   if( Result = -1 )
   {
  CurrentBeg++;
  CurrentEnd = CurrentBeg + 1;
  Continue;
   }

   // If Pattern is Found . Print it! and Increase the Current End by 1 so
that now you search for a bigger pattern starting with same //first
charecter.
   Printf("%s\n",Pattern.c_str());
   CurrentEnd++;
  }
}

On Wed, Feb 3, 2010 at 1:30 AM, ankit mahendru wrote:

> Rephrasing the question again :
>
> Q. Find all the patterns  which are present in the character array given. A
> pattern is a sub-array containing 2 or more chars and is having a frequency
> of more than one.
>
> Example:
>
> i/p: aabcdadabc
>
> o/p: ab, abc, bc, da
>
> basically what we have to search is those sub-string(s) of length 2 or more
> which repeats itself(not necessarily twice, but 'n' number of times). In the
> above example 'ab' has been highlighted with red in order to make it
> clear.
>
> Another example:
>
> i/p : fghjerhjfgjefgh
>
> o/p: fg, je , hj, fgh
>
> I hope its clear now.
>
> Thanks
>
> Ankit Mahendru
>
>
> On Tue, Feb 2, 2010 at 8:31 PM, vivek bijlwan  wrote:
>
>> explain the question a little further please
>>
>>
>> On Tue, Feb 2, 2010 at 11:03 AM, Algoose Chase wrote:
>>
>>> Hope you meant a pattern is sub-array containing 2 or more UNIQUE chars.
>>> hope based on dfn, "abcd" is also a pattern in the input you have given.
>>>
>>>
>>> On Tue, Feb 2, 2010 at 1:11 AM, ankit mahendru <
>>> ankit.mahend...@gmail.com> wrote:
>>>
>>>> Q. Find all the patterns once which are present in the character array
>>>> given. A pattern is a sub-array containing 2 or more chars.
>>>>
>>>> Example:
>>>>
>>>> i/p: aabcdadabc
>>>>
>>>> o/p: ab, abc, bc, da
>>>>
>>>> --
>>>> 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 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] Add 2 long integers with digits represented by linked lists

[Algoose Chase]

@saurabh :
so you scanned to find out that both lists are same : O(n) (agreed)
prepare list 3 in time O(n) (agreed)
process list 3 in time O(n) (*HOW ??*)

can you run through your method and show how you process list 3 in O(n)
using the below lists as input:
5->5->5->5->5->5->5->5->5->5 and
4->4->4->4->4->4->4->4->4->5

hope you know the constraints : you cant reverse original list. and you cant
use recursion. and you need to traverse the list LEFT TO RIGHT to satisfy
the first 2 conditions.

Yes , I agree these lists takes O(n) time: list 1 = 4->7->8->1->6
list 2 = 2->3->4
but not in all cases.
I agree that for most cases(except the wild ones) the running time must be
O(n) only but you certainly need multiple passes depending upon the input.

Hope I am clear !


On Mon, Feb 1, 2010 at 11:39 PM, saurabh gupta  wrote:

> the key observation is that your requirement for no space is nullified by
> using the space in the resultant list.
>
> so you scanned to find out that both lists are same : O(n)
> prepare list 3 in time O(n)
> process list 3 in time O(n)
>
> current list 3 is the answer as list 4 is empty
> total time O(n) as k is small
>
>
>
> On Mon, Feb 1, 2010 at 11:19 PM, saurabh gupta  wrote:
>
>> nope,
>> if both lists are of same length list 4 is not required and you save time
>> to deal with list 4
>> so, you have list 3 only
>> time reqd is O(3n)
>>
>> 3 passes approximately
>>
>>
>>
>> On Mon, Feb 1, 2010 at 11:24 AM, Algoose Chase wrote:
>>
>>> Thats true ! ,  The purpose is to add very long integers such that we
>>> cant use premative data types to represent them.
>>>
>>>  The point I was trying to prove is : you would need to go through
>>> multiple passes through the list(essentially to propagate carry) when you
>>> have conditions like No Reversing the original lists and no recursion and no
>>> to any extra memory usage.
>>>
>>> @ saurabh: Hope you have not considered the worst case before
>>> generalizing the running time to 2n+m .
>>>
>>> lets assume the 2 lists are of same size so n = m.This eliminates the
>>> need to find out m or to create list 4
>>> and lets assume the linked list are  5->5->5->5->5->5->5->5->5->5 and
>>>
>>> 4->4->4->4->4->4->4->4->4->5
>>> Only thing is you need to create list 3 (as u have mentioned) . Now its
>>> not possible to add the 2 lists through a single pass from left to right .
>>> This would need n passes on a linked list of size n  making the running time
>>> n^2.
>>>
>>>
>>>
>>> On Thu, Jan 28, 2010 at 5:51 AM, saurabh gupta wrote:
>>>
>>>> this defeats the purpose,
>>>> they are stored in linked list because they cannot be stored in a given
>>>> type.
>>>>
>>>>
>>>>
>>>> On Thu, Jan 28, 2010 at 3:25 AM, Deva R  wrote:
>>>>
>>>>> i faced this qn in * interview.
>>>>>
>>>>> best soln i could give was:
>>>>>
>>>>> - traverse each list and derive both the numbers.. something like below
>>>>>
>>>>>   node = list->head;
>>>>>   i=1; value =0;
>>>>>while (node)
>>>>>{  value = (node->data)*i +value;
>>>>>   i*=10;
>>>>>   node = node->next;
>>>>>}
>>>>>
>>>>> - add both the numbers. u can either return the number or form a new
>>>>> list and return.
>>>>>
>>>>> i gave the code.. and its o(m+n), for lists of size m,n.
>>>>>
>>>>> -Deva
>>>>>
>>>>>
>>>>>
>>>>> On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta wrote:
>>>>>
>>>>>> step 1 is n not m
>>>>>> which makes it O(3n)
>>>>>>
>>>>>>
>>>>>> On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta wrote:
>>>>>>
>>>>>>> its not exponential
>>>>>>> time to find out m = m
>>>>>>> time to create list 3 = m
>>>>>>> time to create list 4 = n-m
>>>>>>> time to come up with proper added list (list 3 modification) = m
>>>>>>> time to merge list 3 and list 4 = n-m
>>>>>

Re: [algogeeks] string ques

[Algoose Chase]

Hope you meant a pattern is sub-array containing 2 or more UNIQUE chars.
hope based on dfn, "abcd" is also a pattern in the input you have given.

On Tue, Feb 2, 2010 at 1:11 AM, ankit mahendru wrote:

> Q. Find all the patterns once which are present in the character array
> given. A pattern is a sub-array containing 2 or more chars.
>
> Example:
>
> i/p: aabcdadabc
>
> o/p: ab, abc, bc, da
>
> --
> 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] Add 2 long integers with digits represented by linked lists

[Algoose Chase]

Thats true ! ,  The purpose is to add very long integers such that we cant
use premative data types to represent them.

 The point I was trying to prove is : you would need to go through multiple
passes through the list(essentially to propagate carry) when you have
conditions like No Reversing the original lists and no recursion and no to
any extra memory usage.

@ saurabh: Hope you have not considered the worst case before generalizing
the running time to 2n+m .

lets assume the 2 lists are of same size so n = m.This eliminates the need
to find out m or to create list 4
and lets assume the linked list are  5->5->5->5->5->5->5->5->5->5 and

4->4->4->4->4->4->4->4->4->5
Only thing is you need to create list 3 (as u have mentioned) . Now its not
possible to add the 2 lists through a single pass from left to right . This
would need n passes on a linked list of size n  making the running time n^2.



On Thu, Jan 28, 2010 at 5:51 AM, saurabh gupta  wrote:

> this defeats the purpose,
> they are stored in linked list because they cannot be stored in a given
> type.
>
>
>
> On Thu, Jan 28, 2010 at 3:25 AM, Deva R  wrote:
>
>> i faced this qn in * interview.
>>
>> best soln i could give was:
>>
>> - traverse each list and derive both the numbers.. something like below
>>
>>   node = list->head;
>>   i=1; value =0;
>>while (node)
>>{  value = (node->data)*i +value;
>>   i*=10;
>>   node = node->next;
>>}
>>
>> - add both the numbers. u can either return the number or form a new list
>> and return.
>>
>> i gave the code.. and its o(m+n), for lists of size m,n.
>>
>> -Deva
>>
>>
>>
>> On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta wrote:
>>
>>> step 1 is n not m
>>> which makes it O(3n)
>>>
>>>
>>> On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta wrote:
>>>
>>>> its not exponential
>>>> time to find out m = m
>>>> time to create list 3 = m
>>>> time to create list 4 = n-m
>>>> time to come up with proper added list (list 3 modification) = m
>>>> time to merge list 3 and list 4 = n-m
>>>>
>>>> total time = 2n+m
>>>>
>>>> except step 1 all are reversals with approximately same constant and
>>>> constant for step 1 is smaller
>>>> so one can say
>>>>
>>>> O(2n+m)
>>>>
>>>>
>>>> On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia wrote:
>>>>
>>>>> If that is the representation, then the lists have to be reversed.
>>>>> Otherwise the time goes up exponentially.
>>>>>
>>>>> On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase 
>>>>> wrote:
>>>>> > Condition:
>>>>> > Can we do it keeping the original lists intact ? ie without reversing
>>>>> it.
>>>>> > I mean , No recursion & no Reversing ... is it possible ?
>>>>> >
>>>>> > @kumar :
>>>>> > 15234 is represented as  1->5->2->3->4
>>>>> >
>>>>> > On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta 
>>>>> wrote:
>>>>> >>
>>>>> >> perhaps you mean,
>>>>> >> reverse each link list O(n+m).
>>>>> >> then sum each node with carryover maintained.
>>>>> >>
>>>>> >> On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia <
>>>>> abhati...@gmail.com>
>>>>> >> wrote:
>>>>> >>>
>>>>> >>> Let us take an example -
>>>>> >>>
>>>>> >>> Num 1 = 123456
>>>>> >>> Num 2= 1234
>>>>> >>> Link-1->Link-2->Link-3->Link-4->Link5->Link6
>>>>> >>> Link-1->Link-2->Link-3->Link-4
>>>>> >>>
>>>>> >>> Add nodes into linkedlist 1 till either one of the list is not
>>>>> null.
>>>>> >>> Make sure you process the carry in each iteration.
>>>>> >>>
>>>>> >>>
>>>>> >>> --AB
>>>>> >>>
>>>>> >>>
>>>>> >>> On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase <
>>>>> harishp...@gmail.com>
>>>>> >>> wrote:
>>>>> &g

Re: [algogeeks] Add 2 long integers with digits represented by linked lists

[Algoose Chase]

Condition:
Can we do it keeping the original lists intact ? ie without reversing it.
I mean , No recursion & no Reversing ... is it possible ?

@kumar :
15234 is represented as  1->5->2->3->4


On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta  wrote:

> perhaps you mean,
> reverse each link list O(n+m).
> then sum each node with carryover maintained.
>
> On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia wrote:
>
>> Let us take an example -
>>
>> Num 1 = 123456
>> Num 2= 1234
>> Link-1->Link-2->Link-3->Link-4->Link5->Link6
>> Link-1->Link-2->Link-3->Link-4
>>
>> Add nodes into linkedlist 1 till either one of the list is not null.
>> Make sure you process the carry in each iteration.
>>
>>
>> --AB
>>
>>
>> On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase 
>> wrote:
>> > conditions:
>> > NO extra memory (@ stack or Heap) at all. No recursion.
>> >
>> > Any body has got any hint about how to get this done ?
>> >
>> >
>> >
>> > --
>> > 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.

[algogeeks] Add 2 long integers with digits represented by linked lists

[Algoose Chase]

conditions:
NO extra memory (@ stack or Heap) at all. No recursion.

Any body has got any hint about how to get this done ?

-- 
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] Algorithm for vector problem

[Algoose Chase]

void PrintFamilyTree(const short& generation)
{
  printf("Name : %s Generation = %d\n", m_Name.c_str(),generation);

  vector::iterator it;

  for (it = this.begin(); it< this.end() ;it++)
  {
 it->PrintFamilyTree(generation+1);
  }
}


On Tue, Nov 24, 2009 at 9:20 PM, Aditya Shankar <
iitm.adityashan...@gmail.com> wrote:

>
> Hi,
>
> On Tue, Nov 24, 2009 at 6:38 PM, Ankur  wrote:
>
>> What would be the best algorithm for the undermentioned problem.
>>
>> Implement method PrintFamilyTree() that prints out the Name and
>> Generation of the tree
>> Output should resemble
>> Name: Jan Generation:0
>> Name: Mike Generation:1
>> Name: Greg Generation:2
>> Name: Carol: Generation: 2
>> Name: Peter Generation: 3
>> Name: Marcia Generation: 3
>> Name: Bobby Generation: 1
>>
>> The order you have mentioned is preorder traversal of the tree.
>
> Regards
> Aditya Shankar
>
>> class Human : public std::vector
>> {
>> public:
>> Human(const std::string &name) : m_Name(name) {};
>> virtual void PrintFamilyTree(const short &generation = 0) const;
>> protected:
>> std::string m_Name;
>> };
>>
>> class Male: public Human
>> {
>> public:
>> Male(const std::string &name) : Human(name) {};
>> };
>>
>> class Female: public Human
>> {
>> public:
>> Female(const std::string &name) : Human(name) {};
>> };
>>
>> void main()
>> {
>> Male m1("Mike"), m2("Greg"), m3("Peter"), m4("Bobby");
>> Female f1("Carol"), f2("Marcia"), f3("Jan");
>>
>> m1.push_back(&m2);
>> f1.push_back(&m3);
>> f1.push_back(&f2);
>> m1.push_back(&f1);
>> f3.push_back(&m1);
>> f3.push_back(&m4);
>>
>> f3.PrintFamilyTree();
>>
>> --
>>
>> 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: Print binary tree in spiral

[Algoose Chase]

I posted this long b4 but dint see this error : Delivery to the following
recipient failed permanently: algogeeks@googlegroups.com
re-posting:
BST_Spiral(struct node* root)
{
  ht = Height(root);

  for( i = 0; i<= ht; i++)
  {
PrintSpiral(root, i, i%2  /*flip 1 and 0 alternately on each
iteration*/);
  }

void PrintSpiral(struct node* root, int level, bool bRTL/* Right-To-Left */)
{
  if ( root == NULL) return;

 if( level == 0 )
 {
   printf("%d", root->data)
   return;
 }

 if( bRTL )
 {
   PrintSpiral(root->right,level-
1,bRTL)
   PrintSpiral(root->left,level-1,bRTL)
 }
 else
 {
   PrintSpiral(root->left,level-1,bRTL)
   PrintSpiral(root->right,level-1,bRTL)
 }
}


On Tue, Nov 24, 2009 at 11:12 AM, Rohit Saraf
wrote:

> And it cannot be made more efficient.
>
> --
> 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 nearest point

[Algoose Chase]

Hi ,

I dont mean to present the exact solution but a trivial and
(hopefully)possible one.
Maintain 2  vectors one sorted based on Latitude values
and other sorted based on Longitude values.
Given a coordinate say (x,y) , from the vector sorted based on latitudes
identify the coordinates whose latitude is close to X and keep a track of
them. Similarly from the other vector note down the coordinates whose
longitudes are close to Y.

Now the nearest person to the given point x,y must be within the two subsets
and find distance from each coordinates within the subset to the given point
x,y.

The tricky part is identifying which coordinates from the 2 vectors are
close to the given point.

Hope there must be a better solution than this.

Given an element within the vector, we should be
2009/11/17 Tiago Reul 

> Suppose that you have the position of each person in the world.
> Position is the pair (latitude, longitude).
>
> How to represent the data so that I can find the nearest person
> from a point (φ,λ) without comparing to every pair in the collection?
>
> --
>
> 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=.
>
>
>

--

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=.