Apple Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
This might fail in case, we have two or more spaces lying together, for e.g., in the case of the following string- {'a', ' ', ' ', 'b'}. Instead of
if (*copy_from == ' ')
we should loop around to check if there are even more spaces.
It won't fail if there are multiple spaces. It continues to increment the copy_from pointer for every space it sees.
// Assumes in-place removal of spaces
// Time O(n) - Space O(1)
void removeSpaces(char* s) {
if (!s) {
return;
}
char* nonwhite = s - 1;
char* itr = s;
while (*itr) {
if (*itr != ' ') {
*(++nonwhite) = *itr;
}
++itr;
}
*(++nonwhite) = '\0';
}
It is potentially dangerour to set char* nonwhite = s - 1;
It then points to a position that is practically an illegal address!
I know that because of the prefix increment this addressing won't happen but why are you afread of using postfix increments?
It is not, because the variable "nonwhite" is always pre-incremented before being used. In the local bind of the method, you can set whatever value for the variables. Only accessing the memory at the position (s-1) can be dangerous, but it is never done, since nonwhite is always pre-incremented, and so its first value when used is s.
#include<stdio.h>
#include<conio.h>
int main()
{
char ch[]="ram is a good boy";
int i;
for(i=0;i<20;i++)
{
if(ch[i]==' ')
continue;
else
printf("%c",ch[i]);
}
getch();
return 0;
}
private static void RemoveSpaces()
{
string temp = "nayni sh sdfg j k k";
char[] myArr = temp.ToCharArray();
SpaceCheck(ref myArr, 0, 0);
foreach (char item in myArr)
{
Console.Write(item);
}
}
private static void SpaceCheck(ref char[] myArr, int i, int j)
{
if (i < myArr.Length)
{
if (Char.IsWhiteSpace(myArr[i]))
{
if (!Char.IsWhiteSpace(myArr[j]))
{
j++;
SpaceCheck(ref myArr, i, j);
}
else
{
i++;
SpaceCheck(ref myArr, i, j);
}
}
else if (!Char.IsWhiteSpace(myArr[i]))
{
if (Char.IsWhiteSpace(myArr[j]))
{
char temp;
temp = myArr[i];
myArr[i] = myArr[j];
myArr[j] = temp;
i++; j++;
SpaceCheck(ref myArr, i, j);
}
else
{
j++; i++;
SpaceCheck(ref myArr, i, j);
}
}
}
}
void reverse_String(char *str) {
int len = strlen(str) - 1;
int i = 0, j = 0;
for(i = 0; i < n; i++) {
if(str[i] == ' ' | str[i] == '\t\) {}
else {
str[j] = str[i];
j++;
}
}
str[j] = '\0';
}
void remove_space_from_a_string(char *oldstring, char *newstring)
{
while(*oldstring !='\0')
{ if(*oldstring != ' ')
{ *newstring = *oldstring;
newstring++; oldstring++;
}
else
oldstring++;
}
*newstring = '\0 ';
}
I would like to change the code a little bit to make it better:
void remove_space_from_a_string(char *oldstring)
{
char *newstring;
newstring = oldstring;
while(*oldstring !='\0')
{ if(*oldstring != ' ')
{ *newstring = *oldstring;
newstring++; oldstring++;
}
else
oldstring++;
}
*newstring = '\0 ';
}
The in-place solution has complexity of O(N^2) because you have to move the characters following a space after it's removed. (N characters moved N times).
By copying the string we don't have to move any characters so the solution is O(N). Only one pass is necessary if we can return the copied string, otherwise a second pass is necessary to copy it back to the original. Either way it's still O(N).
No, it is O(n). The movement is done while iterating through the string. If a string has N chars, then the loop will be executed N times, not N*N times.
A python solution:
def removeSpaces(inputString):
length=len(inputString)
numberOfdeletions=0
for i in range(0,length):
if inputString[i-numberOfdeletions]==' ':
print "here"
nwLength=length-numberOfdeletions
inputString=inputString[:i-numberOfdeletions]+inputString[i+1-numberOfdeletions:]
numberOfdeletions+=1
print numberOfdeletions
print inputString
char[] foo(char str[])
{
char* c = str;
while(*c!='\0'){
if(*c == ' '){
*c++='\0';
strcat(str, c);
}
c++;
}
return str;
}
- Martin October 04, 2012