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

(Last Updated On: May 18, 2010)
Learn the Secret

Get  our 2 Free Books

Get these now which land directly to their inbox.
Invalid email address

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!
This entry was posted in Quant Development and tagged , , , , on by .

About caustic

Hi i there My name is Bryan Downing. I am part of a company called QuantLabs.Net This is specifically a company with a high profile blog about technology, trading, financial, investment, quant, etc. It posts things on how to do job interviews with large companies like Morgan Stanley, Bloomberg, Citibank, and IBM. It also posts different unique tips and tricks on Java, C++, or C programming. It posts about different techniques in learning about Matlab and building models or strategies. There is a lot here if you are into venturing into the financial world like quant or technical analysis. It also discusses the future generation of trading and programming Specialties: C++, Java, C#, Matlab, quant, models, strategies, technical analysis, linux, windows P.S. I have been known to be the worst typist. Do not be offended by it as I like to bang stuff out and put priorty of what I do over typing. Maybe one day I can get a full time copy editor to help out. Do note I prefer videos as they are much easier to produce so check out my many video at youtube.com/quantlabs