Bloomberg LP Interview Question Interns
Team: London
Country: United States
Interview Type: Phone Interview
#include <iostream>
#include <string>
using namespace std;
string compressString(string);
int main(){
string str="Ashiq assdewfefkljhdsklfdsklkljlkjklll";
cout<<str<<" : "<<compressString(str)<<endl;
return 0;
}
string compressString(string data){
string result="";
if(data.length()<1) return result;
int count=1;
for(int index = 0; index < data.length()-1; index++){
if(data.at(index) != data.at(index+1)){
result +=to_string(count)+data.at(index);
count=1;
}
else count++;
}
result +=to_string(count)+data.at(data.length()-1);
return result;
}
public class Solution {
public static String encodeRepeatedChars(String source) {
StringBuffer result = new StringBuffer();
for (int idx = 0; idx < source.length(); idx++) {
int runLength = 1;
while (idx + 1 < source.length()
&& source.charAt(idx) == source.charAt(idx + 1)) {
runLength++;
idx++;
}
result.append(runLength);
result.append(source.charAt(idx));
}
return result.toString();
}
public static void main(String[] args) {
String example = "aaaggbbbbc";
System.out.println(encodeRepeatedChars(example));
}
}
Time Complexity: O(N)
char *encode(char *src) {
{
int length = strlen(src);
if(length == 0) return NULL;
char * first = *src;
char * next = *(++first);
char * result = new char[length];
int occur=1;
while (*next != '\0')
{
if(*first == *next)
{
occur++;
}
else
{
sprintf(result, "%d%c", occur, *first);
occur =1;
}
first++; next++;
}
sprintf(result, "%d%c", occur, *first);
}
}
class Main {
public static void main(String[] args) {
String str = "aaacccbbfffffff";
int count = 0;
for(int i=0; i< str.length(); i++) {
if(i+1 < str.length() && str.charAt(i) == str.charAt(i+1)){
count++;
} else if(i+1 < str.length() && str.charAt(i) != str.charAt(i+1)){
System.out.print(count+1 + "" + str.charAt(i));
count = 0;
} else {
System.out.print(count+1 + "" + str.charAt(i));
count = 0;
}
}
}
}
public static String charFreq(String input){
StringBuilder output=new StringBuilder();
Character ch = null;
int count = 0;
for(char eachC: input.toCharArray()){
if(ch != null && eachC != ch){
output.append(count).append(ch);
ch = eachC;
count=1;
}else{
ch = eachC;
count++;
}
}
//Last set of character not handled in above for loop
output.append(count).append(ch);
return output.toString();
}
inputstr = 'aaaggbbbbc'
outputstr = '3a2g4b1c'
from collections import OrderedDict
def encode(string):
assert (len(string) > 0), 'Must pass a valid string'
i = 0
# charmap = {}
charmap = OrderedDict()
while i < len(string):
x = string[i]
# assert (x.isspace() == False), 'Contiguous letters expected'
if x.isalpha():
v = charmap.get(x)
if v is not None:
charmap[x] += 1
else:
charmap.setdefault(x, 1)
i += 1
strbuilder = ''.join(['%d%s' % (v, k) for k,v in charmap.items()])
return strbuilder
result = encode(inputstr)
print('Decoded string: %s' % (result))
assert (result == outputstr) , 'Input and Output must match'
inputstr = 'aaaggbbbbc'
outputstr = '3a2g4b1c'
from collections import OrderedDict
def encode(string):
assert (len(string) > 0), 'Must pass a valid string'
i = 0
# charmap = {}
charmap = OrderedDict()
while i < len(string):
x = string[i]
# assert (x.isspace() == False), 'Contiguous letters expected'
if x.isalpha():
v = charmap.get(x)
if v is not None:
charmap[x] += 1
else:
charmap.setdefault(x, 1)
i += 1
strbuilder = ''.join(['%d%s' % (v, k) for k,v in charmap.items()])
return strbuilder
result = encode(inputstr)
print('Decoded string: %s' % (result))
assert (result == outputstr) , 'Input and Output must match'
Here is my Java Solution using LinkedHashMap...
package com.careercup;
/**
* Created by ejangpa on 1/25/2017.
*/
import java.util.*;
public class RepeatedCharacters {
public static void main(String[] args) {
String str = "aaaggbbbbc"; // we can take input from scanner also
char[] strArray = str.toCharArray();
Map<Character,Integer> map = new LinkedHashMap<>(); // taking LinkedHashMap to
// maintain the insetion order
for (char ch : strArray ) {
if (map.containsKey(ch)) {
int value = map.get(ch);
map.put(ch, value + 1);
} else {
map.put(ch, 1);
}
}
Set set = map.entrySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry) iterator.next();
System.out.print(entry.getValue() +""+ entry.getKey());
}
}
}
#include <iostream>
#include <string>
using namespace std;
string compressString(string);
int main(){
string str="Ashiq assdewfefkljhdsklfdsklkljlkjklll";
cout<<str<<" : "<<compressString(str)<<endl;
return 0;
}
string compressString(string data){
string result="";
if(data.length()<1) return result;
int count=1;
for(int index = 0; index < data.length()-1; index++){
if(data.at(index) != data.at(index+1)){
result +=to_string(count)+data.at(index);
count=1;
}
else count++;
}
result +=to_string(count)+data.at(data.length()-1);
return result;
}
My Solution In C#
string S = "aaaggbbbbcccf";
int Cnt = 1;
StringBuilder str = new StringBuilder();
for (int i=0;i<S.Length-1;i++)
{
if (S[i] != S[i+1])
{
str.Append(Cnt);
str.Append(S[i]);
Cnt=1;
}
else
{
Cnt = Cnt+ 1;
}
if (i == S.Length -2)
{
if (S[i] != S[i+1])
{
str.Append(Cnt);
str.Append(S[i+1]);
}
else
{
str.Append(Cnt);
str.Append(S[i]);
}
}
}
Console.WriteLine("Output: " + str);
public static void calculateAndReplaceRepeatedChars()
{
string text = "aaaggbbbbc";
char[] chars = text.ToCharArray();
short counter = 0;
string current = "a";
string output = "";
for (int i = 0; i < chars.Length; i++)
{
if (current == chars[i].ToString())
{
counter++;
}
else
{
output += (counter.ToString() + current);
current = chars[i].ToString();
counter = 1;
}
}
output += (counter.ToString() + current);
Console.WriteLine(output);
}
public static void calculateAndReplaceRepeatedChars()
{
string text = "aaaggbbbbc";
char[] chars = text.ToCharArray();
short counter = 0;
string current = "a";
string output = "";
for (int i = 0; i < chars.Length; i++)
{
if (current == chars[i].ToString())
{
counter++;
}
else
{
output += (counter.ToString() + current);
current = chars[i].ToString();
counter = 1;
}
}
output += (counter.ToString() + current);
Console.WriteLine(output);
}
from itertools import groupby
#Solution in Python
def CountOccurences(mystring):
for val,occur in groupby(mystring):
char,num=val,len(list(occur))
mystring=mystring.replace(char*(num),str((num))+char,1)
return mystring
if __name__ == "__main__":
print CountOccurences("aaaggbbbbcaaaa") #Outputs 3a2g4b1c4a
def CountOccurences(mystring):
mynewstring=""
prev=mystring[0]
count=0
for char in mystring:
if char != prev :
mynewstring += str(count)+prev
count=0
count+=1
prev=char
mynewstring += str(count)+prev
return mynewstring
if __name__ == "__main__":
print CountOccurences("aaaggbbbbcaaaa") #Outputs 3a2g4b1c4a
public static void main(String args[])
{
StringBuffer str = new StringBuffer("aaabbbgggcc");
int curStartPos = 0;
int curEndPos = 0;
int count = 1;
for(int i=0; i<str.length()-1; i++)
{
if(str.charAt(i) == str.charAt(i+1))
{
count++;
curEndPos++;
}
else
{
String replaceMentStr = Integer.toString(count)+str.charAt(i);
str.replace(curStartPos, curEndPos+1, replaceMentStr);
curStartPos+= 2;
curEndPos = curStartPos;
i = curStartPos-1;
count = 1;
}
}
//Update for Last character
if(count != 0)
{
String replaceMentStr = Integer.toString(count)+str.charAt(str.length()-1);
str.replace(curStartPos, curEndPos+1, replaceMentStr);
}
System.out.println(str.toString());
}
Time Complexity = O(n)
Space Complexity = O(1)
#include <iostream>
#include <string>
#include <map>
#include <sstream>
using namespace std;
int main(int argc, char* argv[]) {
if(argc != 2 ) {
cerr<<"Error: Usage: "<<endl;
return -1;
}
string input = string(argv[1]);
map<char, int> char_counting;
int times = 1;
for(int i = 0; i < input.length(); i++) {
if(char_counting.find(input[i]) != char_counting.end() ) {
times = char_counting[input[i]];
char_counting[input[i]] = ++times;
}
char_counting[input[i]] = times;
}
string output;
for(map<char, int>::iterator itr = char_counting.begin(); itr != char_counting.end(); itr++)
{
stringstream ss;
ss << itr->second;
ss << itr->first;
output += ss.str();
}
cout<<output<<endl;
}
#include <iostream>
#include <string>
#include <map>
#include <sstream>
using namespace std;
int main(int argc, char* argv[]) {
if(argc != 2 ) {
cerr<<"Error: Usage: "<<endl;
return -1;
}
string input = string(argv[1]);
map<char, int> char_counting;
int times = 1;
for(int i = 0; i < input.length(); i++) {
if(char_counting.find(input[i]) != char_counting.end() ) {
times = char_counting[input[i]];
char_counting[input[i]] = ++times;
}
char_counting[input[i]] = times;
}
string output;
for(map<char, int>::iterator itr = char_counting.begin(); itr != char_counting.end(); itr++)
{
stringstream ss;
ss << itr->second;
ss << itr->first;
output += ss.str();
}
cout<<output<<endl;
}
Here you go
public string compressString(string input)
{
if(input == null)
{
throw new ArgumentException();
}
var output = new StringBuilder();
char currentchar;
int occurance = 0;
for(int i = 0;i<input.Length;i++)
{
occurance = 1;
if(input[i] < 48 && input[i] > 57)
{
currentchar = input[i];
for(int j = i; j < input.Length;j++)
{
if(input[j] == currentchar)
{
occurance++;
}
else
{
break;
}
}
output.Append(occurance);
output.Append(currentchar);
i = j-1;
}
output.Append(input[i]);
}
return output.ToString();
}
The complexity of this algorithm is O(N) + O(N).
Still looking for O(N) inplace for this problem, general input are all having worst case O(N) space complexity
public class Exm{
public static void main(String[]args)
{
String data="aaaabbggggcccccyyy";
String now="";
String charr="";
int c=0;
for(int k=0;k<data.length();k++)
{
if(k==0)
{
c++;
charr=data.charAt(k)+"";
now=data.charAt(k)+"";
}else
{
if(charr.equals(data.charAt(k)+""))
{
c++;
}else{
now+=c+"";
now+=data.charAt(k);
charr=data.charAt(k)+"";
c=1;
}
}
}
now+=c;
System.out.print(now);
}
}
public String charToFrequency(String input) {
int size = input.length();
StringBuilder sb = new StringBuilder();
for(int i=0;i<size;i++){
char current = input.charAt(i);
sb.append(Math.abs(i - (input.lastIndexOf(current)+1))).append(current);
i = input.lastIndexOf(current);
}
return sb.toString();
}
public String charToFrequency(String input) {
int size = input.length();
StringBuilder sb = new StringBuilder();
for(int i=0;i<size;i++){
char current = input.charAt(i);
sb.append(Math.abs(i - (input.lastIndexOf(current)+1))).append(current);
i = input.lastIndexOf(current);
}
return sb.toString();
In Swift 4
func transform(_ string: String) -> String {
var dict = [Character: Int]()
var arr = [Character]()
for character in string {
if let val = dict[character] {
dict[character] = val + 1
} else {
dict[character] = 1
arr.append(character)
}
}
return arr.map { "\(dict[$0]!)\($0)" }.joined(separator: "")
}
public class ParentClassStatic {
public static String encodeRepeatedChars(String source) {
StringBuilder sb = new StringBuilder();
Map<Character, Integer> map = new HashMap<Character,Integer>();
for(int i= 0; i<source.length(); i++){
map.put(source.charAt(i), map.containsKey(source.charAt(i))? map.get(source.charAt(i))+1 : 1 );
}
Set<Entry<Character, Integer>> set = map.entrySet();
for(Entry<Character,Integer> e : set){
sb.append(e.getValue()+""+e.getKey());
}
return sb.toString();
}
public static void main(String[] args) {
String example = "aaaggbbbbc";
System.out.println(encodeRepeatedChars(example));
}
}
Solution in java
public String charToFrequency(String str) { if (str == null || str.isEmpty()) { return str; } char current = str.charAt(0); int count = 1; StringBuilder output = new StringBuilder(); for (int i=1; i<str.length(); i++) { if (str.charAt(i) == current) { count++; } else { output.append(count).append(current); current = str.charAt(i); count = 1; } } output.append(count).append(current); return output.toString(); }Time Complexity: O(n)
- slvrhwk January 25, 2017Space Complexity: O(n)