Pergunta de entrevista da empresa Google
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.
Respostas da entrevista
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 ]
In the code the above formula will use recursion to find the column number.
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.
void printColumn(uint32_t col)
{
col --;
int div = 26;
int add = 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');
}
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 && col < (quotient * denominator + low) ) {
quotient --;
}
printf("%c", quotient - 1 + 'A');
col = col - denominator * quotient;
denominator /= 26;
}
}
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 >= 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 > 0) sb.append((char) xcelNum);
return sb.toString();
}
int columnNumber(String col)
{
result = 0;
for(i = 0;i< strlen(col) ; i++)
{
result *= 26;
result + = col[i] - 'A' +1;
}
}
int columnNumber(String col)
{
result = 0;
for(i = 0;i< strlen(col) ; i++)
{
result *= 26;
result + = col[i] - 'A' +1;
}
}
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;
}
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 < 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);
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 < 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);
I think the above is incorrect and it should be :
public static String xcelString(int xcelNum) {
StringBuffer sb = new StringBuffer();
while(xcelNum >= 26){
int i = 1;
for(;(26 * (i + 1)) 0)
sb.append((char) xcelNum);
return sb.toString();
}
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 > 26){ i = 1; num++;} else i++;
which is important in finding the combination of num and i which multiples at least to xcelNum.