## Amazon Interview Question for Software Engineer / Developers

• 0

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

A recursive algorithm for generating permutations.

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

Java implementation:

when call, we call firstly printResult(input,"")

public static void printResult(String inputSequence,String result)
{
int len=inputSequence.length();
if(len==0)
{
System.out.println(result.toString());
return ;
}

char c=inputSequence.charAt(0);
String substring=inputSequence.substring(1);
if(!dict.containsKey(c))
{
//invalid character, skip
printResult(substring,result);
return ;
}

ArrayList<Character> ds= dict.get(c);
for(int i=0;i<ds.size();i++)
{
String r2= result+ ds.get(i);
printResult(substring, r2);
}

}

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

//normal backtracking
void generate(string phonenum,vector<string> digit2letter,char* result,int resultsize,int idx)
{
if(idx==phonenum.size()){
cout<<result<<"\n";
return;
}
for(int i=0;i<digit2letter[idx].size();i++)
{
result[resultsize]=digit2letter[idx][i];
generate(phonenum,digit2letter,result,resultsize+1,idx+1);
result[resultsize]='\0';
}
}

//call with generate(phonenum,digit2letter,result,0,0);

I am not sure about time complexity...someone tell me plzz.

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

1, if the digit2letter vector looks like this: {"ABC", "DEF", ..., "WXYZ"}, digit2letter[idx] should be changed to digit2letter[phonenum[idx] - '2'];

2, probably we need to deal with the cases where phonenum[idx] is '0' or '1';

3, the idx and resultsize variables can be merged to one becoz they're always identical.

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

@cxxpsu...yeah u r right..my mistake

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

Are you sure we need to print all the possible strings that can be generated from the given 9 digit phone number ?? If this being the case then there will be infinite strings.

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

No. As abc is same as bca/cab etc. total no. of posible strings will be 26C1 + 26C2 + ... + 26C26 (no permutation).

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

(2^26)-1 is still too large.

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

how come there'll be infinite strings??
maximum number of strings is 4^9 = 262144

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

Here's some tested code:

``````/**
* PhoneChar.cc
* (c) souravgh@usc.edu
* Sat Feb 12 1423
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>

using namespace std;
using namespace __gnu_cxx;

// Recursive procedure which inspects each possible permutation
// of strings formable using the digits given in inputCharPtr.
// inputCharPtr: The string containing the no. eg. "234"
void printChars (char *inputCharPtr);

int main () {
char inputCharPtr[10];

scanf ("%s", inputCharPtr);

printChars (inputCharPtr);

return EXIT_SUCCESS;
}

const char *digitLetterMapCharPtrPtr[] = {"+", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
stack <char> charStack;

// Print the entire string contained in the charStack
void printStack ();

// Recursive procedure which inspects each possible permutation
// of strings formable using the digits given in inputCharPtr.
// inputCharPtr: The string containing the no. eg. "234"
void printChars (char *inputCharPtr) {
if (!inputCharPtr[0]) {
printStack ();
return;
}

// Get the int representation of the current digit.
// Need this to index the digitLetterMapCharPtrPtr array.
int currentDigitInt = *inputCharPtr - '0';

// We start from the first character and inspect each character
// calling the procedure recursively with the next character.
for (int indexInt = 0;
indexInt < (int)strlen (digitLetterMapCharPtrPtr[currentDigitInt]);
indexInt++) {
charStack.push (digitLetterMapCharPtrPtr[currentDigitInt][indexInt]);
printChars (inputCharPtr + 1);
charStack.pop ();
}
}

// Print the entire string contained in the charStack
void printStack () {
stack <char> tempCharStack;

// Reverse the stack.
for( ; charStack.size (); charStack.pop ()) {
tempCharStack.push (charStack.top ());
}

printf ("=> ");

// Restore and print out the stack.
for ( ; tempCharStack.size (); tempCharStack.pop ()) {
printf ("%c", tempCharStack.top ());
charStack.push (tempCharStack.top ());
}

printf ("\n");
}``````

The complexity in this case depends on the no. of output permutations. To that effect I feel it's something like: O (3^n), where n is the length of the input string e.g. "234". (Why 3? Each digit has 3 possible characters associated with it. All except 0, 1, 7, 9).

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

char *num[] ={ "abc",
"def",
"ghi",
"jkl",
"mno",
"pqr",
"stu",
"vwx",
"yz"
};

void printallperm1(int p[10], int q[10] , char *b ,int l , int k, char *ss)
{
if( k == l )
{
*b = '\0';
std::cout<<ss<<" "<<"\n";
return;
}
else
{
char * s = num[p[k]];

for( int j =0 ; j<strlen(s) ; j++ )
{
char ch = s[j];
*b = ch;
b++;
printallperm1(p,q,b,l,k+1,ss);
b--;
}

}
}

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

input:

int pp[10];
pp[0] = 1;
pp[1] = 2;
pp[2] = 3;
pp[3] = 4;

int q[10];
char *bb = new char[5];
char *sstt = bb;
printallperm1(pp,q,bb,4,0,sstt);

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

after initializing out and num, call foll fn with current = 0.

void Print(int current, char out[], int num[]){
static int flag = 0;//for not printing the first 8 recursions
if(current==8) flag =1;
if((current >= 9)||(num[current]==1 or 0))
return;
int num_chars;//No. of characters for a digit

if(num[current]==9)
{ num_chars = 4; }
else
{ num_chars = 3; }

for(int j=0; j<=num_chars; j++){
out[current] = getChar(num[current], j);
if(flag){ puts(out); }//print the string
Print(current+1, out, num);
}

}

char getChar(int num, int position){
switch(num){
case 2: switch(position){
case 1: return 'a';
case 2: return 'b';
case 3: return 'c';
}
case 3:________

//upto 9;
}

}

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

Not sure what the question means, can we push the keys as many times as possible?

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.