Re: [algogeeks] Re: Check if one tree is sub tree of other
@sidarth
your method would not work it think.
let a case
sub tree: 4Main tree:
6
5 6
4 7
5
8
inorder traversal of sub tree str1= 5,4,6 and inorder traversal of Main
tree str2=5,4,6,7,8
and str1 is subset of str2 but the sub-tree is not actually a sub tree...
correct me if im wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 11:20 AM, Dheeraj Sharma
dheerajsharma1...@gmail.com wrote:
No..am nt talking about binary search tree..bt about binary tree.. It
was asked in my amazon written
@shady..doing the substring search..as we have to search for subset of
tree..it searchng substrn might find some false nodes..that doesnt
belong to that subtree
On 3/21/12, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
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.
--
Sent from my mobile device
*Dheeraj Sharma*
--
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.
--
AMRIT
--
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: Check if one tree is sub tree of other
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.comwrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
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.
--
HARSHIT PAHUJA
M.N.N.I.T.
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.
--
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] Amazon question
hi i found this qstn frum career cup pls help to solve this. Given an integer n, compute 2 integers x, y satisfying: n=x*y=n+2; |x-y| is minimal. Thanks Regards Amrit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/YF1blviMR8kJ. 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: Check if one tree is sub tree of other
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.com
wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
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.
--
HARSHIT PAHUJA
M.N.N.I.T.
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.
--
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.
--
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: Check if one tree is sub tree of other
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady sinv...@gmail.com wrote:
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.com wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
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.
--
HARSHIT PAHUJA
M.N.N.I.T.
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.
--
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.
--
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.
--
AMRIT
--
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
Re: [algogeeks] Re: Check if one tree is sub tree of other
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34###for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main1
/ \
34
/ \
51
/ \
34
preorder traversal= 1353##4##1##4##
sub
5
/\
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM, amrit harry dabbcomput...@gmail.comwrote:
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady sinv...@gmail.com wrote:
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.com wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and
one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
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.
--
HARSHIT PAHUJA
M.N.N.I.T.
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.
--
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
Re: [algogeeks] Re: Run Length Decoding... inplace
wasnt able to come up with an algo which would satisfy all the cases input
like a1b1c4 here output length is equal to input length . till now i dont
knw how to handle these type of input. :( :(
On Wed, Mar 21, 2012 at 10:02 AM, atul anand atul.87fri...@gmail.comwrote:
@Gene : yes you are right , i misunderstood the problem . so m/m available
is just enough to hold the output.
thanks for correcting ... that would make this ques little interesting :)
:)...i guess my first posted code can be modified to meet the requirement.
i will post the updated code.
On Tue, Mar 20, 2012 at 5:45 PM, Gene gene.ress...@gmail.com wrote:
I don't think you're seeing the requirement completely. The problem
promises only that the output buffer will be big enough to hold the
output. You have made it huge. I tried your code on an input of
a1b1c6
with the required output space of 8 characters (plus 1 for the C null
character), and it printed
cc
and stopped.
Last night I realized there is another approach that will work in all
cases, so I deleted my post. I guess it wasn't deleted on the server
in your part of the world.
You all can certainly work it out. You can't just copy the input to a
predetermined place in the buffer before processing it. It needs to be
placed carefully, and it needs to be processed from both ends to a
certain point in the middle.
On Mar 20, 7:32 am, atul anand atul.87fri...@gmail.com wrote:
using Gene logic , but we need to take care of number with more than 1
digits , so updated gene's code is as follows :-
#includestdio.h
#define MAX 1000
int copy(char *str,int len)
{
int max_len=MAX-1,i;
for(i=len-1;i=0;i--)
{
str[max_len]=str[i];
max_len--;
}
return max_len+1;
}
void runLength(char *str)
{
unsigned int j,k=1,loop=0,res_len=0;
int i,n_start;
char c;
/*copying input to the end of the buffer*/
n_start=copy(str,strlen(str));
for(i=MAX-1;i=n_start;i--)
{
if(str[i]='0' str[i]='9')
{
continue;
}
else
{
sscanf(str[i],%c%d,c,loop);
for(j=0;jloop;j++)
{
str[res_len]=c;
res_len++;
}
}
}
str[res_len]='\0';
printf(\nDecoded Msg = %s\n,str);
}
int main()
{
char str[MAX];
memset(str,0,MAX);
printf(\nEnter String = );
scanf(%s,str);
runLength(str);
return 1;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this 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] Amazon question
One possible way is:
1) Put the three candidate number together into an array [n, n + 1, n + 2]
2) Iterate each element *E* in that array and test whether *E* is a prime
number
2.1) If it is, there will be only one way to find the two numbers
product to be *E*, i.e. {x = 1, y = E} OR {x = E, y = 1}, so the result is
E - 1
2.2) Otherwise, we should choose x and y that are closest to the
sqrt of *E*, which is quite straight forward.
E.g. 72 = 8 * 9 and 72 = 2 * 36 (2 8 and 36 9, so |9 -
8| |36 - 2|)
So total time complexity is O(sqrt(E)).
--
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: Google written test
@Hemesh : dats would be an over kill , you are converting O(n) solution to
a subset sum problem which NP
On Tue, Mar 20, 2012 at 7:35 PM, Hemesh Singh hemesh.mn...@gmail.comwrote:
Isn't it a standard subset sum problem? You can generate the Fibonacci
numbers and put them in an array. Now just apply the standard algorithm to
find that which Fibonacci numbers add up to make the given sum. Please
correct me if I am wrong.
On Mon, Mar 19, 2012 at 8:58 PM, atul anand atul.87fri...@gmail.comwrote:
@Gene : yeah i skipped ur updated code...its dere
@shady : it is similar to fib encoding...you just need to reverse the
output from gene code and append '1' at the end...
while decoding it ...this extra '1' is not considered..
i am nt sure but maybe the reason for adding '1' at the end is to mark
end of word
On 19 Mar 2012 19:10, shady sinv...@gmail.com wrote:
@gene it does show your updated code.
@atul from the given input it seems different from Fibonacci encoding.
On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote:
Thanks.
I noticed this too. If the n'th 1/0 digit is supposed to correspond
with the n'th fibonacci number, then my original code would have been
right. But the example isn't done this way.
I fixed the code to match the example the evening of the 18th
(Eastern time), but I guess the change is not showing on your server
yet.
On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote:
@Gene : your code will work fine by changing the argument passed from
main(), you just need to call rite f(n, 1, 1); from main instead of
f(n,
1, 0);
On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com
wrote:
@all : i guess question is on Fibonacci coding.
here you can find the algo :-
http://en.wikipedia.org/wiki/Fibonacci_coding
On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh
atulsingh7...@gmail.comwrote:
@Ravi... there should be only one answer as for fibonacci
representation
of a number we have to include the part of the fibonacci number
just less
than the number then remaining part of the sum is filled by
fibonacci
numbers starting from 1
suppose we have to convert 6 into fibonacci representation
then 6 has two sum sets as {1,2,3} or {1,5}
then the fibonacci number just less than 6 is 5 so bit
representing 5 is
set then for completing the sum to 6 bit 1 is also set.
so *fibonacci representation of 6 is 1001 .* not 0111
ATul Singh | Final Year | Computer Science Engineering | NIT
Jalandhar | 9530739855 |
--
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.
--
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.
--
Hemesh singh
--
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: Check if one tree is sub tree of other
@amrit : i guess this will work.
On Wed, Mar 21, 2012 at 1:51 PM, amrit harry dabbcomput...@gmail.comwrote:
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34###for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main1
/ \
34
/ \
51
/ \
34
preorder traversal= 1353##4##1##4##
sub
5
/\
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM, amrit harry dabbcomput...@gmail.comwrote:
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady sinv...@gmail.com wrote:
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.com wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left,
t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all
the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and
one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
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.
--
HARSHIT PAHUJA
M.N.N.I.T.
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.
--
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
[algogeeks] Re: Check if one tree is sub tree of other
Yeah..i wrote sumthig similar..i placed L for left null and R for
right null..and then checked for substring in preorder traversal..i
dont know if its correct or not..
On 3/21/12, atul anand atul.87fri...@gmail.com wrote:
@amrit : i guess this will work.
On Wed, Mar 21, 2012 at 1:51 PM, amrit harry dabbcomput...@gmail.comwrote:
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34###for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main1
/ \
34
/ \
51
/ \
34
preorder traversal= 1353##4##1##4##
sub
5
/\
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM, amrit harry
dabbcomput...@gmail.comwrote:
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady sinv...@gmail.com wrote:
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur
tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.com wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left,
t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all
the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and
one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching
sub
tree.
If they are binary search trees, it could be more efficient. Did
you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
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.
--
HARSHIT PAHUJA
M.N.N.I.T.
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.
--
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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
@Sunny: A little doubt, how are you making sure that the candidate sum is
actually a sum that can be formed by contiguous elements of the array?
Can you please explain your algo for this array : 1 , 2 , 99 , 100 , we
need the 3rd smallest sum.
On Wed, Feb 22, 2012 at 3:11 PM, atul anand atul.87fri...@gmail.com wrote:
ok got it ..thanks for resolving queries :) :)
On Wed, Feb 22, 2012 at 11:10 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
*NO, u r getting it wrong*
*given a value x, we can find how many contiguous sums are lesser than x
using the above mentioned algorithm in O(N)*
*so we are searching a x in range 0-S such that, x has exactly k-1 sums
lesser than x and x is kth*
*
*
*Algorithm: *
*for
*
On Wed, Feb 22, 2012 at 10:41 AM, atul anand atul.87fri...@gmail.comwrote:
/*
algo goes as follows
*do a binary search in range 0-S*, for each such candidate sum find how
many sums are smaller than candidate sum
*/
do a binary search in range 0-S-- to search what??
acc to the complexity , O(N *log S) it seems that you are searching each
element in given input array from range 0-S
for given input = 1,2,3,4,5
S= 15
please clarify . sorry but i am not getting it ...
On Wed, Feb 22, 2012 at 10:25 AM, sunny agrawal sunny816.i...@gmail.com
wrote:
Yes, read my first post
On Wed, Feb 22, 2012 at 10:19 AM, atul anand
atul.87fri...@gmail.comwrote:
sum[0-1] = 3 -- (1,2)
sum[0-2] = 6 -- (1,2,3)
sum[1-2] = 5 -- (2,3)
ok...so we can consider 3 , (1,2) as different contiguous.
how did you choose candidate sum for the given input ?? will it not
add to the complexity
On Wed, Feb 22, 2012 at 9:59 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
@atul there are 8 sums less than 7
sum[0 - 0] = 1
sum[1-1] = 2
sum[2 - 2] = 3
sum[3-3] = 4
sum[4-4] = 5
sum[0-1] = 3
sum[0-2] = 6
sum[1-2] = 5
contiguous sum (1,2) , (2,3) -- these contiguous sum has already
been counted ??? where ?
Read problem statement carefully !!
On Wed, Feb 22, 2012 at 9:39 AM, atul anand
atul.87fri...@gmail.comwrote:
@sunny : before moving to your algorithm , i can see wrong output in
your example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
we need to find how many sums are less than candidate Sum chosen in
one iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i
are lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say
that i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then
u can add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to
find a index g such that sum[g - i] candidate sum, and increase the
count
by ((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given
example{1,2,3,4,5}) k = 3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start
from the beginning ? can you explain for that same example... should
we
check for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all
are positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find
how many sums are smaller than candidate sum
there is also need to take care of some cases when there are
exactly k-1 sums less than candidate sum, but there is no contigious
where
sum = candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.comwrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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
[algogeeks] Re: Check if one tree is sub tree of other
@All
[ Let the tree to be searched in be 'T' and the subtree to be matched
be 'S']
If i understood the previous posts correctly.. then basically we
discussed about 2 methods:
1) Brute force, wherein we consider each node of the 'T' as the root
of new subtree and try to compare it with 'S'.
Complexity - O( |T| * |S| ) ... ( |X| = size of 'X' )
2) Preorder with special characters...
Time complexity:-
Time taken to generate the preordered string for
'T' :- 2* |T| + 1
Time taken to generate the preordered string for
'S' :- 2* |S| + 1
Time taken to find a match : O(2* |T|) + O(2* |S|)
Hence, total time complexity : O(|T|) .. [assuming that |T| =|
S| ]
Space complexity: 2*( |T| + |S| + 1)
I think we can come up with a third method where the time complexity
will be of the order of O(|T|) with constant space..
Here is the idea,
As we know that the subtree in the question is a perfect subtree, we
can use it to develop a O(|T|) algo..
If we know the count of nodes for each perfect subtree of |T| then for
all those subtrees having the count equal to |S| we will perform a
check to see if the subtrees match, otherwise we won't..
Basic operations:
1) Count the no. of nodes of |S| : CountNodes(node * root) ( Time
Complexity : |S|)
2) Check whether 2 trees are equal : isTREqual(node *T1, node *T2)
( Time Complexity : |S|, as we are going to check only for those
subtrees of |T| whose count is equal to |S|)
3) Modify the CountNodes(node *root) API to calculate the count of the
subtrees as well as check with the subtree of 'T' is equal to 'S' when
the counts match.
Regarding time complexity of the above algo:
As we already know the time complexity of operations 1 and 2, lets
talk about operation 3.
The count procedure will take |T| time in total...
What about the match procedure ?
Say that we have identified subtrees T1, T2...Tn.. whose count is
equal to |S|, hence the time taken by the tree match procedure will be
|S| * (n)..
Lets look at this derivation in a slightly different way exploiting
one of the properties of the found subtrees:
Now, as we know that all the subtrees of T having the same node count |
S| can't share nodes among them...
hence,
|T1| + |T2| + ... |Tn| = |T| , i.,e |S| * (n) = |T| , equality holds
when S = T..
Hence Time complexity (for operation 3) is equal to 2*|T|..
Total complexity: time taken by operation (1) + (3)
: |S| + 2*|T| = O(|T|)
---
Pseudocode:
// I m not jolting down the code for CountNodes and isTREqual..
// Also, currently assuming that |S| and |T| are not null trees.. well
this special case can be handled, if required.. but i don't think its
a valid use case..
bool areTreesSame(node *T, node *S, int countS, int *nCount)
{
int leftCount=0, rightCount=0;
if (T == NULL)
return false;
if ( areTreesSame(T- left, S, countS, leftCount) ||
areTreesSame(T- right, S, countS, rightCount)
)
return true;
else
{
*nCount = leftCount+rightCount+1;
if(nCountS == *nCount)
return isTREqual(T, S);
else
return false;
}
}
---
On Mar 21, 5:04 pm, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
Yeah..i wrote sumthig similar..i placed L for left null and R for
right null..and then checked for substring in preorder traversal..i
dont know if its correct or not..
On 3/21/12, atul anand atul.87fri...@gmail.com wrote:
@amrit : i guess this will work.
On Wed, Mar 21, 2012 at 1:51 PM, amrit harry dabbcomput...@gmail.comwrote:
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34### for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main 1
/ \
3 4
/ \
5 1
/ \
3 4
preorder traversal= 1353##4##1##4##
sub
5
/ \
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM, amrit harry
dabbcomput...@gmail.comwrote:
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady
Re: [algogeeks] Re: Run Length Decoding... inplace
Gene, Atul
How would a string of say 257 or say 10 times a would be represented, will
it be a10 or aascii of 10
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Mar 21, 2012 at 2:04 PM, atul anand atul.87fri...@gmail.com wrote:
wasnt able to come up with an algo which would satisfy all the cases input
like a1b1c4 here output length is equal to input length . till now i dont
knw how to handle these type of input. :( :(
On Wed, Mar 21, 2012 at 10:02 AM, atul anand atul.87fri...@gmail.comwrote:
@Gene : yes you are right , i misunderstood the problem . so m/m
available is just enough to hold the output.
thanks for correcting ... that would make this ques little interesting :)
:)...i guess my first posted code can be modified to meet the requirement.
i will post the updated code.
On Tue, Mar 20, 2012 at 5:45 PM, Gene gene.ress...@gmail.com wrote:
I don't think you're seeing the requirement completely. The problem
promises only that the output buffer will be big enough to hold the
output. You have made it huge. I tried your code on an input of
a1b1c6
with the required output space of 8 characters (plus 1 for the C null
character), and it printed
cc
and stopped.
Last night I realized there is another approach that will work in all
cases, so I deleted my post. I guess it wasn't deleted on the server
in your part of the world.
You all can certainly work it out. You can't just copy the input to a
predetermined place in the buffer before processing it. It needs to be
placed carefully, and it needs to be processed from both ends to a
certain point in the middle.
On Mar 20, 7:32 am, atul anand atul.87fri...@gmail.com wrote:
using Gene logic , but we need to take care of number with more than 1
digits , so updated gene's code is as follows :-
#includestdio.h
#define MAX 1000
int copy(char *str,int len)
{
int max_len=MAX-1,i;
for(i=len-1;i=0;i--)
{
str[max_len]=str[i];
max_len--;
}
return max_len+1;
}
void runLength(char *str)
{
unsigned int j,k=1,loop=0,res_len=0;
int i,n_start;
char c;
/*copying input to the end of the buffer*/
n_start=copy(str,strlen(str));
for(i=MAX-1;i=n_start;i--)
{
if(str[i]='0' str[i]='9')
{
continue;
}
else
{
sscanf(str[i],%c%d,c,loop);
for(j=0;jloop;j++)
{
str[res_len]=c;
res_len++;
}
}
}
str[res_len]='\0';
printf(\nDecoded Msg = %s\n,str);
}
int main()
{
char str[MAX];
memset(str,0,MAX);
printf(\nEnter String = );
scanf(%s,str);
runLength(str);
return 1;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this 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] Amazon question
@Rujin : mathematically point 2.2 seems straight forward but can we achieve
value of x and y with an algo whose complexity wud be O(sqrt(E)) ??
On Wed, Mar 21, 2012 at 2:37 PM, Rujin Cao drizzle...@gmail.com wrote:
One possible way is:
1) Put the three candidate number together into an array [n, n + 1, n + 2]
2) Iterate each element *E* in that array and test whether *E* is a prime
number
2.1) If it is, there will be only one way to find the two numbers
product to be *E*, i.e. {x = 1, y = E} OR {x = E, y = 1}, so the result
is E - 1
2.2) Otherwise, we should choose x and y that are closest to the
sqrt of *E*, which is quite straight forward.
E.g. 72 = 8 * 9 and 72 = 2 * 36 (2 8 and 36 9, so |9
- 8| |36 - 2|)
So total time complexity is O(sqrt(E)).
--
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.
