How we handle this question on interview [Thinking process + DP solution]


  • 90
    J

    Question:
    Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

    Thinking:

    1. We do not need check the input parameter, because the question has already mentioned that the number is non negative.

    2. How we do this? The first idea come up with is find the pattern or rules for the result. Therefore, we can get following pattern

    Index : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    num : 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

    Do you find the pattern?

    Obviously, this is overlap sub problem, and we can come up the DP solution. For now, we need find the function to implement DP.

    dp[0] = 0;

    dp[1] = dp[0] + 1;

    dp[2] = dp[0] + 1;

    dp[3] = dp[1] +1;

    dp[4] = dp[0] + 1;

    dp[5] = dp[1] + 1;

    dp[6] = dp[2] + 1;

    dp[7] = dp[3] + 1;

    dp[8] = dp[0] + 1;
    ...

    This is the function we get, now we need find the other pattern for the function to get the general function. After we analyze the above function, we can get
    dp[0] = 0;

    dp[1] = dp[1-1] + 1;

    dp[2] = dp[2-2] + 1;

    dp[3] = dp[3-2] +1;

    dp[4] = dp[4-4] + 1;

    dp[5] = dp[5-4] + 1;

    dp[6] = dp[6-4] + 1;

    dp[7] = dp[7-4] + 1;

    dp[8] = dp[8-8] + 1;
    ..

    Obviously, we can find the pattern for above example, so now we get the general function

    dp[index] = dp[index - offset] + 1;

    Coding:

    public int[] countBits(int num) {
        int result[] = new int[num + 1];
        int offset = 1;
        for (int index = 1; index < num + 1; ++index){
            if (offset * 2 == index){
                offset *= 2;
            }
            result[index] = result[index - offset] + 1;
        }
        return result;
    }

  • 4
    1. We do not need check the input parameter, because the question has
      already mentioned that the number is non negative.

    I wouldn't be so sure. Because it seems to me, such a statement asks exactly for parameter checking. Throwing exceptions on illegal arguments is a good practice, and I'd at least mention it during the interview.


  • 1
    J

    Yes your are right, but this is for question rather than real world.


  • 2

    Well, as I understand it, the point of interview is to check how well the interviewee can work in the real world. If I was facing this question in a real interview, I'd rather say something like “here should be an argument check, but I'll omit it for brevity” than “we don't need to check the input parameter”.


  • 0
    J

    Absolutely agree with you:)


  • 0
    This post is deleted!

  • 0
    D

    Much thanks. Struggled a lot to figure out the pattern. But your post really explained in a nice way.


  • 0
    H

    My solution is similar to yours <^>

    vector<int> countBits(int num) {
            if(num < 0) return vector<int>();
            vector<int> res(num + 1,0);
            res[0] = 0; int j = 0; 
            int mark = 2;
            for(int i = 1; i < num + 1; i++) {
                res[i] = res[j++] + 1;
                if(mark == i+1) {
                    j = 0;
                    mark <<= 1;
                }
            }
            return res;
        }
    

  • 0

    great explanation!


  • 1
    N

    Nice solution. But it is tricky to come up with this
    one in an interview.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.