Google Interview Question for Software Engineer / Developers


Country: Switzerland
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
9
of 11 vote

It can be solved using two pointers thats it :-)

void replace(char *str)
{
    int i=0;
    char *q=str;
    while(*q)
    {
        if(*q=='b')
        q++;
        else
        {
            if(*q=='c'&&(str[i-1]=='a'&&i>0))
            {
                q++;
                i--;
            }

            else
            {
                str[i]=*q;
                q++;
                i++;

            }
        }
    }
    str[i]='\0';
}

- Arunkumar Somalinga May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that's good

- Bright May 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great

- Abhishek S May 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This seems to be fine for this specific problem, but we can't extend this solution to a generic solution using current approach.

- mYth June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

This has a trivial bug. Try input: 'c'. It will try to reference str[-1].

- Shyam Santhanam June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Change if condition
"if(*q=='c'&&(str[i-1]=='a'&&i>0))" to if(*q=='c'&&(i>0 && str[i-1]=='a'))"

- skum July 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
7
of 15 vote

we need delete the chars and move the remaining chars in the same iteration

int eliminate( char* p)
{
    int deleted = 0;
    if (  ! p )
        return deleted;
    while (*p)
    {
	if ( *p == 'b' )
		deleted++;
	else if ( ( *p == 'a' ) && ( *(p+1) == 'c'))
	{
		deleted += 2;
		p++;
	} else if ( deleted > 0 )
		*(p-deleted) = *p;
	p++;
    }
    return deleted;
}

- testjay May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 votes

before return deleted, we should also add:

if ( deleted > 0 )
	*(p-deleted+1) = '\0';

- testjay May 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Will it work with "aaaccc" sequence

- jguest May 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@testjay: could you plz explain how will it work with abc.

- anonymous May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please ignore my previous comment...had misunderstood the question

- anonymous May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not working for many strings such as abac, adb, etc.

- Abhishek S May 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check my solution... working perfect with all inputs.

public class removeacAndb {
public static void main(String[] args) {
int k = 0;
int i = 0;
String s = "acbadc";
char[] a = s.toCharArray();

while (i < a.length) {
if (!(a[i] == 'a' && ((a[i + 1] == 'c') && i + 1 < a.length))) {
if (a[i] != 'b') {
a[k] = a[i];
k++;
}
} else
i++;
i++;
}
int p = 0;
while (k > p) {
System.out.print(a[p]);
p++;
}
}
}

- champ June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Potential bug in the program. program will crash for input "a" because of ( *(p+1) == 'c').

- Vin June 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wrote this python version of your code.

def eliminate(word):
    #convert the string to list
    str = []
    for ch in word:
        str.append(ch)
    i = 0
    pos_to_replace = -1
    while i < len(str):
        if str[i] == 'b':
            pos_to_replace = i
        elif str[i] == 'a':
            if (i < len(str) - 1) and str[i+1] == 'c':
                pos_to_replace = i
                i = i+2
                continue
        elif pos_to_replace >= 0:
            str[pos_to_replace] = str[i]
            pos_to_replace = pos_to_replace + 1
        i = i+1        
    if pos_to_replace >= 0:
        return ''.join(c for c in str[:pos_to_replace])  #back to string
    else:
        return ''.join(c for c in str) #back to string

- BP January 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

Logic is simple:
Take 2 pointers which initially points to the start of the array. Here first one represents the end of string without 'b' and 'ac' and first represents the current scan position.
scan the array from the start to end
if the current characters is 'b' or 'ac', increment only second pointer appropriately
if the current characters is not 'b' and 'ac', swap characters pointed by two pointers and then increment both pointers.
result will be the string from the start of the array to the location pointed by first pointer.

void removeBandAC(char *p, int size)
{
	int i = 0;
	int j = 0;

	while( i < size )
	{
		if (p[i] == 'b')
		{
			i++;
		}
		else if ((p[i] == 'a') &&  (i+1 < size) && (p[i+1] == 'c'))
		{
			i += 2;
		}
		else
		{
			if (i != J) swap(p[i], p[j]);
			i++;
			j++;
		}
	}

	p[j] = '\0';
}

- Vin May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you have to replace them in-place with what? I think this too straight forward or am i missing something?

i=0;
start iteration;
if char[i] ='a' Flag=1;
if char[i]='b' remove char[i]; reset Flag=0;
if char[i]='c' and Flag=1; remove char[i] and char[i-1]; reset flag;
if char[i] is any other letter; reset flag;
i++;

- Prithvi May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Input : x a b c y

Start iteration :
for 'x' : flag = 0
for 'a' : flag = 1
for 'b' : remove b and set flag = 0
for 'c' : nothing since flag is 0
for 'x' : nothing since flag is 0

Your output : xacy
Desired Output : xy

- nick May 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the example in the question says abc-> ac NOT an empty array.
for your input "x a b c y" the desired result would be "x a c y"

- Prithvi May 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ElliminateChars {
	public static void main(String[] args) {
		char[] ch = "abcacd".toCharArray();
		int opArrayIndex, ipArrayIndex;
		for (opArrayIndex = 0, ipArrayIndex = 0; ipArrayIndex < ch.length;) {
			if (ch[ipArrayIndex] == 'b') {
				ipArrayIndex++;
			} else if (ch[ipArrayIndex] == 'a' && ch[ipArrayIndex + 1] == 'c') {
				ipArrayIndex += 2;
			}
			ch[opArrayIndex] = ch[ipArrayIndex];
			opArrayIndex++;
			ipArrayIndex++;
		}
		for (; opArrayIndex < ch.length; opArrayIndex++) {
			ch[opArrayIndex] = ' ';
		}

		for (opArrayIndex = 0; opArrayIndex < ch.length; opArrayIndex++) {
			System.out.print(ch[opArrayIndex]);
		}

	}
}

- manish May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

static void Eliminate(char[] s)
        {
            int index = 0;

            for (int i = 0; i < s.Length; i++)
            {
                char c = s[i];

                if (c == 'b')
                    continue;
                else if (c == 'a' && i + 1 < s.Length && s[i + 1] == 'c')
                {
                    i++; continue;
                }

                if (index != i)
                    s[index] = c;

                index++;
            }

            if (index < s.Length)
            {
                //compact array
                for (int i = index; i < s.Length; i++)
                    s[i] = '\0';
            }
        }

- Alex May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void remove_ac_or_b(char* str)
{
	unsigned int len = strlen(str);
	int curr_pos_to_fill = 0;		/* index of char to fill */
	int curr_pos_to_check = 0;		/* index of char to check */

	printf("input: (%s)\n",str);
	while (curr_pos_to_check < len)
	{
		/* if we reached "ac", go 2 chars ahead */
		if ((curr_pos_to_check < (len - 1)) &&
			(str[curr_pos_to_check] == 'a' && str[curr_pos_to_check+1] == 'c'))
		{
			curr_pos_to_check += 2;
			continue;
		}
		/* if we reached "b", go 1 char ahead */
		if (str[curr_pos_to_check] == 'b')
		{
			curr_pos_to_check++;
			continue;
		}
		/*
			we didn't reach any special char, just fill current fill location with current check location
			and then increase them both
		*/
		str[curr_pos_to_fill] = str[curr_pos_to_check];
		curr_pos_to_fill++;
		curr_pos_to_check++;
	}
	/* null terimiate the string */
	str[curr_pos_to_fill] = '\0';
	printf("result: (%s)\n",str);
}

- RD83 May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static string ReplaceString(char[] toreplace)
{
int totalIndex = toreplace.Count();
int writeIndex = 1;
if (toreplace[0] == 'b')
{
writeIndex = 0;
}

for (int i = 1; i < totalIndex; ++i)
{
if (toreplace[i] == 'b')
{
continue;
}

if (toreplace[i] == 'c')
{
if (toreplace[writeIndex - 1] == 'a')
{
writeIndex--;
continue;
}
}

toreplace[writeIndex] = toreplace[i];
writeIndex++;
}

return new string(toreplace, 0, writeIndex);
}

- jguest May 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic:
-Traverse array
-check each char for 'a' or 'b'
-in case found 'b' delete it and continue traversing
-in case found 'a' check for next char
-in case after 'a' next char is not 'b' continue
-in case after 'a' next char is 'b' check for this 'b' next char
-in case after 'a' next char is 'b' and 'b's next char is not 'c' then delete 'b' and continue traversing
- in case after 'a' next char is 'b' and 'b's next char is 'c' then delete 'abc' and continue traversing

conclusion:
search for occurrence of 'a' or 'b' in case 'b' comes first delete it or check whether 'abc' pattern is there.... if yes.... delete it.

- PKT May 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Doubt:
if input is "abcd"
then the output should "d" or "acd"

- vinit May 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

as mentioned in qus:

Examples:
abc -> ac
ac->''
react->rt

it seems for i/p 'abcd' should be 'd'.... not sure...
Question filler [jeso]'s input required...

- PKT May 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have similar doubt ...

- srigurubelli May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

really?? with abc -> ac already given to you??

obviously, abcd -> acd holds true in current context.

- ankit.batra11 May 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my efforts for to solve this problem.

void foo(char a[], int n) {

	int k = 0;
	for (int i=0; i<n; ++i) {  

		if (a[i] != 'b') {

			if (a[i] != 'a') { 
				a[k++] = a[i];
			}
			else if ((i + 1) < n && a[i+1] == 'c') {
				i += 1;
			}
			else { 
				a[k++] = a[i];
			}
		}
	}

	if (k < n)
		a[k] = '\0';

}

- Laiq Ahmed May 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String removeBAndAC(String s) {
    Stack<Integer> stack = new Stack<Integer>();
    StringBuffer newString = new StringBuffer();
    
    for (int i = 0; i < s.length(); i++) {
      char currentChar = s.charAt(i);
      switch (currentChar) {
        case 'a':
          stack.push(i);
          break;
        case 'b':
          break;
        case 'c':
          if (!(stack.isEmpty())) {
            stack.pop();
          }
          else {
            newString.append(currentChar);
          }
          break;
        default:
          if (!(stack.isEmpty())) {
            stack.pop();
            newString.append('a');
          }
          newString.append(currentChar);
          break;
      }
    }
    
    while (!(stack.isEmpty())) {
      stack.pop();
      newString.append('a');
    }
    return newString.toString();
    
  } // End of removeBAndAC()

- jbai_98@yahoo.com May 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

As you are using stack this is not inplace.. Space complexity O(n)

- Abhishek S May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

in Scala solution is simple 4-liner:

def eliminate(s: String) : String = {

    def eliminateImpl(s: List[Char]): List[Char] = s match {
      case Nil => Nil
      case 'a'::'c'::cs => eliminateImpl(cs)
      case 'b'::cs => eliminateImpl(cs)
      case h::tail => h::eliminateImpl(tail)
    }

    eliminateImpl(s.toList).mkString

}

- Anonymous May 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static char[] eliminateChar(char[] input) {
        int len = input.length, i=0;
        for(i=0; i<len; i++) {
            if(input[i] == 'b'){
                input[i] = ' ';
            } 
            else if(input[i] == 'a' && i+1 < len && input[i+1] == 'c') {
                    input[i] = input [i+1] = ' ';
                }
        }
        return input;
    }

- King007 May 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't it be a while(input[i] == 'b') and then increment i inside?

- trav August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

char *str = "aaabbcccbaxc";
std::vector<char> myVector;

for (int i = 0; i < strlen(str); i++)
{
if(str[i] == 'c')
{
if(!myVector.empty())
{
if(myVector.back() == 'a')
myVector.pop_back();
else
myVector.push_back(str[i]);
}
}
else if(str[i] != 'b')
myVector.push_back(str[i]);
}

int i;
char *str2 = new char[myVector.size() + 1];
for ( i = 0; i<myVector.size(); i++)
str2[i] = myVector[i];
str2[i] = '\0';

- Anonymous May 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static void Eliminate (String[] strIn){
		
		List<String> list = new ArrayList<String>(Arrays.asList(strIn));
		
		for (int i = 0; i < list.size(); i++) {
			if (list.get(i).equals("b")){
					list.remove(i);
					i--;
			} else if ((list.get(i).equals("a")) && (i+1) < list.size())
			{
				if ((list.get(i+1).equals("c"))) {
					list.remove(i+1);
					list.remove(i);
					i--;
				}
			}
		}
	System.out.println(list);

}

- Memabo May 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this code should solve this problem..

public static String eliminate(String data){
char[] strArr = data.toCharArray();
int len = strArr.length;
int i = 0 ;
while(len>0){
if(strArr[i]=='b')
strArr[i]= ' ';
if( i<data.length() && strArr[i]== 'a' && strArr[i+1]=='c')
strArr[i] = strArr[i+1] = ' ';
i++;
len--;
}

return new String(strArr);
}

- Rahul Khanna May 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pure c style

void removeBAndAC(char * str)
{
	int size = strlen(str);
	int cur =0;  // always wait for available content to copy over;
	int rear =0;
	while(rear < size)
	{
		if( !(str[rear] == 'b') && !(rear!= size-1&&str[rear]=='a'&&str[rear]=='c') )
		{
			str[cur] = str[rear];
			cur++;
		}
		else if( rear != size -1 && str[rear] =='a' && str[rear+1] == 'c' )
		{
			rear++;
		}
		rear++;
	}
	
	str[cur] = '\0';  // ends at here since no more content to be copied over;

}

- James May 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is my solution:

void remove( char s[] ) {
	int c = 0;
	for (int i = 0; s[i]; i++) {
		if(s[i] == 'b')
			c++;
		else if (s[i] == 'c' && i > 0 && s[i-1]  == 'a') 
			c+=2;
		else
			s[i - c] = s[i];	
	}	
}

- thiago.xth1 May 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static char[] replace_b_ac(char[] array) {

        int j = 0;
        for (int i = 0; i < array.length; i++) {

            if (array[i] != 'b') {

                if (array[i] == 'c' && j > 0 && array[j - 1] == 'a') {
                    j--;
                } else {
                    array[j] = array[i];
                    j++;
                }
            }

        }

        for (int k = j; k < array.length; k++) array[k] = '\0';
        return array;
    }

- chris May 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void 
eliminate (char *s)
{
        int move = 0;
        while (*s != '\0') {
                if (move) {
                        if ((*s != 'b') && !(*s == 'a' && *(s+1) == 'c')) {
                                *(s-move) = *s;
                        }
                }
                if (*s == 'b') {
                        move++;
                }
                if (*s == 'a' && *(s+1) == 'c') {
                        s++;
                        move=move+2;
                }
                s++;
        }
        *(s-move)='\0';
        return;
}

- varun.bhadauria May 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be achieved in O(n)

private String remove(String s) {
StringBuilder temp = new StringBuilder();
int len = s.length();

for(int i=0;i<len;i++) {
if((s.charAt(i) != 'b') && (s.charAt(i) != 'a')) {
temp.append(s.charAt(i));
}

if(s.charAt(i) == 'a') {
if(s.charAt(i+1) == 'c') {
i++;
} else {
temp.append(s.charAt(i));
}
}
}

return temp.toString();
}

- dhaval0129 May 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.

Examples:
abc -> ac
ac->''
react->rt*/

#include<stdio.h>
int move=0;

int checkOut(int aPt,char *str)
{
int i,x=0,j;
for(i=aPt+1;i<strlen(str);i++)
{
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
printf("%d %s\n",aPt,str);
if(str[j+1]=='c')
{
move+=2+x;
str[j-x]=str[j+2];
}
return i;
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
return i;
}
else
return i;
}
}

int main()
{
char str[50];
int i,j,x=0;
scanf("%s",str);
for(i=0;i<strlen(str);i++)
{
printf("%d %d %s\n",i,move,str);
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
if(str[j+1]=='c')
{
move+=2+x;
if(j+2!=strlen(str))
str[j-x]=str[j+2];
}
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
}
else
str[i-move]=str[i];
}
str[strlen(str)-move]='\0';
printf("%d %s\n",move,str);
}

- bhupesh May 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.

Examples:
abc -> ac
ac->''
react->rt*/

#include<stdio.h>
int move=0;

int checkOut(int aPt,char *str)
{
int i,x=0,j;
for(i=aPt+1;i<strlen(str);i++)
{
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
printf("%d %s\n",aPt,str);
if(str[j+1]=='c')
{
move+=2+x;
str[j-x]=str[j+2];
}
return i;
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
return i;
}
else
return i;
}
}

int main()
{
char str[50];
int i,j,x=0;
scanf("%s",str);
for(i=0;i<strlen(str);i++)
{
printf("%d %d %s\n",i,move,str);
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
if(str[j+1]=='c')
{
move+=2+x;
if(j+2!=strlen(str))
str[j-x]=str[j+2];
}
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
}
else
str[i-move]=str[i];
}
str[strlen(str)-move]='\0';
printf("%d %s\n",move,str);
}

- Anonymous May 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
{
int i,j;

}

- nnhj May 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
	int main()
	{
		int i,j;
		for(i=0;i<10;i++)
		{
			printf("%d\n",i);
		}
	}

- Anonymous May 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.

Examples:
abc -> ac
ac->''
react->rt*/

#include<stdio.h>
int move=0;

int checkOut(int aPt,char *str)
{
    int i,x=0,j;
    for(i=aPt+1;i<strlen(str);i++)
    {
        if(str[i]=='b')
            x++;
        else if(str[i]=='a')
        {
            j=i;
            i=checkOut(i,str);
            printf("%d %s\n",aPt,str);
            if(str[j+1]=='c')
            {
                move+=2+x;
                str[j-x]=str[j+2];
            }
            return i;
        }
        else if(str[i]=='c')
        {
            str[i-x]='c';
            move+=x;
            return i;
        }
        else
            return i;
    }
}

int main()
{
    char str[50];
    int i,j,x=0;
    scanf("%s",str);
    for(i=0;i<strlen(str);i++)
    {
        printf("%d %d %s\n",i,move,str);
        if(str[i]=='b')
            x++;
        else if(str[i]=='a')
        {
            j=i;
            i=checkOut(i,str);
            if(str[j+1]=='c')
            {
                move+=2+x;
                if(j+2!=strlen(str))
                    str[j-x]=str[j+2];
            }
        }
        else if(str[i]=='c')
        {
            str[i-x]='c';
            move+=x;
        }
        else
            str[i-move]=str[i];
    }
    str[strlen(str)-move]='\0';
    printf("%d %s\n",move,str);
}

- bhupesh kumar May 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void eliminate(char *p){
     char *q=p;
     while(*p){
               while((*p=='b') || (*p=='a' && *(p+1)=='c')){
                               if(*p=='b')
                                          p++;
                               else
                                          p+=2;
               }
               *q=*p;
               q++;
               p++;
     }     
     *q='\0';
}

- priyanka.keshari104 May 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {

char []arr = {'r','b','x','y','c','c','c'};
int j=-1;
for(int i=0;i<arr.length;i++){
if(arr[i]=='b'){
// arr[j]=arr[i+1];
continue;
}
if(arr[i]=='c' && arr[j]=='a'){
j-=1;
continue;
}
j+=1;
arr[j]=arr[i];
}
System.out.println("Final length is:"+(j+1));
for(int i=0;i<=j;i++){
System.out.print(arr[i]+",");
}
}

- Coder May 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This should work fine ...

void filter(char *str)
{

        int j = 0;
        int remove=0;

        if ( !str )
                return;

        for (j =0 ; str[j] != '\0'; j++)
        {
                if(str[j] == 'b' )
                        remove++;
                else if ( str[j] == 'a' && str[j+1] == 'c')
                {
                        remove+=2;
                        j++;
                 }
                else
                        str[j-remove] = str[j];

        }
        str[j - remove] = '\0';
}

- Abhishek S May 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
i=0
c=0

while i <array.len
if a[i]=b then i++
elseif a[i]=a and i+1<array.len and a[i+1]=c and then i=i+2
else {
a[c]=a[i]
c++
}

}

- andreas June 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class removeacAndb {
	public static void main(String[] args) {
		int k = 0;
		int i = 0;
		String s = "acbadc";
		char[] a = s.toCharArray();

		while (i < a.length) {
			if (!(a[i] == 'a' && ((a[i + 1] == 'c') && i + 1 < a.length))) {
				if (a[i] != 'b') {
					a[k] = a[i];
					k++;
				}
			} else
				i++;
			i++;
		}
		int p = 0;
		while (k > p) {
			System.out.print(a[p]);
			p++;
		}
	}
}

- Champ June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Best solution.. Easy one.

- Anonymous June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice code... Thanks Champ :)

- Linda June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great Code

- Anonymous June 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use prime numbers for this one.

- hprem99 June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use two pointer char * write and char * scan, write points to the position to write, whereas scan points to the position to scan.

#include <iostream>
#include <string>
#include <memory>
#include <cstring>

void remove(char * str){
	char * write = str;
	char * scan = str;
	while (*scan != '\0') {
		if (*scan == 'b')
			++scan;
		else if (*scan == 'a' && *(scan+1) == 'c')
			scan += 2;
		else
			*write++ = *scan++;
	}
	*write = '\0';
}

void test_remove_ac_or_b(){
	std::string str;
	while(true) {
		std::getline(std::cin,str);
		std::shared_ptr<char> s(new char[str.size()+1]);
		strcpy(s.get(), str.c_str());
		std::cout << s.get() << std::endl;
		remove(s.get());
		std::cout << s.get() << std::endl;
	}
}

- leon June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I was thinking about different solutions but didn't find any one of them generic for all such problems, so writing this solution of mine. I am planning to use a TRIE tree. Will create an TRIE tree using all pairs which can be replaced like b -> "" and ac ->"". TRIE will be something like

node

/        \

b         a

\

c

Now we will start with our main string which is rabct
1. start pointer points to r and tries to find it in TRIE tree's first node, but no such thing is there
2. Then increment pointer and move to a, which is present in tree.
3. Move to b and try to find b in child tree of a, but no such thing is there. In this case we need to move to next node to a, which is b.
4. Search b in tree and we find it, now as next node of b is null, means we have our b and delete it from tree. But now there exist a pattern which start before b, so once we find a pattern, we start from current node - (height of TRIE tree - 1), which is 2 in our case, so move back to (node was b at 3rd node - 2 height of tree -1) which is again a.
5. Search a in TRIE and we have it.
6. Move to next node which is c (as b is deleted), search for c, which is there so delete ac, then move back to r.
7. Check for r, then move ahead and check for t. Then we are done.

In this case we assumed that everything will end up in "", but we can replace it with some different value by putting it at last node of TRIE tree for each path. This way we can make this solution generic and independent of whatever is given to us. As per my understand, complexity is O(n^m) where n is number of pattern and m is length of test string

Please give your valuable feedback.

- mYth June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

here c is child of a.

- mYth June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Replacing ac and b with blank. Once done, splitting, merging and converting to char[] again.

for(int i=0,j=-1;i<arr.length;i++){
switch(arr[i]){
case 'a' : j=i;
break;
case 'c' : if(j!=-1){
arr[j--] = ' ';
arr[i] = ' ';
}
break;
case 'b' : arr[i] = ' ';
break;
default : j=-1;
break;

}
}

String result = "";
for(String s : (new String(arr).split(" ")))
result = result + s;

arr = result.toCharArray();

for(char c : arr)
System.out.print(c+" ");

- AlgoAlgae June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi, please check this piece of code. If there is any issue in this

public class eliminatebAndac {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		fneliminatebAndac("rebtacd");
	}
	public static void fneliminatebAndac(String s){
		String result="";
		System.out.println(s.length());
		for (int i=0;i<s.length();){
			
			if(i==s.length()-1){
				if(s.charAt(i)=='b'){
					continue;
				}
				else{
					result=result+(s.charAt(i));
					break;
				}
			}
			else if((s.charAt(i)=='b')){
				i=i+1;
			}
			else if( (""+s.charAt(i)+s.charAt(i+1)).equals("ac")){
				i=i+2;
			}
			else {
				result=result+(s.charAt(i));
				i=i+1;
			}
		}
		
		
		System.out.println(result);
		
	}

}

- ambuj.saviola June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void removeChars(char *src){
char *i = src, *j = src;
while ((*i++ = *j++)) {
if(*(j-1) == 'b') i--;
if((i-src) >=2 && *(j-1) == 'c' && *(j-2) == 'a') i-=2;
}
}

- Anonymous July 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
void edit(char *str);
int main()
{
        char str[20]="bacbacapplebbac";
        edit(str);
        printf("%s\n",str);
}
void edit(char *str)
{
    int i=0;
    char *temp=str;
    while(*temp)
    {
        if(*temp=='b')
       temp++;
        else
        {
            if(*temp=='a'&&(*(temp+1)=='c'))
            {
                temp=temp+2;

            }

            else
            {
                str[i]=*temp;
                temp++;i++;


            }
        }
    }
        str[i]='\0' ;
}

- Anonymous August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good 1.. :)

- drona August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using in-place stack - this is the only right solution and it actually works!

public static String removeBAndAC(String s)
        {
            char[] str = s.ToCharArray();
            int t = -1;
            for (int i = 0; i < str.Length; i++)
            {
                t++; // push char
                str[t] = str[i];
                int tt; // temp var to see if we are done poping
                do
                {
                    tt = t;
                    if (str[t] == 'b') t -= 1; // pop 'b', if needed
                    else if (t >= 1 && str[t - 1] == 'a' && str[t] == 'c') t -= 2; // pop 'ac', if needed
                }
                while (tt != t); // keep going while there was stuff to pop out
            }

            s = new String(str.Take(t+1).ToArray());
            Console.WriteLine(s);
            return s;
        }

removeBAndAC("zaabccbxabyzc"); // returns "zxayzc"

- Anonymous September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

int main() 
{
    char s[] = "adaabunhaccc";
    
    int p, i, l;
    
    l = strlen(s);
    i = 0;
    p = -1;
     
    while(i < l)
    {
        if(s[i] == 'b')
          s[i] = '\0';
        else if(s[i] == 'a' && s[i + 1] == 'c')
        {
          s[i] = s[i + 1] = '\0';
          ++i;
        }
        else if(s[i] == 'c')
        {
            if(s[p] == 'a')
            {
               s[i] = s[p] = '\0';
               --p;
            }
            else
               s[++p] = s[i];
        }
        else
           s[++p] = s[i];
        ++i;
    }
    s[++p] = '\0';
    
    cout << s << endl;
}

- Silent October 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple java implementation

public static char[] removeBandAC(char[] chars)
	{
		int i = 0, r = 0, n = chars.length;

		while (i < n)
		{
			if (chars[i] == 'b')
			{
				// do nothing
			}
			else if (chars[i] == 'a' && i < n - 1 && chars[i + 1] == 'c')
			{
				i++;
			}
			else
			{
				chars[r] = chars[i];
				r++;
			}
			i++;
		}

		while (r < n)
		{
			chars[r] = '\0';
			r++;
		}
		return chars;
	}

- aviundefined September 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

void stringFilter(char *str)
{
int i,j=0;
for(i=0;str[i]!='\0';)
{
if(str[i] =='b'){
i++;
continue;
}
else if(str[i]=='a' && str[i+1] == 'c'){
i+=2;
continue;
}
str[j++] = str[i++];
if(j>1 && str[j-2]=='a' && str[j-1] == 'c')
j-=2;
}
str[j] = '\0';
}
int main()
{
char str1[] = "abbbbd";
stringFilter(str1);
cout << str1 << endl;

char str2[] = "acbac";
stringFilter(str2);
cout << str2 << endl;

char str3[] = "aaac";
stringFilter(str3);
cout << str3 << endl;

char str4[] = "react";
stringFilter(str4);
cout << str4 << endl;

char str5[] = "aa";
stringFilter(str5);
cout << str5 << endl;

char str6[] = "ababaac";
stringFilter(str6);
cout << str6 << endl;

char str7[] = "aacacc";
stringFilter(str7);
cout << str7 << endl;

char str8[] = "aacaccd";
stringFilter(str8);
cout << str8 << endl;

return 0;
}

- ram October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple O(n) implementation
#include <iostream>
using namespace std;

void stringFilter(char *str)
{
int i,j=0;
for(i=0;str[i]!='\0';)
{
if(str[i] =='b'){
i++;
continue;
}
else if(str[i]=='a' && str[i+1] == 'c'){
i+=2;
continue;
}
str[j++] = str[i++];
if(j>1 && str[j-2]=='a' && str[j-1] == 'c')
j-=2;
}
str[j] = '\0';
}
int main()
{
char str1[] = "abbbbd";
stringFilter(str1);
cout << str1 << endl;

char str2[] = "acbac";
stringFilter(str2);
cout << str2 << endl;

char str3[] = "aaac";
stringFilter(str3);
cout << str3 << endl;

char str4[] = "react";
stringFilter(str4);
cout << str4 << endl;

char str5[] = "aa";
stringFilter(str5);
cout << str5 << endl;

char str6[] = "ababaac";
stringFilter(str6);
cout << str6 << endl;

char str7[] = "aacacc";
stringFilter(str7);
cout << str7 << endl;

char str8[] = "aacaccd";
stringFilter(str8);
cout << str8 << endl;

return 0;
}

- ram October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple O(n) implementation
#include <iostream>
using namespace std;

void stringFilter(char *str)
{
int i,j=0;
for(i=0;str[i]!='\0';)
{
if(str[i] =='b'){
i++;
continue;
}
else if(str[i]=='a' && str[i+1] == 'c'){
i+=2;
continue;
}
str[j++] = str[i++];
if(j>1 && str[j-2]=='a' && str[j-1] == 'c')
j-=2;
}
str[j] = '\0';
}
int main()
{
char str1[] = "abbbbd";
stringFilter(str1);
cout << str1 << endl;

char str2[] = "acbac";
stringFilter(str2);
cout << str2 << endl;

char str3[] = "aaac";
stringFilter(str3);
cout << str3 << endl;

char str4[] = "react";
stringFilter(str4);
cout << str4 << endl;

char str5[] = "aa";
stringFilter(str5);
cout << str5 << endl;

char str6[] = "ababaac";
stringFilter(str6);
cout << str6 << endl;

char str7[] = "aacacc";
stringFilter(str7);
cout << str7 << endl;

char str8[] = "aacaccd";
stringFilter(str8);
cout << str8 << endl;

return 0;
}

- ram October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static char[] eliminate(char[] arr){
		if(arr == null) return arr;
		int p = -1;
		for(int i = 0; i<arr.length;i++){
			p++;
			if(p!=i) 
				arr[p] = arr[i];
			if( arr[p] =='b') 
				p--;
			if(arr[p] == 'c' && p>0 && arr[p-1] =='a') 
				p-=2;
		}
		p++;
		if(p<=arr.length -1) 
			arr[p] = '\0';
		return arr;
	}

- srcnaks November 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void function(string& str)
{
    int pos = 0;

    for(int i=0;i<str.length()-1;i++)
    {
        if(str[i] == 'b')
            continue;
        else if(str[i] == 'a' && str[i+1] == 'c')
        {
            i += 1;
            continue;
        }
        if(i < str.length()-1)
            str[pos++] = str[i];
    }
    
    if(!(str[str.length()-1] != 'b' || (str[str.length()-2] != 'a' && str[str.length()-1] != 'c')))
            str[pos++] = str[str.length()-1];
    
    for(int i=0;i<pos;i++)
        cout<<str[i];
    cout<<endl;
}

- skum July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Eliminate all 'b' and 'ac'.cpp : Defines the entry point for the console application.
// Program to eliminate all "b" and "ac" in a string

#include<iostream>

int main()
{
	char szStr[] = "abcbac";

	int i = 0;
	int j = 0;

	while (szStr[j])
	{
		if (szStr[j] == 'b' || (szStr[j] == 'a' && szStr[j + 1] && szStr[j + 1] == 'c'))
		{
			if (szStr[j] == 'a')
			{
				j++;
			}
		}
		else
		{
			if (i != j)
			{
				szStr[i] = szStr[j];
			}
			i++;
		}
		j++;
	}

	szStr[i] = '\0';

	std::cout << "String after removing b and ac is " << szStr << std::endl;

	return 0;
}

- Anonymous September 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

int main()
{
	char szStr[] = "abcbac";

	int i = 0;
	int j = 0;

	while (szStr[j])
	{
		if (szStr[j] == 'b' || (szStr[j] == 'a' && szStr[j + 1] && szStr[j + 1] == 'c'))
		{
			if (szStr[j] == 'a')
			{
				j++;
			}
		}
		else
		{
			if (i != j)
			{
				szStr[i] = szStr[j];
			}
			i++;
		}
		j++;
	}

	szStr[i] = '\0';

	std::cout << "String after removing b and ac is " << szStr << std::endl;

	return 0;
}

- sid1505 September 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 *
 * Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.
 *
 * Examples:
 * abc -> ac
 * ac->''
 * react->rt
 *
 */
public class ReplaceCharacters {
    private final String[] charPool = new String[]{"abc", "ac", "react", "actuator", "bubble"};

    public void replaceCharArray() {
        String selectedStr = charPool[2];

        // eliminate the 'ac's first to avoid having to end up with 'ac' that had 'b' in between
        char[] chars = selectedStr.replaceAll("ac", "").toCharArray();

        StringBuilder stringBuilder = new StringBuilder();
        for (int index = 0; index < chars.length; index++) {
            if (chars[index] != 'b')
                stringBuilder.append(chars[index]);
        }
        chars = stringBuilder.toString().toCharArray();
        
        // an optional output loop
        System.out.println("Output: ");
        for (char ch : chars) {
            System.out.print(ch);
        }
    }
}

- pluto December 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

In the first pass remove all 'b'
Then in the second pass search for a 'c' and once you find a 'c' then go back and look for its immediate 'a' and found delete it.

- DashDash May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@dashdash you can't have second pass. "you are only allowed to iterate over the char array once."

@jeso is it react->ret or rt?

- Prithvi May 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public String removeBandAC(String s) {
String s = s.removeAll(s,"b");
s = s.removeAll(s,"ac");
return s;
}

- Narendra Sharma May 20, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More