Tag Archives: toughest

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!