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

Sigiloso

29 de jun. de 2010

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 ]

2

Sigiloso

29 de jun. de 2010

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

1

Sigiloso

19 de mar. de 2009

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.

6

Sigiloso

21 de mai. de 2009

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'); }

1

Sigiloso

31 de mai. de 2009

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; } }

Sigiloso

10 de dez. de 2010

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(); }

Sigiloso

4 de nov. de 2014

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

Sigiloso

4 de nov. de 2014

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

Sigiloso

13 de jan. de 2015

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; }

Sigiloso

10 de out. de 2014

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);

Sigiloso

10 de out. de 2014

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);

Sigiloso

10 de dez. de 2010

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(); }

Sigiloso

10 de dez. de 2010

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.