## Google Interview Question for Software Engineer / Developers

• 7

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';
}``````

Comment hidden because of low score. Click to expand.
0

that's good

Comment hidden because of low score. Click to expand.
0

Great

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
3

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

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

Comment hidden because of low score. Click to expand.
4

before return deleted, we should also add:

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

Comment hidden because of low score. Click to expand.
2

Will it work with "aaaccc" sequence

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

public class removeacAndb {
public static void main(String[] args) {
int k = 0;
int i = 0;
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++;
}
}
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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``````

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';
}``````

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++;``````

Comment hidden because of low score. Click to expand.
0

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

Desired Output : xy

Comment hidden because of low score. Click to expand.
0

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"

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]);
}

}
}``````

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';
}
}``````

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);
}``````

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);
}

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.

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"

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

I have similar doubt ...

Comment hidden because of low score. Click to expand.
0

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

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

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';

}``````

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()``````

Comment hidden because of low score. Click to expand.
0

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

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``````

}

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

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';

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);``````

}

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);
}

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;

}``````

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];
}
}``````

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;
}``````

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;
}``````

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();
}

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);
}

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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

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);
}
}``````

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);
}``````

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';
}``````

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]+",");
}
}

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';
}``````

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++
}

}

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;
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++;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Best solution.. Easy one.

Comment hidden because of low score. Click to expand.
0

Nice code... Thanks Champ :)

Comment hidden because of low score. Click to expand.
0

Great Code

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use prime numbers for this one.

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;
}
}``````

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``

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

Comment hidden because of low score. Click to expand.
0

here c is child of a.

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+" ");

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);

}

}``````

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;
}
}

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' ;
}``````

Comment hidden because of low score. Click to expand.
0

Good 1.. :)

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"``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>

using namespace std;

int main()
{

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;
}``````

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;
}``````

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;
}

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;
}

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;
}

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;
}``````

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;
}``````

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;
}``````

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;
}``````

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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

string ans="";

char cur=str[0];

for(int i=1;i<str.length();){

if(cur=='b')
{
cur=str[i];
i++;
}

else if(cur=='a' && str[i]=='c'){
cur=str[i+1];
i+=2;
}

else {
ans+=cur;
cur=str[i];
i++;
}
}
if(cur!='b')
return ans+cur;

return ans;

Comment hidden because of low score. Click to expand.
0
of 0 vote

string ans="";

char cur=str[0];

for(int i=1;i<str.length();){

if(cur=='b')
{
cur=str[i];
i++;
}

else if(cur=='a' && str[i]=='c'){
cur=str[i+1];
i+=2;
}

else {
ans+=cur;
cur=str[i];
i++;
}
}
if(cur!='b')
return ans+cur;

return ans;

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.

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?

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;
}

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.

### 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.