Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    14
    Answers

    Numbers are represented using letter as in phone keypad. For ex 2->a,b,c 3->d,e,f till 9->w,x,y,z (0 and 1 are not represented by any letter). Print all the possible strings that can be generated from the given 9 digit phone number.
    For ex 23 would generate 9 strings
    ad,ae,af,bd,be,bf,cd,ce,cf

    - Vivek on February 12, 2011 Report Duplicate | Flag
    Amazon Software Engineer / Developer Algorithm



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

A recursive algorithm for generating permutations.

- Myth on February 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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


}

- HertzLee on February 12, 2011 | Flag
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.

- XYZ on February 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- cxxpsu on February 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- XYZ on February 12, 2011 | Flag
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.

- Anonymous on February 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- imap on February 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on February 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on February 12, 2011 | Flag
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).

- souravghosh.btbg on February 12, 2011 | Flag Reply
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--;
}

}
}

- Anonymous on February 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on February 13, 2011 | Flag
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;
}

}

- gatorsPK on February 14, 2011 | Flag Reply
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?

- ninghsu267 on February 16, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More