Re: [algogeeks] Re: DP equation for interval problem

[anshu]

@ all.
what if we use greedy approch..like if we slice when in remaining fruits on 
screen any one fruit is going to disappear?will it work?



On Friday, February 1, 2013 9:07:14 AM UTC+5:30, emmy wrote:
>
> Ohk.. I finally got it.
> Thanks guys!!
> This was great help.
>
>
> On Mon, Jan 28, 2013 at 4:11 PM, Nikhil Karnwal 
> 
> > wrote:
>
>> no ...when u figure out those m matches just sort them ..now let k=[0,m]
>> if currently u are assuming that kth match is already sliced then all 
>> before that k matches are already sliced.and this u can do by moving 
>> incrementally from 0 to mth matches. 
>>
>> On Mon, Jan 28, 2013 at 1:43 PM, foram lakhani 
>> 
>> > wrote:
>>
>>> by match u mean that number of fruits that overlap with i th fruit but 
>>> are not sliced before time i.
>>> which means we have to consider 2^m cases where m is the maximum number 
>>> of fruits that overlap with ith fruit.
>>>  And this we have to do for each fruit.
>>>
>>> On Mon, Jan 28, 2013 at 12:54 AM, Nikhil Karnwal 
>>> 
>>> > wrote:
>>>
 Actually dp[i] represent the state in which u make a slice at appearing 
 time of i th fruits.and match represent the overlapping fruits  
 with i.
 so 
 for each i dp[i]=max(dp[i],dp[j]+match);
 for all j=[0,i] and match =overlapped fruits with i which are not 
 sliced until the cut of j.
 Hope this will help.
 Thanks

 On Thu, Jan 24, 2013 at 10:18 PM, foram lakhani 
 
 > wrote:

> Thanx for the reply but I didnt get you. What does dp[i] represent ?
>
>
>  On Thu, Jan 24, 2013 at 9:50 PM, sunny 
> > wrote:
>
>> take a structure or pair of start time and finish time and then sort 
>> the the structure you know the comparator function  the for each for 
>> each 
>> dp[i] select j belongs to  (0,i) and then count the overlap value 
>>
>>
>> if(j==0)
>> dp[i]=max(dp[i],match);
>> else
>>  dp[i]=max(dp[i],dp[j-1]+match);
>>
>>
>> with this recursive relation my code got accepted in .24 sec others 
>> approach you mentioned may lead to the TLE
>>
>> On Thursday, January 24, 2013 1:35:38 PM UTC+5:30, emmy wrote:
>>>
>>> please help me with the following problem:
>>>  
>>> http://www.spoj.com/problems/**JUICE/
>>>
>>> bit mask will require very large memory.
>>> If I sort the intervals in decreasing order of their start time.. I 
>>> still cant make it to a dp
>>> If I sort the intervals in decreasing order of their finish times I 
>>> am still not getting a recurrence for dp that is valid
>>> If I convert this to an interval graph, I have to find the maximum 
>>> number of vertices that can be included in some clique of size >=3. But 
>>> this also seems like a brute force approach. 
>>>
>>> Which approach to try?? please help!!
>>>
>>>  -- 
>>  
>>  
>>
>
>  -- 
>  
>  
>

  -- 
 You received this message because you are subscribed to the Google 
 Groups "Algorithm Geeks" group.
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com .
 For more options, visit https://groups.google.com/groups/opt_out.
  
  

>>>
>>>  -- 
>>> You received this message because you are subscribed to the Google 
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send 
>>> an email to algogeeks+...@googlegroups.com .
>>>
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>  
>>>  
>>>
>>
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to algogeeks+...@googlegroups.com .
>>
>> For more options, visit https://groups.google.com/groups/opt_out.
>>  
>>  
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Directi Interview Ques

[Anshu Mishra]

two arrays are suppose x[n], y[n];

take a function
f( x(i, n), y(j, n) , 0) --> taking x[i] as a first element of merged array
then max sum;
f( x(i, n), y(j, n), 1)  --> taking y[j] as a first element of merged array
then max sum;


f( x(i, n), y(j, n) ,0) = max(  { x[i] * x[i+1] +  f( x(i+1, n), y(j, n),
0)  }, { x[i] * y[j] +  f( x(i+1, n), y(j, n), 1 ) } );
f( x(i, n), y(j, n) ,1) = max(  { x[i] * y[j] +  f( x(i, n), y(j+1, n), 0)
 }, { y[j] * y[j+1] +  f( x(i, n), y(j+1, n), 1 ) } );

final sol = max (  f( x(0, n), y(0, n) ,0), f( x(0, n), y(0, n) ,1) );

Now it's looking a very simple *dp *problem with O(n^2) time and space
complexity. :)

-- 
Anshuman Mishra | Software Development Engineer | Amazon

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

[Anshu Mishra]

on first iteration *ptr == 'h'  so it will enter in the loop.
   ptr++ --> *ptr == 'e';
  comparing *ptr with least i.e 127 (ascii)  *ptr will be 'e' now;
2nd iteration *ptr == e
ptr++ -> *ptr = 'l'
comparing 'e' with 'l' and 'e' will be assgined to least and so on;

coz 'e' has the lowest ascii value in given set of characters so least will
never change when first time it is assgined to 'e';

-- 
Anshuman Mishra | Software Development Engineer | Amazon

-- 
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: candies - interviewstreet -- how to go about solving this problem

[Anshu Mishra]

@sanjay it's not like that

e.g : (3 5 6 7 8 4) 7
1 2 3 4 5 1  2
Yes we have to increase just by one, but while decreasing choose the lowest
possible such that each trivial component, if it is in decreasing phase,
should end with 1.

On Mon, Jul 9, 2012 at 12:53 PM, sanjay pandey wrote:

> does ur sol seems lyk incerasing 1 if next number is greater that prev n
> decreasing 1 if less..???
>
>  --
> 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.
>



-- 
Anshuman Mishra | Software Development Engineer | Amazon

-- 
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] MS Design Ques

[Anshu Mishra]

Best will be storing BIG_INT in array of integers.

int [] val; //store actual number
int size; // required length of val array.

take the string as input for constructors and convert it into 2's
complement form, maintaining little endian order or big endian order.
Perform other operation keeping order in mind.



On Sat, Jul 7, 2012 at 5:23 PM, sravanreddy001 wrote:

> i was thinking of character array. which is same as string.
> Any thoughts on better alternatives?
>
>
> On Friday, 6 July 2012 13:34:01 UTC-4, anshu wrote:
>>
>> yes, We can have much better data structure for storing big integer
>> instead of string just for simplicity I have taken string.
>>
>> On Fri, Jul 6, 2012 at 11:11 AM, Mithun Kumar wrote:
>>
>>> @anshuman...
>>>
>>> Are you converting numbers to string because data types ranges
>>> and precision differs? or is there any other reason?
>>>
>>> -mithun
>>>
>>> On Fri, Jul 6, 2012 at 12:58 AM, payal gupta wrote:
>>>
>>>> thnx...4 d rply..
>>>>
>>>> Regards,
>>>> PAYAL GUPTA,
>>>> NIT-B.
>>>>
>>>>
>>>> On Fri, Jul 6, 2012 at 12:43 AM, Anshu Mishra <
>>>> anshumishra6...@gmail.com> wrote:
>>>>
>>>>> First define all the basic operation you can apply on two numbers.
>>>>>
>>>>> Binary operation : +, -, *, /, %, optional(&(and), |(or), ^(xor))
>>>>> Unary operation : !, ~, -
>>>>> Comparison : <, > ==, !=
>>>>>
>>>>> Define all these operation.
>>>>>
>>>>> Most simplest one can be,
>>>>> class BIG_INT {
>>>>>private string val;
>>>>>//Define constructor
>>>>>private BIG_INT(){}
>>>>>public BIG_INT(int x) {
>>>>>this.val = x.toString();
>>>>>}
>>>>>public BIG_INT(long x) {
>>>>>this.val = x.toString();
>>>>>}
>>>>>public BIG_INT(string x) {
>>>>>this.val = x;
>>>>>}
>>>>>public BIG_INT add(BIG_INT x);
>>>>>public BIG_INT add(int x);
>>>>>public BIG_INT add(long x);
>>>>>
>>>>>   similarly write methods for other operation also;
>>>>>
>>>>>   }
>>>>>
>>>>> If this question asked for only design testing purpose only all method
>>>>> declaration will be sufficient.
>>>>>
>>>>> --
>>>>> Anshuman Mishra | Software Development Engineer | Amazon
>>>>>
>>>>>
>>>>>  --
>>>>> 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+unsubscribe@**
>>>>> googlegroups.com .
>>>>> For more options, visit this group at http://groups.google.com/**
>>>>> group/algogeeks?hl=en <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+unsubscribe@**
>>>> googlegroups.com .
>>>> For more options, visit this group at http://groups.google.com/**
>>>> group/algogeeks?hl=en <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+unsubscribe@**
>>> googlegroups.com .
>>> For more options, visit this group at http://groups.google.com/**
>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>.
>>>
>>
>>
>>
>> --
>> Anshuman Mishra | Software Development Engineer | Amazon
>>
>>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/pkUNaazktKAJ.
>
> 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.
>



-- 
Anshuman Mishra | Software Development Engineer | Amazon

-- 
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] MS Design Ques

[Anshu Mishra]

yes, We can have much better data structure for storing big integer instead
of string just for simplicity I have taken string.

On Fri, Jul 6, 2012 at 11:11 AM, Mithun Kumar  wrote:

> @anshuman...
>
> Are you converting numbers to string because data types ranges
> and precision differs? or is there any other reason?
>
> -mithun
>
> On Fri, Jul 6, 2012 at 12:58 AM, payal gupta  wrote:
>
>> thnx...4 d rply..
>>
>> Regards,
>> PAYAL GUPTA,
>> NIT-B.
>>
>>
>> On Fri, Jul 6, 2012 at 12:43 AM, Anshu Mishra 
>> wrote:
>>
>>> First define all the basic operation you can apply on two numbers.
>>>
>>> Binary operation : +, -, *, /, %, optional(&(and), |(or), ^(xor))
>>> Unary operation : !, ~, -
>>> Comparison : <, > ==, !=
>>>
>>> Define all these operation.
>>>
>>> Most simplest one can be,
>>> class BIG_INT {
>>>private string val;
>>>//Define constructor
>>>private BIG_INT(){}
>>>public BIG_INT(int x) {
>>>this.val = x.toString();
>>>}
>>>public BIG_INT(long x) {
>>>this.val = x.toString();
>>>}
>>>public BIG_INT(string x) {
>>>this.val = x;
>>>}
>>>public BIG_INT add(BIG_INT x);
>>>public BIG_INT add(int x);
>>>public BIG_INT add(long x);
>>>
>>>   similarly write methods for other operation also;
>>>
>>>   }
>>>
>>> If this question asked for only design testing purpose only all method
>>> declaration will be sufficient.
>>>
>>> --
>>> Anshuman Mishra | Software Development Engineer | Amazon
>>>
>>>
>>>  --
>>> 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.
>



-- 
Anshuman Mishra | Software Development Engineer | Amazon

-- 
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] MS Design Ques

[Anshu Mishra]

First define all the basic operation you can apply on two numbers.

Binary operation : +, -, *, /, %, optional(&(and), |(or), ^(xor))
Unary operation : !, ~, -
Comparison : <, > ==, !=

Define all these operation.

Most simplest one can be,
class BIG_INT {
   private string val;
   //Define constructor
   private BIG_INT(){}
   public BIG_INT(int x) {
   this.val = x.toString();
   }
   public BIG_INT(long x) {
   this.val = x.toString();
   }
   public BIG_INT(string x) {
   this.val = x;
   }
   public BIG_INT add(BIG_INT x);
   public BIG_INT add(int x);
   public BIG_INT add(long x);

  similarly write methods for other operation also;

  }

If this question asked for only design testing purpose only all method
declaration will be sufficient.

-- 
Anshuman Mishra | Software Development Engineer | Amazon

-- 
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: Reverse Engg.

[anshu mishra]

awesome question :D :D

-- 
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] LCA of a Binary tree not a binary search tree

[anshu mishra]

first try to understand the sol then comment. it is for binary tree not for
BST.

On Mon, Nov 21, 2011 at 10:25 PM, Piyush Grover
wrote:

> For BST it would be rather simpler. find the first node which lies in
> between the two.
>
> On Wed, Nov 16, 2011 at 1:44 PM, anshu mishra 
> wrote:
>
>> Node *LCA(node *root, node *e1, node *e2, int &x)
>>
>> {
>>
>> Node *temp =NULL;
>>
>> Int y = 0;
>>
>> If (root->left) temp = LCA(root->left, e1, e2, y);
>>
>> x+=y;
>>
>> if (temp) return temp;
>>
>>if (x==2) return node;
>>
>> y = 0;
>>
>> If (root->right) temp = LCA(root->right, e1, e2, y);
>>
>> x+=y;
>>
>> if (temp) return temp;
>>
>> if (x==2) return node;
>>
>> If (root == e1 || root == e2) x++;
>>
>> Return null;
>>
>> }
>>
>> --
>> 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.
>



-- 
Anshuman Mishra | Software Development Engineer | Amazon

-- 
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] LCA of a Binary tree not a binary search tree

[anshu mishra]

Node *LCA(node *root, node *e1, node *e2, int &x)

{

Node *temp =NULL;

Int y = 0;

If (root->left) temp = LCA(root->left, e1, e2, y);

x+=y;

if (temp) return temp;

   if (x==2) return node;

y = 0;

If (root->right) temp = LCA(root->right, e1, e2, y);

x+=y;

if (temp) return temp;

if (x==2) return node;

If (root == e1 || root == e2) x++;

Return null;

}

-- 
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] Amazon Question - Find Pythagorean triplet in an unsorted array

[anshu mishra]

@Ravindra

To check the particular number square can be written as sum of two squares
or not.

If it has any prime factor x such that x % 4 == 1 then only.

Now about time complexity.

suppose u have given array is.

10 6 13 9 17 4 18 12 1 5.

now u can easily skip the numbers(1, 4, 6, 9, 12, 18);


and u have to check only for these numbers(5, 10, 13, 17);

so time complexity will reduce to O(n * (number of side which can be largest
one for any triplet) ).

-- 
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] Amazon Ques Suggest Algo

[anshu mishra]

index  =  0 1 2  3  4 5  6
ar   =  0 1 2 -4 -3 6 -3
sumar =  0 1 3 -1 -4 2 -1

first index where we get the number which has already appeared in sumar will
be the last index of sub array whose sum will be zero and (index of first
apperance of this number + 1) in sumar will be the start index.

so start index = 3 + 1 = 4;
last index = 6;

By set or treeMap we can solve it in O(nlogn) and by hashMap we can solve it
in O(n).

-- 
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] Amazon Question - Find Pythagorean triplet in an unsorted array

[anshu mishra]

@Ravindra
may be the interviewer wants from u that instead of blindly checking for
every number. first check that particular number can be written as the sum
of two squares or not if yes than only search for that number. So the order
will be decrease from O(n^2) to O(n * (number of side which is largest one
for any triplet)) and in practical it will be much less compare to O(n^2);

-- 
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] Reconstruct BST from preorder traversal

[anshu mishra]

@Anand

As given it is a BST so any single traversal(pre or post or in) is
sufficient to construct the tree. :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.

Re: [algogeeks] Reconstruct BST from preorder traversal

[anshu mishra]

this is an O(n^2) solution. By pre processing the array we can also solve it
O(n)

int find_mid(int ar[], int s, int e, int val)
{
int i;
for (i = s; ar[i] < val; i++);
return i;
}
node * constructTree(int ar[], int s, int e)
{
node *root;
root = new node();
root->val = ar[s];
root->left = root->right = NULL;
int mid = find_mid(ar, s+1, e, ar[s]);
if (s+1 < mid)
root -> left = constructTree(ar, s+1, mid);
if (mid < e)
root -> right = constructTree(ar, mid, e);
return root;
}

-- 
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: Algo for Search in a 2D Matrix

[anshu mishra]

struct data
{
int row, col,
int val;
};

priority_queue heap;

now fine?

-- 
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: Algo for Search in a 2D Matrix

[anshu mishra]

push the two adjacent element that is one right and below

-- 
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: Algo for Search in a 2D Matrix

[anshu mishra]

If O(k*logk) solution is acceptable then it is very simple.

maintain a min heap.
push a[0][0],
i = 0;
while ( i < k)
{
pop an element. ---> O(log(i)) --> coz number of elements in heap is i;
push the two adjacent element that is one right and right below. --->
O(log(i));
i++;
}
last element popped will be answer.

size of heap at every iteration will increase by one coz we are inserting
two elements and removing one element at every iteration.

If anyone has doubt on correctness of this solution can ask.

-- 
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] How to Solve This

[anshu mishra]

@amol
I was not sure that for every number that has 3 in its unit place has one
multiple which has all one. So I used that is if the remainder is coming
that already appeared stop there coz it will make stuck in a loop.
for ex. remainders are
1 3 19 23 37 1 3 19  that will repeat.

but it in this case u can remove the set. Code will look more simpler.

string all1Multiple(int x)
{
string s;
int r=1;
do
{
s += '1';
r = r % x;
r = r * 10 + 1;
} while(r != 1);
return s;
}

-- 
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] subset of an array

[anshu mishra]

the simplest code could be for this question is

void printAllSubsetSum(int ar[], int n, int x)
{
for (i = 0; i < (1

Re: [algogeeks] How to Solve This

[anshu mishra]

string all1Multiple(int x)
{
string s;
set mySet;
mySet.push(0);
int psize, r=1;
do
{
psize = mySet.size();
s += '1';
r = r % x;
mySet.push(r);
r = r * 10 + 1;
} while(mySet.size() > psize);

if (r != 1) return "not Possible";
return s;
}

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

[anshu mishra]

wat is ur question finding maximum path sum or anything other 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 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] Tree Center Problem

[anshu mishra]

do this way.

start with any node(k) calculate sk = sum(k, i) for all i  0 <= i < n;

and u can easily get sj = sum(j,i) where j is adjacent to k; in O(n);

suppose nj = number of nodes remains after removing edge(j,k) in subtree
containing node j;
suppose nk = number of nodes remains after removing edge(j,k) in subtree
containing node k;
sj = sk - nj * edgecost(j,k) + nk * edgecost(j,k);

traverse the tree in bfs or dfs manner.

maintain a minsum at every node compare it and modify accordingly.

for ni (for all 0<=i < n) you have to preprocess the tree and u can get all
in O(n);

avgcost = minsum/n;

-- 
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: best way to learn data structure

[anshu mishra]

In which year you are now. May i can give you some idea.

-- 
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: Array Problem??

[anshu mishra]

int count(int x, int tree[], int s, int e, int n)
{
tree[n]++;
if (s==e) return 0;
int cnt = 0;
int mid = (s+e)/2;
if (mid < x)  return tree[2*n+1]+count(x, tree, mid+1, e, 2*n+2);
else return count(x, tree, s, mid, 2*n+1);
}

main()
{
  for(i=n-1;i>=0; i--)
  {
  sol[i] = insert(ar[i], tree, 0, n-1, 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.

Re: [algogeeks] Re: Array Problem??

[anshu mishra]

use segment tree or binary index tree to solve O(nlogn)

-- 
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] Find lowest common ancestor of Binary Tree

[anshu mishra]

node* LCA(node *root, node *n1, node *n2, int &x)
{
int y = 0;
node *temp;

if (root->left) temp = LCA(root->left, n1, n2, y);
x += y;
if (temp != NULL) return temp;
if (x == 2) return node;

if (root->right) temp = LCA(root->right, n1, n2, y);
x += y;
if (temp != NULL) return temp;
if (x == 2) return node;

if (root == e1 || root == e2) x++;
return NULL:
}

-- 
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] doubt???

[anshu mishra]

You cant do.

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

Re: [algogeeks] Re: MS Question -> Median of a BST without using extra space and in O(n)

[anshu mishra]

*@all to median of BST time O(n) space O(1) (modified code of nitin to
get median)


medianBST*(node, n)
  int x = 0;
  *while* hasleftchild(node) *do*
node = node.left
  *do*

x++;
if (x == n/2) return node->val;
*if* (hasrightchild(node)) *then*
  node = node.right
  *while* hasleftchild(node) *do*
node = node.left
*else*

  *while* node.parent ≠ *null* *and* node == node.parent.right *do*
node = node.parent
  node = node.parent
  *while* node ≠ *null*


@dheeraj u

U  can get the number of elements by just traversing the who tree by above
method

-- 
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: MS Question -> Median of a BST without using extra space and in O(n)

[anshu mishra]

its not o(n) it is O(max height of tree) :P
i have not seen the constraint.

-- 
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] MS Question -> Median of a BST without using extra space and in O(n)

[anshu mishra]

int bstMedian(node *root, int n, int &x)
{
if (node->left) return bstMedian(root->left, n, x);
x++;
if (x == n/2) return node->val;
if (node->right) return bstMedian(root->right, n, x);
}
call bstMedian(root, n, 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.

Re: [algogeeks] MS Question -> Median of a BST without using extra space and in O(n)

[anshu mishra]

do the inorder traversal as soon as reached at n/2th element that will be
median.

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

[anshu mishra]

suppose adress of a = 0x12;
0x12 has 
0x13 has 0001
so p = 0x12;
p++ = 0x13;
now modifying the value pointed p by will modify the  only 0x13 bcoz it is
char type pointer and its value wiil be 0010

so finally 0x12 to 0x15 will have 512

-- 
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] Function pointer

[anshu mishra]

as function object also

-- 
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] Amazon SDE onsite interview question

[anshu mishra]

explanation:

Node :
lock - that node is locked or not;
lockedDesc - number of descendents locked of that node
left, right,par as name sugest;

unLock():
when we unlock a node than all its ancestor has to decrease its lockedDesc
value by 1.

Lock():
when we lock a node than all its ancestor has to increase its lockedDesc
value by 1.

I hope now it should be clear. :)

-- 
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: What is the time to get min element from the binary max heap !!

[anshu mishra]

If we know the size of heap we can get the minimum element in O(n);

int findMinFromMaxHeap(int ar[], int n)
{
  if ( (n+1) & n == 0)
  {
  for (i = n>>1; i < n; i++)
   min = min > ar[i] ? ar[i] : min;
  }
  else
  {
 int x = n, y = 1;
  while(x >1)
  {
   y <<= 1;
   x >>= 1;
  }
  y -= 1;
  x = (n - y + 1) / 2;
  for (i = y / 2 + x; i < n; i++)
  min = min > ar[i] ? ar[i] : min;
}
return min;
}

-- 
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] Amazon SDE onsite interview question

[anshu mishra]

for simplicity i am doing it for binary tree (liittle modification)

struct node
{
 bool lock;
 int lockedDesc;
 node *left, *right, *par;
};

bool Islock(node *cur)
{
return cur->bool;
}

void unLock(node *cur)
{
 node *temp;
 cur->lock = false;
 temp = cur->par;
 while (temp != NULL)
 {
 temp->lockedDesc--;
 temp = temp->par;
 }
}

bool Lock(node *cur)
{
 if (cur->lockedDesc) return false;
 node *temp = cur->par;
 while (temp != NULL && temp->lock== false)
 {
 temp->lockedDesc++;
 temp = temp->par;
 }
if (temp == NULL)
{
cur->lock = true;
return true;
}
cur = cur->par;
while (cur != temp)
{
cur->lockedDesc--;
cur= cur->par;
}
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 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] Amazon SDE onsite interview question

[anshu mishra]

for simplicity i doing it for binary tree

struct node
{
 bool lock;
 int lockedDesc;
 node *left, *right, *par;
};

bool Islock(node *cur)
{
return cur->bool;
}

void unLock(node *cur)
{
 node *temp;
 cur->lock = false;
 temp = cur->par;
 while (temp != NULL)
 {
 temp->lockedDesc--;
 temp = temp->par;
 }
}

bool Lock(node *cur)
{
 if (cur->anydesc) return false;
 node *temp = cur->par;
 while (temp != NULL && temp->lock== false)
 {
 temp->lockedDesc++;
 temp = temp->par;
 }
if (temp == NULL)
{
cur->lock = true;
return true;
}
cur = cur->par;
while (cur != temp)
{
cur->lockedDesc--;
cur= cur->par;
}
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 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] Array A and B

[anshu mishra]

you can use mergesort technique, segment tree, binary index tree or BST

-- 
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] MICROSOFT WRITTEN IN VASAVI

[anshu mishra]

void allCase(string r)
{
int n = s.sise();
string s;
for (i = 0; i < (1 << n); i++)
{
 s = r;
  for ( j = 0; j < n; j++)
  {
if ( i & ( 1 << j) )
{
  s[j] = s[j] + ('a' - 'A');
}
  }
  cout << s << endl;
}
}

-- 
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: convert a word into a palindrome with minimum addition of letters to it

[anshu mishra]

http://www.spoj.pl/problems/AIBOHP/

same problem u have asked!!

-- 
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: print all paths which sum up to a value.

[anshu mishra]

start  from leaves.(leaves have possible sum only its value)
go up step by step
save all the possible sums on that node.

for example
if left node has possible sums( 4, 6, 7 ,13) and right node has
possible sums (3, 5, 9); and node itself value has 5 than
this node all possible sums will be (8, 10, 11, 12, 14, 18)

till u reach the root node u have all possible sums at each node.

search ur desired sum node in the tree track all possible path for that
sum(u have to just only downside of the 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.

[algogeeks] Re: Plz tell wat questions are asked by MICROSOFT IDC and IT both...Plz Reply fast.....anyone...!!

[anshu kandhari]

How you got the call buddy


On Aug 10, 11:43 pm, vishwan baghla  wrote:
>

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

[algogeeks] get rid of sohail panzer spam

[anshu]

For those people who want to get rid of sohail panzer spam
create a filter
>From : sohail.panz...@gmail.com

mark on Delete it

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

Re: [algogeeks] Re: Binary Tree Problem

[anshu mishra]

little modification
start with any node(r) find the node(x) which is at maximum distance.

-- 
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: Binary Tree Problem

[anshu mishra]

this is a very standard problem :D

start with any node(x) find the node which is at maximum distance.

now start with x travese the tree and find the node(y) which is at maximum
distance.

so finally answer wil be (x, y)

traversing the tree two times. so the order for finiding the such nodes
equals to O(n);

-- 
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: Finding Blocks in a matrix

[anshu mishra]

main()
{
for (i = 0; i < n; i++)
{
 for (j = 0; j < n; j++)
 {
if (flag[i][[j])
   {
 bfs(mat, flag, i, j);
 count++;
   }
 }
}
}
bfs(mat[][], flag[][], i, j)
while (!q.empty())
{
x = q.top();
q.pop();
if(node notvisited already && adjacent to x && value = x)
add to queue
}
}

this is thw whole code

-- 
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: A Graph Problem

[anshu mishra]

biaprtie graph is special case when we can color the whole graph just  by
two colors.

-- 
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: Finding Blocks in a matrix

[anshu mishra]

@ross no, a particular element has to read only 5 times maximum.

1 reading (i,j) (if its flag is already false skip)
2 read by top element
3. read by bottom element
4 read by left element
5 read by right element

coz atleast one of the this operation its flag will be unset(false), then we
have to just skip it.

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

Re: [algogeeks] Re: Finding Blocks in a matrix

[anshu mishra]

@ akash

solution is complete. :P
first try to understand the solution.

-- 
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: Finding Blocks in a matrix

[anshu mishra]

@piyush

void bfs(int mat[][n], bool flag[][n], int i, int j)
{
queue.push(mat[i][j]);
while (!q.empty())
{
x = q.top();
q.pop();
add top bottom, left right element in qeuue if their flag is true and their
value is equal to x and mark their flag false;
}
}

-- 
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: Finding Blocks in a matrix

[anshu mishra]

@vishal ur sol wil give wrong answer for this
1 1 2
1 3 1
2 3 4
answer should be 6 but ur sol wil give 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.

Re: [algogeeks] Re: Finding Blocks in a matrix

[anshu mishra]

it is a simple graph problem. travese the whole matrix using BFS. it will be
O(n^2).

for (i = 0; i < n; i++)
{
 for (j = 0; j < n; j++)
 {
if (flag[i][[j])
   {
 bfs(mat, flag, i, j);
 count++;
   }
 }
}

-- 
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: posix threads

[anshu mishra]

PS dont forget to bind ith thread with ith processor

-- 
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: posix threads

[anshu mishra]

write these three lines in ur function, it will bind that particular thread
to (id)th processor wher

void func(int id)
{
unsigned long mask;
mask = 1

Re: [algogeeks] A Graph Problem

[anshu mishra]

it is exactly a graph coloring problem. so it has no polynomial order
solution.

-- 
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] Google Interview Question

[anshu mishra]

@all go through this code

#include
#include

using namespace std;
bool compare(int a, int b)
{
string u, v;
u = v = "";
while (a)
{
u += (a % 10 + '0');
a/=10;
}
while (b)
{
v += (b % 10 + '0');
b/=10;
}
int i = 0, j = 0;
reverse(u.begin(), u.end());
reverse(v.begin(), v.end());
while (i < u.size() || j < v.size())
{
if (i == u.size()) i = 0;
if (j == v.size()) j = 0;
for (; i < u.size() && j < v.size(); i++, j++)
{
if (u[i] == v[j]) continue;
return (u[i] > v[j]);
}
}
if (u.size() == v.size()) return true;
}
int main()
{
int n;
cin >> n;
int ar[n];
int i;
for (i = 0; i < n; i++)
{
cin >> ar[i];
}
sort (ar, ar +n, compare);
for (i = 0; i < n; i++) cout << ar[i];
cout << endl;
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.

Re: [algogeeks] Re: sum of two

[anshu mishra]

map is internally implemented with balanced binary tree and inserting in a
BST is o(logn);

-- 
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: Round Robin Schedulling Problem

[anshu mishra]

@gopi
by mistake i have written "i" in place of IN[i];

my fault, 2nd thing( (F[i].idx - F[i-1].idx - (F[i].rep - F[i-1].rep) ) i
have really not think of that. thanks :)

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

[anshu mishra]

it is os responsibility to map user level thread to kernel level thread.
Usually os implements many to many mapping.
In pthread we can bind a particular thread to particular processor or set of
processor.

-- 
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] Round Robin Schedulling Problem

[anshu mishra]

L[i] tells how many elements D[j] less than D[i] such that j < i ;
for this u have to use BIT, segment tree, or any balanced BST(balanced
implies to avoid the worst case that is o(n^2));


rem = n;
curtime = 0;
last = 0;
for (i = 0; i < n;)

  ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1);
  curtime += (D[i] - last) * rem;
  i++;
  rem--;
  while (i < n && D[i] == D[i-1])
  {
 ans[IN[i]] = ans[IN[i-1]] + 1; i++;
 rem--;
  }
  last = d[i-1];
}

curtime = total time till the iteration in which last event(which has burst
time just less than current event) has been completed.

-- 
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] Round Robin Schedulling Problem

[anshu mishra]

two thing i have forgot do;

that is at every iteration

rem--;
last = D[i-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.

Re: [algogeeks] Round Robin Schedulling Problem

[anshu mishra]

first for every element get the number of element before its index have less
value.

example
L[]=   0 0 1 1 3
D[]   =   8 1 3 3 8
IN[]   =   0 1 2 3 4
you can use segment tree for this it will give solution in o(nlogn);

after that sort the array and start from 0th index

D[] = {1 3 3 8 8}
IN[] = {1 2 3 0 4}
rem = n;
curtime = 0;
last = 0;
for (i = 0; i < n;)

  ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1);
  i++;
  while (i < n && D[i] == D[i-1])
  {
 ans[IN[i]] = ans[IN[i-1]]; i++;
  }
  curtime += (D[i] - last) * rem;
}

finally answer will be solution;

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

[anshu mishra]

@all

it is simple binary search problem

we can write

f(n) = f(n/2 + 2)*f(n/2) + {f(n/2 + 1)}^2 if n is even  similary u can get
formula when n is odd.

f(3), f(4), f(5) > f(6)
f(6), f(7), f(8) > f(12)
.
.
.
as soon as you got a fibnocci number greater than n suppose p-- than you
have two ranges p, p/2;

now apply binary search in range (p/2 & p)

that is cal f(p+p/2) compare the value from n. accordigly move left or
right.

till (p - p/2 != 1)

solution is o(log(n));

hopefully i am clear.

-- 
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: Find closest point

[anshu mishra]

@piyush
suppose A is latitude
nd  B is longitude,  R is raduis of earth

z = Rsin(A);
r' = Rcos(A); > radius of circle at z height;

x = r'cos(B);
y = r'sin(B);

(x,y,z) is coordinate of point assuming (0,0,0) is the center of earth;

-- 
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: Find closest point

[anshu mishra]

@sravanreddy001


no u will go from point A to point B by walking on the surface not by making
the tunnel in the earth.

-- 
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: Find closest point

[anshu mishra]

@sravanreddy001
u r not at plain surface its sphere :P :D. u have to go by angle
-- 
Anshuman Mishra
IIIT Allahabad
-

anshumishra6...@gmail.com
rit2007...@iiita.ac.in

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

[anshu mishra]

@sravanreddy001
suppose u have to calulate A^n u can calculate in O(d^3*log(n));
d is dimesion of matrixl
while (n)
{
if (n&1) mul(ans, A, d);
mul(A, A, d);
n >>=1;
}


-- 
Anshuman Mishra
IIIT Allahabad
-

anshumishra6...@gmail.com
rit2007...@iiita.ac.in

-- 
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: Facebook Interview Question from glassdoor

[anshu mishra]

the same question i have asked in microsoft interview. (if it is the same
:P)

for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf);
i have given them 3 solution(recusrsive, stack based) and the last one what
they wanted.

take a tertiary number(n) = 3^(number of digits) in case of 12 it is equals
to 2;

i m solving the save problem. assuming on every key there are only 2
alphabets.

char c[][2] = {ab , cd, ..};

char n[] = 2156169 (number is pressed);
so k = 7;
for (i = 0; i < (1

Re: [algogeeks] Facebook Interview Question from glassdoor

[anshu mishra]

for 12 answer will be 36? is it ur question?

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

Re: [algogeeks] Re: first fit bin packing

[anshu mishra]

void query(int w, int s, int e, int node)
{
if (s==e)
{
tree[node] -= w;
prpogateNewMax(node);
return;
}
mid = (s+e)>>1;
if (tree[(node<<1)+1] > = w) query(w, s, mid, (node<<1)+1);
else query(w, mid+1, e, (node<<1)+2);
}

void prpogateNewMax(int node)
{
if (node == 0) return;
int par = (node-1)>>1;
int a = tree[(par<<1)+1];
int b = tree[(par<<1)+2];

tree[par] = a > b ? a : b;

prpogateNewMax(par);
}

Now I think everything is clear. For a single query we have traverse from
root to leaf than leaf to root. total 2*log(n); So finally for n queries
order will be O(n*logn);

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

[algogeeks] Re: first fit bin packing

[anshu]

we can use BIT or segment trees.

algorithm using segment tree

1. intialize all node wid zeros
2. read the array element according their index update the node value.

void update(int s, int e, int k, int node)
{
if (tree[node] < ar[k]) tree[node] = ar[k];
if (s==e) return;
mid = (s+e)>> 1;
if (k <= mid) update(s, mid, k, (node<<1)+1);
else update(mid+1, e, k, (node<<1)+2);
}

3. now ur query part start
  if left nodes value greater or equals to given value V then
goto left node otherwise goto right node as soon as you reach the leaf
node that will be your first fit bin and subtract value v from leaf
node. and accordingly update value from leaf to root.

if the algorithm is not clear. you are welcome to ask.

-- 
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] Print Subsets

[anshu mishra]

its DP problem can be solved in O(m*n)
where m is number of elements in array and n is value of the given number.

-- 
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] Array problem

[anshu mishra]

@amit ur code is wrong. just check it for this {5, 4, 1, 8, 4, 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.

Re: [algogeeks] Inversion Count

[anshu mishra]

no all these data structure also take time O(nlogn)

solving this problem using segment tree

map all elements to its index on the sorted array.

ex. 2 3 8 6 1 --> 1 2 4 3 0

intialiize all element in segment tree wid zero

start from the last index of array

whenever u visit a node increase its value by 1 --> one more value came in
this range

if u have go right child then increase the count by number of element in
left child(that is value left node). thats it;

void query(int a, int s, int e, int node, unsigned long long &count)
{
int mid = (s+e)>>1;
tree[node] += 1;
if (s == e) return;
if (a <= mid)
{
query(a, s, mid, (node<<1)+1, count);
}
else
{
count += tree[(node<<1)+1];
query(a, mid+1, e, (node<<1)+2, count);
}
return;
}

I have written another code using ur logic its giving correct answer. I m
not getting where u r wrong. :P

#include 

unsigned long long int merge_and_count (int *a, int start, int mid, int end)
{
int len_a = mid - start + 1;

int len_b = end - mid;
int C[end - start + 1];
int k = 0;
int i = start;
int j = mid + 1;
unsigned long long int count = 0;
int rem = len_a;

while ( i <= mid && j <= end ) {

C[k++] = a[i] < a[j] ? a[i] : a[j];
if ( a[j] <= a[i] ) {
count += rem;
j++;
} else {
i++;
rem--;
}
}

while ( i <= mid ) {
C[k++] = a[i++];
}

while ( j <= end ) {

C[k++] = a[j++];
}

for ( i = start; i <= end; i++ ) {
a[i] = C[i-start];
}

return count;
}

unsigned long long int sort_and_count(int *a, int start, int end)
{
int mid;

unsigned long long int rA, rB, r;

if ( end == start )
return 0;
else {
mid = (start + end) >> 1;
rA = sort_and_count (a, start, mid);
rB = sort_and_count (a, mid + 1, end);
r = merge_and_count (a, start, mid, end);

} return (rA+rB+r);
}

int main()
{
int t, n, i;
int a[200100];

scanf ("%d", &t);

while ( t-- ) {
scanf ("%d", &n);

for ( i = 0; i < n; i++ ) {

scanf ("%d", &a[i]);
}

printf ("%llu\n", sort_and_count(a, 0, n - 1));
}

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.

Re: [algogeeks] Inversion Count

[anshu mishra]

explain your logic instead of posting code, use binary index tree or segment
tree or bst to solve this problem.

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

[anshu mishra]

@pacific you are perfectly right but the order is not o(kn) its is
O(k*n*log(n)) because to get the least number u have to use priority queue
nd at every iteration (from 1 to k*n) u have to push and pop one single
element.
-- 
Anshuman Mishra
IIIT Allahabad
-

anshumishra6...@gmail.com
rit2007...@iiita.ac.in

-- 
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: partitioning the array

[anshu mishra]

@gaurav
f(i, j) = {(total number we need to make sum j including ith number in
array), if its not possible than -1};

f(i, j) = f(i-1, j-ar[i]) + 1 --> if (i-1, j-ar[i]) != -1;

answer will be the largest j for which f(i, j) will be exactly equals to
n/2;

there is something more in this but when you start to write the code you can
easily get that.

https://www.spoj.pl/problems/AMR10D/ a little bit similar problem on spoj.

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

[algogeeks] Re: partitioning the array

[anshu]

@gaurav both things are same, matrix is  a simple and efficient way to
do problem like this.
 .

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

[algogeeks] Re: partitioning the array

[anshu]

Use KnapSack DP. suppose the sum of element = s and number of elements
= n make a 2-dimesnsional array of size n * ((s+1)/2); I think that
much hint is enough.

if we think little bit more we can optimize it also.

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

[algogeeks] Re: Divisibility by five

[anshu]

algorithm:

if any number(a) is divisible by 5 it can be wriiten as 4*b + b -->
this cleary shows the last two bit of a & b will be same.

lets understand by an example (35)10 = (100011)2

 xx1100
+   xx11
-
 100011

now this clearly shows we can calculate the unknowns(x) by traversing
right to left

code:

int main()
{
int n, m;
cin >> n;
m = n;

int a, b;
int i=2;

a = (m&3)<<2;
b = (m&3);
m >>= 2;

bool rem = 0,s,r;

while (m>3)
{
r = a&(1<>= 1;
}

if (a+b == n) cout << "yes\n";
else cout << "no\n";

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.

[algogeeks] Re: programming problem

[anshu]

This question aint clear
So, for example in above list hippopotamuses  is also in the list of
word in the file.
So this word includes itself and is 14 characters.
where is a condition that concatenation is a must?



On May 20, 3:39 am, greg <[EMAIL PROTECTED]> wrote:
>  Write a program that reads a file containing a sorted list of
>  words (one word per line, no spaces, all lower case), then identifies
> the
>  longest  word in the file that can be constructed by concatenating
> copies of
>  shorter words also found in the file.
>
>  For example, if the file contained:
>
>  cat
>  cats
>  catsdogcats
>  catxdogcatsrat
>  dog
>  dogcatsdog
>  hippopotamuses
>  rat
>  ratcatdogcat
>
>  The answer would be 'ratcatdogcat' - at 12 letters, it is the longest
>  word made up of other words in the list.
>
> I'm having trouble coming up with anything other than starting with
> the longest word in the list and checking for each of the other words
> in the list, which seems incredibly inefficient, any ideas or
> suggestions of things to look at?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: need an algorithm for inserting tags....

[anshu]

Can you please state more clearly, if in above e.g.
"bidd dd d", you want to tag occurrence of words -
bidd, dd and d in a para?
So for e.g.
if para is --
"fjsd d fjwelkjw dd dwere bidd"
you want
"fjsd d fjwelkjw dd dwere bidd"
as output

Please correct me if you meant something else...
Thanks,
-Anshu


On Sep 16, 5:20 pm, gomsi <[EMAIL PROTECTED]> wrote:
> hi,
>
> i have a paragraph where i have to insert  and  tags to
> highlight the required words.i am implementing it in c++  i am
> currently doing it as follows..
>
> i take the corresponding position at which the word occurs within the
> paragraph and the word length and store it in a map(STL)..and start
> inserting the tags after i scan the paragraph for the words
> although it works fine for larger words problem occurs when the word
> to be marked are like "bidder dd d"..the tags start overlapping and
> become mixed up within the paragraph.. can someone provide a good
> algorithm and help please... asap..


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Post order traversal of a binary tree without recursion

[anshu]

yeah..Sorry for the mistake ..
I did not check boundary conditions correctly..
your correction should make it work perfectly..
We can also add a little optimization to not push the last one ..
because as soon as its pushed its popped..
Thanks,
-anshu

Thanks,
-anshu


On Sep 9, 8:33 am, "chandra kumar" <[EMAIL PROTECTED]> wrote:
> Hi,
> But in your second while( ) loop when the check 'root->left = NULL'
> executes 'root' is already NULL, because only then the first loop
> terminates. So you need to insert the following statement inbetween the
> loops
>
> root = pop( )
>
> Also your solution assumes that the value at the nodes are of 'single
> character'. Say, if the values are of multiple character strings, then
> instead of 'string_reverse( )' the function 'reverse_words_in_string( )'.
>
>Other than this the solution should be perfect. Correct me if I'm wrong.
>
> Thanks and Regards,
> K.V.Chandra Kumar.
>
> On 07/09/2007, anshu <[EMAIL PROTECTED]> wrote:
>
>
>
> > An alternative algorithm that works without the explored() function
> > could be as under.
> > Just written a rough algorithm, there are a few more optimizations in
> > loop possible,..
> > The basi idea used here is -
> > Post order mean "Data-Left-Right"
> > If pre-order algorithm be executed with the difference that instead of
> > left we explore right.
> > The final order obtained when reversed will give post order.
>
> > post_order(root)
> > {
> > string_reverse( func(root));
> > }
>
> > func(root)
> > {
> >do {
> >   while(root != NULL)
> >   {
> > print(root->data);
> > push(root);
> > root=root->right;
> >   }
> >   while( root->left=NULL || stack ! empty)
> >   root=pop()
> >   if(root->left !=NULL)
> >   {
> > root=root->left
> >   }
>
> >}while( stack ! empty);
>
> > }
>
> > On Aug 28, 8:39 am, "chandra kumar" <[EMAIL PROTECTED]>
> > wrote:
> > > Hi,
> > > Need more details about explored(  Node * ) function,
>
> > > Consider the "NULL" input
>
> > > if your explored( NULL ) returns "true" then I guess that every
> > thing
> > > works fine, and also most of your checks could be eliminated ( code will
> > > become simpler )
> > > if your explored( NULL ) returns "false", then the same case as in
> > my
> > > previous mail will result in wrong answer.
> > > *if((s->left == null && s->right==null)
> > > ||(explored(s->left)&&explored(s->right)) *
> > > *---as s->left == null && explored( s->right )   ( and vice
> > versa
> > > are not there )*
>
> > > Correct me if I'm wrong.
>
> > > Thanks and Regards,
> > > K.V.Chandra Kumar.
>
> > > On 28/08/07, MD <[EMAIL PROTECTED]> wrote:
>
> > > > I think first s=pop() in while is not the right approach. This is an
> > > > alternate approach where explored() checks if the node is visited or
> > > > not... hence discarding that path.. and I think the following handles
> > > > the null conditions as well.. (ex given by chandra)
>
> > > > void postOrderTraversal(Tree *root)
> > > > {
> > > > node * previous = null;
> > > > node * s = root;
> > > > push(s);
>
> > > > while( stack is not empty)
> > > > {
> > > > if(s->left && !explored(s->left))  //explored check if the node was
> > > > previously visited
> > > >{push(s->left);
> > > >s=s->left}
> > > > else
> > > >   {if(s->right && !explored(s->right))
> > > >   {push(s->right);
> > > >s=s->right;}
> > > >   }
>
> > > >   if((s->left == null && s->right==null) ||(explored(s-
> > > > >left)&&explored(s->right)) //last level-child or both childern are
> > > > explored
> > > >   { s = pop(); //
> > > > print(s->data);
> > > > s= pop(); //POP Againpoint s to next element.
> > > >   }
> > > > }//end of while
>
> > > > }
>
> > > >

[algogeeks] Re: Post order traversal of a binary tree without recursion

[anshu]

An alternative algorithm that works without the explored() function
could be as under.
Just written a rough algorithm, there are a few more optimizations in
loop possible,..
The basi idea used here is -
Post order mean "Data-Left-Right"
If pre-order algorithm be executed with the difference that instead of
left we explore right.
The final order obtained when reversed will give post order.


post_order(root)
{
string_reverse( func(root));
}


func(root)
{
   do {
  while(root != NULL)
  {
print(root->data);
push(root);
root=root->right;
  }
  while( root->left=NULL || stack ! empty)
  root=pop()
  if(root->left !=NULL)
  {
root=root->left
  }

   }while( stack ! empty);

}


On Aug 28, 8:39 am, "chandra kumar" <[EMAIL PROTECTED]>
wrote:
> Hi,
> Need more details about explored(  Node * ) function,
>
> Consider the "NULL" input
>
> if your explored( NULL ) returns "true" then I guess that every thing
> works fine, and also most of your checks could be eliminated ( code will
> become simpler )
> if your explored( NULL ) returns "false", then the same case as in my
> previous mail will result in wrong answer.
> *if((s->left == null && s->right==null)
> ||(explored(s->left)&&explored(s->right)) *
> *---as s->left == null && explored( s->right )   ( and vice versa
> are not there )*
>
> Correct me if I'm wrong.
>
> Thanks and Regards,
> K.V.Chandra Kumar.
>
> On 28/08/07, MD <[EMAIL PROTECTED]> wrote:
>
>
>
> > I think first s=pop() in while is not the right approach. This is an
> > alternate approach where explored() checks if the node is visited or
> > not... hence discarding that path.. and I think the following handles
> > the null conditions as well.. (ex given by chandra)
>
> > void postOrderTraversal(Tree *root)
> > {
> > node * previous = null;
> > node * s = root;
> > push(s);
>
> > while( stack is not empty)
> > {
> > if(s->left && !explored(s->left))  //explored check if the node was
> > previously visited
> >{push(s->left);
> >s=s->left}
> > else
> >   {if(s->right && !explored(s->right))
> >   {push(s->right);
> >s=s->right;}
> >   }
>
> >   if((s->left == null && s->right==null) ||(explored(s-
> > >left)&&explored(s->right)) //last level-child or both childern are
> > explored
> >   { s = pop(); //
> > print(s->data);
> > s= pop(); //POP Againpoint s to next element.
> >   }
> > }//end of while
>
> > }
>
> > On Aug 24, 6:17 am, "Phani Kumar Ch. V." <[EMAIL PROTECTED]> wrote:
> > > Hi all,
>
> > > Please let me know if this pseudo code gives correct solution for
> > iterative
> > > post-order traversal of a binary tree.
> > > 
> > > void postOrderTraversal(Tree *root)
> > > {
> > > node * previous = null;
> > > node * s = null;
> > > push(root);
> > > while( stack is not empty )
> > > {
> > >   s = pop();
>
> > >   if(s->right == null and s->left == null)
> > >   {
> > > previous = s;
> > > process node s;
> > >   }
> > >   else
> > >   {
> > > if( s->right == previous or s->left == previous )
> > > {
> > >   previous = s;
> > >   process node s;
> > > }
> > > else
> > > {
> > >   push( s );
> > >   if(s->right) { push(s->right); }
> > >   if(s->left)  { push(s->left);  }
> > > }
> > >   }}
>
> > > ---
> > > Regards
> > > Phani


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Algo to get GCD of given numbers

[anshu]

Do you think sorting would help here?
I mean, arranging the numbers in descending order and then computing
progressively.

Why I am suggesting sorting is that considering an array like the
following
2, 80, 36, 70, 150, 300
It would be pretty expensive to do the euclidean algo first with
gcd(2, 80 ) = 2  --- O(40)
gcd(2, 36 )= 2 -- O(18)
gcd(2 , 70)  =
gcd(2, 150)

vs
gcd(150, 300) =  150
gcd(70,150) = 10
etc..

gcd (a,b)
{
   if ( b > a )
 b  = b % a
   else
a= a % b
} //this is same as euclidean algorithm.



On Aug 12, 9:25 pm, Muntasir Azam Khan <[EMAIL PROTECTED]>
wrote:
> On Aug 12, 9:54 pm, "sumedh sakdeo" <[EMAIL PROTECTED]> wrote:
>
>
>
> > well i have made this ...
>
> > ·Find minimum of n numbers.
>
> > ·Run loop from i=1 to minimum number
>
> > ·Check if i is divisible by all the three numbers
>
> > ·If yes, gcd=i
>
> > ·Continue the step till you get the gcd which is less than or equal
> > to minimum of three numbers
> > anyone can do it less complexity?
>
> > On 8/12/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote:
>
> > >  Google is your friend.
>
> > > - Original Message -
> > > *From:* sumedh sakdeo <[EMAIL PROTECTED]>
> > > *To:* algogeeks@googlegroups.com
> > > *Sent:* Sunday, August 12, 2007 9:37 PM
> > > *Subject:* [algogeeks] Algo to get GCD of given numbers
>
> > > Write algorithm for finding the GCD of given numbers.
>
> Try thishttp://en.wikipedia.org/wiki/Euclidean_algorithm
>
> Once you can find the gcd of two numbers, you can easily extend this
> to get the GCD of n numbers.
>
> gcd(a,b,c )= gcd ( a, gcd( b, c ) )
>
> Hope this helps,
> Muntasir


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: visit trees

[anshu]

You are ignoring the possibility that we might want to leave to
adjacent levels for a higher-valued descendant.

I think this should be formulated as a DP problem.
Writing the recursive version:
optimal value of node(at level l) = max of {its value+sum of optimal
values of level l+2 , sum of optimal values of all children at level
l+1}

T(n)=Max{ C_n +Sum_{i=1 to k}(all children at T(n+2)), Sum_{i=1 to k}
T(l+1) for all k children
We start with T(0) :
T(l) : Best solution for level l
C_i= Value contained in node i

Not sure if notation is explicit..
Explaning with the example tree discussed in prev threads..
   4(1)
/   \
   1(2) 20(3)
  / \/ \
10(4)  5(5)   2(6)   3(7)

P.S : no in brackets denote their ids.
T(1)= Max{4+T(4)+T(5)+T(6)+ T(7), T(2) + T(3)}
T(2) = Max{1, T(4)+T(5)} = Max{1,10+5} = 15
T(3) = Max{20, T(6)+t(7) } = 20
Substituting in T(1), we have
T(1) = Max{4+10+2+2, 20+15 }
T(1) = 35.

A complete solution would have a bottom up approach, storing computed
values of tree nodes. I guess its similar to one of the DP problems
discussed in CLR, for tree organization.
I am not sure if starting from any node is good idea, because we shud
maek use of tree organization to eliminate the number of combinations.

Hope this helps.

~anshu.


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Array subsequence of sum N.

[anshu]

meke a corresponding cumulative sums array..
where S[i]= Summation(a[0] ... a[i])

Sum of subseq.  [i..j]= S[j]-S[i-1]

check all i,j pairs

but this is O(n^2).. may be a better exists


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Linking sibling in a binary tree

[anshu]

Tree is just a data structure..
so if its an array implementation(considering binary tree), siblings
are adjancent elements anyways..

Also, if its a linked represntation then u can just add another field
for parent..like some of the traversal algorithms use.

Also, we can use Threaded binary tree representation, which stores the
inorder successor and a slight effort will give us the sibling in
constant time.



NUPUL wrote:
> >I was wondering if there is any >method to link all sibling nodes >in a 
> >binary tree
>
> i suggest you read up something on B trees and B+ trees and then put
> forth this question.
> 
> Nupul


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---