Microsoft Interview Question
Developer Program EngineersCountry: India
I think this must be used as a screening question
A straightforward solution in C is
char* removeSpaces(char* str)
{
if (str)
{
char* pWrite = str;
for (char* p=str; *p; p++)
if (*p!=' ')
*(pWrite++) = *p;
*pWrite = 0;
}
return str;
}
Note that this can be made a little faster by partially unrolling the loop, skipping over characters before the first space since they don't need to be copied.
Now, if you know a language which has advanced meta-programming, you can follow-up the simple solution above by showing a "lazy evaluation" solution, such as the following code in D. This is O(m) instead of O(n), where m is the number of spaces at the start of the string.
auto removeSpaces(E)(E[] input)
{
struct Result
{
private E[] source = input;
private void skipSpaces()
{
while(!source.empty && source.front==' ')
source.popFront();
}
this() { skipSpaces(); }
@property E front() { return source.front; }
@property bool empty () { return source.empty; }
void popFront()
{
source.popFront();
skipSpaces();
}
};
Result r;
return r;
}
logic correct, but question given than without shifting... otherwise it is very easy question not a MS question
@Anonymous talking about easy/MS: What does the question exactly mean? Care to elaborate?
you are not allowed to shift the characters from one location to another. here if there is space you are shifting the character from i to i-1 location... so total length of the string will be decreased but expected is should be of same length.
What does not shifting even mean? Can I shift from i+100 to i?
Ridiculous question.
A simpler way would be to ask for an O(n) time, in-place algorithm. Which I suspect it was, but OP managed to screw up.
one possible but fullish way is to use linked list instead of char array...... here we can delete the node with whitespace....
not a answer but a possible way :)
class string // Just deleting character
{
public static void main(String[] args)
{
String x="teja is a good boy";
x=x.replaceAll(" ","");
System.out.println(x);
}
}
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
string str = "how are you";
int n = str.Length;
int i=0;
char[] s = str.ToCharArray();
Console.WriteLine("Original string : " + str);
for (i = 0; i < n; i++)
{
if (s[i] == ' ')
s[i] = '\a'; // ascii for bell
}
Console.Write("String w/o space : ");
for (i = 0; i < n; i++)
Console.Write(s[i]);
Console.Read();
}
}
}
char s[] = "how are you";
int n = strlen(s);
int i=0;
while(s[i] != '\0')
{
if(s[i] == ' ')
s[i] = 7; // ascii for bell
i++;
}
cout << s << endl;
instead of 7 you can use character "audible" i.e..'\a'...
when display receives this character it will not get printed
s[i] = '\a'; // ascii for audible
How about we fill the white spaces with null character('\0') and concatenate the sub strings.. plzz comment
concatenation of 2 strings requires O(m+n) extra space. so this approach is not inplace.
No we are not using extra space. we are splitting the string into substrings and concatenating at the same time.
- Kevin March 07, 2013