Interview Timing

April 19, 2016

I came across an interesting interview question recently. I’ll tell you the question shortly. What made it interesting was that the same question was given to all candidates, and they were timed in getting a solution; candidates with shorter times were given higher scores than candidates with longer times.

Your task is to write the requested program, which you can access HERE after you are set up for timing.

Pages: 1 2 3

23 Responses to “Interview Timing”

  1. Typical perl solution…. convert number to binary – and count the ones… approx 1 minute.

    [sourcecode lang="perl"]
    use feature ‘say’;
    say 1 == (sprintf ‘%b’, shift) =~ tr/1/1/ ? ‘T’ : ‘F’;
    [/soucecode]

  2. Zack said

    function is_power_of_2(n::Int64)
    x = 2

    while x < n
    if n % x != 0
    return false
    end

    x *= 2
    end

    return true
    end

    <5 min, incl. unit testing

  3. Jussi Piitulainen said

    I searched the web for a Scheme function that counts bits. Guile, at least, has one, called logcount. For a positive integer, it returns the number of 1’s in its binary expansion.

    (= (logcount n) 1)
    

    It took me a few hours to think of this and then a couple of minutes more to execute the plan, and it’s still not a program. It’s easy to make it a procedure, but what exactly the shebang line should be? (I know Guile supports scripting, but I would have to look this up) and how to access the command line parameters? (I think I’ve done this before and it’s not complicated, but I would have to look this up again).

    I did write a Python expression initially, in five minutes or so, checking that the bits after the initial 1 in a written representation are all 0. I could set a script to access a first command line parameter in a minute, but then I would wish that I had taken the time to use the argparse library, which I would have to look up again (or copy from another script).

    set(bin(n)[3:]) == set('0') # bin(n) begins "0b1"
    

    That’s also not quite right, because there’s a power of 2 that does not contain a 0 at all. Is it better to have written a flawed expression in five minutes or a fixed version in five hours? (So I got distracted in the middle of this interview.)

  4. Jussi Piitulainen said

    You want to wrap your code in sourcecode brackets, so the platform keeps the indentation. Like James did above but without the typo in the end bracket. Apparently the lang attribute is optional, or you can call your language just “text” if it’s not specifically supported. (Thanks for that documentation link in the previous exercise.)

  5. programmingpraxis said

    @Jussi: I used population count as an exercise: https://programmingpraxis.com/2011/01/28/population-count/.

  6. Marshall Quander said

    I wrote it in forty seconds because I knew a trick:

    (defn power-of-two [n] (zero? (bit-and n (dec n))))

  7. Globules said

    Haskell (in ghci). Less than a minute.

    λ> let isPow2 n = Data.Bits.popCount n == 1
    λ> map isPow2 [0..9]
    [False,True,True,False,True,False,False,False,True,False]
    λ> 
    
  8. Paul said

    Maybe not the fastest.

    def is_power_of_2(n):
        if n <= 0:
            return False
        while n % 2 == 0:
            n //= 2
        return n == 1
    
  9. Mike said

    Two versions: First version counts the number of 1’s in the string representation of n. The second version ensures only most significant bit is set.

    def is_power_of_two_v1(n):
    return bin(n).count(‘1’) == 1

    def is_power_of_two_v2(n):
    return n and n == 1 << n.bit_length() – 1

    Took less than a minute to write and test the first version. And another minute and a half to write the second.

  10. kernelbob said

    Thirty-nine seconds. The first `date` command was before I clicked the link.

    ~$ date
    Thu Apr 21 08:33:31 PDT 2016
    ~$ python
    Python 3.5.1 (default, Mar 10 2016, 06:59:42) 
    [GCC 4.2.1 Compatible Apple LLVM 7.0.2 (clang-700.1.81)] on darwin
    Type "help", "copyright", "credits" or "license" for more information.
    >>> def f(n): return (n & (n - 1)) == 0
    ... 
    >>> f(3), f(4)
    (False, True)
    >>> 
    ~$ date
    Thu Apr 21 08:34:10 PDT 2016
    
  11. matthew said

    I suppose this took about an hour including googling for esoteric properties of powers of two, reading http://www.cut-the-knot.org/arithmetic/UnpropertyOfPowersOf2.shtml and actually implementing the algorithm – all natural numbers are the sum of two or more consecutive numbers, unless they are powers of two:

    def ispow2(n):
        for i in range(2,n):
            t = 2*n + i - i*i
            if t <= 0: break
            if t % (2*i) == 0: return False
        return True
    
    print [(n,ispow2(n)) for n in range(1,20)]
    
  12. matthew said

    Of course, in an actual interview it might be good to check on the scope of the question – maybe they want a solution for an esoteric floating point or bignum format.

  13. Daniel said

    Here’s a Java solution.

    static boolean isPower2(long num) {
    return num > 0 && Long.highestOneBit(num) == num;
    }

  14. Daniel said

    Same as above, but attempting to add source formatting.

    static boolean isPower2(long num) {
        return num > 0 && Long.highestOneBit(num) == num;
    }
    
  15. matthew said

    Here’s another bit twiddling solution, only using shift and xor though:

    #include <stdio.h>
    template<int n, typename T>
    struct aux {
      static bool f(T t) {
        T t0 = t & ((T(1)<<n)-1);
        T t1 = t >> n;
        if (t1 == 0) return aux<n/2,T>::f(t0);
        if (t0 == 0) return aux<n/2,T>::f(t1);
        return false;
      }
    };
    
    template<typename T>
    struct aux<0,T> {
      static bool f(T t) { return t; }
    };
    
    int main() {
      for (int i = 0; i < 20*64; i++) {
        printf("%c%s",
               aux<16,int>::f(i)?'*':'-',
               (i+1)%64?"":"\n");
      }
    }
    
  16. Daniel said

    The bit twiddling solution that I’ve previously seen for this problem uses the fact that BITWISE_AND(n, n-1) == 0 if and only if n is a power of two, .

    Here it is in Java.

    static boolean isPowerOfTwo(long num) {
        return num > 0 && (num & (num-1)) == 0;
    }
    
  17. Rocky said
    def powoftwo(n):
    	import math
    	# Tells if n is a power of two.
    	log = math.log(n, 2)
    	if log == int(log):
    		return True
    	else: 
    		return False
    

    Took about a minute. I first thought to do something very similar to what paul said but then I decided to take advantage of pythons built in math libraries. I’m sure theres an easier way to do the boolean expression i have in the if statement but, we’ll see i suppose.

  18. Daniel said

    > “I’m sure theres an easier way to do the boolean expression i have in the if statement but, we’ll see i suppose.”

    @Rocky, I suppose both of the following approaches could be considered be “easier ways” to do the boolean expression.

    import math
    def powoftwo2(n):
        log = math.log(n, 2)
        return log == int(log)
    
    def powoftwo3(n):
        return math.log(n, 2).is_integer()
    

    However, beware that approaches using math.log run into numerical precision issues for large n. For example, 140737488355328L is a power of two, but poweroftwo returns False. And 281474976710655L is not a power of two (it’s odd), but poweroftwo returns True.

  19. Daniel said

    The following uses math.log and has a workaround for the numerical precision issues in the examples above.

    import math
    def powoftwo4(n):
        return 2 ** int(math.log(n, 2)) == n
    
  20. matthew said

    @Rocky, @Daniel: There are still some rounding issues for larger values of n where math.log returns slightly less than the true value, eg. powoftwo4(2**2955) returns False, since math.log(2**2955,2) returns 2954.9999999999995. A simple fix (at least, it works for n up to 2**100000000 – we would run out of precision eventually) is:

    def powoftwo(n): return 2**int(math.log(n, 2) + 0.5) == n
    
  21. Daniel said

    Thanks @matthew.

    I considered that possibility, but missed it, as my test didn’t check numbers high enough (only checked up to 2**400).

    [int(math.log(2**w,2)) for w in range(1,400)] == range(1,400)
    
  22. Daniel said

    > “only checked up to 2**400”

    Or more precisely, 2**399

  23. matthew said

    Thinking a bit more: not important here, but adding 0.5 won’t work for negative numbers (since int() will round towards 0). int(round(x)) is better.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: