Amazon Interview Question
Quality Assurance EngineersCountry: United States
Interview Type: Phone Interview
private void compressUseStringBuffer(String string) {
System.out.println("before compress String:"+string);
System.out.println("before compress size:"+string.length());
int size = countCompress(string);
if(string.length() <size)
{
System.out.println("Actual string is having less size:"+ string);
}
int count = 1;
char last = string.charAt(0);
StringBuffer newString = new StringBuffer();
for(int i=1; i<string.length();i++){
if(string.charAt(i) == last){
count++;
}else{
newString.append(last);
newString.append(count);
last = string.charAt(i);
count = 1;
}
}
newString.append(last);
newString.append(count);
System.out.println("Compressed SB:"+newString);
deCompressUseStringBuffer(newString.toString());
}
private int countCompress(String string) {
char last = string.charAt(0);
int count = 1;
int size = 0 ;
for(int i = 1; i<string.length(); i++){
if(string.charAt(i) == last){
count++;
}else{
last = string.charAt(i);
size += 1 + String.valueOf(count).length();
count = 1;
}
}
size += 1+String.valueOf(count).length();
System.out.println("After Compress size:"+size);
return size;
}
private void deCompressUseStringBuffer(String string) {
System.out.println("before decompress size:"+string.length());
char last = string.charAt(0);
int charCompSize = 1;
StringBuffer newString = new StringBuffer();
for(int i=1; i<string.length();i++){
if(i%2 == 0){
last = string.charAt(i);
}else{
charCompSize = Character.getNumericValue(string.charAt(i));
}
for(int j=0;j<charCompSize;j++){
newString.append(last);
}
charCompSize = 0;
}
System.out.println("After decompress size:"+newString.length());
System.out.println("Decompressed SB:"+newString);
}
To transmit something, you have to create a way to identify the streaming begin/end.
Having the encoding type is good too. So, Something like HTTP would be interesting.
Client -> Server
GET /\r\n
Accepted-Content-Type: gziped, text\r\n
\r\n\r\n
Server -> Client
Content-Type: gziped\r\n
Content-Length: xxx\r\n
[..] GZIP CONTENT [..] (xxx bytes long)
\r\n\r\n
Will the strings be one in a language dictionary? In that case, people should simply send the cardinal number ( index ) of the word in the dictionary, as well as the dictionary identifier. This is known as code-book encoding, and is the fastest, and the cheapest encoding known to mankind.
[ wikipedia.org/wiki/Block_cipher_mode_of_operation ]
private static String decompress(String res){
StringBuffer s=new StringBuffer();
int n=res.length(); int i=0;
while(i<n){
char ch=res.charAt(i);
int j=i+1;
int count=0;
while(j<n && res.charAt(j)>=48 && res.charAt(j)<=57){
Integer val=Integer.parseInt(""+res.charAt(j));
count=count*10+val;
j++;
}
for(int k=0;k<count;k++) s.append(ch);
i=j;
}
return s.toString();
}
private static String compress(String s){
int n=s.length();
int i=0;
StringBuffer res=new StringBuffer();
while(i<n){
int count=1;
char ch=s.charAt(i);
int j=i+1;
while(j<n){
char ch1=s.charAt(j);
if(ch==ch1){ count++; j++;}
else break;
}
i=j;
res.append(ch); res.append(count);
}
if(res.length()<n) return res.toString();
return s;
}
import java.util.Stack;
public class StringCompressor {
public static void main(String[] args){
StringCompressor compressor = new StringCompressor();
String s = "ABCBCEBCBCEBCBCEG";
String compressedStr = compressor.compress(s);
System.out.println("compressed String: "+compressedStr);
String decompressedStr = compressor.decompress(compressedStr);
System.out.println("decompressed String: "+decompressedStr);
}
public String compress(String originalString){
return compress(originalString, 1);
}
//Using recursion. Every recursion, the length of duplicate string increases by 1
//until the half length of result of last recursion.
private String compress(String originalString, int lengthOfDuplicates){
if(lengthOfDuplicates >= (originalString.length()/2+1)) return originalString;
StringBuffer sb = new StringBuffer();
String duplicateStr = originalString.substring(0, lengthOfDuplicates);
int occurence = 1;
for(int i=lengthOfDuplicates; i<=(originalString.length()-lengthOfDuplicates); i++){
String subStr = originalString.substring(i, i+lengthOfDuplicates);
if(subStr.equals(duplicateStr)){
occurence++;;
i = i+lengthOfDuplicates-1; //i points to the last index of duplicate string.
}else{
if(occurence == 1){
sb.append(duplicateStr.substring(0, 1));
duplicateStr = duplicateStr.substring(1)+originalString.charAt(i);
//i points to the last index of duplicate string.
}else{
sb.append(occurence+"["+duplicateStr+"]");
duplicateStr = subStr;
occurence = 1;
i = i+subStr.length()-1; //i points to the last index of duplicate string.
}
}
if((originalString.length()-i-1)<lengthOfDuplicates){ //test the length of remaining string.
if(occurence==1){
sb.append(duplicateStr);
}else{
sb.append(occurence+"["+duplicateStr+"]");
}
sb.append(originalString.substring(i+1));
break;
}
}
return compress(sb.toString(), lengthOfDuplicates+1);
}
public String decompress(String compressedString){
Stack<DecompressWrapper> stack = new Stack<DecompressWrapper>();
stack.add(new DecompressWrapper());
for(int i=0; i<compressedString.length(); i++){
if(isNumber(compressedString.charAt(i))){
int occurence=0;
while(isNumber(compressedString.charAt(i) )){
occurence = occurence*10+(compressedString.charAt(i)-48);
i++;
}
DecompressWrapper wrapper = new DecompressWrapper();
wrapper.setOccurence(occurence);
stack.add(wrapper);
i--;
}else if(compressedString.charAt(i)=='['){
continue;
}else if(compressedString.charAt(i)==']'){
DecompressWrapper wrapper1 = stack.pop();
DecompressWrapper wrapper2 = stack.peek();
int occ = wrapper1.getOccurence();
String dup = wrapper1.getDuplicates().toString();
while(occ>0){
wrapper2.getDuplicates().append(dup);
occ--;
}
}else{
DecompressWrapper wrapper = stack.peek();
wrapper.getDuplicates().append(compressedString.charAt(i));
}
}
return stack.pop().getDuplicates().toString();
}
private boolean isNumber(char c){
if(c>=48 && c<=57) return true;
return false;
}
private class DecompressWrapper{
private StringBuffer duplicates;
private int occurence;
public DecompressWrapper(){
this.duplicates = new StringBuffer();
}
public DecompressWrapper(StringBuffer duplicates, int occurence) {
this.duplicates = duplicates;
this.occurence = occurence;
}
public StringBuffer getDuplicates() {
return duplicates;
}
public void setDuplicates(StringBuffer duplicates) {
this.duplicates = duplicates;
}
public int getOccurence() {
return occurence;
}
public void setOccurence(int occurence) {
this.occurence = occurence;
}
}
}
My solution will give this result:
compressed String: A3[2[BC]E]G
decompressed String: ABCBCEBCBCEBCBCEG
Any optimization is welcome.
This is my solution:
package compressString;
import java.util.ArrayList;
import java.util.List;
public class Main {
private static List<Character> chars;
private static List<Integer> numberChars;
public static void main(String[] args) {
String word = "wwwwaaadexxxxxw"; // “Expected compressed outcome:
// w4a3d1e1x5w1”
System.out.println("Compressing word " + "(" + word + ") .......");
String wordCompressed = compressWord(word);
System.out.println("Word compressed: " + wordCompressed);
System.out.println("Descompresing word " + "(" + wordCompressed + ") .......");
String wordDescompressed = descompressWord(chars, numberChars);
System.out.println("Descompressed word: " + "(" + wordDescompressed + ")");
}
public static String compressWord(String word) {
chars = new ArrayList<Character>(); // Variable stores characters
numberChars = new ArrayList<Integer>(); // Variable stores number of
// repetition of characters
int subN = 0;
int repetitions = 0;
int index = 0;
String compressedWord = "";
for (int i = subN; i < word.length(); i = subN) {
char charToFind = word.charAt(i); // Character to find
for (int j = i; j < word.length(); j++) {
if (charToFind != word.charAt(j)) {
break;
} else {
subN++; // String iterator
repetitions++; // Counts how many times character is repeated
}
}
chars.add(charToFind);
numberChars.add(repetitions);
repetitions = 0; // reset repetitions
}
while (index < chars.size()) {
compressedWord = compressedWord + chars.get(index) + numberChars.get(index);
index++;
}
return compressedWord;
}
public static String descompressWord(List<Character> chars, List<Integer> numberChars) {
String wordDescompressed = "";
int index = 0;
while (index < chars.size()) {
for (int i = 0; i < numberChars.get(index); i++) {
wordDescompressed = wordDescompressed + chars.get(index);
}
index++;
}
return wordDescompressed;
}
}
This is the output of this program:
Compressing word (wwwwaaadexxxxxw) .......
Word compressed: w4a3d1e1x5w1
Descompresing word (w4a3d1e1x5w1) .......
Descompressed word: (wwwwaaadexxxxxw)
package compressString;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
String word = "wwwwaaadexxxxxw"; // “Expected compressed outcome:
// w4a3d1e1x5w1”
System.out.println("Compressing word " + "(" + word + ") .......");
String wordCompressed = compressWord(word);
System.out.println("Word compressed: " + wordCompressed);
System.out.println("Descompresing word " + "(" + wordCompressed + ") .......");
String wordDescompressed = descompressWord(wordCompressed);
System.out.println("Descompressed word: " + "(" + wordDescompressed + ")");
}
public static String compressWord(String word) {
List<Character> chars = new ArrayList<Character>(); // Variable stores characters
List<Integer> numberChars = new ArrayList<Integer>(); // Variable stores number of
// repetition of characters
int subN = 0;
int repetitions = 0;
int index = 0;
String compressedWord = "";
for (int i = subN; i < word.length(); i = subN) {
char charToFind = word.charAt(i); // Character to find
for (int j = i; j < word.length(); j++) {
if (charToFind != word.charAt(j)) {
break;
} else {
subN++; // String iterator
repetitions++; // Counts how many times character is
// repeated
}
}
chars.add(charToFind);
numberChars.add(repetitions);
repetitions = 0; // reset repetitions
}
while (index < chars.size()) {
compressedWord = compressedWord + chars.get(index) + numberChars.get(index);
index++;
}
return compressedWord;
}
public static String descompressWord(String word) {
String wordDescompressed = "";
int num = 0;
int index = 0;
List<Integer> number = new ArrayList<Integer>();
List<Character> chars = new ArrayList<Character>();
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) > '0' && word.charAt(i) < '9') {
num = Integer.parseInt(""+word.charAt(i));
number.add(num);
} else {
chars.add(word.charAt(i));
}
}
while (index < chars.size()) {
for (int i = 0; i < number.get(index); i++) {
wordDescompressed = wordDescompressed + chars.get(index);
}
index++;
}
return wordDescompressed;
}
}
---------------------------------------------------------------------------------------------
output:
Compressing word (wwwwaaadexxxxxw) .......
Word compressed: w4a3d1e1x5w1
Descompresing word (w4a3d1e1x5w1) .......
Descompressed word: (wwwwaaadexxxxxw)
Any optimization is welcome.
My Javascript code
function strcompe(s){
let i = 0;
let out = '';
let c = s[i];
out+= c;
let j =1;
while(i<s.length){
if(c===s[i+1]){
j++;
i++;
}else{
out+=j;
if(s[i+1]){
c = s[i+1];
out+= c;
}
j =1;
i++;
}
}
return out;
}
function strdecompreess(s){
let i = 0;
let out = '';
while(i<s.length){
for(let j=0; j<parseInt(s[i+1]);j++){
out+=s[i];
}
i = i+2;
}
return out;
}
let s = 'aaaabbebbccdddee';
s = strcompe(s);
console.log(s);
s = strdecompreess(s);
console.log(s)
javascript solution
function compress(x) {
let str =[];
let count =1;
let lastChar = x.charAt(0);
for(let i=1; i <x.length; i++){
if(x[i] === x[i-1]) {
count++;
} else {
str.push(`${lastChar}${count}`);
count = 1;
lastChar = x.charAt(i);
}
}
//add the last one
str.push(`${lastChar}${count}`);
return str.join('');
}
function decompress(x) {
let str= [];
for(let i=0; i <x.length - 1; i = i+2) {
str.push(append(x[i], x[i+1]));
}
return str.join('');
}
function append(char, time) {
let chars = "";
while(time > 0) {
chars += char;
time --;
}
return chars;
}
var compressed = compress("WWWWVVVVTRTYUUUUI");
console.log(compressed)
compressed = decompress(compressed);
console.log(compressed)
Compress:
In [8]: def c(a):
...: r = ''
...: c = 1
...: for i in range(1, len(a)):
...: if a[i-1] == a[i]:
...: c += 1
...: else:
...: r += a[i-1] + str(c)
...: c = 1
...: r += a[i] + str(c)
...: return r
Decompress:
In [31]: def de(a):
...: r = ''
...: for i in range(1, len(a), 2):
...: # print(a[i-1], a[i])
...: r += (a[i-1] * int(a[i]))
...: return ''.join(r)
Example:
In [35]: c('aaabbbccceeddaacadfakjlc')
Out[35]: 'a3b3c3e2d2a2c1a1d1f1a1k1j1l1c1'
In [36]: de('a3b3c3e2d2a2c1a1d1f1a1k1j1l1c1')
Out[36]: 'aaabbbccceeddaacadfakjlc'
public static String compressString(String strInput) {
char[] chInput = strInput.toCharArray();
char chTemp = chInput[0];
String strCompressed = "";
int ind = 1;
for(int i=1; i<chInput.length; i++) {
if(chTemp == chInput[i]) {
ind++;
} else {
strCompressed += "" + chTemp + ind;
ind = 1;
chTemp = chInput[i];
}
}
strCompressed += "" + chTemp + ind;
return strCompressed;
}
public static String deCompressString(String strCompInput) {
String strDecompressed = "";
for(int i=0; i<strCompInput.length(); i = i+2) {
for(int j=0; j<Character.getNumericValue(strCompInput.charAt(i+1)); j++) {
strDecompressed += "" + strCompInput.charAt(i);
}
}
return strDecompressed;
}
package Careercup;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
public class CompressString {
public static void main(String[] args) {
String test="aabbccc";
char[] c= test.toCharArray();
HashMap<Character,Integer> m =new HashMap();
for(char i: c)
{
if(!m.containsKey(i))
{
m.put(i, 1);
}
else
{
m.put(i, m.get(i)+1);
}
}
System.out.println("Compressed:");
for(Map.Entry<Character, Integer> i :m.entrySet())
{
System.out.println(i.getKey()+""+i.getValue());
}
System.out.println("Decompressed");
for(Map.Entry<Character, Integer> i :m.entrySet())
{
int count=i.getValue();
while(count>=1)
{
System.out.println(i.getKey());
count--;
}
}
}
}
package Careercup;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
public class CompressString {
public static void main(String[] args) {
String test="aabbccc";
char[] c= test.toCharArray();
HashMap<Character,Integer> m =new HashMap();
for(char i: c)
{
if(!m.containsKey(i))
{
m.put(i, 1);
}
else
{
m.put(i, m.get(i)+1);
}
}
System.out.println("Compressed:");
for(Map.Entry<Character, Integer> i :m.entrySet())
{
System.out.println(i.getKey()+""+i.getValue());
}
System.out.println("Decompressed");
for(Map.Entry<Character, Integer> i :m.entrySet())
{
int count=i.getValue();
while(count>=1)
{
System.out.println(i.getKey());
count--;
}
}
}
}
- Anonymous February 09, 2017