Re: [algogeeks] Designing Data Structure
simple hash ? can you specify the hashing function because if we use stl's map its complexity is O(log(n)) On Thu, Nov 3, 2011 at 1:48 AM, Robert Badita robert.bad...@gmail.comwrote: Simple hash will do it in O(1) but with careful implementation of getRandomElement to distribute probability evenly to each bucket / element in the bucket On Nov 2, 2011, at 5:52 PM, shady sinv...@gmail.com wrote: does anyone knows how much is the complexity of operations erase and pop_back in case of Vector(STL) what would you choose : Design a data structure where the following 3 functions are optimised: 1. Insert(n) 2. GetRandomElement() 3. Remove(n) Write a class, and implement the functions. Give complexity of each of these what would you choose, insertion can always be done in O(1), but what about getrandomelement() if we use simple arrays than for those 1. - O(1) 2. - O(1) 3. - 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. -- 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.
[algogeeks] Re: Median of 2D matrix
Try 1 2 3 2 4 5 3 4 6 1 2 2 3 3 4 4 5 6 Median 3, median of medians is 4. On Nov 2, 11:33 am, Anup Ghatage ghat...@gmail.com wrote: Median of Medians? On Tue, Nov 1, 2011 at 10:44 PM, Ankuj Gupta ankuj2...@gmail.com wrote: We have a N X N matrix whose rows and columns are in sorted order. How efficiently can we find the median of those N^2 keys ? -- 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] Designing Data Structure
The hash function is the middle n bits of x * scramble, choosing the lowest n bits has bad hasing properties On Nov 3, 2011, at 1:59 PM, Robert Badita robert.bad...@gmail.com wrote: What you need is to recreate the hash, and make your own hash structure like an array with 2^n elements where 0.9 * 2^n = N where N is the number of real elements in your structure (use 90% maximum fill factor) If you use the hash as a dynamic vector with minimum 10% fill factor and max 90% then for the grtRandomElement you can choose a random value between 0 and 2^n - 1, if it's occupied output that element, else rechoose until an element is occupied. This method is O(1) since in the worst case you do approx 10 iterations. The hash function is just x * SCRAMBLE_CONSTANT mod 2^n where x is your element to be hashed. - multiplicative hashing On Nov 3, 2011, at 1:09 PM, shady sinv...@gmail.com wrote: simple hash ? can you specify the hashing function because if we use stl's map its complexity is O(log(n)) On Thu, Nov 3, 2011 at 1:48 AM, Robert Badita robert.bad...@gmail.com wrote: Simple hash will do it in O(1) but with careful implementation of getRandomElement to distribute probability evenly to each bucket / element in the bucket On Nov 2, 2011, at 5:52 PM, shady sinv...@gmail.com wrote: does anyone knows how much is the complexity of operations erase and pop_back in case of Vector(STL) what would you choose : Design a data structure where the following 3 functions are optimised: 1. Insert(n) 2. GetRandomElement() 3. Remove(n) Write a class, and implement the functions. Give complexity of each of these what would you choose, insertion can always be done in O(1), but what about getrandomelement() if we use simple arrays than for those 1. - O(1) 2. - O(1) 3. - 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. -- 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] Designing Data Structure
What you need is to recreate the hash, and make your own hash structure like an array with 2^n elements where 0.9 * 2^n = N where N is the number of real elements in your structure (use 90% maximum fill factor) If you use the hash as a dynamic vector with minimum 10% fill factor and max 90% then for the grtRandomElement you can choose a random value between 0 and 2^n - 1, if it's occupied output that element, else rechoose until an element is occupied. This method is O(1) since in the worst case you do approx 10 iterations. The hash function is just x * SCRAMBLE_CONSTANT mod 2^n where x is your element to be hashed. - multiplicative hashing On Nov 3, 2011, at 1:09 PM, shady sinv...@gmail.com wrote: simple hash ? can you specify the hashing function because if we use stl's map its complexity is O(log(n)) On Thu, Nov 3, 2011 at 1:48 AM, Robert Badita robert.bad...@gmail.com wrote: Simple hash will do it in O(1) but with careful implementation of getRandomElement to distribute probability evenly to each bucket / element in the bucket On Nov 2, 2011, at 5:52 PM, shady sinv...@gmail.com wrote: does anyone knows how much is the complexity of operations erase and pop_back in case of Vector(STL) what would you choose : Design a data structure where the following 3 functions are optimised: 1. Insert(n) 2. GetRandomElement() 3. Remove(n) Write a class, and implement the functions. Give complexity of each of these what would you choose, insertion can always be done in O(1), but what about getrandomelement() if we use simple arrays than for those 1. - O(1) 2. - O(1) 3. - 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. -- 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: Re: Re: [algogeeks] Re: Modular arithmetic + Combinatorics
correction: if P is prime VM NSIT, Dwarka On , vaibhavmitta...@gmail.com wrote: Use Lucas Theorem is P is prime. VM NSIT, Dwarka On , Dipit Grover dipitgro...@gmail.com wrote: Thats really cool! Thanks Dave :) -- 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] Reverse dutch flag problem
This is a special case of shuffling problem. In shuffling problem we have
to merge k (here k = 3) parts of array such that each kth element is from
the same sub-array and in same order. For eg -
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become = a1 b1 c1 a2 b2 c2 a3
b3 c3 a4 b4 c4.
Usually shuffling problem can be solved only in O(n*logn) time without
additional space, but here you have an added advantage. You know what the
sequence should look like exactly. So here goes the O(n) solution with
constant space.
1- Take 2 pointers p1 and p2 initialize both of them to index 1 (second
element)
2- now for each element at p2 find the right index where it should go and
put it thr. The right index is -
(k*p2 -1) % (n-1); // k=3 here
3- Keep doing it until p2 becomes same as p1 again.
4- Now advance p1 till the elements are in order 0 1 2 0
5- if p1 is less than n-1 than set p2 = p1. Repeat thru step 2-5 again.
Here is a primitive C code to do the same.
int p1 = p2 = 1;
int preVal, next, temp;
while (p1 n)
{
preVal = a[p1];
p2 = p1;
do{
next = (k*p2 -1) % (n-1); // k=3 here
temp = a[next];
a[next] = preVal;
preVal = temp;
p2 = next;
} while (p2 != p1)
while(p1 n)
{
if( ((a[p1] - a[p1-1]) == 1) || (a[p1] - a[p1-1]) == -2)) //
elements are in sequence 0 1 2 0
p1++;
else
break;
}
}
Feedback welcome :-).
- Ravindra
On Wed, Nov 2, 2011 at 6:43 PM, shady sinv...@gmail.com wrote:
any solutions for this ?
dutch national flag problem could be done in O(n) time and O(1) space by
considering two pointers, but how to do this (reverse dutch national flag
problem) ?
On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal srn...@gmail.com wrote:
Suppose we are given a string .
Make it 012012012012 in O(n) time and O(1) space.
Sanju
:)
--
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.
[algogeeks] Re: Designing Data Structure
Often you can get optimal performance with unusual combinations of
operations by combining data structures. Here you can get O(1) for all
operations by combining a hash table and a bag of pointers in an
array. The hash table references bag elements by index, and the bag
elements point back at hash table entries. Random lookups occur in
the bag array. Here is a quick C toy to show what I mean. There are
other possible implementations.
#include stdio.h
#include stdlib.h
typedef struct key_pair_s {
struct key_pair_s *next;
unsigned value, bag_index;
} KEY_PAIR;
typedef struct table_s {
KEY_PAIR *buckets[1007], *bag[1];
unsigned size;
} TABLE;
#define ARRAY_SIZE(A) (sizeof A/sizeof *A)
void init_table(TABLE *table)
{
unsigned i;
for (i = 0; i ARRAY_SIZE(table-buckets); i++)
table-buckets[i] = NULL;
table-size = 0;
}
unsigned hash(unsigned key)
{
return key % ARRAY_SIZE(((TABLE*)42)-buckets);
}
int Remove(TABLE *table, int value)
{
KEY_PAIR *p, *q;
unsigned h = hash(value);
for (q = NULL, p = table-buckets[h]; p; q = p, p = p-next)
if (p-value == value) {
if (q)
q-next = p-next;
else
table-buckets[h] = p-next;
// Move last element into hole in bag. Update hash table.
q = table-bag[--table-size];
table-bag[p-bag_index] = q;
q-bag_index = p-bag_index;
free(p);
return 1;
}
return 0;
}
void Insert(TABLE *table, int value)
{
// Put a new key pair in the hash table.
KEY_PAIR *p = malloc(sizeof *p);
unsigned h = hash(value);
p-next = table-buckets[h];
table-buckets[h] = p;
p-value = value;
// Allocate a new bag element for this pair.
p-bag_index = table-size++;
table-bag[p-bag_index] = p;
}
#define N_RAND (RAND_MAX + 1)
unsigned unbiased_rand(unsigned n)
{
unsigned r, m = N_RAND - N_RAND % n;
do r = rand(); while (r = m);
return r % n;
}
void GetRandomElement(TABLE *table, unsigned *value)
{
if (table-size 0)
*value = table-bag[unbiased_rand(table-size)]-value;
}
void Print(TABLE *table)
{
unsigned i;
printf(table:);
for (i = 0; i table-size; i++)
printf( %u, table-bag[i]-value);
printf(\n);
}
int main(void)
{
TABLE table[1];
unsigned i, values[10];
char cmd;
init_table(table);
for (i = 0; i ARRAY_SIZE(values); i++) {
values[i] = rand();
Insert(table, values[i]);
}
for (;;) {
Print(table);
printf(cmd [arg] );
scanf( %c, cmd);
switch(cmd) {
case 'i':
scanf(%u, i);
Insert(table, i);
printf(Inserted %u\n, i);
break;
case 'r':
scanf(%u, i);
if (Remove(table, i))
printf(Removed %u\n, i);
else
printf(Couldn't find %u\n, i);
break;
case 'g':
i = 0;
GetRandomElement(table, i);
printf(Random element: %u\n, i);
break;
case 'q':
return 0;
default:
printf(Unknown command\n);
break;
}
}
}
On Nov 2, 4:52 pm, shady sinv...@gmail.com wrote:
does anyone knows how much is the complexity of operations erase and
pop_back in case of Vector(STL)
what would you choose :
Design a data structure where the following 3 functions are optimised:
1. Insert(n)
2. GetRandomElement()
3. Remove(n)
Write a class, and implement the functions. Give complexity of each of these
what would you choose, insertion can always be done in O(1), but what about
getrandomelement() if we use simple arrays than for those
1. - O(1)
2. - O(1)
3. - 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.
[algogeeks] Re: Median of 2D matrix
any better solution than O(N^2) in worst case? How do we take advantage of sorting and find in O(N lg N) -- 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/-/UdCc1n4a6TUJ. 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] to generate a automatic voting time table
Ques:we have following data from basis of that one can write algo to generate a automatic offline voting time table 1.population of different region 2.distance between them them 3.security label like[ A(secure),B(a little bit risky),C(sensitive) ] 4.geographical configuration if u want 5.available security member -- 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] Reverse dutch flag problem
Sorry, small mistake in designated index calculation.
It should be k*p2 % (n-1) instead of (k*p2 -1) % (n - 1).
Thanks,
- Ravindra
On Thu, Nov 3, 2011 at 11:37 PM, ravindra patel ravindra.it...@gmail.comwrote:
This is a special case of shuffling problem. In shuffling problem we have
to merge k (here k = 3) parts of array such that each kth element is from
the same sub-array and in same order. For eg -
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become = a1 b1 c1 a2 b2 c2 a3
b3 c3 a4 b4 c4.
Usually shuffling problem can be solved only in O(n*logn) time without
additional space, but here you have an added advantage. You know what the
sequence should look like exactly. So here goes the O(n) solution with
constant space.
1- Take 2 pointers p1 and p2 initialize both of them to index 1 (second
element)
2- now for each element at p2 find the right index where it should go and
put it thr. The right index is -
(k*p2 -1) % (n-1); // k=3 here
3- Keep doing it until p2 becomes same as p1 again.
4- Now advance p1 till the elements are in order 0 1 2 0
5- if p1 is less than n-1 than set p2 = p1. Repeat thru step 2-5 again.
Here is a primitive C code to do the same.
int p1 = p2 = 1;
int preVal, next, temp;
while (p1 n)
{
preVal = a[p1];
p2 = p1;
do{
next = (k*p2 -1) % (n-1); // k=3 here
temp = a[next];
a[next] = preVal;
preVal = temp;
p2 = next;
} while (p2 != p1)
while(p1 n)
{
if( ((a[p1] - a[p1-1]) == 1) || (a[p1] - a[p1-1]) == -2)) //
elements are in sequence 0 1 2 0
p1++;
else
break;
}
}
Feedback welcome :-).
- Ravindra
On Wed, Nov 2, 2011 at 6:43 PM, shady sinv...@gmail.com wrote:
any solutions for this ?
dutch national flag problem could be done in O(n) time and O(1) space by
considering two pointers, but how to do this (reverse dutch national flag
problem) ?
On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal srn...@gmail.com wrote:
Suppose we are given a string .
Make it 012012012012 in O(n) time and O(1) space.
Sanju
:)
--
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.
[algogeeks] Long nCr Calculations
Lets say i want to calculate (1000C500)%MOD.
*My Code : *
*
*
long long ans=n;
for(int i=1;i=r;i++) {
ans=(ans*(n-i+1))/i;
ans = ans%MOD;
}
But when the ans inside the loop starts exceeding MOD and you take
ans=ans%MOD then you cannot be sure to get the correct answer..
How to deal with this situation ?
--
Aamir Khan | 3rd Year | Computer Science Engineering | IIT 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.
Re: [algogeeks] Re: Questions
@vikas
ur algo will search for 1st element of 1d in whole 2d array,
on worst case u'll search it in n^2, then search for all 1d elements
in 2d in O(n)
so whole complexity goes to O(n^2 +n)
it can be reduced if we use hashing of 1d array, and count_found
and while searching for 1st element of 1d in 2d array, if it's found
make temp[i][j] as true(even though its not first element) and false
if its not in 1d hash, and increase count_found
this will reduce to O(n^2)
surender
On 11/1/11, vikas vikas.rastogi2...@gmail.com wrote:
ok,
so do it like this;
1. create boolean array
boolean temp[][] = new boolean[row][column];
init(temp, true);
2. traverse the array for the 1d array of 0th index and then a
recursive search
if search fails, or position already contains false, return and search
again
boolean search(int searchArray[][], int givenArray[], int rpos, int
cpos, int gpos){
if(gpos givenArray.len) return false;
if(temp[rpos][cpos] == false) return false;
if(searchArray[rpos][cpos] == givenArray[gpos])
{
temp[rpos][cpos] = search(searchArray, givenArray, rpos
+1, cpos, gpos+1)|
search(searchArray,
givenArray, rpos-1, cpos, gpos+1) |
search(searchArray,
givenArray, rpos, cpos+1, gpos+1)|
search(searchArray,
givenArray, rpos+1, cpos-1, gpos+1)
}
if(temp[rpos][cpos]) return true;
if(cpos searchArray.len)
search(searchArray, givenArray, rpos, cpos+1, 0);
else
search(searchArray, givenArray, rpos+1, 0, 0);
}
On Nov 1, 4:25 pm, SAMM somnath.nit...@gmail.com wrote:
For example :-
2d array ::
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
we hav 1d array as :-- 13 2 21 10 23 12
So the 1d array is a subset of 2d array ...
On 11/1/11, vikas vikas.rastogi2...@gmail.com wrote:
what do you mean by subset of 1D present in the 2D array? is it
something like 3245 , the search may be 3245/ 24/ 45/ all 16
subsets need to be searched?
On Oct 28, 12:02 pm, SAMMM somnath.nit...@gmail.com wrote:
How do u plan to implement 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.
--
Somnath Singh
--
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.
[algogeeks] Re: Long nCr Calculations
Aamir: Check out the thread Modular arithmetic + Combinatorics
recently in this newsgroup.
Dave
On Nov 3, 1:29 pm, Aamir Khan ak4u2...@gmail.com wrote:
Lets say i want to calculate (1000C500)%MOD.
*My Code : *
*
*
long long ans=n;
for(int i=1;i=r;i++) {
ans=(ans*(n-i+1))/i;
ans = ans%MOD;
}
But when the ans inside the loop starts exceeding MOD and you take
ans=ans%MOD then you cannot be sure to get the correct answer..
How to deal with this situation ?
--
Aamir Khan | 3rd Year | Computer Science Engineering | IIT 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.
[algogeeks] Doubt in Lowest Common Ancestor
I have a doubt in calculating LCA. While calculating LCA of two nodes, should those two nodes can also be ancestor. As wikipedia states that The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). But usually we dont consider the nodes itself to be ancestor ? Which approach should be followed ? -- 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.
