[algogeeks] Re: number of BST's
Number of BST with n keysf(n) = [ \sum_{ i=1 to n} f(i-1)* f(n-
i) ]
Root node can be any of n keys. if it is ith ney in ascending order,
it has i-1 keys to left and n-i keys to right.
Can any one explain how/Why is it equal to catalan number?
-Thanks
Bujji
On Aug 1, 1:08 pm, Manjunath Manohar manjunath.n...@gmail.com wrote:
int count(int node)
{
int sum=0;i,left,right;
for(i=0;inode;i++)
{
left=count(node-1);
right=count(node-i);
sum+=left*right;
}
return(sum);
}- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sorting range of numbers in O(n)
You can use count sort or radix sort. Both are of O(n) as running time complexity. You can refer to the book by Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon question
Let us assume that the input data-structure is a matrix G[1..N;1..N]
of dimesion N*N matrix where G(i,j) = 1 if i !=j and i has won, 0
otherwise.
Note that the required sequence cannot contain 1 as 0th player does
not exists
Following algorithm may be used.
For i:=2 to N, do:
{
if ( ( G(i , i+1) = 0 ) AND (G( i , i-1) = 1) )
ouput i ;
}//End of for-loop.
Order of running time 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: minimum window containing charecters
Sub-Module: Permutation (word W)
{
Generate all the unique permutations of W taking all the letters of
W
}//End of Sub-Module.
Now you can use the sub-string matching problem for the two strings.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
@Ram and Nikhil What kind of traversal you will use to visit each node. How come you will get to know about teh number of nodes at each level that needs to be connected. RK On Sun, Aug 1, 2010 at 2:56 AM, Nikhil Jindal fundoon...@yahoo.co.inwrote: @Ram Kumar: Yes. Simple and affective. Just at each node: node-left-side=node-right node-right-side=node-side-left i.e at each node you are setting the side of each of your child. Go on and just do it for all nodes. Done. On Sat, Jul 31, 2010 at 9:39 AM, Ram Kumar harrypotter@gmail.comwrote: DONT DO A BFS!! NOT WORTH IT! CALL THE NEW POINTER AS 'SIDE' POINTER. for every root connect its left and right, for every root connect root-right and root-SIDE-left that ll do -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Discussion on unique-elements-in-an-array
You can refer the following algorithm Let the elements be in the form of an array A[1...N] 1. Sort all the elements of A(This can take at least O(n) time). 2. For i=1 to N, do: while( ( i+1 = N) AND (A[i] == A[i+1]) ) remove A[i+1]. 3. END -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: algorithm
@Anand,
It looks like your algorithm takes O(log N ) time.
Repeatedly choosing one half or the other half.
Similar to binary search.
Please correct me if I am worng.
-Thanks and regards,
Bujji.
On Jul 27, 12:29 am, Anand anandut2...@gmail.com wrote:
*
*
*Using partition Logic of Quick Sort:
*
*Algoritm:*
1. pivot = 1st element.
2. Find the position of pivot in the array using partition logic of Quick
sort
3. If Rank lies on the right side of the position then call this function
with the right array
4. If rank lies on the left side of the position, then call this function
with the left array.
5. If rank == position
- return the element at position
On Sun, Jul 25, 2010 at 4:44 AM, Algoose chase harishp...@gmail.com wrote:
Add Each number from the stream to a Doubly linked list in sorted fashion
i = 1;
j = 1;
while( stream not empty)
{
if( i == 1 j == 1)
{
Median = Cur ; /*Create New list with ist Number*/
}
Add_Node_In_Sorted_Order(Cur);
If( If new node is added after median )
i++; /*if the current median is 3rd node and new
node is added @ 5th position*/
bAddedBeforeMedian = False;
else
j++;
bAddedBeforeMedian = true;
if( i %2 == 1 !bAddedBeforeMedian)
Median = median -next;
else if (j%2==1 bAddedBeforeMeidan)
Median = Median-prev
}
return Median-Data;
At any given point in time Median will point to the median among the
numbers seen so far
-----
On Sat, Jul 24, 2010 at 8:02 PM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:
You are given a stream of numbers which can be positive or negative. You
are required to provide an operation FIND MEDIAN..which when invoked should
be able return the median of the numbers in stream (in sorted order) in
O(1)
time.
Eg: 0 1 2 3 4
Right FIND MEDIAN returns 2 as median
Now input is -2 -4
So Stream = 0 1 2 3 -2 -2 -4
Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sorting range of numbers in O(n)
Counting Sort. On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote: There are N numbers in an array and each number is in the range [0, n*n -1]. Is there a way to sort the elements in O(n)? Thanks, Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Permutation.................
you may also want to see http://www.rawkam.com/?p=351 http://www.rawkam.com/?p=351-Kamal On Sun, Aug 1, 2010 at 7:40 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote: On Sun, Aug 1, 2010 at 5:20 PM, Pramod Negi negi.1...@gmail.com wrote: http://pramnegi.blogspot.com/2009/11/dons-permutaion.html Thanks Pramod Negi On Sun, Aug 1, 2010 at 4:30 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote: Write a C code for generate all possible Permutation as:- 1 2 3 Total no. of Per=6 also print all permutation as:- 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 if inpute is 1 2 3 2 total no of permutation = 12 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Thanks a lot sirjee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Placement Question
driver(Tree *root)
{
node *array = malloc(sizeof(node *) *H ); /* take the height node
pointer array. this will act as source pointer of each list */
makeList(root, 0, array)
}
makeList(Tree *root, int level, node *array)
{
if(! root) return ;
/*do a Depth traversal and store the list pointer*/
append(array[level], root);
/*Traverse the left and right subtrees and store them in list*/
makeList(root-left, level+1, array);
makeList(root-right, level+1, array);
}
time complexity is O(n) space complexity O(log n)
( assuming append has O(1) complexity)
On Aug 1, 2:26 am, Nikhil Jindal fundoon...@yahoo.co.in wrote:
@Ram Kumar: Yes. Simple and affective.
Just at each node:
node-left-side=node-right
node-right-side=node-side-left
i.e at each node you are setting the side of each of your child. Go on and
just do it for all nodes. Done.
On Sat, Jul 31, 2010 at 9:39 AM, Ram Kumar harrypotter@gmail.comwrote:
DONT DO A BFS!! NOT WORTH IT! CALL THE NEW POINTER AS 'SIDE' POINTER.
for every root connect its left and right, for every root connect
root-right and root-SIDE-left
that ll do
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic
communications
disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php- Hide
quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: number of BST's
the calatan number can be derived using the code given above.. plz confirm
by using wiki..
try 2 find derivation of catalan number..
On Mon, Aug 2, 2010 at 11:34 AM, bujji jajalabu...@gmail.com wrote:
Number of BST with n keysf(n) = [ \sum_{ i=1 to n} f(i-1)* f(n-
i) ]
Root node can be any of n keys. if it is ith ney in ascending order,
it has i-1 keys to left and n-i keys to right.
Can any one explain how/Why is it equal to catalan number?
-Thanks
Bujji
On Aug 1, 1:08 pm, Manjunath Manohar manjunath.n...@gmail.com wrote:
int count(int node)
{
int sum=0;i,left,right;
for(i=0;inode;i++)
{
left=count(node-1);
right=count(node-i);
sum+=left*right;
}
return(sum);
}- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards
Ankur Aggarwal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: algorithm
Median can be computed in O(1) time after the element is inserted into existing DS. But inserting a new element in to the AVL takes O(log n) time. Overall it takes O(log n) time including inserting new element and median computation. Can median be computed in O(1) time on the fly? On Jul 28, 7:16 am, Gene gene.ress...@gmail.com wrote: I think you have confused the statement of this problem. The (in sorted order) comment makes no sense because a median is exactly one number. One number is always sorted. After every stream element is read, you want to be able to get the median of all elements read so far. You're correct that the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Permutation.................
Here is simple code to generate permutations
#include stdafx.h
#includestdio.h
int Permute( char *, int);
int PrintArray();
int swap(char *, int);
char A[]={'1','2','3','4','5','6','7','8'};
main( )
{
Permute(A,sizeof(A)/sizeof(char));
return 0;
}
int Permute(char * a, int n)
{ if(n==1)
{ PrintArray();
return 0;
}
int i=0;
for(i=0; in;i++)
{
swap(a,i);
Permute(a+1,n-1);
swap(a,i);
}
}
int PrintArray()
{
int i=0;
static int Number_of_Solutions=0;
printf(\n Conf: %-4d ,++Number_of_Solutions);
for(i=0;isizeof(A);i++)
printf(%c ,A[i]);
return 0;
}
int swap( char *a, int i)
{
if(i0)
return -1;
int temp=*a;
*a=a[i];
a[i]=temp;
return 0;
}
Regards,
Bujji
On Aug 1, 4:00 pm, UMESH KUMAR kumar.umesh...@gmail.com wrote:
Write a C code for generate all possible Permutation
as:- 1 2 3
Total no. of Per=6
also print all permutation
as:- 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
if inpute is 1 2 3 2
total no of permutation = 12
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Placement Question
try this code guys
i think there is redundancy in condition checking.
if so correct me...
#includestdio.h
struct node
{
int data;
struct node* left;
struct node* right;
struct node* sibling;
};
void connectHorizontal(struct node* root)
{
if(root == NULL)
return root;
else if(root-left==NULL root-right ==NULL)
return root;
else
{
if(root-left !=NULL)
connectHorizontal(root-left);
if(root-right!=NULL)
connectHorizontal(root-right);
if(root-left!=NULL)
{
root-left-sibling = (root-right ? root-right :
(root-sibling-left ? root-sibling-left : (root-sibling-right ?
root-sibling-right : NULL)));
}
if(root-right!=NULL)
{
root-right-sibling = (root-sibling-left ?
root-sibling-left : (root-sibling-right ? root-sibling-right : NULL));
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sorting range of numbers in O(n)
i dont think counting sort can be applied since its time cpmplexity is O(n+k) where numbers are in the range 1...k and here k=O(n^2). so the overall complexity will again go to O(n^2) :( On Mon, Aug 2, 2010 at 10:22 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: Counting Sort. On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote: There are N numbers in an array and each number is in the range [0, n*n -1]. Is there a way to sort the elements in O(n)? Thanks, Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: algorithm
This is a great solution. On Jul 28, 3:09 am, janak chandar...@gmail.com wrote: How about keeping heap? Have two heaps 1. max heap and 2. min heap keep them equal size all the time and shift top element from one to other when required... On Wed, Jul 28, 2010 at 7:46 AM, Gene gene.ress...@gmail.com wrote: I think you have confused the statement of this problem. The (in sorted order) comment makes no sense because a median is exactly one number. One number is always sorted. After every stream element is read, you want to be able to get the median of all elements read so far. You're correct that the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: algorithm
@bijju: you are correct. Here goes the code for it. *http://codepad.org/4UgNpOKH * On Mon, Aug 2, 2010 at 7:29 PM, Gene gene.ress...@gmail.com wrote: This is a great solution. On Jul 28, 3:09 am, janak chandar...@gmail.com wrote: How about keeping heap? Have two heaps 1. max heap and 2. min heap keep them equal size all the time and shift top element from one to other when required... On Wed, Jul 28, 2010 at 7:46 AM, Gene gene.ress...@gmail.com wrote: I think you have confused the statement of this problem. The (in sorted order) comment makes no sense because a median is exactly one number. One number is always sorted. After every stream element is read, you want to be able to get the median of all elements read so far. You're correct that the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group athttp:// groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
