Ransom Note problem in F#

Yan Cui

I help clients go faster for less using serverless technologies.

A problem that has shown up multiple times in my preparation for technical interviews is the so called Ransom Note problem.

To solve this in F# is pretty simple.

In the interest of efficiency I decided to use a mutable Dictionary instead of the F# Map to store the no. of times a letter appears in the ransom note.

There’s also an optimization here to stop iterating through the magazine once all the letters for the ransom note is accounted for. One way to do it is to use Seq.takeWhile and mutate the Dictionary as we iterate through letters in the magazine, and stop when letters.Count = 0.

 

Try it Yourself

 

Links


 

Whenever you’re ready, here are 4 ways I can help you:

  1. If you want a one-stop shop to help you quickly level up your serverless skills, you should check out my Production-Ready Serverless workshop. Over 20 AWS Heroes & Community Builders have passed through this workshop, plus 1000+ students from the likes of AWS, LEGO, Booking, HBO and Siemens.
  2. If you want to learn how to test serverless applications without all the pain and hassle, you should check out my latest course, Testing Serverless Architectures.
  3. If you’re a manager or founder and want to help your team move faster and build better software, then check out my consulting services.
  4. If you just want to hang out, talk serverless, or ask for help, then you should join my FREE Community.

 


2 thoughts on “Ransom Note problem in F#”

  1. Can’t it be simpler to use Seq.countBy
    let canConstruct ransomNote =
    let letters = ransomNote |> Seq.countBy id |> Map.ofSeq
    let valueOrDefault letter = defaultArg (Map.tryFind letter letters) 0

    Seq.countBy id >> Seq.exists (fun (letter, count) -> count > valueOrDefault letter)
    Or if you really want to not use a Map
    let canConstruct ransomNote =
    let letters = ransomNote |> Seq.countBy id |> dict
    let valueOrDefault letter = match letters.TryGetValue letter with true, value -> value | _ -> 0

    Seq.countBy id >> Seq.exists (fun (letter, count) -> count > valueOrDefault letter)

  2. good shout, didn’t think of Seq.countBy at the time, it would make it simpler for counting up the letters in the ransomNote, you could do the same with the magazine article too and just check if the corresponding letter count in the magazine article is greater than the ransomNote.

Leave a Comment

Your email address will not be published. Required fields are marked *