[algogeeks] DP Help...
any one give a good link to study Dynamic Programming concepts?? --Regards Vikram -- 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] Array Problem??
Given an array say A=(4,3,1,2). An array B is formed out of this in such a way that B[i] = no. of elements in A, occuring on rhs of A[i], which are less then A[i]. eg.for the A given, B is (3,2,0,0). Here A of length n only contains elements from 1 to n that too distinct.. Now the problem is: 1). You are given with any such A. Find out corresponding B? 2). You are given with any such B. Find out corresponding A? Please provide solution in O(n),if possible?? -- 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: Array Problem??
@ashish: yes it is given that elements are in 1-n range...
@anup: ur sol doesnt work for above case... try to make it general..
@abraham: i hv O(n2) sol, not required, that to of only 1st part...
guys try thinking 2nd part also??
On Tue, Oct 4, 2011 at 8:14 AM, Ashish Goel ashg...@gmail.com wrote:
7 1 4 5 3 6 2
try for
is it necessary to have elements within 1-n range?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 7:36 AM, Anup Ghatage ghat...@gmail.com wrote:
Ummm..
Algorithm:
Start from the right of the array,
make the last element of B to 0,
initialize a variables counter to 0 and max to A[end];
LOOP:
and now move from right to left,
if the next element of the left element max
increment counter and assign it to that B[ n - element ] index.
max = that element.
if the next element is smaller, assign 0 and repeat LOOP
if the next element's index is 0, check and exit
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 0;
max = 2;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 1;
max = 2;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 2;
max = 2;
3 max i.e. 2
b[n - 3] = counter = b[1] = 2
max = 3;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 3;
max = 3;
4 max i.e. 3
b[n - 4] = counter = b[0] = 3
Edge Cases: It shall remain all 0's for all same numbers as well as
ascending numbers.
On Tue, Oct 4, 2011 at 7:13 AM, DIVIJ WADHAWAN divij...@gmail.comwrote:
int B[sizeof(A)];
int k=0 , j ;
for(j=i;jn;j++)
{
if (A[j] A[i])
B[k++]=A[j];
}
On Tue, Oct 4, 2011 at 5:30 AM, Abraham freedomsou...@gmail.com wrote:
Hi Vikram!
Obviously The naivest solution is O(n2). Could you give a hint for
this problem?
On Oct 3, 4:39 pm, Vikram Singh singhvikram...@gmail.com wrote:
Given an array say A=(4,3,1,2). An array B is formed out of this in
such a way that B[i] = no. of elements in A, occuring on rhs of A[i],
which are less then A[i].
eg.for the A given, B is (3,2,0,0).
Here A of length n only contains elements from 1 to n that too
distinct..
Now the problem is:
1). You are given with any such A. Find out corresponding B?
2). You are given with any such B. Find out corresponding A?
Please provide solution in O(n),if possible??
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anup Ghatage
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
@anshu: pls elaborate... give an example... On Tue, Oct 4, 2011 at 9:51 AM, anshu mishra anshumishra6...@gmail.comwrote: use segment tree or binary index tree to solve O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sqrt function...
ok.. thanks guys... one doubt now... if this ques is asked in an interview(its already been asked in ms interview)... then u cant just write the code... u hv to explain the whole approach like why u r choosing that way to narrowing dowm the range... so pls explain how this sol is derived... On Sun, Sep 25, 2011 at 10:15 AM, keyan karthi keyankarthi1...@gmail.comwrote: binary search!!! :) On Sat, Sep 24, 2011 at 11:38 PM, sunny agrawal sunny816.i...@gmail.comwrote: let x be the number initialize ans to some value like x or x/2 now repeatedly do the following ans = (ans + x/ans)/2 each time you perform this operation you will move closer to the sqrt value and depending upon the precision required stop On Sat, Sep 24, 2011 at 11:17 PM, siddharth srivastava akssps...@gmail.com wrote: On 24 September 2011 13:45, shady sinv...@gmail.com wrote: one of the simplest way is to do binary search... :) +1 On Sat, Sep 24, 2011 at 8:42 PM, teja bala pawanjalsa.t...@gmail.comwrote: http://www.geeksforgeeks.org/archives/3187 check dis one. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Siddharth Srivastava -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] sqrt function...
any one suggest an algo to write own sqrt func...?? -- 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: MICROSOFT WRITTEN
how abt this: (i hv used some variables) a=x; b=-x; k1=a7; (if we assume 8 bit number) k2=b7; n=k1 | k2; n=n-1; k=n7; return (y-k*(y-z)); Explanation: if(x0 or x0) a and b are of opp signs, one of k1 and k2 is 0and other is 1... n=1; n becomes 0; k =0; y is returned if(x==0) a=b=0; k1=k2=0; n=0; n becomes -1 k becomes 1; z is returned... correct me if i m wrong... and it can be reduced in a single statement... On Sep 12, 10:43 am, teja bala pawanjalsa.t...@gmail.com wrote: If you're familiar with the ? operator x ? y : z you have to implement that in a function: int cond(int x, int y, int z); using only ~, !, ^, , +, |, , no if statements, or loops or anything else, just those operators, and the function should correctly return y or z based on the value of x. You may use constants, but only 8 bit constants. You can cast all you want. You're not supposed to use extra variables, but in the end, it won't really matter, using variables just makes things cleaner. You should be able to reduce your solution to a single line in the end though that requires no extra vars. -- 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: Microsoft written!!!
i m asking again, cos no one replied earlier: in example given by mohit... is the leftmost right cousin of 8 and 9, NULL or 12?? On Aug 27, 6:42 pm, aditi garg aditi.garg.6...@gmail.com wrote: This grp is full of MS interview ques..search the archives... On Sat, Aug 27, 2011 at 6:55 PM, teja bala pawanjalsa.t...@gmail.comwrote: if any one aware of microsoft written test please give me the suggestions and respective links thx. -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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: microsoft interview
how abt this:
if(!a[0][0])
{
first traverse the 1st row till we find any 1...
On Sep 2, 12:32 pm, kranthi raj kranthi...@gmail.com wrote:
oops missed Space Complexity
On Fri, Sep 2, 2011 at 12:55 PM, kranthi raj kranthi...@gmail.com wrote:
for( i = 0 ; i n ; ++i )
for( j = 0 ; j m ; ++j )
if( a[i][j] != 0 )
row[j]=col[i]=1;
for( i = 0 ; i n ; ++i )
for( j = 0 ; j m ; ++j )
{
if (row[j]==1 || col[i]==1)
a[i][j]=1;
}
Does this work?
--
Sincerely,
Kranthi Raj A
2nd Mtech
Dept Of Computer Science ,
Indian Institute of Technology, Madras
#9884989577begin_of_the_skype_highlighting 9884989577 end_of_the_skype_highlighting
--
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: microsoft interview
how abt this:
if(!a[0][0])
{
first traverse the 1st row till we find 1.
if dere is 1 do a[0][0]+=2;
then traverse the first column till 1..
if dere is 1... do a[0][0]+=3;
}
apply dave's method
if(a[0][0]==2)
make 1st row 1
else if(a[0][0]==3)
make 1st column 1...
else if(a[0][0]==5 || a[0][0]==1)
make both 1st row and col 1...
On Sep 2, 12:32 pm, kranthi raj kranthi...@gmail.com wrote:
oops missed Space Complexity
On Fri, Sep 2, 2011 at 12:55 PM, kranthi raj kranthi...@gmail.com wrote:
for( i = 0 ; i n ; ++i )
for( j = 0 ; j m ; ++j )
if( a[i][j] != 0 )
row[j]=col[i]=1;
for( i = 0 ; i n ; ++i )
for( j = 0 ; j m ; ++j )
{
if (row[j]==1 || col[i]==1)
a[i][j]=1;
}
Does this work?
--
Sincerely,
Kranthi Raj A
2nd Mtech
Dept Of Computer Science ,
Indian Institute of Technology, Madras
#9884989577begin_of_the_skype_highlighting 9884989577 end_of_the_skype_highlighting
--
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: Microsoft written!!!
in above example... is the leftmost right cousin of 8 and 9, NULL or 12?? On Aug 10, 4:36 pm, Brijesh Upadhyay brijeshupadhyay...@gmail.com wrote: thank u , i couldnot have answered this :P -- 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] inorder predecessor
i figured out algo to find the inorder predecessor of a bst without using parent pointer... just wanna confirm if its missing any case if the left child(subtree) of node exist, then predecessor ll be the max value in the left subtree. else predecessor ll be one of the ancestor in this case, starting from the given node, we hv to find a closest ancestrous node which is right child of its parent... the parent ll be the predecessor... and i made the parent implementation without changing the structure of the node... using while loop... let me know if i m missing ant case... -- 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: inorder predecessor
ya thats one option but that gives ans in O(n), requires additional memory... and unnecessarily finds for all which is not required... my sol doesnt require any extra space i.e. in O(1) space... and also in O(log n) time... tell if dere is any missing case On Aug 26, 4:58 pm, sukran dhawan sukrandha...@gmail.com wrote: is it not possible to traverse tree in order and store in array. then figure out the element and print the previous element? On Fri, Aug 26, 2011 at 2:04 PM, Vikram Singh singhvikram...@gmail.comwrote: i figured out algo to find the inorder predecessor of a bst without using parent pointer... just wanna confirm if its missing any case if the left child(subtree) of node exist, then predecessor ll be the max value in the left subtree. else predecessor ll be one of the ancestor in this case, starting from the given node, we hv to find a closest ancestrous node which is right child of its parent... the parent ll be the predecessor... and i made the parent implementation without changing the structure of the node... using while loop... let me know if i m missing ant case... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: inorder predecessor
i m writing just a pseudocode...
// root is the root of treeand node is the node whose
predecessor is to be found
predecessor(root, node)
{
parent=NULL;
if(root==NULL)
return ;
if(node-left!=NULL)
{
// find max value in left subtree...
}
else
{
while(root!=NULL root-data!=node-data)
{
if(root-data node-data)
{
root=root-left;
}
else if(root-data node-data)
{
parent=root;
root=root-right;
}
}
return parent;
}
}
i hope it makes u understand@sanjay...
On Aug 26, 5:27 pm, Sanjay Rajpal srn...@gmail.com wrote:
Vikram : will u plz elaborate more on ur solution ?
Sanju
:)
On Fri, Aug 26, 2011 at 5:24 AM, Vikram Singh singhvikram...@gmail.comwrote:
ya thats one option but that gives ans in O(n), requires additional
memory... and unnecessarily finds for all which is not required...
my sol doesnt require any extra space i.e. in O(1) space... and also
in O(log n) time...
tell if dere is any missing case
On Aug 26, 4:58 pm, sukran dhawan sukrandha...@gmail.com wrote:
is it not possible to traverse tree in order and store in array. then
figure
out the element and print the previous element?
On Fri, Aug 26, 2011 at 2:04 PM, Vikram Singh singhvikram...@gmail.com
wrote:
i figured out algo to find the inorder predecessor of a bst without
using parent pointer... just wanna confirm if its missing any case
if the left child(subtree) of node exist, then predecessor ll be the
max value in the left subtree.
else predecessor ll be one of the ancestor in this case, starting
from the given node, we hv to find a closest ancestrous node which is
right child of its parent... the parent ll be the predecessor...
and i made the parent implementation without changing the structure of
the node... using while loop...
let me know if i m missing ant case...
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
