Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
This code sample seems to work.
public static String convert(int n) {
if (n < 0) {
return "";
}
int m = n % 26;
StringBuilder sb = new StringBuilder();
sb.append((char)('A' + m));
n = n/26;
while (n > 26) {
m = n % 26;
sb.insert(0, (char)('A' + m - 1));
n/=26;
}
if (n > 0) {
sb.insert(0, (char)('A' + n - 1));
}
return sb.toString();
}
public class ExcelColumnGenerator {
char[] alpha;
int base;
ExcelColumnGenerator(int base){
this.base = base;
StringBuffer sb = new StringBuffer();
for (int i = 0; i< base; i++){
sb.append((char)('A'+i));
}
alpha = sb.toString().toCharArray();
}
public String column(int n){
boolean flag = false;
int r;
StringBuffer sb = new StringBuffer();
do{
r = n%base;
if(flag == false){
sb.insert(0, alpha[r]);
flag = true;
}
else{
sb.insert(0, alpha[r-1]);
}
n = n/base;
}while(n>0);
return sb.toString();
}
public static void main(String[] args){
ExcelColumnGenerator ecg = new ExcelColumnGenerator(26);
for (int i=0;i<100;i++){
System.out.println("n == " + i + " Column: "+ ecg.column(i));
}
System.out.println("n == " + 1000 + " Column: "+ ecg.column(1000));
}
}
Output:
n == 0 Column: A
n == 1 Column: B
n == 2 Column: C
n == 3 Column: D
n == 4 Column: E
n == 5 Column: F
n == 6 Column: G
n == 7 Column: H
n == 8 Column: I
n == 9 Column: J
n == 10 Column: K
n == 11 Column: L
n == 12 Column: M
n == 13 Column: N
n == 14 Column: O
n == 15 Column: P
n == 16 Column: Q
n == 17 Column: R
n == 18 Column: S
n == 19 Column: T
n == 20 Column: U
n == 21 Column: V
n == 22 Column: W
n == 23 Column: X
n == 24 Column: Y
n == 25 Column: Z
n == 26 Column: AA
n == 27 Column: AB
n == 28 Column: AC
n == 29 Column: AD
n == 30 Column: AE
n == 31 Column: AF
n == 32 Column: AG
n == 33 Column: AH
n == 34 Column: AI
n == 35 Column: AJ
n == 36 Column: AK
n == 37 Column: AL
n == 38 Column: AM
n == 39 Column: AN
n == 40 Column: AO
n == 41 Column: AP
n == 42 Column: AQ
n == 43 Column: AR
n == 1000 Column: ALM
public class ConvertNoToColHeader {
public static void ConvAndPrint(int n){
System.out.println(ConverNoToColHdr(n));
}
public static String ConverNoToColHdr(int n){
if(n < 26){
char mChar = (char)(65 + n);
return Character.toString(mChar);
}
else
{
String strHeader = ConverNoToColHdr(n/26 - 1);
strHeader += ConverNoToColHdr(n%26);
return strHeader;
}
}
}
public static void main(String[] args) {
String strColHeader;
ConvertNoToColHeader.ConvAndPrint(10);
ConvertNoToColHeader.ConvAndPrint(20);
ConvertNoToColHeader.ConvAndPrint(25);
ConvertNoToColHeader.ConvAndPrint(26);
ConvertNoToColHeader.ConvAndPrint(27);
ConvertNoToColHeader.ConvAndPrint(52);
ConvertNoToColHeader.ConvAndPrint(53);
ConvertNoToColHeader.ConvAndPrint(100);
ConvertNoToColHeader.ConvAndPrint(700);
ConvertNoToColHeader.ConvAndPrint(750);
ConvertNoToColHeader.ConvAndPrint(800);
ConvertNoToColHeader.ConvAndPrint(1000);
ConvertNoToColHeader.ConvAndPrint(100000);
}
public class MS2 {
public static void main(String[] args) {
MS2 ms2 = new MS2();
int index = 1000;
String column = ms2.excelColumnString(index);
System.out.println(column);
}
private String excelColumnString(int index) {
String str = "";
if(index<0) return str;
int count=1, num=26, numOld=0;
while(true){
if(index>=num){
count++;
numOld=num;
num = num+(int)Math.pow((double)num, count);
System.out.println(num);
}
else break;
}
int remIndex = index-numOld;
int alphabetIndex;
System.out.println("remIndex: "+remIndex+", count:"+count);
count--;
int power;
while(count>=0){
power = (int)Math.pow(26,count);
alphabetIndex = remIndex / power;
remIndex = remIndex % power;
System.out.println("alphabetIndex:"+alphabetIndex+" remIndex:"+remIndex);
str = indexToString(alphabetIndex,str);
count--;
}
return str;
}
private String indexToString(int alphabetIndex, String str) {
char c = (char) ('A'+alphabetIndex);
str = str+c;
return str;
}
}
My code initially failed for large number when more that 2 characters required for column name. Adding some test data to check the code.
A - Z will be represented by 0-25
AA - ZZ will create 26*26 = 676 more numbers.
so AA-ZZ will be from 26 - 701
Number - Column name
701 - ZZ
702 - AAA
703 - AAB
* Order of complexity was also asked for the code.
my design
given no is n
n%26 store it in array one by one until it n become zero for example given no is 702 then
array[0]=702%26 is 0
702/26=27
now array[1]=27%26 is 1
27/26 =1
now array[2]=1%26 is 1
1/26 is 0
take array[2]array[1]array[0]which is 1 1 0 now subtract one from all but last will give you 0 0 0 now print AAA
another example 323
will give 12 11 subtract by one but last gives 11 11 which is LL thats all
public class excelChar {
public void convertToString(int col) {
StringBuilder sb= new StringBuilder();
while(col!=-1) {
sb.insert(0,(char)('A'+col%26));
col=(col/26)-1;
}
System.out.println(sb.toString());
}
public static void main(String [] args) {
excelChar e= new excelChar();
e.convertToString(Integer.parseInt(args[0]));
}
}
alpha contains A-Z from 0 to 25
public static void generate(char[] alpha, int num){
int n=num;
int r;
Boolean flag=false;
StringBuffer sb = new StringBuffer();
while(n>=26){
r=n%26;
if(flag)sb.insert(0, alpha[r-1]);
else sb.insert(0, alpha[r]);
n=n/26;
if(!flag) flag=true;
}
if(flag)sb.insert(0, alpha[n-1]);
else sb.insert(0, alpha[n]);
System.out.println(num+" "+sb.toString());
}
This is just a small Python script I wrote. I am not sure if it works for all cases but worked for the cases I tried. Here I am running the program as <program name> <number>.
The ord () gives ascii value of character.
The chr () gives the ascii characted of the interger value.
string[::-1] does a string reverse.
Rest is just trivial.
#!/usr/bin/python
import sys
num = int(sys.argv[1])
s = ''
start = ord('A')
visited = False;
while (num > 0):
temp = num % 26
num = num / 26
temp = temp + start
if visited:
temp -= 1
visited = True
s += chr(temp)
print s[::-1]
I am not a Python programmer so this might not be the best way to code this program.
char* getColumn(int colunNumber){
int count = 0;
int n = colunNumber;
do{
count++;
n=n/26;
}while (n);
char* name=(char*)malloc(count+1);
if(NULL != name){
name[count]='\0';
for(int i=count-1;i>=0;i-- ){
name[i] = 'A'+colunNumber%26;
colunNumber = colunNumber/26;
colunNumber--;
}
}
return name;
}
public static String getExcelColumnName(int number) {
int dividend = number + 1;
int modulo;
String columnName = "";
while(dividend > 0) {
modulo = (dividend - 1) % 26;
char c = (char) (65 + modulo);
columnName = Character.toString(c) + columnName;
dividend = (dividend - modulo) / 26;
}
return columnName;
}
Here's a recursive approach. Assuming column 0 is A. and so on.
private static String getStringRepresentation(int num){
char[] A={'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'};
StringBuilder output=new StringBuilder();
if(num<26){
output.append(A[num]);
return output.toString();
}
int tmp=(num/26)-1;
int rem=num%26;
if(tmp<26){
output.append(A[tmp]);
}
else{
output.append(getStringRepresentation(tmp));
}
output.append(A[rem]);
return output.toString();
}
public class ExcelSheet {
static char[] array;
static {
array = new char[26];
for (int i = 0; i < 26; i++) {
array[i] = (char) (i + 97);
}
}
public static void convert(int n){
System.out.println(convertInteger(n));
}
public static String convertInteger(int n) {
if (n <= 0) {
return "a";
}
if(n < 26){
return ""+array[n];
}
int remainder = n % 26;
if (remainder == 0) {
return convertInteger((n - 1) / 26) + array[remainder];
} else {
return convertInteger(n / 26 - 1) + array[remainder];
}
}
public static void main(String[] args) {
convert(76);
}
}
void printString(int num){
- hotcoder October 16, 2012int N = num;
int n;
String result ="";
boolean flag = false;
if(N >= 26) flag = true;
while(N != 0){
n = N % 26;
N= N/26;
if(N == 0 && flag){
n = n-1;
}
result = getchar(n)+result;
}
System.out.println("Result is :"+result);
}
public char getchar(int n){
char c = (char)(65+n);
return c;
}