Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
edit:
I forgot to update currentChar to readed char on the "else" part of the for loop, also the readedPointer var is unecesary because the "i" in the for loop serves the same purpose.
C++ solution.
1. Have two counters -- readIndex and writeIndex
2. If writeIndex is ahead of readIndex move characters to a temporary buffer
void output(string &s, string &temp, int &readIndex, int &writeIndex, int count, char ch) {
s[writeIndex++]=ch;
string countStr = to_string(count);
for(int i = 0; i < countStr.size(); i++) {
if(writeIndex == readIndex) {
temp.push_back(s[readIndex]);
readIndex++;
}
s[writeIndex] = countStr[i];
writeIndex++;
}
}
void compress(string &s) {
char prevChar = s[0];
char currentChar;
int count = 1;
string temp;
int tempIndex = 0;
int readIndex = 1;
int writeIndex = 0;
s.push_back('\0');
while(readIndex < s.size()) {
currentChar = s[readIndex++];
if(currentChar != prevChar) {
output(s,temp,readIndex,writeIndex,count,prevChar);
count = 1;
} else {
count++;
}
prevChar = currentChar;
while (tempIndex < temp.size())
{
currentChar = temp[tempIndex++];
if(currentChar != prevChar) {
output(s,temp,readIndex,writeIndex,count,prevChar);
count = 1;
} else {
count++;
}
prevChar = currentChar;
}
}
s.resize(writeIndex);
}
The same solution as above with a bug corrected
void output(string &s, string &temp, int &readIndex, int &writeIndex, int count, char ch) {
if(readIndex == writeIndex) {
temp.push_back(s[readIndex]);
readIndex++;
}
s[writeIndex]=ch;
writeIndex++;
string countStr = to_string(count);
for(int i = 0; i < countStr.size(); i++) {
if(writeIndex == readIndex) {
temp.push_back(s[readIndex]);
readIndex++;
}
s[writeIndex] = countStr[i];
writeIndex++;
}
}
void compress(string &s) {
char prevChar = s[0];
char currentChar;
int count = 1;
string temp;
int tempIndex = 0;
int readIndex = 1;
int writeIndex = 0;
s.push_back('\0');
while(readIndex < s.size()) {
currentChar = s[readIndex++];
if(currentChar != prevChar) {
output(s,temp,readIndex,writeIndex,count,prevChar);
count = 1;
} else {
count++;
}
prevChar = currentChar;
while (tempIndex < temp.size())
{
currentChar = temp[tempIndex++];
if(currentChar != prevChar) {
output(s,temp,readIndex,writeIndex,count,prevChar);
count = 1;
} else {
count++;
}
prevChar = currentChar;
}
}
s.resize(writeIndex);
}
The objective C solution to this,
NSMutableString *finalValue = [NSMutableString new];
__block int count = 1;
__block NSString *currentCharStr = [[NSString alloc]initWithString:[inputString substringWithRange:NSMakeRange(0, 1)]];
[inputString enumerateSubstringsInRange:NSMakeRange(1, inputString.length-1) options:NSStringEnumerationByComposedCharacterSequences usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) {
if ([currentCharStr isEqualToString:substring]) {
count++;
}else{
[finalValue appendFormat:[NSString stringWithFormat:@"%@%d",currentCharStr,count]];
count = 1;
currentCharStr = substring;
}
if (substringRange.location==inputString.length-1) {
[finalValue appendFormat:[NSString stringWithFormat:@"%@%d",currentCharStr,count]];
}
}];
Hi all, this is my first submission! Here's the implementation in Java.
The drawback of this implementation I see, is that it duplicates the memory of input string by splitting it into a char array.
Suggestion for improvements are welcomed.
private static void runtimeLengthCode(String data) {
if (data.length() < 1) {
return;
}
char[] a = data.toCharArray();
char currentChar = a[0];
int count = 1;
StringBuilder result = new StringBuilder();
for (int i = 1; i < a.length; i++) {
if (currentChar == a[i]) {
count++;
} else {
result.append(currentChar).append(count);
currentChar = a[i];
count = 1;
}
}
result.append(currentChar).append(count);
System.out.println(result.toString());
}
}
This code is using extra memory.As per the problem description only input array needs to be edited to store the output result. Let me know if i am missing anything.
It can be solved using HashMap,
public static String charLength(String str) {
Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i<str.length(); i++) {
if(map.get(str.charAt(i)) == null)
map.put(str.charAt(i), 1);
else
map.put(str.charAt(i), map.get(str.charAt(i)) + 1);
}
String temp = "";
for(Map.Entry<Character, Integer> m : map.entrySet()) {
temp += m.getKey().toString() + m.getValue();
}
return temp;
}
This is a working code in Java :
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class DuplicateAlphas {
public static void main(String args[])
{
String str="ABBCDEFGGGGGGGGHHXXXYY";
char ch[]=str.toCharArray();
Map m = new LinkedHashMap<Character,Integer>();
for(int i=0;i<ch.length;i++)
{
if(m.containsKey(ch[i]))
{
int count=Integer.parseInt(m.get(ch[i]).toString())+1;
m.put(ch[i], count);
}
else
m.put(ch[i], 1);
}
Set k = m.keySet();
Iterator it = k.iterator();
while(it.hasNext())
{
Object key = it.next();
System.out.println(key+""+m.get(key));
}
}
}
/*
Write an algorithm to convert the given input string to the expected output string. The input string shall be the length of few million characters. So the output has to be updated in the same string...
Input String = "ABBCDEFGGGGGGGGHHXX..<20 more X>..XYY..."
Expected output = "A1B2C1D1E1F1G8H2X23Y2..."
Note: The count of each character has to be appended with the same character in the output string
*/
public class Problem1 {
/**
* @param args
*/
public String appendFrequency(String s)
{
String result="";
char c[]=s.toCharArray();
int count=0;
int i=0;
char x=c[0];
while(i<c.length)
{
count=0;
x=c[i];
while(i<c.length && c[i]==x)
{
count++;
i++;
}
result=result+x+count;
}
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(new Problem1().appendFrequency("aabbbbbcccdd"));
}
}
/*
Write an algorithm to convert the given input string to the expected output string. The input string shall be the length of few million characters. So the output has to be updated in the same string...
Input String = "ABBCDEFGGGGGGGGHHXX..<20 more X>..XYY..."
Expected output = "A1B2C1D1E1F1G8H2X23Y2..."
Note: The count of each character has to be appended with the same character in the output string
*/
public class Problem1 {
/**
* @param args
*/
public String appendFrequency(String s)
{
String result="";
char c[]=s.toCharArray();
int count=0;
int i=0;
char x=c[0];
while(i<c.length)
{
count=0;
x=c[i];
while(i<c.length && c[i]==x)
{
count++;
i++;
}
result=result+x+count;
}
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(new Problem1().appendFrequency("aabbbbbcccdd"));
}
}
I made it by java.
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(compressString("ABBCCCAAAADDDZZZZZZZZZXWW"));
}
private static String compressString(String original) {
int length = original.length();
String returnValue = "";
char curChar = ' ';
int count = 0;
for (int index = 0; index < length; index++) {
char tmpChar = original.charAt(index);
if (index == 0) {
curChar = tmpChar;
count = 1;
} else if (tmpChar == curChar) {
count++;
} else {
returnValue += (curChar+""+count);
curChar = tmpChar;
count = 1;
}
}
return returnValue;
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(compressString("ABBCCCAAAADDDZZZZZZZZZXWW"));
}
private static String compressString(String original) {
int length = original.length();
String returnValue = "";
char curChar = ' ';
int count = 0;
for (int index = 0; index < length; index++) {
char tmpChar = original.charAt(index);
if (index == 0) {
curChar = tmpChar;
count = 1;
} else if (tmpChar == curChar) {
count++;
} else {
returnValue += (curChar+""+count);
curChar = tmpChar;
count = 1;
}
if (index == length -1) {
returnValue += (curChar+""+count);
}
}
return returnValue;
}
}
I have tried with ASCII value and here is the solution:
input: "AABBCCCDDDEEFFGGGHH"
output:"A2B2C3D3E2F2G3H2"
public class StringPgm {
public static void main(String[] args) {
String s = "AABBCCCDDDEEFFGGGHH";
char[] c = s.toCharArray();
int count=0;
for (int i = 65; i <=90; i++)
{
for(int j = 0; j < c.length; j++)
{
if(i==c[j])
{
count++;
}
}
if(count>0){
System.out.print((char)i+""+count);
count=0;
}
}
}
}
This is known as Runtime Length Encoding, a common image compression algorithm for bitmaps, the first pertinent question for the interviewer will be to ask if the output string always has enough space, why?
well because what is the input string is "ABCD" length 4, the output will be "A1B1C1D1" length 8, in this case the program would not work due to the "inplace" space requirements.
the proposed solution assumes that theres actually enough space to store the result string inside the input, so no defensive coding techniques where applied.
the meat of the algorithm requires a few variables,
writing pointer: where in the string I need to write
Read pointer: current read position on input string
current character: current value from read pointer
current character count: amount of times current character appears after itself
initialize all pointers, read first character and increment read pointer, start at position number 1 in the string (first char is at position 0).
for each character in the string...
update current character
advance read pointer
if( currentCharacter == readCharacter)
increment currentCharCount
else
save the value at write pointer,
advance write pointer
set currentChar = readChar
reset currentCharCount = 0
in C++ they code will look something like
void RuntinmeLengthEncode(string &data) { unsigned long long writePointer, readPointer, currentCharCount;//in case we go from a few million to a couple million char readed, currentChar; //sanity checks first if (data.length() < 1 ) return; currentChar = data[0]; currentCharCount = 0; writePointer = 0; readPointer = 0; for(int i = 1; i < data.length(); i++){ readed = data[i]; if (currentChar == readed ){ currentCharCount++; } else { data[writePointer] = currentChar; string currentCharCountString = toString( currentCharCount ); data[writePointer + 1] = currentCharCountSTring; writePointer = writePointer + 1 + currentCharCountString.length(); } } }A word of caution will be when updating the string with the character count before moving to the next character, an edge case could what would happen if the integer representation of the currentcharacter count overwrites somo unread character?
- RED November 14, 2014again pardon my french, code typed directly into reply box