Daily Coding Problem 1

Daily Coding Problem 1

Daily Coding Problem 1

Problem Statement

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?

Solution

Strategy 1 - Brute Force

Take each element in the list, add to every other element, and check if any of the sums equals k.
In [1]:
// Easy way to work with any Nuget packages
#load "Paket.fsx"
Paket.Package 
    [ "FSharp.Collections.ParallelSeq"
      "Expecto"
      "Xplot.Plotly"
      "XPlot.GoogleCharts"
    ]
#load "Paket.Generated.Refs.fsx"
#load "XPlot.GoogleCharts.fsx"

// Load the DLLs
#r "packages/FSharp.Collections.ParallelSeq/lib/net45/FSharp.Collections.ParallelSeq.dll"
#r "packages/Expecto/lib/net461/Expecto.dll"
In [2]:
open System
// Use Parallel operations to speed up execution
open FSharp.Collections.ParallelSeq

/// Quick debugging
let tee f x = f x |> ignore; x

/// Remove the first occurrence of an element from a list.  This is a safe method because 
/// if the element does not occur, the list will be returned unchanged.
let removeFirstOccurrence e lst =
    let rec loop accum = function
        | [] -> List.rev accum
        | h::t when e = h -> (List.rev accum) @ t
        | h::t -> loop (h::accum) t
    loop [] lst

/// Brute force method
let bruteForceRun ilist k =
    ilist
    |> PSeq.map (fun e -> e, removeFirstOccurrence e ilist)
    |> PSeq.collect (fun (e,remElem) -> PSeq.map (fun re -> re + e) remElem)
    |> PSeq.exists (( = ) k)
In [3]:
// Separate the run from the definitions because we don't want to re-compile definitions to run tests.
open Expecto

/// Basic brute-force tests to ensure the logic works correctly
let bruteForceTests =
    testList "Brute force tests" [
        test "[10; 15; 3; 7] 17" {
            Expect.isTrue (bruteForceRun [10; 15; 3; 7] 17) "[10; 15; 3; 7] 17"
        }
        
        test "[10; 15; 3; 7] 18" {
            Expect.isTrue (bruteForceRun [10; 15; 3; 7] 18) "[10; 15; 3; 7] 18"
        }
        
        test "[10; 15; 3; 7] 28" {
            Expect.isFalse (bruteForceRun [10; 15; 3; 7] 28) "[10; 15; 3; 7] 28"
        }
        
        test "[10; 15; 3; 7] 20" {
            Expect.isFalse (bruteForceRun [10; 15; 3; 7] 20) "[10; 15; 3; 7] 20"
        }
        
        test "[10; 15; 3; 7; 10] 20" {
            Expect.isTrue (bruteForceRun [10; 15; 3; 7; 10] 20) "[10; 15; 3; 7; 10] 20"
        }
    ]

runTests defaultConfig bruteForceTests
Out[3]:
0
[08:04:28 INF] EXPECTO? Running tests... <Expecto>
[08:04:29 INF] EXPECTO! 5 tests run in 00:00:00.0956010 for Brute force tests5 passed, 0 ignored, 0 failed, 0 errored. Success! <Expecto>
Excellent, our logic works!
Now, to try a different strategy.

Strategy 2

Take each element, subtract it from k, and find the remainder in the rest of the list.
In [4]:
/// Subtraction method
let subtractionRun ilist k = 
    ilist
    |> PSeq.map (fun e -> (k - e), removeFirstOccurrence e ilist)
    |> PSeq.exists (fun (rem, remL) -> PSeq.exists ((=) rem) remL)
In [5]:
/// Basic subtraction tests to ensure the logic works correctly
let subtractionTests =
    testList "Subtraction tests" [
        test "[10; 15; 3; 7] 17" {
            Expect.isTrue (subtractionRun [10; 15; 3; 7] 17) "[10; 15; 3; 7] 17"
        }
        
        test "[10; 15; 3; 7] 18" {
            Expect.isTrue (subtractionRun [10; 15; 3; 7] 18) "[10; 15; 3; 7] 18"
        }
        
        test "[10; 15; 3; 7] 28" {
            Expect.isFalse (subtractionRun [10; 15; 3; 7] 28) "[10; 15; 3; 7] 28"
        }
        
        test "[10; 15; 3; 7] 20" {
            Expect.isFalse (subtractionRun [10; 15; 3; 7] 20) "[10; 15; 3; 7] 20"
        }
        
        test "[10; 15; 3; 7; 10] 20" {
            Expect.isTrue (subtractionRun [10; 15; 3; 7; 10] 20) "[10; 15; 3; 7; 10] 20"
        }
    ]

runTests defaultConfig subtractionTests
Out[5]:
0
[08:04:29 INF] EXPECTO? Running tests... <Expecto>
[08:04:29 INF] EXPECTO! 5 tests run in 00:00:00.0307871 for Subtraction tests5 passed, 0 ignored, 0 failed, 0 errored. Success! <Expecto>

Performance Comparison

Let's do some basic performance comparisons using BenchmarkDotNet.
In [6]:
/// Performance testing setup - change the input parameter if you want repeatable tests
/// NOTE: System.Random is NOT thread-safe.  Using PSeq here is dubious at best.
let random = Random((int) DateTime.Now.Ticks &&& 0x0000FFFF)
let mutable randLock = Object()

/// Convenience method to generate random numbers safely.
let getNextRand (min, max) = lock randLock (fun () -> random.Next (min, max))

/// Represents inputs to the algorithms, with type (int list, int) list.
let inputGenerator numToGenerate : (int list * int) list = 
    // Generate a single input
    let generateOne () =
        // list length is between 10 and 10,000 entries
        let listLen = getNextRand (10, 10000)

        // limiting each list element to be between 0 and 1,000,000
        let lst = 
            PSeq.init listLen 
                (fun _ -> getNextRand (0, 1000000))
            |> PSeq.toList

        // k can go up to 2,000,000, which is double the maximum entry in the list
        let k = getNextRand (0, 2000000)

        lst, k
        
    PSeq.init numToGenerate (fun _ -> generateOne())
    |> PSeq.toList
In [7]:
/// Brute force performance tests
let bruteForcePerformanceTest inputs =
    [ for i in 0 .. List.length inputs - 1 do
        yield bruteForceRun (fst inputs.[i]) (snd inputs.[i]) ]
    |> ignore

/// Subtraction performance tests
let subtractionPerformanceTest inputs = 
    [ for i in 0 .. List.length inputs - 1 do
        yield subtractionRun (fst inputs.[i]) (snd inputs.[i]) ]
    |> ignore

/// Control variable for run: how many entries in each run?
let numToGenerate = 100

/// Control variable for run: how many runs?
let numberOfRuns = 6

/// Each run has different inputs
let inputs = 
    [ for i in 0 .. numberOfRuns-1 do
        yield inputGenerator numToGenerate ]

// Measure performance
let bfStopwatch = System.Diagnostics.Stopwatch()
let subStopwatch = System.Diagnostics.Stopwatch()
let stopwatchResults =
    [ for i in 0 .. numberOfRuns-1 do
        bfStopwatch.Reset()
        bfStopwatch.Start()
        bruteForcePerformanceTest inputs.[i]
        bfStopwatch.Stop()

        subStopwatch.Reset()
        subStopwatch.Start()
        subtractionPerformanceTest inputs.[i]
        subStopwatch.Stop()
        
        let percentDiff = 
            100m 
                * (decimal(bfStopwatch.ElapsedMilliseconds) - decimal(subStopwatch.ElapsedMilliseconds)) 
                / decimal(bfStopwatch.ElapsedMilliseconds)
            
        yield 
            [ bfStopwatch.Elapsed.ToString("c")
              subStopwatch.Elapsed.ToString("c")
              String.Format("{0:0.###}%", percentDiff) ]
    ]
And now to show the results in a nice format (just because I can :)). The charts assume that Brute-force is the baseline method.
In [8]:
open XPlot.GoogleCharts

// Transform the results into inputs that GoogleCharts can use
let names = [ "Brute-force"; "Subtraction"; "Percentage difference" ]
let results =
    [ for i in 0 .. numberOfRuns-1 do
        yield List.zip names stopwatchResults.[i] ]

// And plot the reuslts
results
|> Chart.Table
|> Chart.WithOptions(Options(showRowNumber = true))
|> Chart.WithLabels ("Technique"::[for i in 1 .. numberOfRuns do yield sprintf "Time %i" i])
Out[8]:

Conclusion

Even though the 2 techniques look very similar, the Subtraction method is approximately 20-30% faster than the Brute-force method. See you in the next one!

Comments

  1. This problem can be solved in O(n) with a hash map, (compared to yours O(n^2))
    in which you hash the number in a way that if x + y = k, they would end up in the same slot.
    Then you would just hash each element and check if the slot already contains some number, if yes, you found the pair.

    ReplyDelete

Post a Comment

Popular posts from this blog

How to Setup a Fable-Elmish Project (May 1 2017)