a) Find the median - O(n)
b) remove the element and again find the median
c) conitnue b until you get k-1 elements
time complexity - kO(n)
On Wed, Jan 26, 2011 at 9:55 PM, ritu wrote:
>
> solution is nice!!but How to keep track of k closet numbers?
>
>
> On Jan 23, 9:22 pm, ritesh wrote:
> > 1
Hey all...Can anyone provide me with the recent (/most common) written test
questions(or links ) of Microsoft IDC and Microsoft IT SDE positions...??
Thanks in advance..
Regards,
Ankit.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To pos
I understand the algorithm, but what is the question?
On Wed, Jan 26, 2011 at 10:10 AM, bittu wrote:
> In order to make their newest microcontroller as cheap as possible,
> the ACME Widget Company designed it with a very simple cache. The
> processor is connected to a slow memory system that con
9 + 1 - ( 1 / 9 )
On Wed, Jan 26, 2011 at 10:29 PM, satish wrote:
> 19-(9/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 e
Hook Length Formula
A formula for the number of Young tableaux associated with a given
Young diagram. In each box, write the sum of one plus the number of
boxes horizontally to the right and vertically below the box (the
"hook length"). The number of tableaux is then n! divided by the
product of
How do we solve the problem http://www.spoj.pl/problems/SQRBR/ using
dynamic programming?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send em
Do the inoreder traversal of the tree ,find for maximum continous
increasing sequence in that.find start and end of the elements in that
sequence in the tree,move upto their common ancestoer which is BST
On Jan 15, 6:32 pm, Decipher wrote:
> Find the largest BST in a binary tree ? What's the comp
after adding the T' as right sub tree of largest element of T ,height
of new tree should be h= (lg m + lg n)/2
perform left rotations starting from root till hth node in rightmost
path of T
On Jan 21, 7:41 pm, Divya Jain wrote:
> @ above height will not be balanced then
>
> On 21 January 2011 19
19-(9/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 gro
solution is nice!!but How to keep track of k closet numbers?
On Jan 23, 9:22 pm, ritesh wrote:
> 1.) find x= median in o(n)
> 2.) subtract x from each number of the array
> 3.) find the k smallest number using o(n) algrithm
>
> On Jan 21, 4:04 am, snehal jain wrote:
>
> > Given an unsorted arr
@neha yeah you can use them as per your choice
On Wed, Jan 26, 2011 at 9:31 PM, Dave wrote:
> 9/.9 + 1 - 1
>
> On Jan 26, 8:12 am, "may.I.answer" wrote:
> > You have four numbers 1 , 1 , 9 ,9 .
> > Now using these four and operator + , - , * ,/ and parentheses(if
> > required) your have to get
Following approach works by calculating the least amount of fuel at
station i
min_fuel[n] = 0 //indicates least amount of fuel that should be in
car when it is at station i
d[i] = distance b/w station i+1 and i
l[i] = liters available at station i
for (i=n-1 to 1)
{
if (l[i] < (d[i] + min_fue
@Sankalp: Whoa! My complaint is that the code you presented in
http://groups.google.com/group/algogeeks/msg/9ab2623efeb73311 requires
the line to go through (0,0). I presented an example where it is
impossible to divide the points with a line through (0,0). You
responded by saying that you would ju
9/.9 + 1 - 1
On Jan 26, 8:12 am, "may.I.answer" wrote:
> You have four numbers 1 , 1 , 9 ,9 .
> Now using these four and operator + , - , * ,/ and parentheses(if
> required) your have to get 10.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" gro
@above
How can you calculate dp[n][0] with above recursive eq??
On Jan 23, 5:40 pm, sankalp srivastava
wrote:
> @ above
> In that case , it will be a simple dynamic programming based
> recursion
>
> assuming the total distance one has to cover is n ;
> d[i][j]=minimum number of fuel stations to
@above One million is 10^6.
Problem wants 1 million of prime numbers. Not the prime numbers in range
1..1000.
So, you should use two sieves.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@g
@rahul, juver++,sankalp
Though this can be solved using incrementing the range in sieve. But due to
this incremental approach how much the efficiency can be improved, any
guesses :)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to
@above person
ur solution is O(n^3) in worst case !let's say the row[] and col[]
arrays formed are
col[]=123 124 125 126
row[]=127 , 128, 129,126
every element of row[] traverses through n elements of the array
col[] and and makes O(n) comparisons in the worst case . Thus , each
traversal requir
@dave , There is a proof for it .
Let's say there is a point x0 , y0 .. and I claim that between any two
points ... x1,y1 and x2,y2 assuming they are non-collinear having a
line b/w them a line of some slope passes somewhere b/w them .This
collinearity does not affect our result .
Let's say a poi
Use a seive . it's complexity is O(nlog n)
1 million is 1*10^7 , this will run within time limit ... assuming u
optimize ur code enough !!
On Jan 26, 5:48 pm, juver++ wrote:
> Generate primes numbers for the range 1..10^7 using sieve.
> Than apply sieve bigger range using these prime numbers.
--
is it neccesary to use all four operators or we can use any combination??
i mean...can we use an operator twice??
On Wed, Jan 26, 2011 at 7:42 PM, may.I.answer wrote:
> You have four numbers 1 , 1 , 9 ,9 .
> Now using these four and operator + , - , * ,/ and parentheses(if
> required) your hav
11-(9/9)
On Wed, Jan 26, 2011 at 7:42 PM, may.I.answer wrote:
> You have four numbers 1 , 1 , 9 ,9 .
> Now using these four and operator + , - , * ,/ and parentheses(if
> required) your have to get 10.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorith
@Priyanka - what exactly is the difference between extra space and auxiliary
space? As far as the algorithm is concerned, it does use space whose order
of growth is a function of the input size and that is all that matters here.
On Wed, Jan 26, 2011 at 7:55 AM, may.I.answer wrote:
> Well the solu
A nxn matrix is sparse if the number of non-zero entries in the matrix
is much less than n^2. Multiply 2 nxn matrices containing L1, L2, non-
zero entries is O(L1L2).
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, sen
You have four numbers 1 , 1 , 9 ,9 .
Now using these four and operator + , - , * ,/ and parentheses(if
required) your have to get 10.
--
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
Well the solution is pretty simple.
What you have to do is just do inoder traversal of tree in reverse
order.
Here goes my C++ code for that
int ith_order(Tree *root,int i)
{
static int c;
static int ans;
if(root)
{
ith_order(root->right,i);
Generate primes numbers for the range 1..10^7 using sieve.
Than apply sieve bigger range using these prime numbers.
--
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 unsubscrib
I think one can use an elimination method . List out all the numbers
. Keep on eliminating the multiples of 2{excluding 2} , then multiples
of 3 , then multiples of 5 , then 7 , the denseness of the numbers
eliminated will get less . And obviouslly you will get the numbers .
On 1/25/11, siddharth
I don't seem to understand ur solution .
[quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
It is to be repeated for every node exc
@Ritu,
Right ! I misread you post
On Wed, Jan 26, 2011 at 3:44 PM, Ritu Garg wrote:
> @Algoose
>
> I said ..*.For every node x,go to the last node in its left subtree and
> mark the right child of that node as x.*
>
> it is to be repeated for all nodes except leaf nodes.
> to apply this approach
you can also go through the array printing the indexes, but what if I
want to know the indexes of some certain elements?
2010/12/30 siva viknesh :
> if we sort the first array along with the indexes ...in the next pass
> we can directly print the indexes as result no
> why should we do binary
@Algoose
I said ..*.For every node x,go to the last node in its left subtree and mark
the right child of that node as x.*
it is to be repeated for all nodes except leaf nodes.
to apply this approach ,you need to go down the tree.No parent pointers
required.
for every node say x whose left sub tre
As Navies it can be done in O(n^2)
Make numbers by using every elements in the row in array row[].
Similarly convert column elements into numbers and put them in array
col[]. Now compare both the arrays where the number matches print the
index of both row[] and col[] array...
eg:-
2, 3, 4
3, 4, 5
Hey Dave
On 25 January 2011 18:17, Dave wrote:
> The most efficient approach is to google "millionth prime number" and
> select the first hit.
>
> Good one. But it was asked to me in an interview.
The trivial approach would be to check for every number to be a prime an
continue till
the count of
1>do reverse inorder and increment count variable it uses internal
stack...
2> otherwise modify morris traversal
I agree with* juver++*...internal stack!=extra space.internal
stack=auxillary space
On 26 January 2011 12:53, juver++ wrote:
> @abovew NO!
>
> --
> You received this
@ritu
how would you find a successor without extra space if you dont have a parent
pointer ?
for Instance from the right most node of left subtree to the parent of left
subtree(root) ?
@Juver++
Internal stack does count as extra space !!
On Wed, Jan 26, 2011 at 3:02 PM, ritu wrote:
> No,no extr
No,no extra space is needed.
Right children which are NULL pointers are replaced with pointer to
successor.
On Jan 26, 1:18 pm, nphard nphard wrote:
> If you convert the given binary tree into right threaded binary tree, won't
> you be using extra space while doing so? Either the given tree shoul
CALL FOR PAPERS
and
Call For Workshop/Session Proposals
FECS'11
The 2011 International Conference on Frontiers
in Education: Computer Science and Computer Engineering
Date and L
In order to make their newest microcontroller as cheap as possible,
the ACME Widget Company designed it with a very simple cache. The
processor is connected to a slow memory system that contains n bytes,
numbered 0 to n - 1. The cache holds a copy of k of these bytes at a
time, for fast access. It
If you convert the given binary tree into right threaded binary tree, won't
you be using extra space while doing so? Either the given tree should
already be right-threaded (or with parent pointers at each node) or internal
stack should be allowed for recursion but no extra space usage apart from
th
it can be done in O(n) time using right threaded binary tree.
1.Convert the tree to right threaded tree.
right threaded tree means every node points to its successor in
tree.if right child is not NULL,then it already contains a pointer to
its successor Else it needs to filled up as following
it can be done in O(n) time using right threaded binary tree.
1.Convert the tree to right threaded tree.
right threaded tree means every node points to its successor in
tree.if right child is not NULL,then it already contains a pointer to
its successor Else it needs to filled up as following
42 matches
Mail list logo
