Bloomberg LP Interview Question for SDE1s


Country: United States
Interview Type: Phone Interview




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

class State {
    constructor() {
        this.n = 0;
        this.start_of_current_char = 0;
    }
    collapse_string( s ) {
        // Need to cut out a piece of the string and move some pointers around
        let result = s.substring(0,this.start_of_current_char)+s.substring(this.n);
        //
        this.n = this.start_of_current_char;
        while( result[this.start_of_current_char-1]==result[this.n] ) {
            this.start_of_current_char--;
            if( this.start_of_current_char<0 ) {
                this.start_of_current_char = 0;
                break;
            }
        }
        return result;
    }
    toString() {
        return "n="+this.n+",start_of_current_char="+this.start_of_current_char;
    }
}
function cleanse_string( s ) {
    let state = new State();
    for( state.n=0; state.n<s.length; state.n++ ) {
        if( s[state.n]!=s[state.start_of_current_char] ) {
            if( (state.n-state.start_of_current_char)>=3 ) {
                s = state.collapse_string(s);
            }
            else {
                state.start_of_current_char = state.n;
            }
        }
    }
    if( (state.n-state.start_of_current_char)>=3 ) {
        s = state.collapse_string(s);
    }
    return s;
}

console.log(cleanse_string(process.argv[2]));

- catfat August 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's what I'd do
find repetition and remove if more than 3, repeat

public static void main(String[] args)
{

    String input = (new Scanner(System.in)).nextLine();

    for (int i = 0; i < input.length(); i++) {
        int j = i;
        while (j < input.length() && input.charAt(j) == input.charAt(i))
            j++;
        if (j - i > 3) {
            input = input.substring(0, i) + input.substring(j);
            System.out.println(input);
            i = 0;
        }
    }

    System.out.println("Final string : " + input);

}

- PeyarTheriyaa August 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi there,

There are couple of solutions for this problem. This implementation may be a bit slower than just working on string (actually in the end big O is the same), but it is much more elegant - you don't need to write that many temp variables and conditions.

static void Main(string[] args)
        {
            string characters = "ABCCCCBBA";
            Stack<char> stackOfChars = new Stack<char>();
            FillStackInReverseOrder(stackOfChars,characters);
            Stack<char> tempStackOfChars = new Stack<char>();
            
            int numberOfRepetitions=1;//we always have 1 repetition for 1 char
            while(stackOfChars.Count>0){
                tempStackOfChars.Push(stackOfChars.Pop());
                if(tempStackOfChars.Count>0 && 
                   stackOfChars.Count>0 && 
                   stackOfChars.Peek()==tempStackOfChars.Peek()){
                    numberOfRepetitions++;
                }else{
                    if(numberOfRepetitions>=3){
                        PopTopChars(numberOfRepetitions,tempStackOfChars);
                        CopyElements(tempStackOfChars,stackOfChars,2);
                    }
                    numberOfRepetitions=1;//we always have 1 repetition for 1 char
                }
            }
            
            //printing
            string outputString=String.Empty;
            while(tempStackOfChars.Count>0){
                outputString=tempStackOfChars.Pop()+outputString;
            }
            Console.WriteLine(outputString);
            Console.ReadLine();
        }

        private static void CopyElements(Stack<char> fromStack, Stack<char> toStack, int count)
        {
            for(int i=0;i<count && fromStack.Count>0;i++){
                toStack.Push(fromStack.Pop());
            }
        }

        private static void PopTopChars(int count, Stack<char> tempStackOfChars)
        {
            for(int i=0;i<count && tempStackOfChars.Count>0;i++){
                tempStackOfChars.Pop();
            }
        }

        private static void FillStackInReverseOrder(Stack<char> stack, string characters){
            for(int i =characters.Length-1;i>=0;i--){
                stack.Push(characters[i]);
            }
        }

        private static void PopSameChars(Stack<char> stack)
        {
            char charOnTop = stack.Pop();
            while(stack.Peek()==charOnTop){
                stack.Pop();
            }
        }
    }

- DoubleA August 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static void removeThreeConsecutive(String s){

int i=0;

while(i<=s.length()-1){

if((s.charAt(i)==s.charAt(i+1)) && (s.charAt(i+2)==s.charAt(i)) && (i<=s.length()-2)){
if(i==0){
s=s.substring(i+3,s.length()-1);
i++;
}else{
s=s.substring(0,i-1)+s.substring(i+3,s.length()-1);
i++;
}

}else if((s.charAt(i)==s.charAt(i+1)) && (i<=s.length()-1)){
i+=2;
}else{
i++;
}

}
}

- Anonymous November 01, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static void removeThreeConsecutive(String s){

int i=0;

while(i<=s.length()-1){

if((s.charAt(i)==s.charAt(i+1)) && (s.charAt(i+2)==s.charAt(i)) && (i<=s.length()-2)){
if(i==0){
s=s.substring(i+3,s.length()-1);
i++;
}else{
s=s.substring(0,i-1)+s.substring(i+3,s.length()-1);
i++;
}

}else if((s.charAt(i)==s.charAt(i+1)) && (i<=s.length()-1)){
i+=2;
}else{
i++;
}

}
}

- Anonymous November 01, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution that uses read and write indices inside the string to remove consecutive chars, but with a go-back clause instead of recursion. Seems pretty optimal.

void remove3consecutive(string &s) {
  const size_t len = s.length();
  
  if (len >= 3) { // no action possible if < 3 chars long.
    char c = s[0];  // Prime the loop with the first char
    size_t write_index = 0, count = 1;

    // Start loop from [1] now primed
    for (size_t read_index = 1; read_index < len; ++read_index) {
      if (s[read_index] == c) {
        count++;
      }
      else if (count >= 3) {
        c = s[read_index];  // Reset the char counting state
        count = 1;

        // Check if the previous written char matches next read char
        if ((write_index > 0) && (s[read_index] == s[write_index - 1])) {
          --write_index;
          count = 2;

          // Check 2nd char back
          if ((write_index > 0) && (s[read_index] == s[write_index - 1])) {
            --write_index;
            count = 3;
          }
        }
      } else {
        while (count--) {
          s[write_index++] = c;
        }
        c = s[read_index];  // Reset the char counting state
        count = 1;
      }
    }

    if (count < 3) { // Write any final sequence
      while (count--) {
        s[write_index++] = c;
      }
    }
  
    s.resize(write_index);  // Remove chars after write_index as not needed.
  }
}

- Luc November 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python 3 implementation:

def remove_3_consecutives(s):
    output = []
    counter = 1
    flag_to_remove = None
    for char in s:
        if not flag_to_remove == char:
            flag_to_remove = None
            if len(output):
                if not char == output[-1]:
                    output.append(char)
                    counter = 1
                else:
                    if counter < 2:
                        counter += 1
                        output.append(char)
                    else:
                        del output[-2:]
                        flag_to_remove = char
                        counter = 1
            else:
                output.append(char)
                flag_to_remove = None

    return output


if __name__ == '__main__':
    s = 'ABCCCCBBA'
    remove_3_consecutives(s)

- sjjpo2002 November 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public  String remove3consucutiveChars(String string) {
		if(string.length()<3)
			return string;
		
		int count=1;
		for(int i=1;i<string.length(); i++) {
			char c = string.charAt(i);
			while(c==string.charAt(i-1)) {
				count++;
				if(i<string.length()-1) {
					i++;
					c = string.charAt(i);
				}else
					break;
			}
			if(count>=3) {
				string = string.substring(0, i-count)+string.substring(i);
				i=0;
				count=1;
			}
		}
		return string;
		
	}

- madhusangita.android January 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class HelloWorld{

public static void main(String []args){
String a="BAAABB";
System.out.println(remove(a));
}

public static String remove(String s){

return _remove(s);

}

public static String _remove(String s){

if(s==null || s.length()==0) return s;
String temp = threeSame(s);
if(s.equals(temp)) return temp;

return _remove(temp);

}

public static String threeSame(String s){

if(s.length()<3) return s;

char prev=s.charAt(0);

int i=1;
int count=1;

for(;i<s.length();++i){
if(prev==s.charAt(i)){

count++;
}else{
if(count>=3) break;
count=1;
}
prev=s.charAt(i);
}

return count<3?s:s.replace(s.substring(i-count,i),"");
}
}

- Abhishek January 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class HelloWorld{

public static void main(String []args){
String a="BAAABB";
System.out.println(remove(a));
}

public static String remove(String s){

return _remove(s);

}

public static String _remove(String s){

if(s==null || s.length()==0) return s;
String temp = threeSame(s);
if(s.equals(temp)) return temp;

return _remove(temp);

}

public static String threeSame(String s){

if(s.length()<3) return s;

char prev=s.charAt(0);

int i=1;
int count=1;

for(;i<s.length();++i){
if(prev==s.charAt(i)){

count++;
}else{
if(count>=3) break;
count=1;
}
prev=s.charAt(i);
}

return count<3?s:s.replace(s.substring(i-count,i),"");
}
}

- Abhishek January 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class HelloWorld{

public static void main(String []args){
String a="BAAABB";
System.out.println(remove(a));
}

public static String remove(String s){

return _remove(s);

}

public static String _remove(String s){

if(s==null || s.length()==0) return s;
String temp = threeSame(s);
if(s.equals(temp)) return temp;

return _remove(temp);

}

public static String threeSame(String s){

if(s.length()<3) return s;

char prev=s.charAt(0);

int i=1;
int count=1;

for(;i<s.length();++i){
if(prev==s.charAt(i)){

count++;
}else{
if(count>=3) break;
count=1;
}
prev=s.charAt(i);
}

return count<3?s:s.replace(s.substring(i-count,i),"");
}
}

- Abhishek January 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static String removeCharacters(String input, int n) {

		if (n == 0 || input == null || input.length() == 0 || input.trim().isEmpty()) {
			return input;
		}

		if (n == 1) {
			return "";
		}

		int i = 0;
		while (i < input.length()) {
			int j = i;
			boolean hasDuplicates = false;
			while (j < input.length() && input.charAt(j) == input.charAt(i)) {
				if (i != j) {
					hasDuplicates = true;
				}
				j++;
			}
			if (hasDuplicates && i != j && j - i >= n) {
				input = input.substring(0, i) + input.substring(j);
				i = 0;
				hasDuplicates = false;
			} else {
				i++;
			}
		}

		return input;
	}

- Srikar April 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String [] args){
//String str= "ABCCCCBBA";
String str= "ABCCCCABBA";
int prev=0;
int count=0;
int curr=1;
char [] chArray= str.toCharArray();
while(curr < chArray.length){
if(chArray[prev]!=chArray[curr]){
curr++;
prev++;
}
else{
int c= 1;
while(curr < chArray.length && chArray[prev] == chArray[curr]){
c++;
curr++;
}
if(c>=3){
// delete char from prev to curr-1
int k=prev;
while(k < curr){
chArray[k]='#';
k++;
}
prev=prev-1;
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < chArray.length ; i++){
if(chArray[i] !='#') sb.append(chArray[i]);
}
System.out.println(sb.toString());
}

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

public static void main(String [] args){
	//String str= "ABCCCCBBA";
		String str= "ABCCCCABBA";	
	int prev=0;
	int count=0;
	int curr=1;
	char [] chArray= str.toCharArray();
	while(curr < chArray.length){
	  if(chArray[prev]!=chArray[curr]){
		  curr++;
		  prev++;
	  }
	  else{
		  int c= 1;
		  while(curr < chArray.length  && chArray[prev] == chArray[curr]){
			  c++;
			  curr++;
		  }
		  if(c>=3){
			  // delete char from prev to curr-1
			  int k=prev;
			  while(k < curr){
				  chArray[k]='#';
				  k++;
			  }
			  prev=prev-1;
		  }
	  }
	}
	StringBuilder sb = new StringBuilder();
    for(int i = 0 ; i < chArray.length ; i++){
    	if(chArray[i] !='#') sb.append(chArray[i]);
    }
    System.out.println(sb.toString());
  }

- Amit April 18, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**




public static void main(String [] args){
//String str= "ABCCCCBBA";
String str= "ABCCCCABBA";
int prev=0;
int count=0;
int curr=1;
char [] chArray= str.toCharArray();
while(curr < chArray.length){
if(chArray[prev]!=chArray[curr]){
curr++;
prev++;
}
else{
int c= 1;
while(curr < chArray.length && chArray[prev] == chArray[curr]){
c++;
curr++;
}
if(c>=3){
// delete char from prev to curr-1
int k=prev;
while(k < curr){
chArray[k]='#';
k++;
}
prev=prev-1;
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < chArray.length ; i++){
if(chArray[i] !='#') sb.append(chArray[i]);
}
System.out.println(sb.toString());
}
**/

- Amit April 18, 2019 | 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