Amazon Interview Question for Quality Assurance Engineers


Country: United States
Interview Type: Phone Interview




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

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);
	}

- Anonymous February 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

- swamy February 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Felipe Cerqueira February 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ]

- NoOne February 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How to compress "ABCBCEBCBCEBCBCE" to "A3[2[BC]E]"?

- yankeson2013 February 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous February 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- yankeson2013 February 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Jose. February 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jose R. February 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- pinn.chait February 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Huffman coding

- rd22 March 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- rocks May 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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'

- Anon March 03, 2018 | 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