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

(Last Updated On: May 18, 2010)

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

typedef struct Node Node;
struct Node {
int len;
Node* next;
};

Node* insertNode(Node* head, Node* node) {
return node;
}

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

Node* insertNum(Node* head, int len) {
}

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

printf(“\n”);
}

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!
Don't miss out!
Get my TRADE LIKE A BOSS 2 PDF Books

Give it a try. You can unsubscribe at any time.

NOTE!

Check NEW site on stock forex and ETF analysis and automation

Scroll to Top