Microsoft Interview Question
Software Engineer in Tests#include <stdio.h>
// Provided destination does not come inbetween start and stop
int CutNPaste(char* str, int start, int stop, int destination)
{
int length = stop - start + 1;
char *temp = new char[length];
for (int i = 0; i < length; ++i)
{
temp[i] = str[start + i];
}
for (int i = 0; i < destination - stop; ++i)
{
str[start + i] = str[stop + i + 1];
}
for (int i = 0; i < length; ++i)
{
str[destination - length + i] = temp[i];
}
}
int main()
{
char *str = "jump the over wall";
CutNPaste(str, 4, 7, 13);
printf("%s", str);
return 0;
}
You are asked to implement the Cut and Paste feature of a text editor.
-Imagine the text is a string say str[] = "abcdefg"
-Cut "cd" from the string and paste it at the str[4]
-Output of this would be "abecdfg"
This means that letters in the array have to be shifted...Array size after cut and paste should be the same.
One solution is to copy the contents to a clipboard, shift the letters accordingly and paste your string at the appropriate location.
But the question was to do this efficiently without making use of a clipboard.
when you say move it to str[4], is that the 4th index before you cut the string or after you cut the string? can you explain your example a little better? Would appreciate that.
int CutNPaste(char* str, int start, int stop, int dest)
{
char temp;
int length = stop - start + 1;
Reverse(str, start, stop);
Reverse(str, stop + 1, dest + length - 1);
for (int i = 0; i < length; ++i)
{
temp = str[start + i];
str[start + i] = str[dest + length - i - 1];
str[dest + length - i - 1] = temp;
}
if (dest > stop)
{
Reverse(str, stop + 1, dest - 1);
}
else
{
CutNPaste(str, stop - (stop - dest), dest - 1, dest + length - (stop - dest));
}
}
@xyz, your algorithm works only if the destination is > stop. Below works in both cases.
void cutnpaste(char *str,int start,int stop, int destination)
{
if (destination < start)
{
min = destination;
mid = start -1;
max = stop;
}
else
{
min = start;
mid = stop;
max = destination;
}
reverse(str,min,mid);
reverse(str,mid+1,max);
reverse(str,min,max);
}
This is the correct code. It takes care of the above cases and if dest >= start and dest <= stop.
If you guys find a mistake please let me know.
void cutnpaste(char * str, int start, int stop, int dest)
{
int min, mid, max;
int length = strlen(str);
if(length <= 1)
return;
if(dest < 0)
dest = 0;
else if(dest > length)
{
dest = length-1;
}
if(dest < start)
{
min = dest;
mid = start-1;
max = stop;
}
else if(dest > stop)
{
min = start;
mid = stop;
max = dest;
}
else // i.e. dest >= start and dest <= stop
{
min = start;
mid = stop;
max = stop + (dest - start);
}
reverse(str, min, mid);
reverse(str, mid+1, max);
reverse(str, min, max);
printf("%s\n", str);
}
void reverse(char *str, int start, int stop)
{
for (int i = start; i < (start + stop + 1) / 2; ++i)
{
char temp = str[i];
str[i] = str[stop - (i - start)];
str[stop - (i - start)] = temp;
}
}
int main()
{
char str[] = "This is a test string";
cutnpaste(str, 10, 13, 13);
return 0;
}
hi paritosh in your code the only case it fails is dest<start. the only problem is that in this case dest is not assumed to be started from 0 index in the resultant string e.g. abcdefg start=4, stop=5 dest=1 then if you assume all index starting from 0 the result should be abefcdg but the result is aefbcdg..while in rest of the two cases the dest is with respect to 0 index only. here is the code with fix.
#include<stdio.h>
#include<string.h>
void rot(char *src, int s, int e)
{
char t;
while(s<=e)
{
t = src[s];
src[s] = src[e];
src[e] = t ;
s++;
e--;
}
return ;
}
char *cNp(char *src, int p, int cs, int ce)
{
char t;
int l = ce-cs +1;
int s, e;
s = cs; e = ce;
rot(src, cs, ce);
// printf("%s\n", src);
if(p<ce)
rot(src, p, ce);
else
rot(src, cs, p-1);
// printf("%s\n", src);
if(p<ce)
rot(src, p+l, ce);
else
rot(src, cs, p-l-1);
printf("%s", src);
return src;
}
void reverse(char *str, int start, int stop)
{
for (int i = start; i < (start + stop + 1) / 2; ++i)
{
char temp = str[i];
str[i] = str[stop - (i - start)];
str[stop - (i - start)] = temp;
}
}
void cutnpaste(char * str, int start, int stop, int dest)
{
int min, mid, max;
int length = strlen(str);
if(length <= 1)
return;
if(dest < 0)
dest = 0;
else if(dest > length)
{
dest = length-1;
}
if(dest < start)
{
min = dest;
mid = start-1;
max = stop;
reverse(str, min, mid);
reverse(str, mid, max);
reverse(str, min, max);
printf("%s\n", str);
return ;
}
else if(dest > stop)
{
min = start;
mid = stop;
max = dest;
}
else // i.e. dest >= start and dest <= stop
{
min = start;
mid = stop;
max = stop + (dest - start);
}
reverse(str, min, mid);
reverse(str, mid+1, max);
reverse(str, min, max);
printf("%s\n", str);
}
int main()
{
char str[] = "abcdefg";
cutnpaste(str, 1, 4, 3);
getchar();
return 0;
}
can you please explain the problem clearly
- nav June 14, 2010