CareerCup

#include <stdio.h>
#include <string.h>

void printArr(char s[], int i, int j) {
    while(i<=j)
        printf("%c   ", s[i++]);
    printf("\n");
}

void palindromes(char s[]) {
    int i, j, L, H;
    L = 0;
    H = strlen(s)-1;
    for(i=L; i<=H; i++) {
        // odd palindromes with i at center
        for(j=1; i-j>=L && i+j<=H && s[i-j]==s[i+j]; j++)
            ;
        if(j>1) {
            printArr(s, i-j+1, i+j-1);
        }
        // even palindromes, no-center
        for(j=0; i-j>=L && i+j+1<=H && s[i-j]==s[i+j+1]; j++)
            ;
        if(j>0)
            printArr(s, i-j+1, i+j);
    }
}

int main() {
    char *s = "malayalam is funny language";
    
    palindromes(s);
    
    return 0;
}

Input: malayalam is funny language
Output:
a l a
m a l a y a l a m
a l a
n n

what is non concentric palindrome? for that matter.. what is concentric palindrome?

I think concentric palindromes are palindromes with the same center.
acasdabadso: sdabads and aba are concentric and aca is not concentric with the rest.

Is this same as determining if a string is a paliandrome whose length is an even number?

in that case thats fairly easy :)

My first idea is, treat each character as the center and starting at it, find the longest radius of the palindrome with this character as the center. the time complexity is O(n*h) where h is the longest palindrome.
Comparing with the suffix method: 1 suffix tree requires O(n) which is much faster. 2. But, what if the hr wanted you to write the code??

void nonConcentricPalindrome (char *str)
{
    if (str == NULL)
        return;
    for (int i = 1; i < strlen (str) - 1; i++)
    {
        if (str[i - 1] == str[i + 1])
        {
            int p = i - 1;
            int q = i + 1;
            while (p >= 0 && q < strlen - 1)
            {
                if (str[p] != str[q])
                    break;
                p++;
                q--;
            }
            printf ("The starting index is %d the ending index is %d and center is %d\n", p, q, i);
        }
    }
}
In the worst case the runtime will be O(n^2). Any better solution would be apprciated

The above code is a good solution. But here we are making an assumption that the string is going to be always ODD length.
eg. It will work for the string like 'abcba', but it will not work for the string 'abccba', which is also an EVEN length pallindrome string.
So to do for the even length string,we should ALSO consider two characters(which are same eg. 'cc') at a time and try to find the biggest radius, as we are doing above. This way we will be able to cover all the cases.

Both, Anil and anonymouS, good one !!!

The code I am pasting below is based on the observation that,

for odd length non concentric palindrome, u only need to check if the palindrome of length 3 extends to 5.

in case of 'layal' - in order to invalidate 'aya' u shud go one more char on either side and establish it is a palindrome. If you cant establish that as a palindrome then u can print out 'aya'

for even length palindromes u only need to look if the palindrome of length 2 extends to 4.

in case of 'anna' - u can discard 'nn' because when u extend it by one more character on either side it will form a palindrome. but in case of 'funny' - when u extend one character on either side of 'nn', it will become 'unny' which is not a palindrome. So u can print out 'nn' as a non-concentric palindrome.

Please let me know if this logic works fine. I have tested it and it seems to be correct. comments are welcome

<pre lang="c++" line="1" title="CodeMonkey787" class="run-this">

#include <iostream>
using namespace std;

void calculateNonConcPalindrome(string& str);
void isPalindrome(string& str, int begin, int size);

int main(int argc, char* argv[]){

cout<<"Calculating non concentric palindromes"<<endl;
string word;
cout<<"Enter word: ";
cin>>word;

calculateNonConcPalindrome(word);
void isPalindrome(string& str, int begin, int size);

return 0;
}

void calculateNonConcPalindrome(string& str){

for(int i=0; i <= str.size()-4; i++){

	//checking for even lengths
	isPalindrome(str, i, 4);
	if(i == str.size()-4)
		return;
		
	isPalindrome(str, i, 5);
}	


}

void isPalindrome(string& str, int begin, int size){

	if((str[begin] == str[begin+size-1]) && (str[begin+1] == str[begin+size-2]))
		return;
		
	if(str[begin+1] == str[begin+size-2]){
		if(size%2 == 0)
		cout<<str[begin+1]<<str[begin+size-2]<<endl;
		
		else
		cout<<str[begin+1]<<str[begin+2]<<str[begin+3]<<endl;
	}
		
		
		
	return;	

}

</pre><pre title="CodeMonkey787" input="yes">
</pre>

Marhaba,

Great piece on Amazon Interview Question for Software Engineer / Developers, I’m a fan of the ‘flowery’ style Looking forward to more long form articles ??

I have AWS ec2 six instance for 3 year subscription and type is c4.xlarge for purpose of web-server. due to high usage of RAM/CPU/IO, we wanted extend capacity means resizes resources for existing c4.xlarge to c42xlarge type. may I know the how much extra cost we need to pay for each instance. if we want resize ec2 instances.

Super likes !!! for this amazing post. I thinks everyone should bookmark this.

Thanks and Regards
Radhey