[algogeeks] Re: shop keeper and the buyer
solution is as following if problem is buy all the n items for
minimum price if there are offers so that item j is free if customer
buys K numbers of item i
1. create two parallel arrays cost[] (cost[i] = item[i] * K ) and
free[](free[i] = j )
2. sort cost[]
3. now for highest priced item ,check if it freely avilable with any
lower cost item
4. add this lower priced item with quantity K to the set
5. else add single quantity of higher priced item to set.
6. remove these item from array and similarly repeat for other items
On Aug 11, 6:19 pm, cegprakash cegprak...@gmail.com wrote:
there are n number of items available in the shop
price[] {size n} gives the cost of each item
and there are quantity[] {size n} means that there are quantity[i]
number of i'th item
the shop keeper provides some free items
if you buy k nos of item i, you will get 1 item j for free (i may be
equal to j)
also there can be such offers for many items
what you have to do is to buy all the items in shop with minimum
expenditure.
.
source: own problem (i don't have 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.
[algogeeks] Re: Probability Puzzle
The statement You randomly pulled one coin from the bag and tossed tells that all the events of tossing the coin are independent hence ans is 3/5 On Aug 7, 10:34 pm, Algo Lover algolear...@gmail.com wrote: A bag contains 5 coins. Four of them are fair and one has heads on both sides. You randomly pulled one coin from the bag and tossed it 5 times, heads turned up all five times. What is the probability that you toss next time, heads turns up. (All this time you don't know you were tossing a fair coin or not). -- 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: GOOGLE Q1
it has O(n2) solution take nxn matrix and for every a[j](j=1 to n) store the d (a[j]-a[i]) value for all i j the trick is that d of the longest AP will occur maximum number of times in matrix count the maximum occuring d value and reconstruct the sequence by going through matrix -Ritu -- 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: Spoj Problem : String based
Could you please explain ..whts the difference b/w KMP Algorithm and This problem. KMP also finds all occurrences of a string in text -- 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: impliment cin : MS question
what question is being discussed here? On Mar 2, 6:11 pm, Ashish Goel ashg...@gmail.com wrote: can it be done without use of a goto? remember that the user can use backspace to remove the previous entered string...eg...before pressing enter, the user enters abcbsdef so the string is abdef How to decide how much buffer is optimum and would use of realloc be a good strategy? Also, i have a very basic question? Why GOTO is not recommended, i see it used like anything in linux kernel..not able to corelate security limitations in user mode vers kernel mode. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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: amazon question
can u explain what is meant by binary tree as a mirror strucrure ? is it like all left and right subtrees in tree should be mirror image of each other.. if that is the case then (A (B (C)), D(E))) should be (A (B (C)), D(,E))) means if C is the left child of B then E should be the right child of D On Feb 6, 3:34 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: Write a function to check whether the Binary Tree is mirror structure. True (A (B (C,D), E( F,G))) or (A (B (C)), D(E))) False (A (B)) or (A (B,C(D,E))) -- tree is represented in string form as given above With Regards, *Jalaj Jaiswal* (+919019947895) Final Year Undergraduate, 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 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: amazon question
Correct representation of tree in string format is (root Left sub tree,right sub tree) and if Left sub tree is NULL then it is (root,right sub tree) so as differentiate b/w case 1. when B is left child of A (A (B)) 2. or B is right child of A(A,(B)) On Feb 6, 3:34 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: Write a function to check whether the Binary Tree is mirror structure. True (A (B (C,D), E( F,G))) or (A (B (C)), D(E))) False (A (B)) or (A (B,C(D,E))) -- tree is represented in string form as given above With Regards, *Jalaj Jaiswal* (+919019947895) Final Year Undergraduate, 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 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 larger element in unsorted array...
@Sankalp range of input is not given ..so count sort can't taken as an option On Jan 31, 6:16 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: Another approach would be to use a counting sort method (less space efficient though ) So , for space efficiency , we can use a bitset .element insertion will take O(n) time in the set (with a space complexity of O(log n) ) so , for the above elements , the bitset will look like (the p# shows the index corresponding to the array) 0p10p2p3p4p5p6p7 Now , start from the 1st element in the bitset , and find the next non- zero element print it ..continue the loop from this element . Not very space efficient I suppose , but it is still O(n) and time is O(n) too . @abhijit reddy Ur simple dp is wrong , you should also process the left part as pointed by juver++ -- 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 larger element in unsorted array...
@Aman
can u explain how creation of tree ll take O(n) time
also ...what abt nodes not having right child
On Feb 1, 7:22 pm, Aman Goyal aman.goya...@gmail.com wrote:
we can create a height balanced tree with all nodes having their value and
also their index value.. can be done in o(n)
then we need to look to d right side of the node and check for index(greater
).. which will be o(log(n))
correct me if i m wrong..
On Tue, Feb 1, 2011 at 7:50 PM, Aman Goyal aman.goya...@gmail.com wrote:
this code will work only for this test case, it is wrong for all
cases...eg 3 4 9 8 6 7 10
there will be -1 output for 8 and 9 which is actually wrong..
On Tue, Feb 1, 2011 at 6:01 PM, Veenus Gupta smartvee...@gmail.comwrote:
#define N 7
int main()
{
int a[N]={1,3,5,7,6,4,8};
int m[N];
m[N-1]=-1;
for(int i=N-2;i=0;i--)
{
if(a[i]=a[i+1])
m[i]=a[i+1];
else
m[i]=m[i+1];
}
for(int i=0;iN;i++)
coutm[i]\t;
system(pause);
}
On Feb 1, 1:06 pm, abc abc may.i.answ...@gmail.com wrote:
Guys please check correctness of your algorithm before posting
On Mon, Jan 31, 2011 at 11:47 PM, ritu ritugarg.c...@gmail.com wrote:
@Ralph
Build a data structure on array B[1..n] in O(n) time such that
the following problem can be solved in O(log n) time:
Given an index i and value v, find the index j of the first
element in B such that j = i and B[j] v.
Return -1 if no such j exists.
then it ll take n*lg(n) time ... while a o(n) solution exists
On Jan 31, 9:25 pm, Ralph Boland rpbol...@gmail.com wrote:
On Jan 30, 11:00 pm, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find
the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity:O(n)
I solved a version of this problem in my thesis.
Build a data structure on array B[1..n] in O(n) time such that
the following problem can be solved in O(log n) time:
Given an index i and value v, find the index j of the first
element in B such that j = i and B[j] v.
Return -1 if no such j exists.
I have an application of this data structure in my thesis (which
is why I invented it) but I would love to hear other applications.
Ralph Boland
--
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.comalgogeeks%2Bunsubscribe@googlegroups.com
algogeeks%2Bunsubscribe@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.comalgogeeks%2Bunsubscribe@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 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] wooden log problem
You are given a wooden log of length n. It has n+1 grooves marked on
it from 0 to n. You are given an array containing numbers within the
range of 1 to n-1. These elements of the array represents the points
on the log at which u need to cut the wooden log. Now the cost of
cutting a log is proportional to the length of the original log being
cut.
Eg: n=15 and A={1,5,9}
Now when u make a cut at 1, the cost is n (the size of original log)
When u cut at 9, the cost will be n-1 as the length of the new
original log is 1 to n i.e n-1
When u cut at 5, since 5 lies between 1 and 9 and the length of this
log is 9-1=8, so the cost will be 8.
--
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 larger element in unsorted array...
@Ralph
Build a data structure on array B[1..n] in O(n) time such that
the following problem can be solved in O(log n) time:
Given an index i and value v, find the index j of the first
element in B such that j = i and B[j] v.
Return -1 if no such j exists.
then it ll take n*lg(n) time ... while a o(n) solution exists
On Jan 31, 9:25 pm, Ralph Boland rpbol...@gmail.com wrote:
On Jan 30, 11:00 pm, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity:O(n)
I solved a version of this problem in my thesis.
Build a data structure on array B[1..n] in O(n) time such that
the following problem can be solved in O(log n) time:
Given an index i and value v, find the index j of the first
element in B such that j = i and B[j] v.
Return -1 if no such j exists.
I have an application of this data structure in my thesis (which
is why I invented it) but I would love to hear other applications.
Ralph Boland
--
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: wooden log problem
DP solution is .. c[i][j] = min (c[i][k] + c[k][j] + (a[j]-a[i])) where k=i+1 to j-1 c[i][j] = a[j]-a[i] when j=i+1 c[i][j] indicates the minimum cost to cut the log starting at a[i] and ending at a[j]... c[0][n] gives the answer.. correct me if i am wrong or any better solutions? -- 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: wooden log problem
DP solution is .. c[i][j] = min (c[i][k] + c[k][j] + (a[j]-a[i])) where ji k=i+1 to j-1 c[i][j] = a[j]-a[i] when j=i+1 c[i][j] indicates the minimum cost to cut the log starting at a[i] and ending at a[j]... c[0][n] gives the answer.. correct me if i am wrong or any better solutions? -- 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: wooden log problem
sorry ..the complete question is
You are given a wooden log of length n. It has n+1 grooves marked on
it from 0 to n. You are given an array containing numbers within the
range of 1 to n-1. These elements of the array represents the points
on the log at which u need to cut the wooden log. Now the cost of
cutting a log is proportional to the length of the original log being
cut.
Eg: n=15 and A={1,5,9}
Now when u make a cut at 1, the cost is n (the size of original log)
When u cut at 9, the cost will be n-1 as the length of the new
original log is 1 to n i.e n-1
When u cut at 5, since 5 lies between 1 and 9 and the length of this
log is 9-1=8, so the cost will be 8.
The question is: given the value of 'n' and the Array A containing the
points at which u need to make a cut, find the order in which the cuts
must be made in order to minimize the total cost of cutting the wooden
log.
--
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] first larger element in unsorted array...
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity: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: first larger element in unsorted array...
for {9,7,8} it gives me {8,8,-1}...not correct
On Jan 31, 11:16 am, abhijith reddy abhijith200...@gmail.com wrote:
simple dp
void solve(int *arr,int sz)
{
int ans[sz];
ans[sz-1]=-1;
for(int i=sz-2;i=0;i--)
{
if(arr[i]arr[i+1]) ans[i]=arr[i+1];
else ans[i]=ans[i+1];
}
for(int i=0;isz;i++)
printf(%d ,ans[i]);
}
On Sun, Jan 30, 2011 at 10:00 PM, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity: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.comalgogeeks%2Bunsubscribe@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 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 Question
Yes,it works for binary search tree only
On Sat, Jan 29, 2011 at 2:22 PM, nphard nphard nphard.nph...@gmail.comwrote:
Looks good. I concede that it works for a Binary Search Tree.
On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg ritugarg.c...@gmail.comwrote:
@nphard,see the following approach carefully to know *if right pointer is
pointing to right child or in order successor*
*
*Q = node-right
IF (Q is not NULL)
{
/*Determine if Q is node's right child or successor*/
/*Q is inorder successor of node*/
IF (Q-left == node OR Q-left-val node-val)
{
}
/*Q is the right child of node*/
ELSE IF (Q-left == NULL or Q-left-val node-right)
{
}
}
1. Q-left is smaller than or equal to node if Q is Inorder Successor of
node
2. Q-left is either NULL or Q-left is greater than node if Q is right
child of node
*
*Hence* in order traversal of right threaded BST without flag* is
possible
On Fri, Jan 28, 2011 at 9:40 AM, nphard nphard
nphard.nph...@gmail.comwrote:
Not correct. You cannot assume that the right node always points to the
successor. If you do that, your traversal will be affected. Consider that
when you reach a node B from the right pointer of its parent A, you traverse
that subtree rooted at B in normal inorder. However, when you reach B from
its inorder predecessor C, you should have the knowledge that you have
visited that node's left subtree and should not visit again (which is only
known if you have the information that you are reaching that node through a
thread).
On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg ritugarg.c...@gmail.comwrote:
@nphard
ideally,a flag is required in right threaded tree to distinguish whether
right child is a pointer to inorder successor or to right child.Even we can
do without flag assuming that there ll be no further insertions taking
place in tree and no other traversal is required.
here we suppose that right pointer always gives the successor..
The solution to get the linear inorder traversal is just tailored for a
situation where there is no extra space,not even for stack!!!
On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard nphard.nph...@gmail.com
wrote:
@Ritu - Do you realize that you cannot just convert a given binary tree
into right-threaded binary tree? You need at least 1 bit information at
each
node to specify whether the right pointer of that node is a regular
pointer
or pointer to the inorder successor. This is because traversal is done
differently when you arrive at a node through its inorder predecessor.
On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg
ritugarg.c...@gmail.comwrote:
solution is not too hard to understand!!
1. [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 !!
last node in left sub tree of any node always have right pointer as
NULL because this is the last node
2. It is to be repeated for every node except the non leaf nodes .
This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
i said that it ll take O(n) time for well balanced tree.
for a node at height h ,it takes O(h) to fill this node as successor
of some other node.if combined for all sum(O(h)) h=1 to lg n ..total
time ll
come as O(n)
3. Take the case below .
1
2 3
1 1.5 2.5 4
for node 2 , you will go to 1 , which is the successor of 2 , you make
2-right=1 but what about node 1.5 ???
same is the case with node 3 ... 3-right=2.5 . How will we refer to 4
now ??
when you ll process node 1,it ll be filled in as right child of 1.5
there is no successor for 4.
In Brief
1. Convert the tree to right threaded binary tree.means all right
children point to their successors.
it ll take no additional space.ll take O(n) time if tree is well
balanced
2. Do inorder traversal to find ith element without using extra space
because succssor of each node is pointed by right child.
i hope you got it now!!
On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
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 except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's
root
makes n-2 , and so on.
Go to the largest node in the left subtree .This means go to the left
subtree and keep on going to the right until it becomes
Re: [algogeeks] Re: Amazon Question
@nphard,see the following approach carefully to know *if right pointer is
pointing to right child or in order successor*
*
*Q = node-right
IF (Q is not NULL)
{
/*Determine if Q is node's right child or successor*/
/*Q is inorder successor of node*/
IF (Q-left == node OR Q-left-val node-val)
{
}
/*Q is the right child of node*/
ELSE IF (Q-left == NULL or Q-left-val node-right)
{
}
}
1. Q-left is smaller than or equal to node if Q is Inorder Successor of
node
2. Q-left is either NULL or Q-left is greater than node if Q is right
child of node
*
*Hence* in order traversal of right threaded BST without flag* is possible
On Fri, Jan 28, 2011 at 9:40 AM, nphard nphard nphard.nph...@gmail.comwrote:
Not correct. You cannot assume that the right node always points to the
successor. If you do that, your traversal will be affected. Consider that
when you reach a node B from the right pointer of its parent A, you traverse
that subtree rooted at B in normal inorder. However, when you reach B from
its inorder predecessor C, you should have the knowledge that you have
visited that node's left subtree and should not visit again (which is only
known if you have the information that you are reaching that node through a
thread).
On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg ritugarg.c...@gmail.comwrote:
@nphard
ideally,a flag is required in right threaded tree to distinguish whether
right child is a pointer to inorder successor or to right child.Even we can
do without flag assuming that there ll be no further insertions taking
place in tree and no other traversal is required.
here we suppose that right pointer always gives the successor..
The solution to get the linear inorder traversal is just tailored for a
situation where there is no extra space,not even for stack!!!
On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard
nphard.nph...@gmail.comwrote:
@Ritu - Do you realize that you cannot just convert a given binary tree
into right-threaded binary tree? You need at least 1 bit information at each
node to specify whether the right pointer of that node is a regular pointer
or pointer to the inorder successor. This is because traversal is done
differently when you arrive at a node through its inorder predecessor.
On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg ritugarg.c...@gmail.comwrote:
solution is not too hard to understand!!
1. [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 !!
last node in left sub tree of any node always have right pointer as NULL
because this is the last node
2. It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
i said that it ll take O(n) time for well balanced tree.
for a node at height h ,it takes O(h) to fill this node as successor of
some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll
come as O(n)
3. Take the case below .
1
2 3
1 1.5 2.5 4
for node 2 , you will go to 1 , which is the successor of 2 , you make
2-right=1 but what about node 1.5 ???
same is the case with node 3 ... 3-right=2.5 . How will we refer to 4
now ??
when you ll process node 1,it ll be filled in as right child of 1.5
there is no successor for 4.
In Brief
1. Convert the tree to right threaded binary tree.means all right
children point to their successors.
it ll take no additional space.ll take O(n) time if tree is well
balanced
2. Do inorder traversal to find ith element without using extra space
because succssor of each node is pointed by right child.
i hope you got it now!!
On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
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 except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
Go to the largest node in the left subtree .This means go to the left
subtree and keep on going to the right until it becomes null , in
which case , you make y-right as x . This means effectively , that y
is the predecessor of x , in the tree . Considering a very good code ,
it may take O(1) space , but you will still need additional pointers.
Take the case below .
1
2 3
1 1.5 2.5
[algogeeks] Re: Doubt regarding Pointers in C......
Here you are passing record pointer by value.
as you call insert(record, 5),stack frame of insert contains a copy
of record.after this value is modified by calling program,it should
be either returned explicitly to caller program or needs to be passed
by reference,so that calling program refers to it always by address.
On Jan 27, 4:17 pm, nishaanth nishaant...@gmail.com wrote:
Hi guys,
I have a small doubt regarding pointers and functions.
Consider the following prototype
void insert(bst * head, int data);
This function creates a node and inserts the data in the node. Lets say i
call this function iteratively from main.
main(){
bst* record=NULL;
insert(record, 5);
insert(record, 8);
}
I see that record is not getting modified. Now is this related to call by
value. But since we are passing pointers shouldnt the change get reflected
in main.
isnt is similar to passing an array?
Enlighten me in this regard. I am tired of segfaults :(
Regards,
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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: Google Question
Following is the algorithm to ger max number of A's
set n[0] = 0
int get_max(int 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: Amazon Question
solution is not too hard to understand!! 1. [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 !! last node in left sub tree of any node always have right pointer as NULL because this is the last node 2. It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. i said that it ll take O(n) time for well balanced tree. for a node at height h ,it takes O(h) to fill this node as successor of some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as O(n) 3. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? when you ll process node 1,it ll be filled in as right child of 1.5 there is no successor for 4. In Brief 1. Convert the tree to right threaded binary tree.means all right children point to their successors. it ll take no additional space.ll take O(n) time if tree is well balanced 2. Do inorder traversal to find ith element without using extra space because succssor of each node is pointed by right child. i hope you got it now!! On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: 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 except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree . Considering a very good code , it may take O(1) space , but you will still need additional pointers. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? Now using inorder traversal with a count , I will start at 1-left , 2- left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1- right=3 ...clearly , this will not give us a solution . A reverse inorder looks just fine to me . On Jan 26, 3:14 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 apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @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 ritugarg.c...@gmail.com wrote: 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 nphard.nph...@gmail.com 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 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 that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: 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 a. For every node x,go to the last node in its left subtree and mark the right child of that node as x
[algogeeks] Re: Google Question
Following is the algorithm to get max number of A's .
it gives number = 20 for n=10
set buff = 0
call get_max(n)
int get_max(int i)
{
if (i=1 i=3)
{
n[i] = i
m[i] = 'A'
return n[i]
}
else
{
num_A = getmax(i-3);
max= MAX(num_A+3,2*num_A, num_A+3*buff)
n[i] = max
if max == 2*num_A
m[i-2] = ctrl-A , m[i-1]=ctrl-C ,m[i-2] = ctrl-V
buff = num_A
if (max == num_A + 3*buff)
m[i]=m[i-1]=m[i-2]='ctrl-v'
else if (max == num_A + 3)
m[i]=m[i-1]=m[i-2]='A'
return n[i]
}
return
}
--
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: Google Question
Following is the algorithm to get max number of A's .
it gives number = 20 for n=10
set buff = 0
call get_max(n)
int get_max(int i)
{
if (i=1 i=3)
{
n[i] = i
m[i] = 'A'
return n[i]
}
else
{
num_A = getmax(i-3);
max= MAX(num_A+3,2*num_A, num_A+3*buff)
n[i] = max
if max == 2*num_A
m[i-2] = ctrl-A , m[i-1]=ctrl-C ,m[i-2] = ctrl-V
buff = num_A
if (max == num_A + 3*buff)
m[i]=m[i-1]=m[i-2]='ctrl-v'
else if (max == num_A + 3)
m[i]=m[i-1]=m[i-2]='A'
return n[i]
}
return
}
--
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 Question
@nphard ideally,a flag is required in right threaded tree to distinguish whether right child is a pointer to inorder successor or to right child.Even we can do without flag assuming that there ll be no further insertions taking place in tree and no other traversal is required. here we suppose that right pointer always gives the successor.. The solution to get the linear inorder traversal is just tailored for a situation where there is no extra space,not even for stack!!! On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard nphard.nph...@gmail.comwrote: @Ritu - Do you realize that you cannot just convert a given binary tree into right-threaded binary tree? You need at least 1 bit information at each node to specify whether the right pointer of that node is a regular pointer or pointer to the inorder successor. This is because traversal is done differently when you arrive at a node through its inorder predecessor. On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg ritugarg.c...@gmail.comwrote: solution is not too hard to understand!! 1. [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 !! last node in left sub tree of any node always have right pointer as NULL because this is the last node 2. It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. i said that it ll take O(n) time for well balanced tree. for a node at height h ,it takes O(h) to fill this node as successor of some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as O(n) 3. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? when you ll process node 1,it ll be filled in as right child of 1.5 there is no successor for 4. In Brief 1. Convert the tree to right threaded binary tree.means all right children point to their successors. it ll take no additional space.ll take O(n) time if tree is well balanced 2. Do inorder traversal to find ith element without using extra space because succssor of each node is pointed by right child. i hope you got it now!! On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: 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 except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree . Considering a very good code , it may take O(1) space , but you will still need additional pointers. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? Now using inorder traversal with a count , I will start at 1-left , 2- left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1- right=3 ...clearly , this will not give us a solution . A reverse inorder looks just fine to me . On Jan 26, 3:14 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 apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @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 ritugarg.c...@gmail.com
[algogeeks] Re: Amazon Question
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 a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: 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 Geeks group. To post to this group, send email to algogeeks@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 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: Amazon Question
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 a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: 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 Geeks group. To post to this group, send email to algogeeks@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 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: Amazon Question
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 nphard.nph...@gmail.com 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 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 that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: 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 a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: 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 Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.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 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 Question
@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 tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @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 ritugarg.c...@gmail.com wrote: 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 nphard.nph...@gmail.com 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 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 that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: 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 a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: 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 Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.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 algogeeks@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 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: find a way
@above How can you calculate dp[n][0] with above recursive eq?? On Jan 23, 5:40 pm, sankalp srivastava richi.sankalp1...@gmail.com 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 stop at in order to cross i stations and with j miles still to go . dp[n][0]= minimum number of fuel stations to stop at in order cross n stations and with 0 miles still to go (Assuming the nth stop coincides with the destination B .In case it does not , we can answer something like dp[n][p] , where p is the distance to go from nth stop to A) The recursion dp[i][k]= min(dp[i+1][k- distance b/w the ith and (i+1)th fuel station] , dp[i+1][k- distance +lk]+1)(lk= distance we can cover on this stop) base case dp[0][j]=0;(for each j )// we have to cover no more stations therefore On Jan 22, 9:40 pm, Divya Jain sweetdivya@gmail.com wrote: if u can take only a certain amount of fuel from a particaular station ie station xi can provide li amoutn of fuel.. then wat? On 22 January 2011 13:46, Terence technic@gmail.com wrote: Greedy-Approach. Refueling only when you have to. On 2011-1-22 15:59, snehal jain wrote: Suppose you want to travel from city A to city B by car, following a fixed route. Your car can travel m miles on a full tank of gas, and you have a map of the n gas stations on the route between A and B that gives the number of miles between each station. Design an algorithm to find a way to get from A to B without running out of gas that minimizes the total number of refueling stops, in O(n) time. -- 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.comalgogeeks%2Bunsubscribe@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: merging 2 search trees
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 sweetdivya@gmail.com wrote: @ above height will not be balanced then On 21 January 2011 19:15, nishaanth nishaant...@gmail.com wrote: Find the node in T which is the maximum(which is either the root or the rightmost in the right subtree). After finding this node, just make the right child of this node point to the root of T'. Correct me if i am wrong On Fri, Jan 21, 2011 at 2:43 PM, snehal jain learner@gmail.comwrote: You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)? -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.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 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: young tableaus
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 all hook lengths. The NumberOfTableaux in the Mathematica package Combinatorica` function implements the hook length formula. http://mathworld.wolfram.com/HookLengthFormula.html On Jan 22, 2:04 pm, snehal jain learner@gmail.com wrote: . Given n distinct elements, how many Young tableaus can you make? i think the ans is 1!*2!*3!...sqrt(n)!*...*3!*2!*1! plz correct me if i am wrong.. -- 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.
