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.
Programming Praxis 
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]
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
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.
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.)
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.)
@Jussi: I used population count as an exercise: https://programmingpraxis.com/2011/01/28/population-count/.
I wrote it in forty seconds because I knew a trick:
(defn power-of-two [n] (zero? (bit-and n (dec n))))
Haskell (in ghci). Less than a minute.
Maybe not the fastest.
def is_power_of_2(n): if n <= 0: return False while n % 2 == 0: n //= 2 return n == 1Two 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.
Thirty-nine seconds. The first `date` command was before I clicked the link.
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)]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.
Here’s a Java solution.
static boolean isPower2(long num) {
return num > 0 && Long.highestOneBit(num) == num;
}
Same as above, but attempting to add source formatting.
static boolean isPower2(long num) { return num > 0 && Long.highestOneBit(num) == num; }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"); } }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; }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.
> “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.
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@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:
Thanks @matthew.
I considered that possibility, but missed it, as my test didn’t check numbers high enough (only checked up to 2**400).
> “only checked up to 2**400”
Or more precisely, 2**399
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.