Excel Sheet Row Numbers

by 107 Replies

Given the sequence S1 = {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence S2 = {0,1,2,3,….}. Write code to convert an element of S2 to the corresponding element of S1.

Your challenge, should you accept it, is to code this problem correctly on your first try. Without any help from the computer of course 🙂 You might think you have the idea to solve it but it is tricky to code it correctly.

Hint:

I’ve created the following table for your convenience.

      a - 0     aa - 26   .....   za - 676    aaa - 702
      b - 1     ab - 27   .....   zb - 677    aab - 703
      c - 2        .                 .            .
        .          .                 .            .
        .          .                 .            .
        .          .                 .            .
      z - 25    az - 51   .....   zz - 701    aaz - 727

From a-z, how many of them are there? How about aa-zz? And aaa-zzz?

Solution:
You should be able to observe that from a-z (a total of 26), from aa-zz (a total of 262), from aaa-zzz (a total of 263), and so on… I will explain why this is important later.

Assume s1 = abc and we need to find its corresponding number, s2. Now imagine that aaa can be magically transformed to 000, aab –> 001, …, and abc to some number xyz. The question is, what should xyz be?

Now this is a trivial question. Why? Remember that our numeral system has 10 as its base. Here, we are merely converting the system from base 26 to base 10. Therefore, xyz = 2*260 + 1*261 + 0*262 = 28.

But wait, we are not finished yet. To find the real value of s2, we need to find how many of them appeared before aaa and add to xyz. Using the important observation earlier, we can easily determine that that there are a total of 26 + 262 = 702 that appeared before aaa. Therefore, s1 corresponds to the number s2 = 28 + 702 = 730.

Assume that we are converting from s2 = n to s1 = “abcde…”.
We can generalize to the following equation (Equation (1)):

Equation (1)

n = 26 + 262 + ... + 26k-1 + a0 + a1*26 + a2*262 + ... + ak-1*26k-1
  = a0 + (a1 + 1) 26 + (a2 + 1) 262 + ... + (ak-1 + 1) 26k-1 

where 
ai ranges from 0-25 (each representing a letter in s1), 
k is the number of letters in s1.

To solve the above equation, we have to find the values of a0, a1, …, ak-1. Once we solve this equation, we are able to determine the string of letters of s1 directly.

a0 can be solved by taking n % 26. Why? Because a0 ranges from 0-25, which is not divisible by 26, while the rest are factor of 26. After we obtained the value of a0, we divide n by 26. This will yield the number 

n' = (a1 + 1) + (a2 + 1) 26 + ... + (ak-1 + 1) 26k-2

You might think that a1 + 1 = n’ % 26. This is wrong. What happens when a1 = 25? For sure, a1 +1 is divisible by 26, and thus the mentioned equation is invalid. We can easily resolve this by doing a1 = (n’ – 1) % 26.

The rest is easy, we continue further with n” = (n’ – 1) / 26 and a2 = (n” – 1) % 26, up until ak-1.

Clearly, we need to do both modulo 26 and divide by 26 operations a total of k-1 times. But do we really need to know the value of k (or the number of letters in s1)?

The beauty of this method is, since we start from the least significant digit and work our way up, we don’t need to evaluate k. We just need to divide n by 26 repeatedly until it becomes 0.

Alternative Solution:
The above solution can be converted to a recursive solution too. The advantage is the recursive solution can print the solution directly without storing the characters into a variable. Check my post: Recursion to the Rescue! where recursion is used to reverse a string.

Further Thoughts:
This question is actually much easier to solve if S2 is changed to:

S2 = {1,2,3,4,….} ie, a->1, b->2, c->3, …, aa->27.

Then transforming from n to a string in S1 is just the same as converting the number from base 10 to base 26. Using this idea as a starting point, you can derive the same Equation (1) above.

VN:F [1.9.22_1171]
Rating: 4.9/5 (11 votes cast)
Excel Sheet Row Numbers, 4.9 out of 5 based on 11 ratings

107 thoughts on “Excel Sheet Row Numbers”

  1. Smirnov

    Bar raiser? Like you said, convert from base 10 to base 26. Something pretty darn obvious once you get the answer.

    I would've expected a bar raiser to be a question more complex that even the answer would require lots of explanation.

    VA:F [1.9.22_1171]
    0
    Reply ↓
    1. xiuyu.song

      a->0
      aa->26 Now the first a has weight 1 instead of 0
      z->25
      as follow the decimal rule, the next should be ba, but we have aa, where if a is zero we get 00
      In other words, 10 based numbers 01 is 1, while here aa is not a

      Now if we follow the rule: right most letters weight 0-25, while others weight 1-26
      so 676 = 26 * 26 should be za = 26*26 + 0;
      27*26 corresponding to aaa = 1*26*26 + 1*26 + 0;

      Reverse the logic is the answer

      VN:F [1.9.22_1171]
      0
      Reply ↓Report user
  2. 1337c0d3r

    No, it's not that straight forward. As mentioned in "Further Thoughts", this question cannot be solved by converting from base 10 to base 26 directly, but it is a good starting point.

    I believe my approach is more complicated than necessary though. (ie, tedious math required to outline the idea)

    VA:F [1.9.22_1171]
    0
    Reply ↓
  3. Anonymous

    Can also solve this problem through recursion.

    public static void printNum2Chr(int num) {
    LinkedList list = convertNum2Chr(num);
    while (list.size() > 0) {
    System.out.print(list.removeLast());
    }
    System.out.println();
    }

    private static LinkedList convertNum2Chr(int num) {
    LinkedList retList = new LinkedList();
    if (num < 26) {
    retList.add(new Character((char)('a' + num)));
    return retList;
    }

    LinkedList tmpList = convertNum2Chr(num – 1);
    int n = 1;
    while (tmpList.size() > 0) {
    char c = tmpList.removeFirst().charValue();
    c = (char)(c + n);
    if (c < 'z') {
    retList.add(c);
    n = 0;
    } else {
    retList.add('a');
    n = 1;
    }

    if (n == 1 && tmpList.size() == 0) {
    retList.add('a');
    }
    }

    return retList
    }

    VA:F [1.9.22_1171]
    0
    Reply ↓
  4. Anonymous

    I believe your solution is not quite right.

    For input value 676, the correct answer is to print out the string aza, but your code prints out the string za. The leading "a", which is kind of zero, is omitted.

    Dealing with leading "zeros" is an essential part of the problem, and is glossed over by just thinking in terms of base conversions.

    Also, fwiw, I find your explanation needlessly tedious and turgid. Why attribute false reasoning to the user, just to shoot it down?

    VA:F [1.9.22_1171]
    0
    Reply ↓
    1. ifanchu

      Actually you are wrong, 676 should get YZ if A = 1, in this question A = 0, so 676 = YY. I actually checked this on Google Spreadsheet…

      VA:F [1.9.22_1171]
      0
      Reply ↓
  5. Anonymous

    this is simple conversion from base 10 to base 26

    void convert(unsigned int N)
    {
    unsigned char a = 'a';
    unsigned int Base = 26;

    if(N < Base)
    {
    printf("%c",a+N);
    }
    else
    {
    convert(N/Base-1);
    printf("%c",a + (N%Base));
    }
    }

    int main()
    {
    unsigned int x;

    for(x= 0; x<= 727; x++)
    {
    printf("%i ", x);
    convert(x);
    printf("\n");
    }

    return 0;
    }

    VA:F [1.9.22_1171]
    0
    Reply ↓
  6. Anonymous

    No it's not just base 26. I was asked this exact same question at a Google interview recently, and failed to get hired. (BTW, that sequence is _exactly_ the column names of a spreadsheet.) I guess they feel they are hiring too many people these days, and are trying to pick the few that come by that can solve problems current employees cannot even solve themselves. Good luck with that Google

    VA:F [1.9.22_1171]
    0
    Reply ↓

  8. Pingback: Amazon “Bar Raiser” Interview Question | 口├人人│의 Blog

  12. Sandeep Giri

    This also looks simple and straight. I just tested it against your code.

    VA:F [1.9.22_1171]
    +1
    Reply ↓
  14. Brady Fang

    VN:F [1.9.22_1171]
    0
    Reply ↓Report user
  17. conkey

    java solution

    VN:F [1.9.22_1171]
    0
    Reply ↓Report user
  18. Leet

    JAVA Solution to convert number to string in excel sheet

    VA:F [1.9.22_1171]
    0
    Reply ↓
  19. Sam

    Hi, can anybody please help me understand this. when we consider a=1,b=2…. we can covert the given string directly to an integer. Here we are converting the base to 26. I am clear with that. but what i am confused about is we are not considering cases when the number can contain digit ‘0’. And that leads me to the confusion that why do we need to add 26^1+26^2…+26^k when we consider a=0,b=1,c=2….I will really appreciate your help

    VA:F [1.9.22_1171]
    0
    Reply ↓
  23. LeonardClots

    example of culture shock essay
    freres scott resume saison 2
    free cloning outline for research paper
    free essay on children and poverty
    good books for english extended essay

    VA:F [1.9.22_1171]
    0
    Reply ↓

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

CAPTCHA

*