Microsoft Interview Question
Software Engineer / DevelopersCan you please clarify the question, by giving a generic example.
Is it possible to have character groups of different sizes and if so, how do we identify the groups?
Assuming character groups of size 2.
Assuming string will not begin with '|' as character group in that case is undefined.
Idea is to reverse the string normally once and in the second pass, identify the character groups(of size three) and reverse them alone to restore their original order.
#include<stdio.h>
#include<string.h>
int getLength(char* input)
{
int length = 0;
while(*input)
{
length++;
input++;
}
return length;
}
//Normal string reversal
void reverseStringRegular(char* input, int begin, int end)
{
if(begin >= end) return;
int i = begin, j = end;
while(i <= j)
{
char ch = input[i];
input[i] = input[j];
input[j] = ch;
i++; j--;
}
}
//Find character groups and reverse them again to get original order
void detectGroupsAndReverse(char* input)
{
int i = 0;
while(input[i] != '\0')
{
if(input[i] == '|')
{
reverseStringRegular(input, i-1, i+1);
i = i+2;
continue;
}
i++;
}
}
void reverseStringByGroup(char* input)
{
int stringLength = getLength(input);
if(input[0] == '|' || input[stringLength - 1] == '|')
{
printf("Invalid string. Character Grouping failed\n");
return;
}
reverseStringRegular(input,0, stringLength - 1);
detectGroupsAndReverse(input);
}
int main()
{
char input[] = "dar|dkik i|s n|ice";
printf("Input String: %s\n", input);
reverseStringByGroup(input);
printf("String Reversed: %s\n", input);
}
O(n) solution. Have two pointrs left = 0 and right = length of string. Keep swapping characters till your pointers either meet or cross.
Now traverse from the beginning. If you find "|" at position 'i', interchange 'i-1' and 'i+1'
Possible validations: 1. Your string should not start or end with "|"
2. During second iteration to reorder the special characters, if your re-ordered character at 'i-1' or 'i+1' is also "|", print that the string is not valid and exit
- Anonymous October 06, 2010