# If Google would be looking to hire F# programmers – part 1

Recently I came across the book Top 10 coding interview problems asked in Google with solutions: Algorithmic Approach. This is perhaps a good book with solutions given in C++, I must admit I just browsed thru the book contents shown by Amazon. Then I thought about an imaginary setting when these coding problems would be given in functional programming interview setting. It seems to me quite tempting to approach them with F# in hand. This post opens a 10 part series where each post would be devoted to F# solution of a problem from this set.

The first problem originates from the “old, but gold” book by Gregory Rawlings Compared to What?: An Introduction to the Analysis of Algorithms under the name **“Nuts and bolts”** (p.293): We wish to sort a bag of n nuts and n bolts by size in the dark. We can compare the sizes of a nut and a bolt by attempting to screw one into the other. This operation tells us that either the nut is bigger than the bolt; the bolt is bigger than the nut; or they are the same size (and so fit together). Because it is dark we are not allowed to compare nuts directly or bolts directly. Devise how to fit all nuts and bolts minimizing number of fittings.

Let’s first establish a solution baseline by using a naïve approach:

- select a random nut;
- fit random bolts one by one until finding the match; put the matching pair aside;
- repeat the process for each of remaining nuts.

Easy to notice that required number of fittings is **O(n*n)**. Can we do better? Sure. Let’s modify the approach:

- as before select a random nut;
- now partition
**ALL**bolts into three piles of fitting, bigger, and smaller, than the pivot nut - then taking a fitting bolt as the pivot (we always have at least one by definition) make the similar partitioning to
**ALL**nuts - at this point we end up with (probably empty) pair of nuts and bolts piles smaller, than pivot, pair of piles of nuts and bolts (having at least one of each) that fit, and (again, probably empty) pair of nuts and bolts piles bigger, than pivot. This is the
**AHA!**moment as it is easy to notice that fitting piles of smaller items and/or fitting piles of bigger items is fully equivalent to the original task, but for shrink dimension.

Using such “divide and conquer” approach we can decrease required number of fittings to only **O(n*log(n))**! And we’ve just rediscovered quickselect, an essential constituent of the famous quicksort.

Now let’s jump to coding. Interestingly, F# would allow us to express the solution very closely to the approach description given above; in other words we can kind of come up with a micro-DSL for solving this particular task:

type Size = int type Bolt = Bolt of Size type Nut = Nut of Size let nutSize = function Nut(size) -> size let boltSize = function Bolt(size) -> size type Bolt with member bolt.Size = boltSize bolt type Nut with member nut.Size = nutSize nut type Bolt with member bolt.Fit (nut: Nut) = bolt.Size.CompareTo nut.Size member bolt.Fit nuts = nuts |> List.partition (bolt.Fit >> (=) 0) |> fun (fit, nonfit) -> let (smaller, bigger) = nonfit |> List.partition (bolt.Fit >> (<) 0) in (fit, smaller, bigger) type Nut with member nut.Fit (bolt: Bolt) = nut.Size.CompareTo bolt.Size member nut.Fit bolts = bolts |> List.partition (nut.Fit >> (=) 0) |> fun (fit, nonfit) -> let (smaller, bigger) = nonfit |> List.partition (nut.Fit >> (<) 0) in (fit, smaller, bigger) let rec fit (nuts: Nut list) (bolts: Bolt list) = seq { match nuts with | [] -> () | _ -> let (boltsFit, boltsSmaller, boltsBigger) = nuts.Head.Fit bolts let (nutsFit, nutsSmaller, nutsBigger) = boltsFit.Head.Fit nuts for (nut,bolt) in (List.zip nutsFit boltsFit) do yield (nut,bolt) yield! fit nutsSmaller boltsSmaller yield! fit nutsBigger boltsBigger }

Let’s see how this works by entertaining the following snippet in FSI:

let amount = 10 let variety = 8 let rand = System.Random() let pieces = [ for i in 1..amount -> rand.Next(1, variety) ] let bagOfNuts = pieces |> List.map Nut let bagOfBolts = pieces |> List.map Bolt |> List.rev fit bagOfNuts bagOfBolts |> Seq.toList

getting:

val pieces : int list = [2; 3; 5; 6; 2; 2; 1; 1; 3; 3] val bagOfNuts : Nut list = [Nut 2; Nut 3; Nut 5; Nut 6; Nut 2; Nut 2; Nut 1; Nut 1; Nut 3; Nut 3] val bagOfBolts : Bolt list = [Bolt 3; Bolt 3; Bolt 1; Bolt 1; Bolt 2; Bolt 2; Bolt 6; Bolt 5; Bolt 3; Bolt 2] val it : (Nut * Bolt) list = [(Nut 2, Bolt 2); (Nut 2, Bolt 2); (Nut 2, Bolt 2); (Nut 1, Bolt 1); (Nut 1, Bolt 1); (Nut 3, Bolt 3); (Nut 3, Bolt 3); (Nut 3, Bolt 3); (Nut 5, Bolt 5); (Nut 6, Bolt 6)]

### Trackbacks & Pingbacks

- If Google would be looking to hire F# programmers – part 2 | In F# Major
- F# Weekly #17, 2013 | Sergey Tihon's Blog
- If Google would be looking to hire F# programmers – part 3 | In F# Major
- Algorithmic Interview questions (with solutions in F#) | musingstudio
- If Google would be looking to hire F# programmers – part 4 | In F# Major
- If Google would be looking to hire F# programmers – part 7 | In F# Major
- Telling Weeds from Wheat: Coding Interview for F# Developer Candidates • Jet Technology Blog

Very cool and interesting post!

Thanks for sharing,

Giacomo

+1 enjoyed this one