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:
google, base conversion, excel
Answer

Interview Answer

13 Answers

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
0

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

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

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 > 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 >= 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 < 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 < 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< 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< 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.