This was the interview question:
How to convert
Dogs like cats
tocats like Dogs
?
My code shows: cats like cats
. Where am I making the mistakes?
#include <iostream>
using namespace std;
int main()
{
char sentence[] = ("dogs like cats");
cout << sentence << endl;
int len = 0;
for (int i = 0; sentence[i] != '\0'; i++)
{
len++;
}
cout << len << endl;
char reverse[len];
int k = 0;
for (int j = len - 1; j >= 0; j--)
{
reverse[k] = sentence[j];
k++;
}
cout << reverse << endl;
int words = 0;
char str[len];
for (int l = 0; reverse[l] != '\0'; l++)
{
if (reverse[l] == ' ' || reverse[l] == '\0') // not sure about this part
{
for (int m = l; m >= 0; m--)
{
str[words] = reverse[m];
words++;
}
}
}
cout << str;
return 0;
}
I know you can do this using pointers, stack, vectors... but interviewer was not interested in that!
Dissecting your algorithm in pieces. First, you find the length of the string, not including the null char terminator. This is correct, though could be simplified.
This could easily be written simply as:
Next, you reverse the entire string, but the first defect surfaces. The VLA (variable length array) you declare here, (which you don't need and shouldn't use, as it is a C++ extension and non-standard) does not account for, nor set, a terminating null-char.
This temporary buffer string is not needed at all. There is no reason you can't do this entire operation in-place. Once we calculate
len
correctly, you simply do something like the following to reverse the entire sequence, which retains the null char terminator in proper position:Next we move to where you try to reverse each internal word. Again, just as before, the buffer length is not correct. It should be
len+1
. Worse (hard to imagine), you never remember where you left off when finding the end point of a word. That location should be the next point you start checking for, and skipping, whitespace. Without retaining that you copy from current point all the way back to the beginning of the string. which essentially blastscats
overdogs
.Once again, this can be done in-place without difficulty at all. One such algorithm looks like this (and notice the loop that reverses the actual word is not-coincidentally the same algorithm as reversing our entire buffer):
Putting It All Together
Though considerably simpler to use pointers than all these index variables, the following will do what you're attempting, in place.
Output
My advise would be to break up the original string into an array of words, reverse that array. Then add those words to your reversed sentence with a space in between.
This is a fixed version of your sample code:
' '
or'\0'
you copy the bytes of the reverse string from the beginning to that point. Example inloop 5
you copy from index 0-5 (stac
) fromreverse
tostr
in reverse order, but in inloop 10
you copy from index 0-10 (stac ekil
) fromreverse
tostr
in reverse order, until here you have already the printed result string ('cats like cats'), and the same inloop 15
all of this incrementing the index ofstr
, in the last loop you are written pass the end of the valid memory ofstr
(and because of that not printed as output).cats like\0dogs
Modified sample code provided:
Some code, written with the restriction of using the most simple features of the language.
Since they asked for no libraries, I assumed no
std::string
, novectors
, nothing at all and so I wrote it in C.. the only thing used isprintf
. Everything else is from scratch :lThe idea is that you reverse the array first. Then split the array by space and reverse each word.
Example: http://ideone.com/io6Bh9
Code:
My solution
}