Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
Java approach:
{
public static String excelColumnEquivalent(int n){
if(n < 0)
return "Invalid number";
String out = "";
StringBuffer sb = new StringBuffer();
while(n > 0){
n--;
sb.append(Character.toChars(n % 26 + 'a'));
out = sb.toString() + out;
sb.setLength(0);
n /= 26;
}
return out;
}
}
Perfect. Just would like to do some trivial optimization :).
public static String excelColumnEquivalent(int n){
if(n < 0)
return "Invalid number";
//String out = "";
StringBuffer sb = new StringBuffer();
while(n > 0){
n--;
//sb.append(Character.toChars(n % 26 + 'a'));
char ch=(char)(n % 26 + 'a');
//out = sb.toString() + out;
//sb.setLength(0);
sb.append(ch);
n /= 26;
}
return sb.reverse().toString();
}
#include <string>
#include <assert.h>
using namespace std;
string chars("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
int getColumnNumberFlat(const string& name)
{
double num = 0;
for ( int i = name.length() - 1; i >= 0 ; --i )
{
int dist = name[i] - chars[0] + 1;
num += dist * pow(chars.length(), (name.length() - 1) - i);
}
return (int)num;
}
int getColumnNumberRecursion(const string& name)
{
if (!name.length())
return 0;
int dist = name[name.length()-1] - chars[0] + 1;
return dist + chars.length()*getColumnNumberRecursion(name.substr(0, name.length()-1));
}
void Amazone11()
{
assert(1 == getColumnNumberFlat("A"));
assert(27 == getColumnNumberFlat("AA"));
assert(/*626*/ 703 == getColumnNumberFlat("AAA"));
assert(1 == getColumnNumberRecursion("A"));
assert(27 == getColumnNumberRecursion("AA"));
assert(/*626*/ 703 == getColumnNumberRecursion("AAA"));
}
QMap<int,QString> aMap;
void buildMap() {
for(int i=1;i<=26;i++)
aMap.insert(('A'+ i).toString());
}
//Assuming the buildMap is given the retrival of the Map can be written as
QString charVal(int i)
{
QString str;
if(i%10==0) {
return str;
}
else
{
int temp = i % 10;
str += aMap.value(temp);
return charVal(i/10);
}
}
// ExcelWord.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#define N 26
char c[] = { "abcdefghijklmnopqrstuvwxyz" };
//Finding Alphabet
void findAlphabet(int n)
{
if (n <= N){
printf("Equivalent Alphabet would be :: %c", c[n - 1]);
}
else{
n = n - N;
if ((n / N) > N){
//Number is 26 square equivalent - AAA - ZZZ
//Similarly extend it
}
else
{
//Number is AA - AZ
int first = (n / N);
int second = n - ((n / N)*N);
if (second == 0) second = 26;
printf("%c%c", c[first - 1],c[second - 1]);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int number = 702;
findAlphabet(number);
printf("%c", c[5]);
return 0;
}
C# Implementation
public static string excelColumnEquivalent(int column)
{
column--;
if (column >= 0 && column < 26)
return ((char)('A' + column)).ToString();
else if (column > 25)
return excelColumnEquivalent(column / 26) + excelColumnEquivalent(column % 26 + 1);
else
throw new Exception("Invalid Column #" + (column + 1).ToString());
}
def convert_to_letters(col):
str = ''
if col in letter:
return letter[col]
else:
l = (col - 1) / 26
l2 = (col - 1) % 26
if l > 26:
str = convert_to_letters(l)
return str + letter[l2 + 1]
else:
return letter[l] + letter[l2 + 1]
def convert_to_numbers(col):
if len(col) <= 0:
return 1
if col in number:
return number[col]
else:
part_num = convert_to_numbers(col[1:])
part_num = (number[col[:1]] + 25) * part_num + 1
return part_num
Test it out, it works :)
// ExcelNumberProb.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <stack>
using namespace std;
void buildExcelString(int num, stack<char> &charList){
if (num / 26 != 0) {
if (num % 26 == 0)
charList.push((char)( 64 + 26));
else
charList.push((char)( 64 + ( num % 26 )));
if ((num % 26) == 0)
num = (num / 26) - 1;
else
num = (num / 26);
buildExcelString(num, charList);
}
else if (num > 0)
charList.push((char)(64 + (num % 26)));
}
void printExcelString(int num)
{
stack<char> charList;
buildExcelString(num, charList);
int s = charList.size();
char *str = new char(charList.size()+1);
for (int i = 0; i < s; i++){
str[i] = charList.top();
charList.pop();
}
str[s] = '\0';
cout << str << endl;
}
int main()
{
printExcelString(27);
printExcelString(52);
printExcelString(53);
printExcelString(701);
printExcelString(702);
printExcelString(703);
return 0;
}
execute below code on: compileonline.com/execute_python_online.php
set temp accordingly
print "Hello World!\n";
temp=700
for i in range(1,temp):
if temp>=1 and temp<=26:
n=1
break
elif temp>(26*(((26**i)-1)/25)):
n=i+1
else:
break
print n
str1=""
if n==1:
str1+=(chr(temp+64))
else:
p=n-1
temp-=(26*(((26**p)-1)/25))
k=0
while n>0:
p=n-1
for i in range(0,temp):
if temp>(26**p)*i:
k=i
else:
break
str1+=(chr(64+k+1))
temp-=(26**p)*k
n-=1
print temp
print str1
execute on: "compileonline.com/execute_python_online.php"
set temp accordingly
temp=700
for i in range(1,temp):
if temp>=1 and temp<=26:
n=1
break
elif temp>(26*(((26**i)-1)/25)):
n=i+1
else:
break
print n
str1=""
if n==1:
str1+=(chr(temp+64))
else:
p=n-1
temp-=(26*(((26**p)-1)/25))
k=0
while n>0:
p=n-1
for i in range(0,temp):
if temp>(26**p)*i:
k=i
else:
break
str1+=(chr(64+k+1))
temp-=(26**p)*k
n-=1
print temp
print str1
'''
Question:
A ... Z are coded in (1,26)
AA ... ZZ are coded in (27, 702)
AAA ... ZZZ are coded in (703,...)
'''
import string,math
charMap = list(string.ascii_lowercase)
def numToCode(_num):
#INPUT: INTEGER, OUTPUT = STRING
_out_code = []
_dist = 1
while _num != 0:
_dist = int(_num % 26)
_out_code.append(charMap[_dist-1])
_num = math.floor(_num/26)
return ''.join(_out_code[::-1])
if __name__ == "__main__":
#TODO take input from user
_inp = ""
while _inp == "":
_inp = input("Enter code:")
_inp_num = int(_inp)
_out_code = numToCode(_inp_num)
print(_out_code)
Using PHP:
function convertNumberToExcel($in_num){
if(floor($in_num/27)<1)
return chr(64+(($in_num % 26)==0?26:($in_num % 26)));
$out_char = chr(64+(($in_num % 26)==0?26:($in_num % 26)));
$out_char = convertNumberToExcel(floor($in_num/27)) . $out_char;
return $out_char;
}
echo "the excel column is: ".convertNumberToExcel(79)."<br>";
To understand the logic behind this, consider this as a numbering system with base 26.
Consider you want to figure out digits from a number. For example to find digits from a number 1537, you would do this:
1537 /10 = 153 - remainder 7
153 / 10 = 15 - remainder 3
15 / 10 = 1 - remainder 5
1 remainder 1.
For a base 26
1537 / 26 = 29 - remainder 3
59 / 26 = 2 - remainder 7
2 remainder 2
so numbers 2, 7, 3 - corresponding letters BGC.
public String calculate(int no){
StringBuilder sb = new StringBuilder();
int n = no;
while(n>0){
sb.append((char)((n%26)-1+'A'));
n=n/26;
}
return sb.toString();
}
It gives wrong result, if i give 39, it produces 'MA'. Supposed to be AM. If we reverse the string after its construction. It may give correct result.
AA = 26^1 x ('A'-'A'+1) + ('A'-'A'+1)
- Champak June 01, 2014ZA = 26^1 x ('Z'-'A'+1) + ('A'-'A'+1)
AAA = 26^2 x ('A'-'A'+1) + 26^1 x ('A'-'A'+1) + ('A'-'A'+1)
The Data provided is wrong. AAA is column no. 703 in excel