## Amazon Interview Question for Senior Software Development Engineers

Country: India
Interview Type: In-Person

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

#include<string.h>
#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;
}

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

The above written code writes all the combinations.Use a counter to get number of combinations.

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

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.

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

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.

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

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

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

Variation of subset sum problem. I will post the code soon.

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

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);
} else {
key = Integer.parseInt(twochrs);
}

}

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

}``````

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

``````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);
} else {
key = Integer.parseInt(twochrs);
}

}

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

}``````

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

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

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

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

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

``````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()) {
return;
}
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');
}
}``````

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

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

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

}``````

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

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

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

The pattern is fibonacci

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.

### 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.