Bloomberg LP Interview Question Financial Software Developers
#include <iostream>
#include <string.h>
using namespace std;
int main(){
char a[] = "a cd ef ed ca";
bool palindromeflag = true;
int pivot1=0,pivot2=sizeof(a)-2;
while(pivot1<=pivot2){
if(a[pivot1]!=' ' and a[pivot2]!=' '){
if(a[pivot1]==a[pivot2]){
++pivot1;--pivot2; continue;
}else{
palindromeflag = false;break;
}
}else if(a[pivot1]==' '){
++pivot1; continue;
}else if(a[pivot2]==' '){
--pivot2; continue;
}
}
if(palindromeflag)
cout<<"Palindrome"<<endl;
else
cout<<"Not a palindrome"<<endl;
}
why cant we just push all characters onto a stack except spaces and pop out and check if they are the same characters...
Conceptually, there's nothing wrong doing it using a stack. However, is that the best we can do in terms of time and space? It is clear that in terms of space using stack isn't efficient than blueskin's and chennavarri's solutions, as we will need to construct a stack.
How about computational efficiency? How many comparisons are needed? If you use stack you will need n comparisons, where n is length of the string, as you will be comparing two different strings. On the other hand blueskin's and chennavarri's solutions take n/2 comparisons.
It's now very clear (at least to me) that stack based solution is probably not the most efficient.
given a string, a = "a cd ef ed ca"
pivot1 points to starting of string, pivot2 points to end of string
- chennavarri October 20, 2010while(pivot1<=pivot2) if(a[pivot1]!=' ' and a[pivot2]!=' ') if(a[pivot1]==a[pivot2]) ++pivot1,--pivot2, continue loop else "Not a palindrome", palindromeflag = false, break; else if(a[pivot1]==' ') increment pivot1 and continue loop else if(a[pivot2]==' ') decrement pivot2 and continue loop