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

- Nik January 09, 2017 | Flag Reply
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)
}
}

- Anonymous January 08, 2017 | Flag Reply
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.

- Raj January 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- MatiasSM January 10, 2017 | Flag
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)
}
}

- Amit Sharma January 08, 2017 | Flag Reply
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)
}

}

- Amit Sharma January 08, 2017 | Flag Reply
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.

- Raj January 09, 2017 | Flag Reply
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.

- srterpe January 09, 2017 | Flag Reply
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.

- srterpe January 09, 2017 | Flag Reply
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.

- Yash January 10, 2017 | Flag Reply
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)).

- Nik January 10, 2017 | Flag Reply
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);
	}
}

- liju.leelives January 11, 2017 | Flag Reply
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;
	}

- Deep January 17, 2017 | Flag Reply
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;
	}

- Deep January 17, 2017 | Flag Reply
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;
	}

- dkholia January 17, 2017 | Flag Reply
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[26];
		
		series[0] = 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();
	}

}

- yankeson2013 February 07, 2017 | Flag Reply
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;
	}
}

- Delwar February 11, 2017 | Flag Reply
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;
	}

}}

- Delwar February 11, 2017 | Flag Reply
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;
	}
}

- Delwar February 11, 2017 | Flag Reply
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;
	}
}

- Anonymous February 11, 2017 | Flag Reply


Add a Comment
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.

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