Skip to content

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

April 24, 2013

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)]

To be continued…

Advertisements

From → F#

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: