Fibonacci Search — Interview Preparation¶

A topic that almost never appears in coding-interview problems but is a favorite whiteboard discussion question at companies that build numerical libraries, embedded firmware, or scientific software (SciPy contributors, MATLAB engineers, control-systems firms, scientific HPC shops). Knowing it cleanly distinguishes a strong candidate.

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Coding Challenge (3 Languages)¶

Challenge: Implement Fibonacci search and verify against binary search¶

Write fib_search(arr, target) that returns any valid index of target (or -1), using only addition / subtraction (no /, no *). Then test it against a binary-search reference on 10,000 random sorted arrays.

Go¶

package main

import (
    "fmt"
    "math/rand"
    "sort"
)

func FibSearch(arr []int, target int) int {
    n := len(arr)
    if n == 0 {
        return -1
    }
    fkm2, fkm1, fk := 0, 1, 1
    for fk < n {
        fkm2, fkm1, fk = fkm1, fk, fkm1+fk
    }
    offset := -1
    for fk > 1 {
        i := offset + fkm2
        if i > n-1 {
            i = n - 1
        }
        if arr[i] < target {
            fk, fkm1, fkm2 = fkm1, fkm2, fkm1-fkm2
            offset = i
        } else if arr[i] > target {
            fk, fkm1, fkm2 = fkm2, fkm1-fkm2, fkm2-(fkm1-fkm2)
        } else {
            return i
        }
    }
    if fkm1 == 1 && offset+1 < n && arr[offset+1] == target {
        return offset + 1
    }
    return -1
}

func BinarySearch(arr []int, target int) int {
    lo, hi := 0, len(arr)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

func main() {
    for k := 0; k < 10_000; k++ {
        n := rand.Intn(200)
        arr := make([]int, n)
        for i := range arr {
            arr[i] = rand.Intn(500)
        }
        sort.Ints(arr)
        target := rand.Intn(500)
        a := BinarySearch(arr, target)
        b := FibSearch(arr, target)
        ok := (a == -1 && b == -1) || (a >= 0 && b >= 0 && arr[a] == arr[b])
        if !ok {
            fmt.Printf("MISMATCH a=%d b=%d arr=%v target=%d\n", a, b, arr, target)
            return
        }
    }
    fmt.Println("10000 random tests passed")
}

Java¶

import java.util.Arrays;
import java.util.Random;

public class FibSearchChallenge {
    public static int fibSearch(int[] arr, int target) {
        int n = arr.length;
        if (n == 0) return -1;
        int fkm2 = 0, fkm1 = 1, fk = 1;
        while (fk < n) { int t = fk; fk = fk + fkm1; fkm2 = fkm1; fkm1 = t; }
        int offset = -1;
        while (fk > 1) {
            int i = Math.min(offset + fkm2, n - 1);
            if (arr[i] < target) { fk = fkm1; fkm1 = fkm2; fkm2 = fk - fkm1; offset = i; }
            else if (arr[i] > target) { fk = fkm2; fkm1 = fkm1 - fkm2; fkm2 = fk - fkm1; }
            else return i;
        }
        if (fkm1 == 1 && offset + 1 < n && arr[offset + 1] == target) return offset + 1;
        return -1;
    }

    public static int binarySearch(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        Random rng = new Random(0xC0FFEE);
        for (int k = 0; k < 10_000; k++) {
            int n = rng.nextInt(200);
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = rng.nextInt(500);
            Arrays.sort(arr);
            int target = rng.nextInt(500);
            int a = binarySearch(arr, target);
            int b = fibSearch(arr, target);
            boolean ok = (a == -1 && b == -1) || (a >= 0 && b >= 0 && arr[a] == arr[b]);
            if (!ok) throw new AssertionError("mismatch");
        }
        System.out.println("10000 random tests passed");
    }
}

Python¶

import random

def fib_search(arr, target):
    n = len(arr)
    if n == 0:
        return -1
    fkm2, fkm1, fk = 0, 1, 1
    while fk < n:
        fkm2, fkm1, fk = fkm1, fk, fk + fkm1
    offset = -1
    while fk > 1:
        i = min(offset + fkm2, n - 1)
        if arr[i] < target:
            fk, fkm1, fkm2 = fkm1, fkm2, fkm1 - fkm2
            offset = i
        elif arr[i] > target:
            fk, fkm1, fkm2 = fkm2, fkm1 - fkm2, fkm2 - (fkm1 - fkm2)
        else:
            return i
    if fkm1 == 1 and offset + 1 < n and arr[offset + 1] == target:
        return offset + 1
    return -1

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

if __name__ == "__main__":
    random.seed(0xC0FFEE)
    for _ in range(10_000):
        n = random.randint(0, 200)
        arr = sorted(random.randint(0, 500) for _ in range(n))
        target = random.randint(0, 500)
        a = binary_search(arr, target)
        b = fib_search(arr, target)
        ok = (a == -1 and b == -1) or (a >= 0 and b >= 0 and arr[a] == arr[b])
        assert ok, f"mismatch arr={arr} target={target} a={a} b={b}"
    print("10000 random tests passed")

Behavioral / System Design Questions¶

Common Follow-Up Probes from Interviewers¶

After your initial answer, expect any of these:

Whiteboard Variants¶

Variant A — Modify for a sorted descending array¶

Flip every comparison: arr[i] > target triggers the "discard left" branch, etc. Don't change the Fibonacci bookkeeping.

Variant B — Fibonacci search on a Comparable<T> array¶

Replace <, >, == with compareTo. Otherwise identical.

Variant C — Iterative bracket-shrink instead of fixed iteration count¶

Run until the bracket has only 1 element, then directly check. This is the most readable form.

Variant D — Find the closest value, not the exact target¶

Run the lower-bound variant; then compare arr[result - 1] and arr[result] to target; return whichever is closer.

Variant E — Fibonacci search over a memoized function (golden-section-style)¶

Cache arr[i] evaluations; when an arr[i] is requested twice (rare with the standard pattern but possible with the lower-bound variant), serve from cache.

"Why Do I Care?" Talking Points for Behavioral Rounds¶

When an interviewer asks "why did you study Fibonacci search?", strong answers connect it to broader competencies:

1. Algorithmic literacy. Understanding why binary search is optimal requires knowing what suboptimal alternatives exist.
2. Numerical optimization. Golden-section search is the entry point to derivative-free 1D optimization, which is fundamental to ML hyperparameter tuning, control-system calibration, and scientific computing.
3. Hardware awareness. Knowing when division is expensive vs free shapes embedded firmware design.
4. Mathematical foundation. The golden ratio's role as the "most irrational number" connects to continued fractions, Diophantine approximation, and the Euclidean GCD.
5. History. The fact that this algorithm was invented in 1960 for tape-drive search — a context that no longer exists — illustrates how cost models drive algorithm design.

Final Tips¶

• Don't oversell Fibonacci search. Acknowledge upfront that binary search is usually better.
• Connect to golden-section search. This is where the interview gets interesting; senior interviewers love the pedagogical chain.
• Be precise about the 1.44 constant. 1 / log_2(φ) = 1.4404... Memorize this.
• Know the proof structure. Even if you don't memorize the full Kiefer proof, sketch the invariant and recurrence.
• Have an embedded story. "On a Cortex-M0 firmware I worked on..." beats abstract theory.
• Bring bisect_left / Arrays.binarySearch / slices.BinarySearch to mind as the default. Recommend these unless the constraints rule them out.
• Mention the SciPy connection. minimize_scalar(method='golden') is the production Python answer; fminbnd for MATLAB; optimize for R.
• Be ready to draw φ on a number line. Many interviewers find this clarifying when discussing the 38/62 split.
• Don't memorize all 30 questions. The graders want depth on 3-5 questions, not surface coverage of 30.

Five-Minute Mock-Interview Script¶

Interviewer: Describe Fibonacci search and when it's useful.

You: Fibonacci search is a sorted-array search algorithm that runs in O(log_φ n) ≈ 1.44 · log₂ n iterations. Unlike binary search, which probes the midpoint, Fibonacci search probes at offset F_{k-2} from the current left edge, using consecutive Fibonacci numbers. The key property is that it uses only addition and subtraction — no division or multiplication. It's useful on CPUs without hardware divide (Cortex-M0, AVR, RV32I base) and as the conceptual ancestor of golden-section search.

Interviewer: Why are Fibonacci numbers the natural splitter?

You: Because F_{k-2} + F_{k-1} = F_k, so when you probe at offset F_{k-2} in a window of size F_k, the two halves have sizes F_{k-2} and F_{k-1} — both still Fibonacci numbers, so the recursion is self-similar.

Interviewer: Walk me through it on [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100, 235], target 85.

You: n=12, smallest Fib ≥ 12 is 13, so F_k=13, F_{k-1}=8, F_{k-2}=5. Offset=−1. Iter 1: probe at index 4, value 45 < 85, shift twice, F_k=8, F_{k-1}=5, F_{k-2}=3, offset=4. Iter 2: probe at 7, value 82 < 85, shift twice, F_k=5, F_{k-1}=3, F_{k-2}=2, offset=7. Iter 3: probe at 9, value 90 > 85, shift once, F_k=2, F_{k-1}=1, F_{k-2}=1, offset=7. Iter 4: probe at 8, value 85 == 85, return 8.

Interviewer: How does this relate to golden-section search?

You: Golden-section search is the continuous analogue. It uses the limit ratio φ = (1 + √5) / 2 as the split, and it has the unique property that one of the previous probe positions falls exactly at the symmetric golden-ratio position of the new bracket — so only one new function evaluation per iteration. That makes it the default 1D minimizer in scipy.optimize.minimize_scalar(method='golden') and the fallback in Brent's method.

Interviewer: What would you actually use in production?

You: For sorted-array search, binary search — every time. For unimodal optimization with expensive evaluations, golden-section or Brent's method.