Amazon Interview Question SDE-2s
Country: United States
Interview Type: Phone Interview
Quite simple. The question is asking to convert a number in decimal(radix-10) system to another (radix-26) system. The regular radix conversion mechanism with a few tricks works:
1. Map as follows:
0 => A
1 => B
...
25 => Z
2. In the conversion process, reduce the value of the dividend by 1 at each step before doing the division.
For ex: If the input is given as 54, subtract 1 from it and do the conversion on 53 from radix-10 to radix-26. Detailed steps are below;
0. Input = 54 (reduce it by 1 before feeding to the next step)
1. Dividend = 53, divide it by 26 which gives remainder 1(=B) and quotient = 2
2. Dividend = 1 (quotient = 2 from previous step - 1) divide it by 26 which gives remainder 1(=B) and quotient = 0
3. Stop and produce the output BB.
Prepare an alphabetarray with 26 alphabets from A-Z
alphabet1=alphabetarray[56(inputnumber)/26]
alphabet2=alphabetarray[56(inputnumber)%26]
output= alphabet1+alphabet2
So, assuming there are 26 letters in the alphabets ( the one that in achii ascii are between 65 and 90).
we can observe that, if the number given is between 0 and 25, we expect a label with just one letter.
How many possible combination there are for two letters? 26 way of pick the first letter times 26 time for picking the second.
26*26 combination,
so again we can conclude that:
from 0-25 -> one letter label
from 26 to 25+(26*26) -> two letters label
from 26+(26*26) to 25+26*26*26 -> three letters label.
we can just now reverse the process, and start dividing our number by 26, the result of the division will be our letter.
Note that the stop condition for the recursion tail, is that the given number, divide by 26 gives 0 and the leftover (or modulo) is what we are looking for for the first letter
const ASCII_STARTING_LETTER = 65;
function labelingByNumber(columnNumber:int):String{
if(Math.floor(columnNumber/26) == 0)
return (columnNumber+ASCII_STARTING_LETTER).toChar();
columnNumber /= 26;
return (columnNumber+ASCII_STARTING_LETTER).toChar() + labelingByNumber((columnNumber));
}
//program for the above problem @unlimited700
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int n,i,r,l,j=0;
char str[300];
cin>>n;
while(n>0)
{
r=n%26;
if(r==0)
{
str[j++]=(char)90;
n-=26;
}
else str[j++]=(char)r+64;
n/=26;
}
str[j]='\0';
l=strlen(str);
for(i=l-1;i>=0;i--)
cout<<str[i];
return 0;
}
public int excelproblem(string str){
//initialize an array to store the string characters
char[] array = str.toCharArrray();
int result = 0;
//for every character in the string map it to the corresponding value that is predefined(haven' defined it here though)
for(i=0;i<str.length;i++){
char c = array[i]; //gets the character at the i position
int num=map(c); // maps the character to the corresponding value in the predefined function
result += num *(power26, i);
}
System.out.println(result);
}
sorry there is mistake int the above solution...its now corrected as parsing the string form its reverse end and incrementing the power value which is initially set to zero.
public int excelproblem(string str){
//initialize an array to store the string characters
char[] array = str.toCharArrray();
int result = 0, j =0;
//for every character in the string map it to the corresponding value that is predefined(haven' defined it here though)
for(i=str.length; i>0; i++){
char c = array[i]; //gets the character at the i position
int num=map(c); // maps the character to the corresponding value in the predefined function
result += num *(power26, j++);
}
System.out.println(result);
}
/*
Excel columns are labelled alphabetically in length-lexicographic order, i.e., A, B, C, ..., Z, AA, AB, ....
Given the 1-based numeric index of a column, return the corresponding label.
Example 1:
1
Output 1:
A
Example 2:
54
Output 2:
BB
*/
#include<stdio.h>
#include<conio.h>
#define MAX 30
void main()
{
int i, input,newi;
int q,r,arr[MAX],count;
printf("Enter the index of column : ");
scanf("%d",&input);
count = 0;
do{
r = input%26;
if(r == 0){
newi = input-1;
q = newi/26;
r = (newi%26)+1;
input = newi/26;;
}
else{
q = input/26;
r = input%26;
input = input/26;
}
arr[count] = r;
count++;
}while(input > 0);
for(i=count-1; i>=0; i--){
printf("%c",(char)(arr[i]+64));
}
getch();
}
#include<stdio.h>
#include<conio.h>
#define MAX 30
void main()
{
int i, input,newi;
int q,r,arr[MAX],count;
printf("Enter the index of column : ");
scanf("%d",&input);
count = 0;
do{
r = input%26;
if(r == 0){
newi = input-1;
q = newi/26;
r = (newi%26)+1;
input = newi/26;;
}
else{
q = input/26;
r = input%26;
input = input/26;
}
arr[count] = r;
count++;
}while(input > 0);
for(i=count-1; i>=0; i--){
printf("%c",(char)(arr[i]+64));
}
getch();
}
import java.util.Scanner;
public class NumtoAlpha {
public NumtoAlpha() {
}
public static void main (String[] args) {
int ipn,n,t,s,r=0;
String c;
char ch;
String str,rev;
str="";
rev="";
Scanner in= new Scanner(System.in);
ipn=in.nextInt();
n=ipn;
while(n>0)
{
t=(n-1)%26;
n=(n-1)/26;
t=65+t;
ch=(char)t;
str= str+ch;
}
s=str.length();
for(int i=s-1;i>=0;i--)
{
rev=rev+str.charAt(i);
}
System.out.print(rev);
}
}
public class ExcelColumn {
public static void main(String args[]) {
int[] result;
System.out.println("Please enter a number");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int inputNumber = 0;
try {
inputNumber = Integer.parseInt(br.readLine());
} catch (NumberFormatException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
int numOfLetters = 0;
for (int j = 1;; j++) {
if (inputNumber < (int) Math.pow(26.0, (double) j)) {
numOfLetters = j;
break;
}
}
int startingLetter = inputNumber / 26;
result = new int[numOfLetters];
int endingLetter = inputNumber % 26;
int i = 0;
for (i = 0; i < result.length - 1; i++) {
result[i] = startingLetter;
}
result[i] = endingLetter;
for (i = 0; i < result.length; i++)
System.out.print((char) result[i]);
}
}
import java.util.HashMap;
public class ExcelNum2Name {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int inputNum = Integer.parseInt(args[0]);
String convertedNum = "";
int divident = inputNum;
int quotient = 0;
int remainder = 0;
createMapping();
/**********************************************************
* This is similar to converting a decimal number to binary
* successively dividing the number and concatenating the
* remainders form the first
***********************************************************/
while(divident/26 != 0){
quotient = divident/26;
remainder = divident%26;
convertedNum += charMap.get(remainder);
divident = quotient;
}
quotient = divident/26;
remainder = divident%26;
convertedNum = charMap.get(remainder) + convertedNum;
System.out.println(convertedNum);
}
public static void createMapping(){
for(int i=1;i <26;i++){
charMap.put(i, (char) (i+65-1));
}
/********************************************************
*Any number %26 gives number less than 26, but it is
*zero for multiples of 26. Hence 0 should be mapped to Z
*********************************************************/
charMap.put(0, 'Z');
}
private static HashMap<Integer,Character> charMap = new HashMap<Integer,Character>();
}
import java.util.*;
import java.lang.*;
public class Excel {
public static void main(String[] args){
changeToString(702);
}
public static void changeToString(int number){
if(number <= 0){
return;
}
Stack<Integer> array = new Stack<Integer>();
int temp = number;
while(temp > 26){
int remain = temp % 26;
if(remain == 0){
remain = 26;
}
array.add(remain);
temp = temp - remain;
temp = temp / 26;
}
if(temp != 0){
array.add(temp);
}
String s = convertToString(array);
System.out.println(s);
}
public static String convertToString(Stack<Integer> array){
StringBuilder sb = new StringBuilder();
while(array.size() != 0){
int number = array.pop();
sb.append(numberToChar(number));
}
return sb.toString();
}
public static char numberToChar(int number){
if(number > 26 || number < 0){
return '\0';
}
char c = (char) ('A' + (number - 1));
return c;
}
}
#include<iostream.h>
#include<conio.h>
void find(char *a,int b)
{ if(b<27)
cout<<*(a+b-1);
else if(b%26==0)
{ find(a,((b/26)-1)); cout<<*(a+25); }
else
{ find(a,b/26); cout<<*(a+(b%26)-1); }
}
int main()
{ int b=0; char z,a[26]={'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'};
while(1)
{ cout<<"Enter the no.: "; cin>>b; cout<<endl<<"the converted thing is: "; find(a,b); cout<<endl;
cout<<endl<<"Do u want 2 find for another no ?(y/n) : "; cin>>z;
if(z=='y' || z=='Y')
{}
else
break ;
}
return(0);
}
package practice;
public class class3 {
public static void main(String args[]){
int m=55;
int a1=m/26;
int a2=m%26;
a1=64+a1;
a2=64+a2;
char s1;
char s2;
s1=(char)a1;
s2=(char)a2;
String s;
s=String.valueOf(s1);
s+=String.valueOf(s2);
System.out.println(s);
}
}
- Anirban August 02, 2013string ConvertToString (int n) { string res = ""; while (n > 0) { int idx = (n - 1) % 26; res = char(idx + 65) + res; n = (n - 1) / 26; } return res; }