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<
