Tag Archives: Palindrome

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!

Is this the toughest C++ interview question? Palindrome with strings

Is this the toughest C++ interview question? Palindrome with strings

This could easily one of the hardest questions you could be asked in an advanced senior level C++ interview. This program has been described as self containing which can find the center of a palindrome and will do it o(n). The algorithm comes from Haskell authored by Johan Jeuring.

#include
#include
#include

// Simple linked list functions
typedef struct Node Node;
struct Node {
int len;
Node* next;
};

Node* insertNode(Node* head, Node* node) {
node->next = head->next;
head->next = node;
return node;
}

Node* createNode(int len) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->len = len;
return newNode;
}

Node* insertNum(Node* head, int len) {
return insertNode(head, createNode(len));
}

void printReverse(Node* node) {
if (node != NULL) {
printReverse(node->next);
printf(“%d “, node->len);
}
}

void printReverseList(Node* head) {
printReverse(head->next);
printf(“\n”);
}

void cleanList(Node* head) {
Node* curr = head;
while (curr != NULL) {
Node* next = curr->next;
free(curr);
curr = next;
}
}

int main(int argc, char* argv[]) {
if (argc < 2) { printf("USAGE: ./pal string\n"); return 0; } char* a = argv[1]; int n = 0; int len = strlen(a); int currTail = 0; // length of the longest tail palindrome Node* centers = createNode(0); centers->next = NULL;
while (n < len) { if (n - currTail != 0 && a[n - currTail - 1] == a[n]) { n++; currTail += 2; continue; } Node* center = centers->next;
insertNum(centers, currTail);
int centerDist = currTail;
while (centerDist != 0 && center != NULL && centerDist – 1 != center->len) {
centerDist–;
insertNum(centers, center->len > centerDist ? centerDist : center->len);
center = center->next;
}
if (centerDist == 0) {
n++;
currTail = 1;
} else {
currTail = center->len;
}
}
Node* center = centers->next;
insertNum(centers, currTail);
while (currTail != 0) {
currTail–;
insertNum(centers, center->len > currTail ? currTail : center->len);
center = center->next;
}
printReverseList(centers);
cleanList(centers);
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!