Markdium-14 Fibonacci Interview Questions (SOLVED) To Brush Before Coding Interview

Markdium-C#.cs

#include 
#include 
#include "search.h"

typedef struct FibonacciValues
{
  // Fibonacci number: F(n) = F(n-1) + F(n-2)
  int Fn_2; // F(n-2)
  int Fn_1; // F(n-1)
  int Fn;   // F(n)

  FibonacciValues(int fn_2, int fn_1, int fn)
    : Fn_2(fn_2)
    , Fn_1(fn_1)
    , Fn(fn)
  {
    assert(Fn == Fn_1 + Fn_2);
  }

  ~FibonacciValues()
  {
  }

  void forward()
  {
    Fn_2 = Fn_1;
    Fn_1 = Fn;
    Fn = Fn_1 + Fn_2;
    assert(Fn == Fn_1 + Fn_2);
  }

  void backward()
  {
    Fn = Fn_1;
    Fn_1 = Fn_2;
    Fn_2 = Fn - Fn_1;
    assert(Fn == Fn_1 + Fn_2);
  }

} FibonacciValues;

// Returns the smallest Fibonacci number that is greater than or equal to k.
FibonacciValues GetFibonacci(int k)
{
  FibonacciValues fib(0, 1, 1);
  while (fib.Fn < k) {
    fib.forward();
  }
  return fib;
}

// Notice that the current middle might exceed the array!

int fibonacciSearch(int list[], const unsigned int length, int key)
{
  assert(list && length);

  int left = 0, right = length - 1, middle;
  // Find a fibonacci number F(n) that F(n) - 1 >= length
  FibonacciValues fib = GetFibonacci(length + 1);

  while (left <= right) {
    // Avoid the middle is over the array.
    middle = std::min(left + (fib.Fn_1 - 1), right);

    if (list[middle] == key) {
      return middle;
    } else if (list[middle] > key) {
      right = middle - 1;
      fib.backward();
    } else { // list[middle] < key
      left = middle + 1;
      fib.backward(); fib.backward();
    }
  }

  return NOT_FOUND;
}