C++ interview questions on strings with string reversal and tough manipulation

Dseadlock

what is deadlock? how to detect if a deadlock has occurred and how to troubleshoot?

String:

Difference between C-strings and string class in C++.

C++ strings are less efficient, but they have more encapsulated functionality. C strings are manipulated by standard functions while C++ string is object-oriented and string is a class. C string is simply an array of characters.

C++ string is a class n hence ny declaration such as string str is declaration of an object str of string class. Thus in built methods add functionality. on the other hand C strings are mere char pointers.

agreed! both answers are correct…good …

string class is a wrapper over c Strings(char arrays)

Given char* func1(char* target, char* substring,char* replacement)

write a c++ code to find the substring in the target and replace the whole substring with the replacement. (hint: replacement can be larger or smaller than the substring.)consider all possible test cases and check.

1) find the starting index of substring

a) can be done by KMP in O(n)

b) brute force O(n*m)

2) replacing

a) if the word to be replaced is larger– then first replace the characters till the length of substring..then use shifting so–> O((l1-l2)*n)

b) if the word to be replaced is small

then just replace snd shift

Can we use extra array for dealing this question?

I think we can just assume the target array have enough memory after ‘\0’

because every replace string work like that or make error

kmp= KMP.c: Implements strstr library function using the Knuth-Morris-Pratt

substring search algorithm.

I made some but it is not KMP or something efficient algorithm but it is easy to write front of interviewer.

int main(int argc, char *argv[])

{

int idx = 0;

char target[100];

char *pTag = target;

char sub[10];

char replace[100];

char *pRpr = replace;

if(argc != 4)

{

cout << "Exit... Bye Bye\n";
exit(1);
}
strcpy(target, argv[1]);
strcpy(sub,argv[2]);
strcpy(replace,argv[3]);
//Loop until target 0
char * pTg, * pSb, *pRp;
pRp = replace;
while(pTag != '\0')
{
pTg = pTag;
pSb = sub;
while(*pSb != '\0' && *pTg != '\0' && *pTg++ == *pSb++);
if(*pSb == '\0' && *(pTg -1) == *(pSb -1))
{
while(*pRp != '\0')pRp++;
while((*pRp++ = *pTg++) != '\0');
while((*pTag++ = *pRpr++) != '\0');
cout << target << "\n";
return 0;
}
pTag++;
}
}
#include

using namespace std;

void replace(char *target, char *substring, char *replace);

int main()

{

char target[100] = “MyNameIsGajanan”;

char *substring = “Gajan”, *rep = “AAA”;

//cout << target <

j = i-> n

k = j -> n

Cheema on December 26, 2009 |Edit | Edit

Oops! I meant O(n^2)

Loop structure will just be nested loops

i = 0 -> n

j = i-> n

Reply to Comment

particularraj on November 12, 2009 |Edit | Edit

My cents:

Building suffix trees is not a bad idea. We can get that in O(nlogn) time.

Reply to Comment

Vishal on November 15, 2009 |Edit | Edit

Take a string

1. Reverse the string

2. XOR with the Original String

3. Find the longest sequence of 0s in the XORed result which will be the corresponding answer

Hi Vishal,

You solution will not work always… You can try it on RACECAR……..

reverse of RACECAR is RACECAR only …. so xoring dem wud giv 0000000 …. which is the longest palindrome … i think vishal’s solution will work for all cases …

Anonymous on November 28, 2009 |Edit | Edit

reverse of RACECAR is RACECAR only …. so xoring dem wud giv 0000000 …. which is the longest palindrome … i think vishal’s solution will work for all cases …

whoami on December 14, 2009 |Edit | Edit

that is an awesome approach.. guess it will work for all cases…

small patch: if XORing is tough for charecters while coding… we can just subtract both the strings charecter by charecter… and then count the max no of consecutive zeros….

Anonymous on January 05, 2010 |Edit | Edit

This won’t work for HTTKNOM

fgh on January 05, 2010 |Edit | Edit

this won’t work for HTTKNOM

Anonymous on January 07, 2010 |Edit | Edit

Stupid solution.

APQP

PQPA

XOR, none are zeroes, but PQP is the longest palindrome.

Reply to Comment

parry on November 15, 2009 |Edit | Edit

start with the first character. try to lookup the same character from the bak. on finding the same character from the back check if the substring is palindrome or not. keep on finding the same character until u reach the index of the first character.

keep on doing the same for all the characters. ….O(n^2)

Anonymous on November 16, 2009 |Edit | Edit

If i’m not mistaken would’nt this be O(n^3)

Reply to Comment

Anonymous on November 16, 2009 |Edit | Edit

Just reverse the string and find the largest substring in both the strings. O(n^2).

Reply to Comment

trey on November 16, 2009 |Edit | Edit

finding the longest substring of the string and it’s reverse won’t work. Consider

abcdefgHELLOWORLDgfedcba The longest palindrome is actually LL, that method would return abcdefggfedcba

Dan on December 15, 2009 |Edit | Edit

the longest palindrome is infact OWO !!

Reply to Comment

gagdeep on November 17, 2009 |Edit | Edit

Keep a current pointer on the second element a(1). place two other pointers at current-1 and current+1. check if curr-1 and curr+1 are equal. then move current pointer ahead. again set curr-1 and curr1 and check for:

If curr is at ith position:

while(i>0)

{

if (curr-1 == curr+1)

{

(curr+1)++;

(curr-1)–;

i–;

}

else break;

}

keep tack of the largest one by storing the value of current for which the length of palindrome was max. also keep track of it’s length for each i. Then u can print the longest palindrome.

gagdeep on November 17, 2009 |Edit | Edit

It’s complexity will be O(n). I have a working code for this. if anybody want.

Anonymous on November 17, 2009 |Edit | Edit

test case: abcddcbe

does it work?

gagdeep on November 17, 2009 |Edit | Edit

No, It doesnot… because i assumed that palindrome will be of odd length…

For this case… place a current ptr and move the curr+ ptr till it goes to the value which is not equal to the current ptr. and then follow the steps above.

Reply to Comment

bala on November 20, 2009 |Edit | Edit

@gagdeep what does the ‘i’ signify ??

Reply to Comment

nalin on November 20, 2009 |Edit | Edit

Can you show the working code by which you arrived O(n)

Reply to Comment

kunalgaind on November 20, 2009 |Edit | Edit

I think we cannot solve this question in less than O(n^3) complexity……..as ideally there are n*n different string that can be created using a string of length n……For example there are 1 string of length n that can be formed from given string and there are 2 string of length n-1 that can be formed using a string of lenght n-1 and there are n string of length 1.

So if you sum it all, there are 1+2+ ……..+ n-1 + n strings = O(n*n)……..

We know how to check for one string in O(n) time, so I think we can just repeat the loop by checking string of length n to 1 and stop whenever we find any palindrome…..

Seriously, I don’t think we can solve this question in less than this time, because we have to check for string of each length and in worst case there might not be any palindrome in string and so we might end up with generating palindrome on length 1 i.e . character itself, if you consider that to be a palindrome…..

Please share your thoughts, I would be happy to hear from anyone….who can help me in improve on this solution………..

Reply to Comment

Thiyanesh on November 20, 2009 |Edit | Edit

maxindex = 1;

maxlen = 1;

for(index = 1 to str.length) {

for(cur = 1 to min(index, abs(str.length – index))) {

if(str[index + cur] == str[index – cur]) {

if(cur < maxlen) continue;
maxlen = cur;
maxindex = index;
}
}
}
May fail for the boundary conditions. But this the logic which i can think of for O(n2) complexity.
We need two such code blocks one for even length and one for the odd length.
Hence the time complexity is O(n2). O(1) space complexity
Reply to Comment
kunalgaind on November 20, 2009 |Edit | Edit
I am not sure about suffix tree, as I have not read those yet, but I don't think we can solve this question iteratively in less than O(n^3) and I don't think dynamic programming will work too as we cannot use the result that I got in previous iteration because if I have two strings that are palindrome then I cannot say that if I merge both string then those will be palindrome also...
Here is my solution using O(n^3) complexity.
There are n*n different string that can be created using a string of length n......For example there are 1 string of length n that can be formed from given string and there are 2 string of length n-1 that can be formed using a string of lenght n-1 and there are n string of length 1.
So if you sum it all, there are 1+2+ ........+ n-1 + n strings = O(n*n)........
We know how to check for one string in O(n) time, so I think we can just repeat the loop by checking string of length n to 1 and stop whenever we find any palindrome.....
Seriously, I don't think we can solve this question in less than this time, because we have to check for string of each length and in worst case there might not be any palindrome in string and so we might end up with generating palindrome on length 1 i.e . character itself, if you consider that to be a palindrome.....
Please share your thoughts, I would be happy to hear from anyone....who can help me in improve on this solution...........
Reply to Comment
kcoder on November 21, 2009 |Edit | Edit
A working solution. O(n*n*n) complexity but good for an interview.
bool ispalindrome (const char * start, const char * end)
{
while (start < end)
{
if (*start != *end)
{
return false;
}
start++;
end--;
}
return true;
}
char * longestPalindrome(const char * str_p)
{
int len = strlen (str_p);
const char * startOfPal = 0; // start of palindrome.
const char * endOfPal = 0; // end of palindrome.
int maxLenOfPal = 0; // len of palindrome.
for (int i = 0; i < len; i++)
{
for (int j = len-1; j > i; j–)

{

const char * start = str_p + i;

const char * end = str_p + j;

if (ispalindrome(start, end))

{

if ((end – start + 1) > maxLenOfPal)

{

startOfPal = start;

endOfPal = end;

maxLenOfPal = end – start + 1;

}

}

}

}

Reply to Comment

Anonymous on November 21, 2009 |Edit | Edit

Not sure what happened to the white space.

Here is a quick test I used.

const char * str = “testanaradaring”;

char * x = longestPalindrome(str);

if (x)

{

cout << x << endl;
}
else
{
cout << "No palindrome found." << endl;
}
Anonymous on November 23, 2009 |Edit | Edit
the simplest way is O(N^2)
if applying suffix tree time can be reduced to O(NlogN)
asuran on November 23, 2009 |Edit | Edit
the simplest way is O(N^2)
if applying suffix tree time can be reduced to O(NlogN)
Reply to Comment
bewnet on November 22, 2009 |Edit | Edit
How about this way:
1. define stringbulder variable called sb and an int called numberOfChars and max
2. for each character in the string
3. add the character to sb, and set numberOfChars to 1.
4. for each remaining character in the string
5. append the character to sb and increment numberOfChars by 1.
6. if the character is the same as the character read in step 2, then what we have in sb is a potential palindrom so, call a helper funtion called IsPalindrome with the value in sb as an argument.
7. If step 6 returns true, then add the content of sb to a dictionary with sb as a key and numberOfChars as a value---you can have duplicate checks
8. inner loop ends here
9. if numberOfChars > max then reset max to numberOfChars and clear sb

9. loop to the first loop.

10. Now, all possible palindrome strings are in your dictionary. Return a key with value equal to max.

Note that:

The algorithm generates all possible palindroms but, i think there might be a better way of doing it.

Reply to Comment

anon on November 25, 2009 |Edit | Edit

Longest thread of answers to Longest palindrome finding ๐

Reply to Comment

SK on December 23, 2009 |Edit | Edit

could not post the link. google for this. the first link has a good solution

finding-the-longest-palindromic-substring-in-linear-time.

Reply to Comment

Anonymous on January 07, 2010 |Edit | Edit

It’s awesome to see people using suffix tree and O(nlogn) at the same time !!

Anonymous on January 07, 2010 |Edit | Edit

And why not?

There are simpler implementations of suffix tree which are O(nlogn).

Because implementing suffix tree can be so complex, ppl might choose to lose some run time over the possible maintenance headaches.

Reply to Comment

c on February 03, 2010 |Edit | Edit

My suggestion is that any approach of O(n^2) time and O(1) space that can be well explained and you can write working code during an interview would suffice!

Reply to Comment

Ryan on February 25, 2010 |Edit | Edit

This self-contained C program will print out all of the palindrome lengths for all possible centers, and it will do it in O(n) time. It is a port of the algorithm in Haskell authored by Johan Jeuring here: johanjeuring.blogspot.com/2007/08/finding-palindromes.html

#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;

}

Reply to Comment

Anonymous on March 08, 2010 |Edit | Edit

Reverse the string and find biggest substring.

hary on March 08, 2010 |Edit | Edit

Precisely. One moethod is what anonymous quoted. reverse and find the longest common substring. O(n2) method.

Second could be for every possible position in the string find the palindrome and keep track of the max found so far. One also has to take care of odd length and even length strings.

AGain O(n2) method.

Reply to Comment

Anonymous on March 08, 2010 |Edit | Edit

No need for such complex algorithms !!!

I was asked this question, I proposed trying all combination (O(n^2) I think) he looked convinced with that approach.

Reply to Comment

Tarun Phaugat on March 09, 2010 |Edit | Edit

Example:

================

Str1=abcbabcmoms

Str2=abcba

ALGO:

================

1.a take A[i]==A[j] , decrement J– till i

if A[i]==A[j]

take paldromeindex=i

and increment i and decrement j till i=j

RANGE[k]=J-I

1.b sort range and return the longest one

CODE:

================

private string LongestPalindrom(Str S1,int size)

{

int maxrange =0;

For(int i=0;i

{

char ch2=s1[j];

IF(CH1==CH2 && i!=j)

{

int range= j-i;

i++;

ch1=s1[i];

}

}

IF(MAXRANGE

tempRange = j – *begin;

if(str[pali] == str[j]){

pali++;

}else{

tempRange = 0;

if(pali != *begin){

break;

}

}

}

if(*range < tempRange){
*range = tempRange;
}
}
}
Reply to Comment
O(n^2) on April 11, 2010 |Edit | Edit
int main()
{
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(q

}

if(q==r) max=max+1;

std::cout<**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!