Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
This type of question is to test if you can come up with all possible scenarios.
- Is it OK to have encoded string larger than original string? Input "a" can be represented as "a1"
- How are you going to escape input string? Input "a2" should be handled because it will be decoded as "aa"
Since string is immutable a new object is created for every operation and assigned to output. The problem however nowhere mentions any efficiency limitations, to make it more efficient you can use StringBuffer.
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class CountCharSeq {
private Map<String,CountSeq> container = new TreeMap<String,CountSeq>();
public static void main(String[] args){
CountCharSeq seq = new CountCharSeq();
seq.printSequence();
}
public CountCharSeq(){
String test = "aaaabbbcccddeggggggggggg";
for(int i=0; i < test.length(); i++){
CountSeq seq = new CountSeq(String.valueOf(test.charAt(i)));
add(seq);
}
}
public void add(CountSeq num){
CountSeq seq = container.get(num.value);
if(seq == null){
container.put(num.value, num);
} else {
seq.count += 1;
}
}
public void printSequence(){
StringBuilder sb = new StringBuilder();
for(Map.Entry<String, CountSeq> entry : container.entrySet()){
sb.append(entry.getKey()+""+entry.getValue().count);
}
System.out.println(sb.toString());
}
private class CountSeq {
private int count;
private String value;
public CountSeq(String value){
this.count = 1;
this.value = value;
}
}
}
int main()
{
char *str = "abcdeeffffghiijjkklmmmmmnoop";
encodeString( str);
}
void encodeString( char *str )
{
char currentChar = str[0];
int cnt = 1;
cout << currentChar;
for( int index = 1; index < (int)strlen( str ); index++ )
{
if( currentChar != str[index] )
{
currentChar = str[index];
cout << cnt;
cout << currentChar;
cnt = 1;
}
else
{
cnt++;
}
}
cout << cnt << endl;
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
void stringEncoding(const char* str, size_t length, std::stringstream& sstream)
{
int sameCharacterCount = 1;
// since str[length] is '\0', so no charactor will equal to it
// we can use it as the safeguard
for(size_t index = 0; index < length; index++)
{
if (str[index] != str[index+1])
{
sstream << str[index] << sameCharacterCount;
// reset sameCharacterCount
sameCharacterCount = 1;
}
else
{
sameCharacterCount++;
}
}
}
int main()
{
string input;
cout << "please enter the string" << endl;
while(cin >> input)
{
stringstream sstream;
stringEncoding(input.c_str(), input.size(), sstream);
cout << sstream.str() << endl;
}
}
def encodeStr(astr):
"""Encode astr in the specified format
>>> encodeStr('aabbaadddc')
'a2b2a2d3c1'
"""
counter = 0
currentLetter = '///'
encodedStr = ''
for char in astr:
if currentLetter != '///':
if char == currentLetter:
counter = counter + 1
else:
encodedStr = encodedStr + currentLetter + str(counter)
counter = 1
currentLetter = char
elif currentLetter == '///':
counter = 1
currentLetter = char
return encodedStr + currentLetter + str(counter)
if __name__ == '__main__':
import doctest
doctest.testmod()
IMHO solving this algo with an extra space is relatively easier. So I have tried to implement the solution with modifying the given string(although this constraint doesn't seem to be given in the problem statement). Here's the sample code:
private static String countLetters(StringBuilder str){
StringBuilder str2 = new StringBuilder();
int count = 1, position = 1;
for (int i = 0; i < str.length() - 1 ; i++) {
if(str.charAt(i) == str.charAt(i+1)){
count++;
}
else{
StringBuilder temp = new StringBuilder();
temp.append(count);
temp.append(str.charAt(i+1));
str.insert(position, temp);
i += 2;
position += 2;
count = 1;
}
}
str.insert(position++, count);
str.delete(position, str.length());
return str.toString();
}
Solution using recursion:
static String getStringAbbr(String input, String output, int position)
{
if(input.length() == position)
return output;
int count = 1;
while(position + 1 < input.length() && input.charAt(position) == input.charAt(position + 1))
{
position++;
count++;
}
output =output + input.charAt(position ) + count;
return getStringAbbr(input, output, position +1 );
}
String str = "aaaabbccddedd";
ArrayList list = new ArrayList();
int count = 1;
for(int i = 0; i < str.length() ; i++) {
if(i != 0 && str.charAt(i-1) == str.charAt(i) ) {
++count;
list.remove(""+str.charAt(i)+":"+(count-1));
list.add(""+str.charAt(i)+":"+count);
}else {
count=1;
list.add(""+str.charAt(i)+":"+count);
}
}
System.out.println(list);
public class StringCompression {
public static void main(String[] args) {
String input = "aabbaadddc";
System.out.println("Compressed String " + compressString(input));
}
private static StringBuilder compressString(String input) {
char[] charArray= input.toCharArray();
StringBuilder output = new StringBuilder();
char lastVisited = charArray[0];
int count = 1;
for (int i = 1; i < charArray.length; i++) {
System.out.println(charArray[i]);
if (charArray[i] == lastVisited) {
count++;
} else {
output.append(lastVisited);
output.append(count);
count = 1;
lastVisited = charArray[i];
}
}
output.append(lastVisited);
output.append(count);
return output;
}
}
int main()
{
char *str = "abcdeeffffghiijjkklmmmmmnoop";
encodeString( str);
}
void encodeString( char *str )
{
char currentChar = str[0];
int cnt = 1;
cout << currentChar;
for( int index = 1; index < (int)strlen( str ); index++ )
{
if( currentChar != str[index] )
{
currentChar = str[index];
cout << cnt;
cout << currentChar;
cnt = 1;
}
else
{
cnt++;
}
}
cout << cnt << endl;
Yet another Python Implementation with O(n) space and time.
def encoding(s):
count = 1
current = 0
next = 1
arr = list()
while current < len(s)-1:
if (s[current] == s[next]):
count += 1
if next == len(s)-1:
arr.append(s[current]+str(count))
else:
arr.append(s[current]+str(count))
count = 1
current = next
next = next + 1
return ''.join(arr)
It is not a compression algorithm because they still want a single character to map to <char>1.
If they had allowed single character to map to single character without a count 1 following it, then it would be a compression algorithm (not simply an encoding), and you would be able to do it inplace.
public class Encode1 {
public static void main(String[] args){
String input = "aabbaadddc";
final int inputLength = input.length();
char[] inputChars = (input+" ").toCharArray();
char[] encodedChars = new char[inputChars.length * 2];
int eIndex = 0;
int count = 1;
for(int i = 0; i < inputLength; ++i){
if(inputChars[i] == inputChars[i+1]) count ++;
else {
encodedChars[eIndex++] = inputChars[i];
encodedChars[eIndex++] = (char) (48 + count);
count = 1;
}
}// for(i=0..inputChars.length)
System.out.println("Input: " +input);
System.out.println("Output: " +new String(encodedChars, 0, eIndex));
}// end of main
}// end of class Encode1
String in = "aabbw88wXXXXXwwrrrrdsyy99887881";
String res="";
char[] ch = in.toCharArray();
int i = 0;
while(i < ch.length){
int j;
for(j=i;j < ch.length ;j++){
if(ch[i]==ch[j])
continue;
else
break;
}
res += ch[i] + String.valueOf(j-i);
i = j;
}
System.out.println(in);
System.out.println(res);
private static String encode(String str)
{
HashMap<Character,Integer> hash = new HashMap<Character,Integer>();
for(int i=0; i<str.length();i++)
{
if(hash.containsKey(str.charAt(i)))
{
hash.put(str.charAt(i), hash.get(str.charAt(i))+1);
}
else
{
hash.put(str.charAt(i),1);
}
}
Set<Character> set = hash.keySet();
StringBuffer sb = new StringBuffer();
for(char c : set)
{
sb.append(hash.get(c));
sb.append(c);
}
sb.reverse();
return sb.toString();
}
public static String encodeString(String format){
char [] chs=format.toCharArray();
int [] dp =new int [chs.length];
//for the result
StringBuilder sb=new StringBuilder();
// the initial value is 1
dp[0] =1 ;
sb.append(chs[0]);
for (int i =1 ; i< chs.length ; ++i){
if (chs[i]==chs[i-1]){
dp[i] = dp[i-1]+1 ;
}else{
sb.append(new Integer(dp[i-1]));
//add a new start
sb.append(chs[i]);
dp[i]=1;
}
}
sb.append(dp[chs.length-1]);
return sb.toString();
}
C++ version:
string encode_str(const string &s1) {
string s2;
char prev = 0;
int count = 0;
for (int i = 0; i <= s1.size(); i++) {
if (i != 0 && (prev != s1[i] || i == s1.size())) {
stringstream ss;
ss << count;
s2 += prev;
s2 += ss.str();
count = 0;
}
prev = s1[i];
count++;
}
return s2;
}
public class CountCharSeqInLoop {
// "AAAAABBBBBAA" -> "5A5B2A"
private String test = "AAAAABBBBBAACCCCCCCCCCRR";
private StringBuilder runningString = new StringBuilder();
public static void main(String[] args) {
CountCharSeqInLoop t = new CountCharSeqInLoop();
t.traverseUpString();
}
private void traverseUpString() {
String prev = String.valueOf(test.charAt(0));
int count = 0;
String current;
for (int i = 0; i < test.length(); i++) {
current = String.valueOf(test.charAt(i));
if ( !prev.equalsIgnoreCase(current) ) {
runningString.append(count).append(prev);
count = 0;
}
prev = current;
count++;
}
System.out.println(runningString.append(count).append(prev));
}
}
C++ version.
#include <iostream>
#include <string>
std::string encode(const std::string& str) {
if (str.empty())
return "";
std::string encoded;
encoded.reserve(str.size());
char last_ch = str[0];
int n = 1;
for (size_t i = 1; i < str.size(); i++) {
char ch = str[i];
if (ch != last_ch) {
encoded.push_back(last_ch);
encoded.append(std::to_string(n));
last_ch = ch;
n = 1;
} else {
n++;
}
}
encoded.push_back(last_ch);
encoded.append(std::to_string(n));
return encoded;
}
int main() {
std::cout << encode("aabbaadddc");
return 0;
}
public class Encoding {
public static void main(String[] args) {
String x=" ";
String s="aaccbbddeedd8888888888";
s=s+" ";
char[] c=s.toCharArray();
String p="";
for(int i=0;i<c.length;i++)
{
int k=1;
if(i+1<c.length)
{
while(c[i]==c[i+1])
{
k++;
i++;
}
String l= Integer.toString(k);
p=c[i]+l;
x=x+p;
//System.out.print(x);
}
}
System.out.println(x);
}
}
Use two pointers, one points to the start of a substring made of a new character, the other moves backwards and record the repeat times till meet the first character not the same. Following is C code:
#include <stdio.h>
#define MAX 100
char* Encode(char* dest, const char* src)
{
if(src == NULL || *src == '\0'){
*dest = '\0';
return dest;
}
int times = 0;
char* t = dest, c;
const char* p;
for(; c = *src; src = p){
for(p = src+1, times = 1; *p != '\0' && *p == c; ++p, ++times) ;
*t++ = c;
t += sprintf(t, "%d", times);
}
return dest;
}
int main()
{
char dest[MAX], *src = "babbaaaaaaaaaaaaaaaaadddc";
Encode(dest, src);
puts(dest);//output is b1a1b2a17d3c1
return 0;
}
- fReaK November 07, 2013String test = "aabbbcccdde"; String output = ""; int count = 1; test = test + " "; for (int i = 0; i < test.length() - 1; i++) { if (count == 1) output = output + test.charAt(i); if (test.charAt(i + 1) == test.charAt(i)) { count++; continue; } output = output + count; count = 1; } System.out.println(output);