Google Interview Question: Come out with an algorithm fo... | Glassdoor.co.in

## Interview Question

Software Engineer Interview Bengaluru

# Come out with an algorithm for getting the column number

provided the column name in a excel sheet and vice versa. Excel has a naming convention of A,B..Z,AA,AB,AC..ZZ,AAA... This had to be converted to the column numbers. A will be 1 and AA will 27.. Also the algorithm to find the name provided column number.
Tags:

6

Its conversion from decimal to base 26 with some exception like there is nothing maps to zero. There might be a better way to do it.

Interview Candidate on 19-Mar-2009
1

void printColumn(uint32_t col)
{
col --;
int div = 26;

while( col / div ) {
div *= 26;
}

div /= 26;

while( div != 1) {
printf("%c", (col / div) + 'a' - 1);
col = col % div;
div /= 26;
}
printf("%c\n", col + 'a');
}

Anonymous on 21-May-2009
0

Opps above does not work after ZZ. The correct one is

void printColumn(uint32_t col)
{
int a = 26;
int denominator = 1;

while(a 0; i /= 26)
low += i;

// if value is lower than lower bound, decrease quotient by one
if( denominator != 1 &amp;&amp; col &lt; (quotient * denominator + low) ) {
quotient --;
}

printf("%c", quotient - 1 + 'A');

col = col - denominator * quotient;
denominator /= 26;
}
}

Anonymous on 30-May-2009
2

Let the size of the string asked is 3 e.g GHD . The formula to this :
[ 26+26^2+...+ 26^(size-1) + (LetterIndex-1)*{26^(size-1)+....+(LetterIndex-1)*26}+Index ]

JParija on 29-Jun-2010
1

In the code the above formula will use recursion to find the column number.

JParija on 29-Jun-2010
0

The answer can be as simple as finding the first combination of number * i such that it is less then xcelcolvalue;

ie
repeat this till xcelColValue &gt;= 26
( 0 = 26){
int i = 1, num = 1;
while((num * (i + 1)) 26){ i = 1; num++;} else i++;
xcelNum -= num*i;
sb.append((char) i);
}
if (xcelNum &gt; 0) sb.append((char) xcelNum);
return sb.toString();
}

Naresh on 10-Dec-2010
0

Also the above code is rough idea and not tested but gives enough idea on simplifying the solution. The code does not use lot of / and % calcuations but could elegantly find the solution. Note the Gaurd if(i &gt; 26){ i = 1; num++;} else i++;
which is important in finding the combination of num and i which multiples at least to xcelNum.

Naresh on 10-Dec-2010
0

I think the above is incorrect and it should be :

public static String xcelString(int xcelNum) {

StringBuffer sb = new StringBuffer();

while(xcelNum &gt;= 26){
int i = 1;
for(;(26 * (i + 1)) 0)
sb.append((char) xcelNum);
return sb.toString();
}

Naresh on 10-Dec-2010
0

Edge conditions aside, the program would be

/* inputString - the column name. For e.g. "BZC" */

char [] columnName = inputString.toUpperCase().toCharArray();

int columnNumber = 0;

for(int i = 0; i &lt; columnName.length - 1; i++){
columnNumber = columnNumber + (int) Math.pow(26, (columnName.length - 1 - i)) * (columnName[i] - 64) ;
}
columnNumber = columnNumber + (columnName[columnName.length - 1] - 64);

System.out.println("Column number is " + columnNumber);

This is quite straight forward. on 10-Oct-2014
0

Edge conditions aside, the program would be

/* inputString - the column name. For e.g. "BZC" */

char [] columnName = inputString.toUpperCase().toCharArray();

int columnNumber = 0;

for(int i = 0; i &lt; columnName.length - 1; i++){
columnNumber = columnNumber + (int) Math.pow(26, (columnName.length - 1 - i)) * (columnName[i] - 64) ;
}
columnNumber = columnNumber + (columnName[columnName.length - 1] - 64);

System.out.println("Column number is " + columnNumber);

Prashant on 10-Oct-2014
0

int columnNumber(String col)
{
result = 0;
for(i = 0;i&lt; strlen(col) ; i++)
{
result *= 26;
result + = col[i] - 'A' +1;
}

}

Anonymous on 04-Nov-2014
0

int columnNumber(String col)
{
result = 0;
for(i = 0;i&lt; strlen(col) ; i++)
{
result *= 26;
result + = col[i] - 'A' +1;
}

}

Alekhya on 04-Nov-2014
0

public static String numToExcel(int n) {

if(n 0) {
int remainder = n%26;
char newChar = (char) ('Z' - (26 -remainder)%26);
result = newChar + result;

n = (n-1)/26;
}
return result;
}

Raghav on 12-Jan-2015