> FizzBuzz is a very simple toy problem for screening programming
> applicants at interviews.
Once upon a time I used questions like the following
to screen for a firm that wanted high power
applicants. The interviewees had pencil and paper
but no computers.
a. Compute y^n in less than O(n) steps.
b. The Fibonacci numbers are defined as follows:
0=0{f
1=1{f
(n{f) = ((n-2){f) + (n-1){f for n>:2
Compute the n-th Fibonacci number is less than O(n) steps.
c. Sort a list of integers in O(n) steps.
d. In C, find the number of bits in a byte.
Spoilers below.
a. Repeated squaring.
b. Successive Fibonacci numbers are related by
multiplication by the matrix 0 1,:1 1. Use
repeated squaring.
c. Lexicographic sort.
d. x is a variable of type char; initialize to 1;
count the number of left shifts to get x to 0.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
