@atul..
I missed a question asked by u above. The answer to it as follows:
/*
bcozz every node should have single child then how should
i interpret mid,left,right ??
*/
Say the given sequence is 10,19,17,14,15,16, the corresponding BST
would be :
10
How to get the soft copy of this book?
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
@topcoder..
As pointed u by earlier that 4 ,2, 6 doesn't work for the initial
code..
The 1st solution that i gave to resolve it is still faulty.. it will
fail for 4 3 2 1.. basically increasing or decreasing set of nos..
// The second and 3rd approach would work fine.. i.e (-INF, +INF) and
(small
@above format got messed up and re-posting..
while ( ++i < N)
{
if (A[i] <= mid && A[i] > left)
{
right = mid;
mid = A[i];
}
else if (A[i] > mid && A[i] <= right)
{
left = mid;
mid = A[i];
}
else
break;
}
On 31 Dec, 10:17, Lucifer wrote:
> @at
@atul.. thanks for pointing out the editing mistake..
I have fixed the while loop below:
while ( ++i < N){ if (A[i] <= mid && A[i] > left) { right =
mid;
mid = A[i]; } else if (A[i] > mid && A[i] <= right) {
left = mid;
mid = A[i]; } else break;}
On 31 D
while ( ++i < N)
{
if (A[i] <= mid && A[i] > left)
{
*mid = A[i]; // both mid and right will contain same value**
right = mid;*
// right=mid; /* i guess this is what you want*/
// mid=A[i]
*
*
}
else if (A[i] > mid && A[i] <= right)
{
*mid = A[i];
@shady..
Correction.. palindromes are not always of even length..
For ex-
abcdcba is a palindrome and not of even length...
On 30 Dec, 22:14, shady wrote:
> ya, you are right...
> btw, palindromes are always of even length so basically it is like finding
> the maximum length palindrome from a
ya, you are right...
btw, palindromes are always of even length so basically it is like finding
the maximum length palindrome from a string such that it is a
substring(continuous in nature)
On Fri, Dec 30, 2011 at 10:15 PM, atul anand wrote:
> @shady :-
>
> correction:-
> input
@shady :-
correction:-
input output
aaggaa aaggaa
On Fri, Dec 30, 2011 at 9:57 PM, shady wrote:
> lucifier question is to find an even length substring which is a
> palindrome, and your algorithm is correct, i didn't go into implementation
> deta
yup its working fine...
i coded for finding first even length palindrome found...but was searching
for longest even length palindrome found.
my bad!...
its working :) :)
sorry...
On Fri, Dec 30, 2011 at 9:57 PM, shady wrote:
> lucifier question is to find an even length substring which is a
> p
lucifier question is to find an even length substring which is a
palindrome, and your algorithm is correct, i didn't go into implementation
details
input output
aabbaaaabbaa
aaaggaaa aaaggaaa
aa
@editing mistake above..
ur just trying to find an even palindrome and *not longest one
On 30 Dec, 21:21, Lucifer wrote:
> @atul..
>
> R u trying. to find the longest even palindrome or just an even
> palindrome ?
>
> If ur looking for the longest even palindrome then it be and the
> size r
@atul..
R u trying. to find the longest even palindrome or just an even
palindrome ?
If ur looking for the longest even palindrome then it be and the
size returned would be 4.
If ur looking for just an even palindrome and want break out as per my
comments given then it will be "bb" and size
@atul,
I don't have a break condition..
Can u be more specific..
On 30 Dec, 21:07, atul anand wrote:
> @Lucifier :
>
> your 1st approach fails for the following cases:-
>
> **
> *aa*bb*aa*
> *aaa*gg*aaa*
>
> etc
>
> basically for cases where the 1st two and last two character of the even
@Lucifier :
your 1st approach fails for the following cases:-
**
*aa*bb*aa*
*aaa*gg*aaa*
etc
basically for cases where the 1st two and last two character of the even
palindrome are same.
for eg:-
1 2 3 4
--
b b b b
1st iteration :-
X = 1 1 1 1
2nd iteration :-
X= 1 1 1 2
@All..
By quadratic did u mean K*N worst case ?... basically its K*(size of
int generated)...?
On 21 Dec, 22:52, SAMMM wrote:
> Yes Quadratic approach will be naive . I thought initially to take the
> input from the Liveware , and do the below :-
>
> And we will computer for the number of unique
@praveen : question is to find longest even length pallindrome.
there was some misunderstanding earlier.
so if input is
output string is =
check lucifier post above.
we discussed another question in the same post bcoz
of initial misunderstanding :-
Q) Given a string of length N, find
The Question is: whther there exist a even length pallindrome or not
since for even ... the two consecutive character will be equal...
so find two character which are equal.. consecutively..
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
--
You received this message because you are subscrib
@atul
Yup.. Thanks .. :)
On 30 Dec, 19:41, atul anand wrote:
> very minute error in lucifier 1st approach , i guess you all have noticed
> it...
>
> while ( pRev > 0)
> {
> for ( pStrt = N; pStrt >=1 ; *--i*)
> {
>
> // *do --pStrt instead of --i*
--
You received this message because you ar
very minute error in lucifier 1st approach , i guess you all have noticed
it...
while ( pRev > 0)
{
for ( pStrt = N; pStrt >=1 ; *--i*)
{
// *do --pStrt instead of --i*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this grou
@shady
Just an addition to the previous solution, in case u are not concerned
about overlapping string i.e orig and rev strs overlap then all you
need to do is remove the following condition and it shall work fine:
*(pStrt < pRev) // remove this condition..
On 30 Dec, 15:03, atul anand wrote:
@shady : for this question
Given a string of length N, find whether there exits an even length
reverse substring of a substring.
you can use hastable , as i have mentioned above.
On Thu, Dec 29, 2011 at 5:50 PM, shady wrote:
> oh, i didn't read all the posts, anyway i have understood lucifie
@topcoder
1) For N <= 2 and not 3 its always a "YES"..
2) Also if u are OK with traversing the array twice i.e instead of a
single run N we can do it 2*N..
Then we can do the following to intialize left and right properly
instead of -+INF :
1) Scan the array to get the smallest and the gr
Actually, the initial code that i have written could have written as
follows:
int left = -INF; // or smallest integral value
int mid = 10; // greatest integral value
int right = +INF;
int i = 0;
while (++i < N)
{
// Same as the previous code..
}
I didn't take the above initialization approach
@topcoder..
You are correct.. I just figured out that the N<=3 condition is not
always correct..
Below i have explained with example the code that will fix it:
Basically for N=3 , say the sequence is a , b, c..
Then the valid cases would be:
a < b < c
a >= b >= c
a < b , (b>=c and a < c)
a >=
yes... right...
i forget to remove this statement..
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
On Fri, Dec 30, 2011 at 2:17 PM, Lucifer wrote:
> @praveen
>
> I think what u are doing above is the following:
> Say, F(n) denotes the no. of binary trees that can be formed using N
> elements g
@praveen
I think what u are doing above is the following:
Say, F(n) denotes the no. of binary trees that can be formed using N
elements given the inorder sequence..
F(n) = SumOver(i= 1 to N) { F(i-1) * F(N-i) }
which is nothing but..
F(N) = (2n C n)/ (n+1) i.e. catalan's no.
Also, i would like
@Lucifer
Looks like Your algo works for all of the my test cases. I am not able
to find counter case.
Also we should not Print "Yes" for N<=3
For eg:
A = 4,2,6
Then 2 is a root with 4 as left child and 6 as right child. It
contains two childs and fails the case.
On Dec 30, 1:26 pm, Lucifer
int countBT(int N)
{
int count =0;
int count1;
if(N==0)
return 0;
if(N<=1)
return 1;
else
{
for(int j=1;j<=N;j++)
{
count1 = countBT(j-1)
count2 =countBT(N-j);
count+=(count1*count2);
}
return (count);
}
}
@above
Also i would like to mention that the above algo considers equal
valued elements and assumes that the BST should have the following
property:
1) leftChild < = root
2) rightChild > root
On 30 Dec, 13:24, Lucifer wrote:
> @An idea...
>
> Let the array of integers be A[N]..
>
> If N < = 3,
@An idea...
Let the array of integers be A[N]..
If N < = 3, then the answer would be YES.
If N > 3, then the following algo will follow:
// The algo is self explanatory as its just ensuring BST property
keeping in mind that a parent node has only one child...
int left = smallest(A[0], A[1], A[
31 matches
Mail list logo
