Tag Archives: O[n^2]

Is this the toughest C++ interview question? Palindrome with strings using O[n^2]

Is this the toughest C++ interview question? Palindrome with strings using O[n^2]

This could easily one of the hardest questions you could be asked in an advanced senior level C++ interview. Here are two attempts o[n^2]

#include
using namespace std;

void longestPalindrome(char *str, int n)

{
int i=0;
int j=0;
int start = 0;
int end = 0;
int range = 0;
int maxstart = 0;
int maxend = 0;

while(i < n && j < n) { start = i; end = j; while((str[start] == str[end]) && (start >=0) && (end <= n)) { if((maxend - maxstart) < (end-start)) { maxend = end; maxstart = start; } end++; start--; } start++; end++; } for(int i = maxstart; i <= maxend; i++) printf("%c", str[i]); } int main() { char * str = "RACECAR"; cout << strlen(str);; longestPalindrome(str,sizeof(str)); //also: based on O(n^2) char a[]="abcdaeeadabb"; char *p,*q,*r,*found; int i=0; int max=0; for(p=a;*p!='\0';p++) { q=p; r=a+strlen(a); while(qmax) {max=i; found=p;}
}
if(q==r) max=max+1;
cout<<"max is: " << max<<*found; return 0; }

NOTE I now post my TRADING ALERTS into my personal FACEBOOK ACCOUNT and TWITTER. Don't worry as I don't post stupid cat videos or what I eat!