Amazon Interview Question
Software DevelopersCountry: India
Interview Type: In-Person
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);
}
}
'''
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.
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.
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.
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)).
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;
}
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;
}
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;
}
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();
}
}
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;
}
}
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;
}
}}
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;
}
}
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;
}
}
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:
- Nik January 09, 2017