Amazon Interview Question Senior Software Development Engineers
Country: India
Interview Type: In-Person
The problem only asks for a count, so it would be more efficient to use dynamic programming:
A(i) = A(i+1) + (substr(i,i+2) < '26' ? A(i+2) : 0)
where A(i) is how many ways you can decode the tail substring starting at i.
Thus, the answer is stored in A(0) and runs in O(n) time where n is the length of the string, as opposed to generating all combinations in O(2^n) time.
What language is that? I am asking because if it is automatically saving the results of sub problems this is the simplest solution on the block and quite frankly the cleanest solution posted.
Either way, this is the backtracking solution in a language like C++/Java that can be modified to the DP solution suggested.
a Java implementation of this algorithm
public class DecodeNumberCount {
public static int getCount(String s, int i) {
System.out.println("i: "+i);
if(i+2 > s.length()) return 1;
else
return getCount(s, i+1) + (stringToChar(s.substring(i, i+2)) < 26 ? getCount(s, i+2) : 0);
}
private static int stringToChar(String s) {
int result = 0;
char[] chars = s.toCharArray();
for(int i=0;i<chars.length;i++) {
result = result*10 + chars[i]-'0';
}
System.out.println(result);
return result<256 ? result : 0;
}
public static void main(String[] args){
String s = "29292929";
System.out.println("Total Count: "+getCount(s, 0));
}
}
Hi,
Using Java I found a solution.Doont know whether its an optimal solution or not.
package com.karthik.samples;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeSet;
public class Test2 {
/**
* @param args
*/
Hashtable<Integer, Character> map = new Hashtable<Integer, Character>();
TreeSet list = new TreeSet();
public static void main(String[] args) {
Test2 test = new Test2();
test.method();
}
public void method() {
char[] alphabet = "abcdefghijklmnopqrstuvwxyz".toCharArray();
for (int i = 1; i <= 26; i++) {
map.put(i, alphabet[i - 1]);
}
int c = 1;
Scanner in = new Scanner(System.in);
System.out
.println("Please enter the characters that you want to encrypt :");
String input = in.nextLine();
for (int i = 0; i < input.length(); i++) {
recursion(input, i, i + 1);
recursion(input, i, i + 2);
}
System.out.println(list);
}
public void recursion(String input, int start, int end) {
if (end > input.length()) {
return;
}
String twochrs = input.substring(start, end);
int key = Integer.parseInt(twochrs);
if (key > 26) {
String strNum = Integer.toString(key);
int[] digits = getDigitsOf(key);
list.add(map.get(digits[0]));
list.add(map.get(digits[1]));
} else {
key = Integer.parseInt(twochrs);
list.add(map.get(key));
}
}
public int[] getDigitsOf(int num) {
int digitCount = Integer.toString(num).length();
if (num < 0) {
digitCount--;
}
int[] result = new int[digitCount];
while (digitCount-- > 0) {
result[digitCount] = num % 10;
num /= 10;
}
return result;
}
}
package com.karthik.samples;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeSet;
public class Test2 {
/**
* @param args
*/
Hashtable<Integer, Character> map = new Hashtable<Integer, Character>();
TreeSet list = new TreeSet();
public static void main(String[] args) {
Test2 test = new Test2();
test.method();
}
public void method() {
char[] alphabet = "abcdefghijklmnopqrstuvwxyz".toCharArray();
for (int i = 1; i <= 26; i++) {
map.put(i, alphabet[i - 1]);
}
int c = 1;
Scanner in = new Scanner(System.in);
System.out
.println("Please enter the characters that you want to encrypt :");
String input = in.nextLine();
for (int i = 0; i < input.length(); i++) {
recursion(input, i, i + 1);
recursion(input, i, i + 2);
}
System.out.println(list);
}
public void recursion(String input, int start, int end) {
if (end > input.length()) {
return;
}
String twochrs = input.substring(start, end);
int key = Integer.parseInt(twochrs);
if (key > 26) {
String strNum = Integer.toString(key);
int[] digits = getDigitsOf(key);
list.add(map.get(digits[0]));
list.add(map.get(digits[1]));
} else {
key = Integer.parseInt(twochrs);
list.add(map.get(key));
}
}
public int[] getDigitsOf(int num) {
int digitCount = Integer.toString(num).length();
if (num < 0) {
digitCount--;
}
int[] result = new int[digitCount];
while (digitCount-- > 0) {
result[digitCount] = num % 10;
num /= 10;
}
return result;
}
}
int decodeRec(int array[], int index, int size)
{
if(index == size)
return 0;
int count = 0;
for(int len = 1; len <=2; len++)
{
int num = 0;
for(int j = 0; j < len; j++)
num = num*10+array[index+j];
if(num >= 1 && num <= 26)
{
int subCount = decodeRec(array, index+len, size);
if(subCount == 0)//leaf
count += 1;
else
count += subCount;
}
}
return count;
}
int decode(int array[], int size)
{
return decodeRec(array, 0, size);
}
int decodeRec(int array[], int index, int size)
{
if(index == size)
return 0;
int count = 0;
for(int len = 1; len <=2; len++)
{
int num = 0;
for(int j = 0; j < len; j++)
num = num*10+array[index+j];
if(num >= 1 && num <= 26)
{
int subCount = decodeRec(array, index+len, size);
if(subCount == 0)//leaf
count += 1;
else
count += subCount;
}
}
return count;
}
int decode(int array[], int size)
{
return decodeRec(array, 0, size);
}
package gao.zone.study;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import static org.junit.Assert.assertArrayEquals;
public class DecodeNumsToChars {
public static void main(String[] args) {
String[] rst = transform("123");
String[] expected = {"abc","lc","aw"};
System.out.println(Arrays.toString(rst));
Arrays.sort(rst);
Arrays.sort(expected);
assertArrayEquals(expected, rst);
}
private static String[] transform(String nums) {
List<String> set = new ArrayList<String>();
transform(nums, set, new StringBuilder(), 0);
return set.toArray(new String[0]);
}
private static void transform(String nums, List<String> list,
StringBuilder prefix, int index) {
if (index >= nums.length()) {
list.add(prefix.toString());
return;
}
int bitNum = readNum(nums, index);
if (bitNum > 3 || index + 1 >= nums.length()) {// 3x,4x,...,9x or last
// bit.
transform(nums, list, prefix.append(numToWordChar(bitNum)),
index + 1);
} else {
// 1x,2x
int nextBitNum = readNum(nums, index + 1);
int combineBitNum = bitNum * 10 + nextBitNum;
if(nextBitNum != 0) {
//1x, 2x, except 10,20.
transform(nums, list, new StringBuilder(prefix).append(numToWordChar(bitNum)), index+1);
}
if (combineBitNum <= 26) {
transform(nums, list, prefix.append(numToWordChar(combineBitNum)), index+2);
}
}
}
private static int readNum(String string, int index) {
return string.charAt(index) - '0';
}
private static char numToWordChar(int num) {
return (char) (num-1 +'a');
}
}
The problem statement mentions spaces. The following code assumes that spaces are encoded as value "0".
package com.foo;
public class Decoder {
private static final String LETTERS = " abcdefghijklmnopqrstuvwxyz";
private static final int MAX_INT = LETTERS.length() - 1;
private int decode(String msg, StringBuilder sb, int pos, int total) {
if (pos >= msg.length()) {
System.out.println(sb.toString());
return ++total;
}
// single digit decode
int digit = msg.charAt(pos) - 48;
sb.append(LETTERS.charAt(digit));
total = decode(msg, sb, pos+1, total);
sb.setLength(sb.length()-1);
// double digit decode
if (pos < msg.length() -1) {
digit = digit*10 + (msg.charAt(pos+1) - 48);
if (digit <= MAX_INT) {
sb.append(LETTERS.charAt(digit));
total = decode(msg, sb, pos+2, total);
sb.setLength(sb.length()-1);
}
}
return total;
}
public void doit(String msg) {
int count = decode(msg, new StringBuilder(), 0, 0);
System.out.println("Total count: " + count);
}
public static void main(String[] args) {
Decoder cl = new Decoder();
cl.doit("12301322619");
}
}
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int main()
{
int str[100], i, pre=0, pre1=1,num,len,x,l;
printf("enter the length of integer array\n");
scanf("%d",&l);
printf("enter string\n");
for(i=0;i<l;i++)
scanf("%d",&str[i]);
len=l;
while(len)
{
len--;
// printf("%d",str[len]);
if(str[len]!=1 && str[len]!=2)
{
pre=pre1;
pre1+=0;
}
else if((str[len]==1 || str[len]==2) && ((str[len]*10)+str[len+1])<=26 && len!=(l-1))
{
// printf("hello\n");
x=pre;
pre=pre1;
pre1+=x;
}
}
printf(" %d ",pre1);
getch();
return 0;
}
#include<string.h>
- Jaytosh August 22, 2014#include<iostream>
using namespace std;
int recur(char *a,char *b,int n,int m,char *c,char *p)
{
int f=sizeof(char);
if(m<=0)
{
cout<<p<<endl;
return 0;
}
if((*b!=' ')&&(m>1))
{
*c=*b;
recur(a+2,b+2,n,m-2,c+1,p);
}
*c=*a;
recur(a+1,b+1,n,m-1,c+1,p);
}
int main()
{
char a[100];
cin>>a;
int b=strlen(a);
cout<<b<<endl;
int arr[b];
for(int i=0;i<b;i++)
{
arr[i]=a[i]-48;
}
char sym[b],symo[b];
for(int i=0;i<b;i++)
{
sym[i]=arr[i]+96;
}
for(int i=0;i<b-1;i++)
{
if(arr[i]*10+arr[i+1]<27)
{
symo[i]=arr[i]*10+arr[i+1]+96;
}
else
{
symo[i]=' ';
}
}
cout<<endl;
char sol[b];
recur(sym,symo,b,b,sol,sol);
return 0;
}