Second Phone Interview w/ A**zon - Edit

C.R. of A**zon called and put me thru a whiteboard exercise.

He asked some questions:
0. what do I want to do (well, Embedded Linux, I think my Resume is clear on that);
1. write a non-recursive Fibonacci generator;
2. change code to return the n-th bit of a bit accumulator;
3. optimize code
(my C-ish pseudo code is below).

I drilled him and got some answers:
i. the development I am interested in is done partly in Cupertino, CA in "Låb 126";
ii. the code-writing interview is to establish a "SDE bar";
iii. they don't have a job in mind for this requisition, it may float among departments;
iv. monetary compensation is part cash part stock; he stressed that one gets shares not options and that compensation is comparable or better than the Seattle pay level of M$ and G**gle.

(This sort of riddles were homework du jour in the 10th and 11th grade in high school. Thanks to my professor, D.G., I went thru them all. She would go ballistic to see the return in the for() loop ;)

Fibonacci:

fib(n) // x(n):=x(n-1)+x(n-2), n > 2; x(1):=1; x(2):=2
{
  if(n < 1) // error
  if(n == 1) return 1;
  if(n == 2) return 2;

  n1 = 1; n2 = 2;
  
  for(i = 3; i <= n; i++) {
    new_n = n1 + n2;
    if(i == n) return new_n; // C.R. asked why in the middle?
    n1 = n2;
    n2 = new_n;
  }

  /*NOTREACHED*/
}

Bit accumulator, crappy implementation:

bit(n) // bit accumulator 
{
  if(n < 0) // error
  if(n == 0) return 0;
  if(n == 1) return 1;

  n1 = 0; n2 = 1;
  
  for(i = 2; i <= n; i++) {
    new_n = (n1 + n2) % 2;
    if(i == n) return new_n;
    n1 = n2;
    n2 = new_n;
  }

  /* NOTREACHED*/
}

Bit accumulator, optimised:

bit(n) // bit accumulator 
{
  // 0 1 2  3 4 5  6 7 8  9
  // -----  -----  -----  -
  // 0 1 1  0 1 1  0 1 1  0

  if((n % 3) == 0) return 0;
  return 1;
}

-ulianov