CareerCup

void RemoveWords(char c)
{
string str = "HELLO WORLD HELLO TO THIS DAY OF THE HAPPY WEEK";
char *s = new char[str.size() + 1];
strcpy(s, str.c_str());

for (int i=0; i<str.size(); i++)
{
if ((i == 0 || s[i-1] == ' ') && s[i] == c)
{
while (s[i] != ' ' && i<str.size())
{
s[i] = ' ';
i++;
}
}
}

int actual_pos=0, new_pos=0;
//for (actual_pos = 0; str[actual_pos] != ' ' && actual_pos < str.size(); actual_pos++);

for (int i=1; i<str.size(); i++)
{
while (s[actual_pos-1] == ' ' && s[actual_pos] == ' ' && actual_pos<str.size())
actual_pos++;

s[new_pos++] = s[actual_pos++];

}

cout << s;

}

Single Pass soln:

void RemoveWordsNoSpace(char c)
{
    int actual_pos=0, new_pos=0;
    string str = "HELLO WORLD HELLO TO THIS DAY OF THE HAPPY WEEK";
    char *s = new char[str.size() + 1];
    strcpy(s, str.c_str());
    
    for (int i=0; i<str.size(); i++)
    {
        if ((i == 0 || s[i-1] == ' ') && s[i] == c)
        {
            while (s[i] != ' ' && i<str.size())
            {
                actual_pos++;
                i++;
            }
            new_pos--;
        }

        s[new_pos++] = s[actual_pos++];
    }
}

I can think of an O(n) solution which makes 2 passes over the list. Did they have any specific requirements ?

Just extract those all strings which is not starting from c.This can be in O(N)

@Balchandra
I proposed them of 2 passes but I eventually gave him one pass solution.

I will paste the code sometime later.

#include<iostream>
#include<string>
using namespace std;

int main()
{
	char inp[100];
	cout<<"Enter the input line = ";
	gets(inp);
	char c = ' ';
	int index = 0;
	cout << "Enter characters to be eliminated = ";
	cin >> c;
	for(int i=0;inp[i];i++)
	{
		if(inp[i] == c)
		{
			while((inp[i] != ' ')&&(inp[i] != '\0'))
			{
				i++;
			}
		i--;	
		}
		else
		{
			inp[index++] = inp[i];
		}
	}
	inp[index] = '\0';
	cout << inp;
	return 0;
}

a python implementation :

>>> def f(str,k):
beg,write=True,True
"""beg indicates whether we have reached the beginning of a new word.
write indicates whether the current character has to be written to
output."""
res=''
"res stores the result"
for c in str:
if beg:
write= not(c=='t')
beg=(c==' ')
if write:
res+=c
return res

>>> f('all the words starting with the letter t will be removed','t')
'all words starting with letter will be removed'
>>>

void RemoveWords(char *str, char c)
{
	int len = str.length;
	int cur = 0;
	int prev = 0;
	while(cur < len)
	{
		if((strArr[cur] != c)
		 || (strArr[cur] == c && cur > 0 && strArr[cur - 1] != ' '))
		{
			if(strArr[cur] != strArr[prev]
			{
				strArr[prev] = strArr[cur];
			}
			cur++; 
			prev++;
		}
		else
		{
			while(strArr[cur] != ' ' && cur < len)
			{
				cur++;
			}
		}		
		
	}
	str[prev] = '\0';

}

hey Aatish were u interviewed in India?Is Microsoft Hiring in India?

ptr=strtok(str," ");
while(ptr!=NULL)
{
if(ptr[0]=='H')
{
ptr=strtok(NULL," ");
continue;
}
cout<<ptr<<endl;
ptr=strtok(NULL," ");

}

Eliminates multiple white spaces between words

void removeWords(char* string, char c){
	if(string == 0)
		return;
	
	int start = 0, current = 0;
	
	while(1){
		int discardToken = (string[current] == c);
		while((string[current] != '\0') && (string[current] != ' ')){
			if(discardToken)
				current++;
			else
				string[start++] = string[current++];
		}
		if((start > 0) & (string[start - 1] != string[current]))
			string[start++] = string[current];
		if(string[current] == '\0')
			return;
		else{
			current++;
		}
	}
}

Flawless code ... Enjoy!!
Time O(n) .... Space O(1)

Below code also takes care of multiple space characters between two words...

void removeWords(char * str, char ch)
{
	if(!str)
		return;
	int i = 0, j = 0;
	while(str[j])
	{
		if(str[j] == ch)
		{
			while(str[j] && str[j] != ' ')
				j++;
			while(str[j] && str[j] == ' ')
				j++;
		}
		else
		{
			while(str[j] && str[j] != ' ')
				str[i++] = str[j++];
			while(str[j] && str[j] == ' ')
				str[i++] = str[j++];
		}
	}
	str[i] = '\0';
}

public class RemoveWordsStartingWithAChar 
{
	/**
	 * @param args
	 */
	static String[] cases = new String[]{"HELLO WORLD HAT", "HE WAS GOING TO THE HUT", "HI!"};
	static char c = 'H';
	
	public static void main(String[] args) 
	{
		for(String case_ : cases)
		{
			System.out.println("Original sentence: "+case_);
			System.out.println("Modified sentence: "+change(case_));
		}

	}
	
	private static String change(String case_)
	{	
		StringBuilder modified_case = new StringBuilder();
		
		boolean addThisWord = true;
		for(int i=0; i<case_.length(); i++)
		{
			if(i==0 || case_.charAt(i-1)==' ')
			{	
				addThisWord = true;
				if(case_.charAt(i)==c)
				{
					addThisWord = false;
				}
			}
			
			if(addThisWord)
				modified_case.append(case_.charAt(i));
			
		}
		return modified_case.toString().trim();
	}

}