@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
1do 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++ avpostni...@gmail.com wrote:
@abovew NO!
--
@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
@Ritu,
Right ! I misread you post
On Wed, Jan 26, 2011 at 3:44 PM, Ritu Garg ritugarg.c...@gmail.com 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
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
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);
@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
Theoretically, the internal stack used by recursive functions must be
considered for space complexity.
On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote:
internal stack != extra space
--
You received this message because you are subscribed to the Google Groups
Algorithm
@abovew NO!
--
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
I don't understand what you mean.
Consider a simple inorder traversal of a balanced binary tree. Using
recursion, the code is simply:
void inorder(Node *node) {
if (node == NULL)
return;
inorder(node-left);
print(node-val);
inorder(node-right);
}
What do you consider to be the above
If we shouldn't use recursion at it uses internal stack, then I hope we can
use Morris tree traversal and use a counter to find the 5th max.
On Fri, Jan 21, 2011 at 11:19 PM, juver++ avpostni...@gmail.com wrote:
@above yes, posted solution needs parent links.
Another solution is to process
internal stack != extra space
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
This question was posted some time ago.
One solution is - start from the largest element (which is the righmost one
in the tree).
Then apply algorithm of searchin node's predecessor. It takes O(k) time to
find k-th largest/smallest number.
--
You received this message because you are
@Juver..doesnt it require the parent information ?
What if the data structure has only left and right pointers.
On Fri, Jan 21, 2011 at 8:41 PM, juver++ avpostni...@gmail.com wrote:
This question was posted some time ago.
One solution is - start from the largest element (which is the righmost
@above yes, posted solution needs parent links.
Another solution is to process tree in reverse inorder: right subtree, root,
left subtree and keeping counter k,
when k is zero return current node
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
There was the same question some days ago.
--
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.
@sunny...yes..it should occupy atleast position because Y is nothing
but the no_of_elements that we wants to store into 2nd array..so
rest(e.g.( ((x+y)-x) in this case ) of the elements initializes to
their default value in case of it is 0 ..i think its okk
Regrads
Shashank
--
You received
@juver++ so post your approach...i will also do the same..i posted the
question here so that we can learn new way to solve or you can say
best way to solve problem...
One Problem Can be Solved My Many Ways But There is Only One Best Way
to Solve It
Regards
Shashank
--
You received this
best method i know is.
start comparing elements from ends and put the larger at end and so on
TC: O(X+Y)
SC: O(1)
On Tue, Jan 11, 2011 at 8:11 PM, bittu shashank7andr...@gmail.com wrote:
@juver++ so post your approach...i will also do the same..i posted the
question here so that we can
Do merging of the array's tails, and place the result at the array's back.
So its right side grows to the left.
It's linear solution.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
There is a linear solution in terms of the matrix's size. So in a whole it
has O(n^2) time complexity.
--
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
2D matrix sum is a simple DP problem, but U need n*n extra space as well or
have to change the i/p.
(u can get the i/p back once if required)
If this is acceptable, let me explain.
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Sun, Dec 19, 2010 at 7:01 PM, juver++
There is O(n^2) solution with O(n) extra space
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
That will also match 999.9.99.9 which isn't an ip address.
On Sep 21, 6:46 am, Neeraj 17.neera...@gmail.com wrote:
*grep -R \[0-9]\+.[0-9]\+.[0-9]\+.[0-9]\+\ * | awk -F':' '{print $1}' |
uniq
*
works on my system :P
On Tue, Sep 21, 2010 at 2:07 PM, Chi c...@linuxdna.com
With perl installed:
find directory | xargs perl -pi -e 's/needle/replace/g'
With sed installed:
#!/bin/bash
find directory mirror
exec 3mirror
while read file 3
do
replace=`more $file | sed -r -e 's/needle/replace/g'`
cat $replace $file
done
On Sep 19, 11:30 pm, bittu
grep /home/user/dir -d recurse -H \b(?:(?:25[0-5]|2[0-4][0-9]|[01]?
[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\b
the ugly looking block matches IP address. GREP is a gnu regex utility
in linux (also available for windows).
/home/user/dir is the location of the directory
-d
*grep -R \[0-9]\+.[0-9]\+.[0-9]\+.[0-9]\+\ * | awk -F':' '{print $1}' |
uniq
*
works on my system :P
On Tue, Sep 21, 2010 at 2:07 PM, Chi c...@linuxdna.com wrote:
With perl installed:
find directory | xargs perl -pi -e 's/needle/replace/g'
With sed installed:
#!/bin/bash
find
What does [0-9]\+. means? Why do you nested it?
On Sep 21, 3:46 pm, Neeraj 17.neera...@gmail.com wrote:
*grep -R \[0-9]\+.[0-9]\+.[0-9]\+.[0-9]\+\ * | awk -F':' '{print $1}' |
uniq
*
works on my system :P
On Tue, Sep 21, 2010 at 2:07 PM, Chi c...@linuxdna.com wrote:
With perl installed:
@Neeraj:
Your approach is good, this however lists .999.999.999 which is
not a valid IP address.
grep -lR [0-255]\.[0-255]\.[0-255]\.[0-255] *
further filter out the output of above to invalidate any ip address
that are reserved.
-l is for suppressing normal output and printing only
Sorry this doesn't work all grep out there ...
On 22 Sep, 01:40, Prem Mallappa prem.malla...@gmail.com wrote:
@Neeraj:
Your approach is good, this however lists .999.999.999 which is
not a valid IP address.
grep -lR [0-255]\.[0-255]\.[0-255]\.[0-255] *
further filter out the output of
struct list
{
median -- median from the start to num
number ---number
list *next
};
during insertion : insert in sorted LL
after that all subseq node's median has to be modified
O(n)
during median_retriev
check the median value and return that
O(1)
I assumed deletion is not happening.
Keep an augmented balanced BST. Augmented data: number of elements in the
right and left subtrees .
Insertion: logn
Find Median: logn
Cheers
Nikhil Jindal
Delhi College of Engineering
On Fri, Sep 17, 2010 at 12:09 PM, vikas kumar vikas.kumar...@gmail.comwrote:
struct list
{
median --
It is true that there are infinitely many solutions (or zero
solutions) (x, y, z) in any case.
But what we are interested here is S=x+y+z.
Apply y = S-x-z, you get:
S/Vp+x(1/Vd-1/Vp)+z/(1/Vu-1/Vp) = T1
S/Vp+x(1/Vu-1/Vp)+z/(1/Vd-1/Vp) = T2
Adding the two, you get
2S/Vp +
You could also get a unique solution if the car has speed of 72 63 56
in downhill, plain and uphill respectively.
I think the speed Vd, Vp, Vu was chosen so that 2Vp = Vd + Vu.
But for unique solution, it ought to be 2/Vp = 1/Vd + 1/Vu.
Under this condition, we can get the unique S=x+y+z:
the solution seems to be simple.
Just try to imagine what is happening
You have a road with downhill and uphill.
So if u travel 5 km uphill and then 5 km on plain and then 5 km on downhill
then time taken
by you will be equal to 15 km on the plain road(that is solely due avg of
speed of downhill
you dont have the structure of the node
typedef struct member node
{
int data;
struct member * next;
}ll;
On Tue, Sep 14, 2010 at 5:57 PM, soundar soundha...@gmail.com wrote:
From first linked list set flag value in each traversal of
node..then start from second linked list suppose if
So if u travel 5 km uphill and then 5 km on plain and then 5 km on
downhill then time taken
by you will be equal to 15 km on the plain road
This is not the truth.
5/72 + 5/64 + 5/56 - 15/64 = 5/72+5/56-10/64 = 10/63-10/64 0
(that is solely due avg of speed of downhill and uphill is = speed
The following algorithm traversals both lists twice to find the
intersection point, without modification to the original nodes.
The only assumptions:
1) Head pointer of two list: La, Lb
2) .next point to the next node.
3) .next of the tail node is NULL
intersect(La,Lb)
{
// Find the length
No. Two linear equations in three unknowns will always yield many
solutions (or zero solutions). These are essentially plane
equations. Two planes intersect in a line (unless they are
parallel). You might get a de facto unique solution for some values
of Vu, Vd, Vu, T1, T2 from the constraints
From first linked list set flag value in each traversal of
node..then start from second linked list suppose if flag value is
already set that is the intersection point
correct me if i am wrong
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Actually the solution is unique. The middle part with the Ys is the
same and therefore can be omitted out. Now you are left with
2 equations and 2 unknowns.
I used time in minutes and I have x = 1.28, z = 0.30476 units (y can
be found out).
I guess the trick was 1. to write the equations that
This isn't right. Dropping both y terms is the same as setting y to
zero. The answer you get is correct, but there are many others as has
been said.
You could get a unique solution if the route were constrained to be
monotonic (level and up or else level and down).
On Sep 14, 4:28 pm,
i think that we have to generate substrings from the given string such that
the similarity is above 50%
for eg.
word =foo
we have to generate the strings which must be greater than half of the given
string length
{fo,oo} (in this case)
after this operation we have the following string set
you will have to use the concept of edit distance ..
google for edit distance and you may find too many good articles on it.
Levenshtein distance is one such algorithm for measuring the amount of
difference between two sequences [edit distance]
On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar
No, best way is to use a trie, or a suffix-trie. Look here:
http://phpir.com/tries-and-wildcards
On Sep 13, 12:32 pm, anuj maurice anuj.maur...@gmail.com wrote:
you will have to use the concept of edit distance ..
google for edit distance and you may find too many good articles on it.
cant it be like '%f%'
On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar praveen200...@gmail.comwrote:
i think that we have to generate substrings from the given string such that
the similarity is above 50%
for eg.
word =foo
we have to generate the strings which must be greater than half of
Well, no, it is not told that you are given the binaries for the
database, too.
On Sep 13, 1:27 pm, sharad kumar aryansmit3...@gmail.com wrote:
cant it be like '%f%'
On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar
praveen200...@gmail.comwrote:
i think that we have to generate substrings
How would you define 50% or more similarity ?
On Sun, Sep 12, 2010 at 6:49 PM, Chi c...@linuxdna.com wrote:
trie
On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote:
pagerank algo
On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me thesnoop...@gmail.com
wrote:
You are given
What does 50% or more similarity means?? Trie will work only if prefix is
equal.
On Sun, Sep 12, 2010 at 6:49 PM, Chi c...@linuxdna.com wrote:
trie
On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote:
pagerank algo
On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me
50% should be define like this:
select * from product
where
name like '%foo%'
and len(name) =6;
On Sep 13, 9:18 am, Bharath bharath1...@gmail.com wrote:
What does 50% or more similarity means?? Trie will work only if prefix is
equal.
On Sun, Sep 12, 2010 at 6:49 PM, Chi
The Final and Finest Answer is
select name form product where name like %foo% and len(name)=6 ;
length should be the =6 because of constraints ..given that 50% and
more
foo can occure anywhere in word as
footba probability of occurance of foo is 50%
byfoot
foofoo 100%
its wouldn't give
trie
On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote:
pagerank algo
On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me thesnoop...@gmail.com wrote:
You are given the amazon.com database which consists of names of
millions of products. When a user enters a search query for
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 ,
101 - 153 of 153 matches
Mail list logo
