Amazon Interview Question
Software Engineer / Developersin this string "malayalam is funny language"
list of all palindromes are
+ malayalam
+ ala (m_ _ _ y _ _ _ m)
+ alayala
+ layal
+ aya
+ nn
for out of all { malayalam, alayala, layal, aya } share the same center so
only
ala and nn are non cocentric
I think concentric palindromes are palindromes with the same center.
acasdabadso: sdabads and aba are concentric and aca is not concentric with the rest.
even ex: In string "dabacabae", aba aba and abacaba are three non concentric palindromes.
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
Nice solution:
some optimization suggested in your code
int p = i - 1;
int q = i + 1;
replaced by
int p = i - 2;
int q = i + 2;
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.
Hi Ricky, I had this thought in my mind when I was working on it. But the question says "non concentric palindrome" which i guess is palindromes which do not have a common center. So i thought all the palindromes had to b around some or the other center but not same, hence developed only for odd length strings
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
Input: malayalam is funny language
- Anil January 25, 2011Output:
a l a
m a l a y a l a m
a l a
n n