Bloomberg LP Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
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);
}
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();
}
}
}
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++;
}
}
}
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++;
}
}
}
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.
}
}
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)
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;
}
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),"");
}
}
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),"");
}
}
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),"");
}
}
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;
}
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());
}
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());
}
/**
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());
}
**/
public static void main (String[] args) throws java.lang.Exception
{
String str = "ABCCCCCBBA";
int i = 0, j = 0, count = 0;
StringBuilder sb = new StringBuilder();
while (i <= j && j < str.length()) {
if (j < str.length() && str.charAt(i) == str.charAt(j)) {
count++;
j++;
} else {
if (count < 3) {
sb.append(str.substring(i, j));
}
i = j;
count = 0;
}
if (j == str.length()) {
sb.append(str.substring(i, j));
break;
}
}
System.out.println(sb.toString());
}
def remove(st):
val = ""
i = 0
while i<len(st):
j = 3;
while (i+j<len(st)) and (st[i]*j == st[i:i+j]):
j += 1
if st[i]*j == st:
return ""
j = j-1
if j >= 3:
i += j
else:
val += st[i]
i += 1
if len(st)==len(val):
return val
else:
return remove(val)
remove("ABCCCCBBA") == "AA"
remove("") == ""
remove("A") == "A"
remove("ABABABABA") == "ABABABABA"
remove("AABAAABAAABAC") == "C"
remove("AAAAAAAAAAAAA")== ""
def remove_three(st):
output = []
lst = list(st)
lst.sort()
i = 0
for letter in lst:
if len(output):
if letter != output[-1]:
output.append(letter)
i =1
elif letter == output[-1]:
if i < 2:
output.append(letter)
i +=1
else:
del output[-2:]
i = 0
else:
output.append(letter)
i =1
return ''.join(output)
#print(remove_three('aaannn'))
#print(remove_three('baaabnnn'))
print(remove_three('annaacddnbddnbn'))
def remove3ConsecutiveDuplicates(string):
val = ""
i = 0
while (i < len(string)):
if (i < len(string) - 2 and
string[i] * 3 == string[i:i + 3]):
i += 3
else:
val += string[i]
i += 1
if (len(val) == len(string)):
return val
else:
return remove3ConsecutiveDuplicates(val)
#include <bits/stdc++.h>
using namespace std;
// ABCCCCBB ==> ABBB ==> A
string remove3Dup(string str) {
int start = 0;
int end = 0;
while (end < str.length()) {
if (str[end] == str[start]) {
end++;
} else if (str[end] != str[start]) {
if (end - start >= 3) {
str.erase(start, (end-start));
if (start - 1 <= 0) {
start = 0;
} else {
start = start - 1;
}
end = start;
} else {
start++;
end++;
}
}
if (end == str.length() && end - start >=3) {
str.erase(start, end - start);
}
}
return str;
}
int main() {
string str = "ABCCCCBBA";
string out = remove3Dup(str);
cout << out << endl;
}
__author__ = 'deepika'
class Solution:
def collapse(self, string):
if len(string) in [0, 1, 2]:
return string
stack = []
i = 0
while i < len(string):
if len(stack) == 0 or stack[-1] != string[i] or i == len(string) - 1:
stack.append(string[i])
i += 1
continue
if i + 1 < len(string) and stack[-1] == string[i]:
if string[i] == string[i+1]:
while i < len(string) and string[i] == stack[-1]:
i += 1
stack.pop()
else:
stack.append(string[i])
i += 1 # safe to jump but it is okay to increment by one as well
return ''.join(stack)
s=Solution()
assert s.collapse("aaaaaa") == ''
assert s.collapse("aaaaaabbbbbb") == ''
assert s.collapse("ababaababa") == "ababaababa"
assert s.collapse("abccc") == "ab"
assert s.collapse("abccccbba") == "aa"
assert s.collapse("abcd") == "abcd"
print("completed test cases")
def remove_repeating_characters(string: str, char_num: int = 3) -> str:
stack = []
for ch in string:
if stack and ch != stack[-1][0] and stack[-1][1] >= char_num:
stack.pop()
if not stack or ch != stack[-1][0]:
stack.append([ch, 1])
else:
stack[-1][1] += 1
if stack and stack[-1][1] >= char_num:
stack.pop()
return "".join(item[0]*item[1] for item in stack)
def remove_repeating_characters(string: str, char_num: int = 3) -> str:
stack = []
for ch in string:
if stack and ch != stack[-1][0] and stack[-1][1] >= char_num:
stack.pop()
if not stack or ch != stack[-1][0]:
stack.append([ch, 1])
else:
stack[-1][1] += 1
if stack and stack[-1][1] >= char_num:
stack.pop()
return "".join(item[0]*item[1] for item in stack)
def remove_repeating_characters(string: str, char_num: int = 3) -> str:
stack = []
for ch in string:
if stack and ch != stack[-1][0] and stack[-1][1] >= char_num:
stack.pop()
if not stack or ch != stack[-1][0]:
stack.append([ch, 1])
else:
stack[-1][1] += 1
if stack and stack[-1][1] >= char_num:
stack.pop()
result = ""
while stack:
item = stack.pop()
result = item[0]*item[1] + result
return result
- catfat August 17, 2018