Google Interview Question
Country: United States
Interview Type: Written Test
It does not account for this input: 9___6aab
The compression would yield: 9_3_6_2ab
Decompression would incorrectly yield: 936aab
Here _ is used as a special character. Special character handling should be there..
let if we encounter one _ then the final output of this will be __ (two _). It will help us to handle special character.
I apologize that I did not state in my engineering model that the special character was not meant for input entry and is assumed that it will not be entered. HOWEVER, if you would like to account for the special character, you can do something like the code below. You can compress the string and keep track of the special character through a list ( a vector in my example). That way, if you are interested in decompressing the string, lets say the the example you gave 9___6aab would compress to 9_6_2ab with our vector storing the '_' at indexes 1,2,3. Unravel the compressed string to 96aab and insert the '_' where needed. I hope this helps!
/*
Let me explain how this function works. This function takes a string called s and uses an algorithm to compress is.
(*NOTE: this is slightly different from the questions ex:, but still accomplishes the same goal)
this algorithm will take a string, say 45eeeedfghfffeff62 and transform it into 4_5_4edfgh3fe2f6_2. If there is a number to the left of a character,
it is there to explain how many times that character should be multiplied (ex: eeee: 4e dddddddddd : 10d) The "_" character is there to denote that
if a number is by itself during input,say 6eee2, then the output will be 6_3e2. This is similar to the "*" character in the example. We do not want vagueness.
(*NOTE: this algorithm is to be used with very large strings. This will do a great job of compressing a large string, such as 5eeeeeeeeeedddddfff65ggggeeffssaasddffdsacvffd,
but not smaller strings like 5ee (takes up the same amount of characters.
AUTHOR: BILL GLESIAS
this algorithm is implemented in c++
*/
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
class StringObj{
private: std::string compressedString;
std::vector<unsigned> indexholder;
public:
StringObj::StringObj(std::vector<unsigned>, std::string);
void StringObj::getAndPrintValues() const;
};
StringObj::StringObj(std::vector<unsigned> index, std::string compString){
this->compressedString = compString;
this->indexholder = index;
}
void StringObj::getAndPrintValues() const{
std::cout << this->compressedString << std::endl;
for(unsigned i = 0; i < this->indexholder.size(); i++){
std::cout<< this->indexholder[i] << std::endl;
}
}
StringObj charCompress(std::string s){
unsigned i = 0;
std::vector<unsigned> indexholder;
std::string newString = "";
while( i < s.length()){
char r = s[i];
if(s[i] == '_'){
indexholder.push_back(i);
}
else if( i == s.length()-1){
newString += s[i];
StringObj a = StringObj::StringObj(indexholder,newString);
return a;
}
else if(s[i] == s[i + 1]){
unsigned sum = 1;
while( i < s.length()- 1 && (s[i] == s[i + 1])){
sum++;
i++;
}
std::ostringstream convert;
convert << sum;
if( i == s.length()-1){
newString += convert.str() + r;
StringObj a = StringObj::StringObj(indexholder,newString);
return a;
}
else{
newString += convert.str() + r;
}
}//end if
else{
newString += s[i];
if(s[i] > 47 && s[i] < 58){
newString += "_";
}
}//end else
i++;
}
}
int main(){
StringObj a = charCompress("9___6aab");
a.getAndPrintValues();
a = charCompress("5eeeeeee____eeedddddfff65ggggeeffs__saasddffdsacvffd");
a.getAndPrintValues();
system("PAUSE");
}
package com.google.practice;
public class Compress2 {
public static void main(String[] arg){
String s = "9___6aab ";//"daaad";//"5eeeecd";//"1aa4aggg3hagst5";
if(s.length()==0)
System.out.println("Provide Input");
else
System.out.println(compress(s));
}
public static String compress(String s){
char p; StringBuilder sb = new StringBuilder();
int i=1,j=0;
for(;i<s.length();i++){
if(s.charAt(i)==s.charAt(j)){
if(j-1<0)
p = 'a';
else
p = s.charAt(j-1);i++;
while(i<s.length() && s.charAt(i)==s.charAt(j))
i++;
if(isDigit(p)){
sb = sb.append("*1"+(i-j)+"*"+s.charAt(j));
}else{
sb = sb.append((i-j)+"*"+s.charAt(j));
}
j = i;
}else{
sb.append(s.charAt(j));
j++;
}
}
if(j<s.length() && j==i-1)
sb.append(s.charAt(j));
return sb.toString();
}
public static boolean isDigit(char p){
try{
int n = Integer.parseInt(""+p);
if(n>=0 && n<=9)
return true;
}catch(Exception e){
return false;
}
return false;
}
}
/*
- bglesias January 30, 2014Let me explain how this function works. This function takes a string called s and uses an algorithm to compress is.
(*NOTE: this is slightly different from the questions ex:, but still accomplishes the same goal)
this algorithm will take a string, say 45eeeedfghfffeff62 and transform it into 4_5_4edfgh3fe2f6_2. If there is a number to the left of a character,
it is there to explain how many times that character should be multiplied (ex: eeee: 4e dddddddddd : 10d) The "_" character is there to denote that
if a number is by itself during input,say 6eee2, then the output will be 6_3e2. This is similar to the "*" character in the example. We do not want vagueness.
(*NOTE: this algorithm is to be used with very large strings. This will do a great job of compressing a large string, such as 5eeeeeeeeeedddddfff65ggggeeffssaasddffdsacvffd,
but not smaller strings like 5ee (takes up the same amount of characters.
AUTHOR: BILL GLESIAS
this algorithm is implemented in c++
*/
#include <iostream>
#include <string>
#include <sstream>
std::string charCompress(std::string s){
unsigned i = 0;
std::string newString = "";
while( i < s.length()){
char r = s[i];
if( i == s.length()-1){
newString += s[i];
return newString;
}
else if(s[i] == s[i + 1]){
unsigned sum = 1;
while( i < s.length()- 1 && (s[i] == s[i + 1])){
sum++;
i++;
}
std::ostringstream convert;
convert << sum;
if( i == s.length()-1){
newString += convert.str() + r;
return newString;
}
else{
newString += convert.str() + r;
}
}//end if
else{
newString += s[i];
if(s[i] > 47 && s[i] < 58){
newString += "_";
}
}//end else
i++;
}
}
int main(){
std::string a = charCompress("5eeeeddf55555dcgleeettff");
std::cout << a << std::endl;
a = charCompress("5eeeeeeeeeedddddfff65ggggeeffssaasddffdsacvffd");
std::cout << a << std::endl;
system("PAUSE");
}