Amazon Interview Question for Software Developers

Country: India
Interview Type: In-Person

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

Hi,

Tried to solve this issue. Calculating number related to each character recursively is relatively slow. Instead, I tried to find relationship of each number to a particular equation, i.e tried to find formula to calculate the numbers(not recursively).

Seems following formula can be used to calculate a number related to a character:

assume, following is true:
F('A') = 1, F('B')=2, ..., F('Z')= 26

N(character) = 2^F(character) + 2^( F(character) - 1 ) + ... + 2^1 - F(character)

After we able to calculate the number, we can also generate string out of given number - we can recursively walk through the alphabet, generate number for each of them and try to divide the given number to the calculated one...

Following is a c++ code that I tried to write. The overall logic might be optimized of course, but then the code may become a bit complicated:

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

int calculate_character( char character )
{
int result = 0;

for( int i = 1; i <= ( character - 'A' + 1 ); ++i )
{
result += pow( 2, i );
}

result -= character - 'A' + 1;

return result;
}

int calculate_sum( string characters )
{
int sum = 0;

for( int i = 0; i < characters.size(); ++i )
{
sum += calculate_character( characters[i] );
}

return sum;
}

string generate_string( int num )
{
string result;

for( int i = 0; i <= 'Z' - 'A'; ++i )
{
int char_num = calculate_character( 'Z' - i );
int div = num / char_num;

if( div )
{
result.append( div, 'Z' - i );
num -= char_num * div;
}
}

return result;
}

int main()
{
cout << calculate_character('A') << endl;
cout << calculate_character('F') << endl;
cout << calculate_character('Z') << endl;
cout << calculate_sum("CBA") << endl;
cout << calculate_sum("A") << endl;
cout << calculate_sum("LKEDA") << endl;
cout << generate_string(1) << endl;
cout << generate_string(120) << endl;
cout << generate_string(134217701) << endl;
cout << generate_string(16) << endl;
cout << generate_string(12345) << endl;

return 0;
}

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

function get(xx){
var arr = ['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'];
if(xx == 'a'){
return 1;
}else{
return 2*get(arr[arr.indexOf(xx)-1]) + (arr.indexOf(xx) +1)
}
}

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

'''
int ComputeSum(map<char, int>& imap, string istr){

int sum = 0;
map<char, int>::iterator it = imap.begin();
for (char c : istr){
it = imap.find(c);
sum += it->second;
}
return sum;
}

int main()
{
//part 1
map<char, int> lettermap;
//fill the map
int index = 1;
int temp = 1;
for (char i = 'A'; i <= 'Z'; i++){
lettermap[i] = temp;
index++;
temp = temp * 2 + index;
}

//part 2 - compute words (computes the sum of numbes corresponding to the individual chars in a word)
string str = "GREP";
cout << ComputeSum(lettermap, str) << endl;

return 1;
}
'''
for the 3rd question, we need to use TRIE data structure and pick the words less than the given number.

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

Instead of a trie, you could use bin-search to find for each value the closest (biggest) letter that fits, then subtract it and repeat.

That would lead to O(N log N) being N the magnitude of the initial number. That is ignoring the cost of calculating each letter value.

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

function get(xx){
var arr = ['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'];
if(xx == 'a'){
return 1;
}else{
return 2*get(arr[arr.indexOf(xx)-1]) + (arr.indexOf(xx) +1)
}
}

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

function get(xx){
var arr = ['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'];
if(xx == 'a'){
return 1;
}else{
return 2*get(arr[arr.indexOf(xx)-1]) + (arr.indexOf(xx) +1)
}

}

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

int ComputeSum(map<char, int>& imap, string istr){

int sum = 0;
map<char, int>::iterator it = imap.begin();
for (char c : istr){
it  = imap.find(c);
sum += it->second;
}
return sum;
}

int main()
{
//part 1
map<char, int> lettermap;
//fill the map
int index = 1;
int temp = 1;
for (char i = 'A'; i <= 'Z'; i++){
lettermap[i] = temp;
index++;
temp = temp * 2 + index;
}

//part 2 - compute words (computes the sum of numbes corresponding to the individual chars in a word)
string str = "GREP";
cout << ComputeSum(lettermap, str) << endl;

return 1;
}

For third part of this question, use TRIE data structure form a dictionary of words and find the word lesser than the given number.

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

I'm a bit confused about the last part.

The MAX 32-bit Int is `2147483647`. 'Z' is only `134217700`. Therefore, give a random distribution of inputs a significant number of possible inputs would divide into 'Z' at least once....therefore it makes sense to have an algorithm like:

var s = ''
while (input < 0) {
for ( x = Z..A ) {
if (input >= x.value) {
input -= x.value
s += x.char
continue
}
}

And you may as well memoize it while you do it.

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

Nik,

You only recurse 26 times so I don't see the value of doing it iteratively -- you are still doing the same number of operations.

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

Part three can be done by backtracking. Way easier and more impressive than the 'trie' solution.

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

Hi. It's true - I'm doing it iteratively. But I think, iterative algorithm is faster compared to recursive. In recursive way, each function call itself while it does not reach the end, and only after that starts to compute numbers in a way back - so to speak on the one way we are filling up stack with function pointers, on another we're loosing efficiency by doing the main operation only on a way back. Whereas, for loop can be optimized by compiler. You may try to run both ways and copy here times for them. I'll also try to perform it on my free time.

Talking about map implementation - if I was allowed to use data structure, I would use unordered_map(hash-map) as it gives O(1) efficiency compared to map's O(Log(N)).

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

Here is the complete code for all the three parts.
Trie may be a good option but, the question specifically mentions no pre-computing!!

public class SeriesAddition {
static char currChar;
public static void main(String[] args) {
// TODO Auto-generated method stub
//Part A
System.out.println(calculateVal('Z'));
//Part B
String inp = "AAZ";
int sum  = 0;
for(int i=0; i< inp.length(); i++){
sum+=calculateVal(inp.charAt(i));
}
System.out.println(sum);
//Part C
int val = 134217702;
int curr = 0;
StringBuilder result = new StringBuilder();
while(val > 0) {
curr = getNextLowest(val);
if (val == curr){
result.append(currChar+"");
break;
}
result.append(currChar+"");
val = val - curr;
}

System.out.println(result.reverse());
}

static int getNextLowest(int val){
char c = 'Z';
int result =  calculateVal(c);
while(result> val){
c--;
result = calculateVal(c);
}
currChar = c;
return result;
}
static int calculateVal(char c){
if(c == 'A')
return 1;
int val =  c - 'A';
return 2*calculateVal(--c) + (val+1);
}
}

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

String  allChars = "abcdefghijklmnopqrstuvwxyz";
public Integer calculateSum(Character [] chars){
Integer sum = 0;
int charIndex = 0;
for(int i =0;i<chars.length;i++){
charIndex = allChars.indexOf(chars[i].toString().toLowerCase())+1;
if( charIndex == 1){
sum += 1;
}else{
sum+= ((charIndex-1) * (charIndex-1)) + charIndex;
}
}
return sum;
}

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

String  allChars = "abcdefghijklmnopqrstuvwxyz";
public Integer calculateSum(Character [] chars){
Integer sum = 0;
int charIndex = 0;
for(int i =0;i<chars.length;i++){
charIndex = allChars.indexOf(chars[i].toString().toLowerCase())+1;
if( charIndex == 1){
sum += 1;
}else{
sum+= ((charIndex-1) * (charIndex-1)) + charIndex;
}
}
return sum;
}

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

String  allChars = "abcdefghijklmnopqrstuvwxyz";
public Integer calculateSum(Character [] chars){
Integer sum = 0;
int charIndex = 0;
for(int i =0;i<chars.length;i++){
charIndex = allChars.indexOf(chars[i].toString().toLowerCase())+1;
if( charIndex == 1){
sum += 1;
}else{
sum+= ((charIndex-1) * (charIndex-1)) + charIndex;
}
}
return sum;
}

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

public class ComputeSum {
private final char[] cArr = {'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[] args){

ComputeSum cs = new ComputeSum();

int[] series = cs.createSeries();
for(int i=0; i<26; i++){
System.out.print(series[i]+" ");
}
System.out.println();

System.out.println(cs.sum("ABCD", series));

String shortestString = cs.createShortestString(200, series);
System.out.println(shortestString);
}

public int[] createSeries(){

int[] series = new int;

series = 1;

for(int i=1; i<26; i++){
series[i] = series[i-1]*2+(i+1);
}

return series;
}

public int sum(String input, int[] series){

int res = 0;
for(int i=0; i<input.length(); i++){
res = res+series[input.charAt(i)-65];
}

return res;
}

public String createShortestString(int bigInt, int[]series){

StringBuffer sb = new StringBuffer();
int remain = bigInt;

for(int i=25; i>=0; i--){

if(remain < series[i]) continue;

int n = remain/series[i];
for(int j=0; j<n; j++) sb.append(cArr[i]);
remain = remain%series[i];
}

return sb.toString();
}

}

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

public class StringVal {
public static void main(String[] args) {
System.out.println(compute("SIMPLE"));
}
static long compute(int charPosition){
if(charPosition == 1) return 1;
return compute(charPosition-1)*2+charPosition;
}
static long compute(String text){
int i = 0;
long result = 0;
while(i < text.length()){
result += compute(text.charAt(i) - 'A' +1);
i++;
}
return result;
}
}

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

public class StringVal {
public static void main(String[] args) {
System.out.println(compute("SIMPLE"));
}
static long compute(int charPosition){
if(charPosition == 1) return 1;
return compute(charPosition-1)*2+charPosition;
}
static long compute(String text){
int i = 0;
long result = 0;
while(i < text.length()){
result += compute(text.charAt(i) - 'A' +1);
i++;
}
return result;
}

}}

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

public class StringVal {
public static void main(String[] args) {
System.out.println(compute("SIMPLE"));
}
static long compute(int charPosition){
if(charPosition == 1) return 1;
return compute(charPosition-1)*2+charPosition;
}
static long compute(String text){
int i = 0;
long result = 0;
while(i < text.length()){
result += compute(text.charAt(i) - 'A' +1);
i++;
}
return result;
}
}

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

public class StringVal {
public static void main(String[] args) {
System.out.println(compute("SIMPLE"));
}
static long compute(int charPosition){
if(charPosition == 1) return 1;
return compute(charPosition-1)*2+charPosition;
}
static long compute(String text){
int i = 0;
long result = 0;
while(i < text.length()){
result += compute(text.charAt(i) - 'A' +1);
i++;
}
return result;
}
}

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.