Amazon Interview Question
Country: United States
Here is a Python implementation:
# wildcad used for digits in string
WILDCARD = "_"
def _compress_n_times(char, count, output):
"""
Helper to append "char" exactly "count" times to "output".
"""
if count > 1:
output += str(count)
if char.isdigit():
output += WILDCARD
output += char
return output
def compress_string(value):
"""
Compress a string by using the counts of repeated characters.
Caveat: adds exactly 1 WILDCARD for each series of digits.
"""
output = ""
previous = None
count = 0
for char in value:
if previous is None:
count = 1
elif previous == char:
count += 1
elif count > 0:
output = _compress_n_times(previous, count, output)
count = 1
previous = char
if previous is not None:
if count == 0:
raise RuntimeError("Reached the end of compression with empty count and previous character.")
output = _compress_n_times(previous, count, output)
return output
def decompress_string(value):
"""
Decompress a string by using the counts of repeated characters.
"""
output = ""
count_digits = ""
previous_was_wildcard = False
for char in value:
if char == WILDCARD:
previous_was_wildcard = True
continue
if char.isdigit():
if previous_was_wildcard:
output += char * int(count_digits or 1)
count_digits = ""
previous_was_wildcard = False
else:
count_digits += char
else:
output += char * int(count_digits or 1)
count_digits = ""
return output
// Here is a Java Implementation
public String unMask(String str) {
String unMaskedStr="";
for(int currentIndex=0;currentIndex<str.length();currentIndex++) {
char ch=str.charAt(currentIndex);
/* if(!Character.isDigit(ch)) {
continue;
}*/
int number=0;
while(Character.isDigit(str.charAt(currentIndex))) {
number = number * 10 + (str.charAt(currentIndex)-48);
currentIndex++;
}
int nextIndex=currentIndex;
char chAtNextIndex= str.charAt(nextIndex);
if(chAtNextIndex=='\\') {
chAtNextIndex= str.charAt(++nextIndex);
}
for(int i=0;i<number;i++) {
unMaskedStr=unMaskedStr+chAtNextIndex;
}
currentIndex=nextIndex;
}
return unMaskedStr;
}
public String mask(String str) {
String maskedSTR="";
for(int currentIndex=0;currentIndex<str.length();) {
char ch=str.charAt(currentIndex);
int nextIndex=currentIndex+1;
int count =1;
while(nextIndex<str.length() && ch==str.charAt(nextIndex)) {
count++;
nextIndex++;
}
if(Character.isDigit(ch))
maskedSTR=maskedSTR+count+"\\"+ch;
else
maskedSTR=maskedSTR+count+ch;
currentIndex=nextIndex;
}
return maskedSTR;
}
Recursive + Non-Recursive Approach:
def get_count(n, start=0, count=0, pointer=0):
if pointer >= len(s):
return count
if s[pointer] != n:
if not count:
return get_count(n, start+1, count, pointer+1)
else:
return count
else:
return get_count(n, start, count+1, pointer+1)
s = "aaaaaaaaaaaaaa2aaa__abccaccccccccccc_aaaa_a;aaczzzzzzz__ccccccc______dcccccssssd_2zzzzzzzzzzzzzzdaaa"
output = ""
def compress():
prev = " "
global output
for _ in range(len(s)):
if s[_] != prev:
c = get_count(s[_], _, 0, _)
if s[_].isdigit():
output += f"_{c}_{s[_]}_"
else:
output += f"{c}{s[_]}"
prev = s[_]
print(output)
def decompress_recursive(o, pointer=0): # Recursice Approach
if pointer >= len(output):
return o
if output[pointer].isdigit():
temp = output[pointer]
pointer += 1
while output[pointer].isdigit():
temp += output[pointer]
pointer += 1
return decompress_recursive(o+output[pointer]*int(temp), pointer+1)
elif output[pointer] == "_":
return decompress_recursive(o+output[pointer+3]*int(output[pointer+1]), pointer+5)
def decompress_non_recursive(): # Non Recursice Approach
i = iter(output)
prev = ""
while True:
try:
x = next(i)
prev = x
temp = ""
if x.isdigit():
while x.isdigit():
temp += x
prev = x
x = next(i)
if x != "_":
print(x*int(temp), end="")
if x == "_":
if prev.isdigit():
print("_"*int(prev), end="")
continue
temp = ""
x = next(i)
if x.isdigit():
while x.isdigit():
temp += x
x = next(i)
z = next(i)
next(i)
print(z*int(temp), end="")
except StopIteration:
return
print("Original : ", end="")
print(s)
print("After Compression : ", end="")
compress()
print("After Decompression : ", end="")
print(decompress_recursive("", 0))
print("After Decompression1 : ", end="")
decompress_non_recursive()
public class T6 {
private static String input = "ab2ccccd";
private static String result = new String();
public static void main(String[] args) {
int count = 0;
int sameCount = 1;
processing(count, sameCount);
System.out.println(result);
}
private static void processing(int count, int sameCount) {
if (count > input.length() - 1)
return;
if (checkNext(count) == true) {
sameCount++;
} else {
if (sameCount > 1) {
result += sameCount;
}
sameCount = 1;
result += input.charAt(count);
}
count++;
processing(count, sameCount);
}
private static boolean checkNext(int count) {
Boolean retVal = false;
if (count + 1 > input.length() - 1)
return false;
String getString = String.valueOf(input.charAt(count));
String getNextString = String.valueOf(input.charAt(count + 1));
if (getString.equalsIgnoreCase(getNextString))
retVal = true;
return retVal;
}
}
- Ashis Kumar Chanda December 19, 2019public String encode(String input){ if(null== input) return null; input = input.toLowerCase(); char[] array = input.toCharArray(); StringBuffer encoded = new StringBuffer(array.length); int prevCount=1; char prev = array[0]; for(int i =1; i < array.length; i++){ char curr = array[i]; if(prev == curr){ prevCount++; }else if(prev != curr){ if(prevCount ==1){ encoded.append(prev); }else{ if(prev=='0' || prev =='1' || prev == '3'|| prev=='4' || prev =='5' || prev =='6'|| prev=='7' || prev =='8' || prev =='9'){ encoded.append("_").append(prevCount).append(prev); }else{ encoded.append(prevCount).append(prev); } } prevCount=1; } prev = curr; } //for last character if(prevCount ==1){ encoded.append(prev); }else{ if(prev=='0' || prev =='1' || prev == '3'|| prev=='4' || prev =='5' || prev =='6'|| prev=='7' || prev =='8' || prev =='9'){ encoded.append("_").append(prevCount).append(prev); }else{ encoded.append(prevCount).append(prev); } } return encoded.toString(); }