Amazon Interview Question Developer Program Engineers
Country: United States
Interview Type: Written Test
I comment heavily on purpose (and use globals heavily too) to keep the idea clear. Which also allows people to see any bad ideas, logic I have :)
In C:
#include <stdio.h>
#include <string.h>
typedef enum {false,true} bool;
#define NUM_DIGITS 4 // {0, 1, ..., NUM_DIGITS-1} will be the digits of pad
int num[NUM_DIGITS]={0, 2, 1, 3}; //the input number
bool used[NUM_DIGITS]; //boolean "hash" (kind of) that keeps track of the keys already touched
char result[NUM_DIGITS+1]; //result (global for convenience)
char *keypad[NUM_DIGITS]={"ab","cd","efgh","xyz"}; //defining the keypad: e.g., 0-key has 'a' and 'b'
void function()
{
int j;
char *letptr;
static int i=0; //index of result we're filling now
if (i==N) { puts(result); return; } //result full, print
for(j=0; j<NUM_DIGITS; j++) //for every possible key on keypad
{
if( used[ num[j] ] ) continue; //if the key was touched already, skip it
used[ num[j] ] = true; //mark key as touched
letptr=keypad[ num[j] ]; //point to first letter corresponding to this key
while(*letptr != '\0') //iterate over all letters corresp. to key
{
result[i++]=*letptr; //fill letter; inc. i in prep. for recursive call
function(); //recursively fill next position of result[]
i--, letptr++; //unwind i, point to next letter corresp. to this key
}
used[ num[j] ]=false; //tried all letters of key, so mark it as untouched
}
}
int main(void)
{
function();
return 0;
}
But what if the user wants to press less than all the keys...
Introduce NUM_PRESS <= NUM_DIGITS:
#include <stdio.h>
#include <string.h>
typedef enum {false,true} bool;
#define NUM_DIGITS 4 // {0, 1, ..., NUM_DIGITS-1} will be the digits of pad
char *keypad[NUM_DIGITS]={"ab","cd","efgh","xyz"}; //defining the keypad: e.g., 0-key has 'a' and 'b'
bool used[NUM_DIGITS]; //boolean "hash" (kind of) that keeps track of the keys already touched
int num[]={0, 2, 1}; //the input number
#define NUM_PRESS (sizeof(num)/sizeof(*num)) //size of input (number of keys we'll press)
char result[NUM_PRESS+1]; //result (global for convenience)
/* note: NUM_PRESS <= NUM_DIGITS allowing for less than all keys pressed */
void function()
{
int k;
char *letptr;
static int i=0; //index of result we're filling now
if (i==NUM_PRESS) { puts(result); return; } //result full, print
for(k=0; k<NUM_PRESS; k++) //for every possible key on the keypad (i.e., numbers 0, ..., NUM_DIGITS-1 )
{
if( used[ num[k] ] ) continue; //if the key was touched already, skip it
used[ num[k] ] = true; //mark key as touched
letptr=keypad[ num[k] ]; //point to first letter corresp. to this key
while(*letptr) //iterate over all letters corresp. to this key
{
result[i++]=*letptr; //fill letter, inc. i in prep. for recursive call
function(); //recursively fill next position of result[]
i--, letptr++; //unwind i and point to next letter
}
used[ num[k] ]=false; //tried all letters of current key, mark untouched
}
}
int main(void)
{
function();
return 0;
}
It can solved mathematically too.
Say you are given 1230 -> number of characters for each place are -
1 2 3 0
_______
3 3 3 4
so total number of result strings you'll get are 3*3*3*6 = 162 (Permutations)
So just create 4 arrays in this case -
1 c,d,e, c,d,e, c, d, e ...(repeat c,d,e 162/3 = 54 times)
2 v,f,r, v,f,r, v,f,r, ....( repeat v,f,r 162/3 = 54 times)
3 b,g,t (162/3 = 54 times)
0 z,a,q,x,s,w (repeat 162/6 = 24 times)
combine all 4 in one by
for ( i=0;i<162;i++)
{ finalArray[i] = a1[i]+a2[i]+a3[i]+a0[i] }
class CharNumberAI
{
public static void Do()
{
Dictionary<int, List<char>> dict = new Dictionary<int, List<char>>();
dict.Add(0, new List<char>() { 'z', 'a', 'q', 'x', 's', 'w' });
dict.Add(1, new List<char>() { 'c', 'd', 'e' });
dict.Add(2, new List<char>() { 'v', 'f', 'r' });
dict.Add(3, new List<char>() { 'b', 'g', 't' });
SimpleDo(1230, dict);
}
public static void SimpleDo(int n, Dictionary<int, List<char>> dict)
{
List<List<char>> allchars = new List<List<char>>();
int num = 0;
while (n > 0)
{
num = n % 10;
n = n / 10;
allchars.Add(dict[num]);
}
PrintPowerSet(allchars, allchars.Count - 1, new StringBuilder());
}
private static void PrintPowerSet(List<List<char>> allchars, int index, StringBuilder sb)
{
List<char> chars = allchars[index];
StringBuilder subSb = new StringBuilder();
foreach (char ch in chars)
{
subSb.Clear();
subSb.Append(sb.ToString());
if (index == 0)
{
//Console.Write("{0};", ch);
subSb.Append(ch);
subSb.Append(";");
Console.WriteLine(subSb.ToString());
}
else
{
//Console.Write(ch);
subSb.Append(ch);
PrintPowerSet(allchars, index - 1, subSb);
}
}
}
}
void Permutation()
{
vector<string> myvector(1,"");
string str[4]={"zaqxsw","cde","vfr","bgt"};
string input="1230";
int len=input.length();
int start=1;
int prev=0;
for(int i=0;i<len;i++)
{
int index=input.at(i)-48;
string temp=str[index];
int x=temp.length();
int y=prev;
int j=0;
int count=0;
while(y<start)
{
for(j=0;j<x;j++)
{
char c=temp.at(j);
myvector.resize(myvector.size()+1);
myvector.at(count+start)=myvector.at(y)+c;
count++;
}
y++;
}
prev=start;
start=start*j+1;
}
int max=myvector.size();
for(int u=prev;u<max;u++)
cout<<myvector.at(u)<<endl;
}
The main idea of code given below is to use number system with variable base to enumerate all combinations. Sample code in C#:
Dictionary<char, string> map = new Dictionary<char, string>
{
{ '0', "zaqxsw" },
{ '1', "cde" },
{ '2', "vfr" },
{ '3', "bgt" }
};
string pattern = "1230";
int cnt = pattern.Select(c => map[c].Length).Aggregate((x, y) => x * y);
for (int i = 0; i < cnt; i++)
{
int mask = i;
foreach (char c in pattern)
{
int pos = mask % map[c].Length;
Console.Write(map[c][pos]);
mask /= map[c].Length;
}
Console.WriteLine();
}
public class DigitPermutation {
private static char[][] dict = {{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r'},{'s','t','u'},{'v','w','x'},{'y'},{'z'}};
public static void main(String arg []){
printletters(38, "");
}
public static void printletters(int digit, String suffix){
int last_digit = digit % 10;
int rest_digit = digit/10;
for (int i =0; i <dict[last_digit].length;i++ ){
if ( rest_digit == 0){
System.out.println( dict[last_digit][i]+ suffix);
}
else{
printletters(rest_digit, dict[last_digit][i]+ suffix);
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DigitsToLet
{
class DigMap
{
private Dictionary<int, List<char>> Map;
public void PrintMap(string digit, string prefix)
{
if (digit.Length == 0)
{
Console.WriteLine(prefix);
return;
}
int index = digit.ToCharArray()[0] - '0';
foreach (char c in Map[index])
{
PrintMap(digit.Substring(1), prefix + c);
}
}
public DigMap()
{
Map = new Dictionary<int, List<char>>();
Map.Add(0, new List<char> { 'z', 'a', 'q', 'x', 's', 'w' });
Map.Add(1, new List<char> { 'c', 'd', 'e' });
Map.Add(2, new List<char>() { 'v', 'f', 'r' });
Map.Add(3, new List<char>() { 'b', 'g', 't' });
}
}
class Program
{
static void Main(string[] args)
{
var digMap = new DigMap();
string str = string.Empty;
int num = 1230;
digMap.PrintMap(num.ToString(), str);
Console.Read();
}
}
}
#include<stdio.h>
#include<conio.h>
void printKeypadAlphabets(char input[], char *keyboard[],char data[], int i, int n)
{
if(i == n)
{
data[i] = 0;
printf("%s\n",data);
return;
}
int j = 0;
char *c = keyboard[input[i]-'0'];
while(*c != '\0')
{
data[i] = *c;
printKeypadAlphabets(input, keyboard, data, i+1, n);
c++;
}
}
int main()
{
char input[] = "123";
char *keyboard[] = {"", "cde", "vfr", "bgt"};
int n = 3;
char data[n+1];
printKeypadAlphabets(input, keyboard, data, 0, n);
getche();
return 0;
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class Perms {
public static void main(String[] args) {
HashMap <Integer, char[]> hm = new HashMap<Integer, char[]>();
char [] c1 = {'c','d','e'};
hm.put(new Integer(1), c1);
char [] c2 = {'v','f','r'};
hm.put(2, c2);
char [] c3 = {'b','g','t'};
hm.put(3, c3);
char [] c0 ={'z','a','q','x','s','w'};
hm.put(0, c0);
int i = 1230;
ArrayList <Integer> ai = new ArrayList<Integer>();
while( i > 0 ){
ai.add(i % 10);
i = i / 10;
}
Collections.reverse(ai);
for( Integer intg: ai)
System.out.print(intg);
StringBuilder sb = null;
perm(hm, ai, 0, ai.size(), sb);
}
private static void perm(Map <Integer, char[]>hm, ArrayList<Integer> ai, int i, int size, StringBuilder sb){
if ( i == size ){
System.out.println(sb.toString());
return;
}
if( i == 0)
sb = new StringBuilder();
char[] ca = hm.get(ai.get(i++));
for( int j = 0; j < ca.length; j++){
StringBuilder sb1 = new StringBuilder();
sb1.append(sb.toString());
sb1.append(ca[j]);
perm(hm, ai, i, size, sb1);
}
}
}
- AlgoBaba October 12, 2013d = { '0': "zaqxsw", '1': "cde", '2': "vfr", '3': "bgt", } def digstolets(digs): if len(digs) == 0: yield '' return first, rest = digs[0], digs[1:] if first not in d: for x in digstolets(rest): yield first + x return else: for x in d[first]: for y in digstolets(rest): yield x + y print(list(digstolets('1230')))