FP public code review (#1)

Imagine the following: You're a software engineer in a small team of an amazing but small company. One day your lead comes up to you saying that the company is looking for more engineers to hire but the person in charge of the tech part of the process had to leave in a hurry for her home country in the middle of the process. Unfortunately she won't be available in the foreseeable future.

Originally there were tons of applications but HR and some juniors already filtered out the most obviously weak ones. There's still a handful of applications for you to sort out however. All the applicants solved the same set of problems using some online tool and your job is to check all remaining solutions for one of the problems.

Since there's only time to invite a limited amount of applicants for an on-site interview, they'd like to have your expert opinion about how well each applicant performed. There will be other factors for sending out the invitation(s) so they need more from you than just selecting the best solution. It would be best if you could describe what each solution does well and how they could be improved, but please make sure to score each from 1 to 10, 10 being a perfect solution.

All solutions are in F#, but the company is looking for good programmers, not necessarily F# experts. It's okay if they aren't using F#-specific shortcuts although that's okay too. You need to review their solutions for the following problem: (copy-paste from the Sieve exercism.io problem)

Sieve problem

Use the Sieve of Eratosthenes to find all the primes from 2 up to a given
number.

The Sieve of Eratosthenes is a simple, ancient algorithm for finding all
prime numbers up to any given limit. It does so by iteratively marking as
composite (i.e. not prime) the multiples of each prime,
starting with the multiples of 2.

Create your range, starting at two and continuing up to and including the given limit. (i.e. [2, limit])

The algorithm consists of repeating the following over and over:

• take the next available unmarked number in your list (it is prime)
• mark all the multiples of that number (they are not prime)

Repeat until you have processed each number in your range.

When the algorithm terminates, all the numbers in the list that have not
been marked are prime.

The Wikipedia article has a useful graphic that explains the algorithm:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Notice that this is a very specific algorithm, and the tests don't check
that you've implemented the algorithm, only that you've come up with the
correct list of primes.

Source

Sieve of Eratosthenes at Wikipedia http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Solutions

Here are the solutions you need to rate, review and report back to management and HR. Use the a comment section of this post for communicating with them:

Solution #1

let primesUpTo2 limit =
    let rec mark st acc prime limit =
        let acc' = acc + prime
        match acc' > limit with
        | true -> st
        | false -> mark (Set.add acc' st) acc' prime limit

    let rec iterate st list limit =
        match list with
        | [] -> st
        | x::tail ->
            match Set.contains x st with
            | true -> iterate st tail limit
            | false ->
                let st' = mark st x x limit
                iterate st' tail limit

    let list = [2..limit]
    let nonPrimes = iterate Set.empty list limit
    (Set.ofList list) - nonPrimes |> Set.toList

Solution #2

let primesUpTo3 n =
    let sieveStep n ((primes, composites) as acc) i =
        if Set.contains i composites then acc
        else (i :: primes, {i..i..n} |> Set.ofSeq |> Set.union composites)

    {2..n}
    |> Seq.fold (sieveStep n) ([], Set.empty)
    |> fst
    |> Seq.rev

Solution #3

let primesUpTo1 limit =
    let sq = (limit |> float |> (fun n -> n ** 0.5) |> int )

    let filterMultiples possiblePrimes prime =
        if prime > sq then possiblePrimes
        else possiblePrimes |> List.filter (fun x -> x <= prime || x % prime <> 0)

    let possiblePrimes = [ 2 .. limit ]

    List.fold filterMultiples possiblePrimes possiblePrimes

Solution #4

let primesUpTo4  n =
    let isMultiple factor x = x % factor = 0
    let rec seiveNextPrime primes = function
        | prime :: tail -> seiveNextPrime (prime :: primes) (List.filter (isMultiple prime >> not) tail)
        | [] -> List.rev primes
    seiveNextPrime [] [2..n]

Solution #5

type Candidate  =
    | Unmarked of int
    | Marked of int

let primesUpTo5 limit =
    let mark prime range =
        range 
        |> List.map (
            function
            | Unmarked i when i % prime = 0 -> Marked i
            | c -> c)

    let rec sieve marked =
        function
        | [] -> marked |> Seq.rev
        | ((Unmarked p) as pp) :: tail -> sieve (pp :: marked) (mark p tail)
        | c :: tail -> sieve (c :: marked) tail

    [2..limit]
    |> List.map Unmarked
    |> sieve []
    |> Seq.map (
        function
        | Unmarked i -> i
        | _ -> 0)
    |> Seq.filter ((<) 1)

If you like this discussion, let me know and there might be more coming.

Comments

[Kasey Speakman]

I was all ready to criticize the premise itself rather than the solutions. (For example, I could not give someone a poor rating if they used a mutable implementation. For all I know the interviewer did not make it clear whether maintainability or performance was a pre-eminent concern, so the candidate had to guess.) But after looking at the code, there appears to be a solid basis for comparison.

I did not test whether these have been verified to work. I'm assuming they have. My ratings are in order.

4 is the most easily understandable. There are some minor issues with formatting (i.e. lines too long).

To me, 3 and 2 are tied for 2nd, each for different reasons.

3 requires light math to understand how it deviates from the original the algorithm. So it will be slightly less readable. I doubt there will be any significant performance savings to offset that. Code may indicate an inclination toward math (to be verified by resume/interview) which might be desirable depending on the position.

2 is nice and brief, but the collection operations make it a slightly slower read versus what is expected based on the problem. The code hints to me that the developer is more advanced, but perhaps also "clever".

1 and 5 are overwrought for the problem at hand. I didn't bother to read through them.

None of these functional algorithms are going to be particularly high performing, so I didn't go into a comparison on that basis. It might be interesting to ask the candidates to write two versions of the algorithm: one focusing on ease of maintenance and another focusing on performance.

I should also note that I would probably hire any of the authors of any of these solutions, so long as I had a sense that they were good to work with. That is the far more important consideration for me. Programming skills can be honed much quicker than "good to work with" skills.

[Peter Aba]

Thanks a lot Kasey!

I understand your criticism of the premise, but I think the scenario is not unthinkable. I didn't won't to define the things you mention on purpose.

I guess I could have worded the scenario in a way that there's this super important part of your code that management wanted to get right. 5 devs created their on versions and you're on a board to choose the best one and give feedback to the devs.

And yes, all 5 of them return the right result, but they don't perform the same. I could have added some performance hints but it would have taken away a bit of the fun. I think it's easy to see that #4 is the most elegant, but it's not among the better performers. ;)

[Kasey Speakman]

In the real world, I usually understand the constraints I'm facing when I write a piece of code. I know the code will need highest performance or I've come back to rewrite it because perf was a problem. By default I assume maintainability is highest priority. The last sample might be a valid starting point if I need to explain how I got results. There is no "best" solution without knowing the constraints.

Asking for a solution without telling the person the constraints you need, and then judging them on those constraints, seems like it will miss the point of finding great developers. Besides if perf was really important the dev would use an imperative solution. I recall seeing a video where an Apple engineer used the sieve as performance justification of why they made Swift an OOP language instead of a FP language. Fortunately F# is multi-paradigm so we can choose the best one for the job.

Edit: Sorry for obsessing. I observe this kind of process used in hiring quite a bit nowadays, and it irks me. I assume the setup in the article was fictitious, so my complaints are probably a bit misplaced here. 🤐

[Jakob Christensen]

I should also note that I would probably hire any of the authors of any of these solutions, so long as I had a sense that they were good to work with. That is the far more important consideration for me. Programming skills can be honed much quicker than "good to work with" skills.

I couldn't agree more :)