Test results - Codility

Tasks Details

medium

1. NumberOfDiscIntersections

Compute the number of intersections in a sequence of discs.

100%

We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:

A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0

There are eleven (unordered) pairs of discs that intersect, namely:

discs 1 and 4 intersect, and both intersect with all the other discs;

disc 2 also intersects with discs 0 and 3.

Write a function:

object Solution { def solution(a: Array[Int]): Int }

that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [0..2,147,483,647].

Solution

Programming language used Scala

Time spent on task 4 minutes

Notes

not defined yet

Task timeline

Code: 22:33:13 UTC, scala, verify, result: Failed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

import scala.collection.JavaConversions._

// you can use println for debugging purposes, e.g.
// println("this is a debug message")

object Solution {
    def solution(A: Array[Int]): Int = {
        case class DiskBorder(location: Long, isOpen: Boolean)
        
        val borders = Array.fill[DiskBorder](A.length * 2)(null)
        @scala.annotation.tailrec
        def fill(idx: Int): Unit = {
            if (idx < A.length) {
                val radius = A(idx).toLong
                val open = DiskBorder(idx.toLong - radius, true)
                borders(2 * idx) = open
                val close = DiskBorder(idx.toLong + radius, false)
                borders(2 * idx + 1) = close
                fill(idx + 1)
            }
        }
        
        fill(0)
        
        val f: DiskBorder => (Int, Int) = {
            case DiskBorder(location, isOpen) =>
                val openFirst = if (isOpen) 0 else 1
                (location, openFirst)
        }
        
        scala.util.Sorting.stableSort(borders, f)
        
        @scala.annotation.tailrec
        def go(idx: Int, currentlyOpen: Int, accum: Int): Int = {
            if (accum > 10000000) -1
            else if (idx >= borders.length) accum
            else {
                if (borders(idx).isOpen) {
                    go(idx + 1, currentlyOpen + 1, accum + currentlyOpen)
                } else {
                    go(idx + 1, currentlyOpen - 1, accum)
                }
            }
        }
        
        go(0, 0, 0)
    }
}

Analysis

Compile error

Solution.scala:28: error: type mismatch;
 found   : Long
 required: Int
                (location, openFirst)
                 ^
one error found

Code: 22:33:37 UTC, scala, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

import scala.collection.JavaConversions._

// you can use println for debugging purposes, e.g.
// println("this is a debug message")

object Solution {
    def solution(A: Array[Int]): Int = {
        case class DiskBorder(location: Long, isOpen: Boolean)
        
        val borders = Array.fill[DiskBorder](A.length * 2)(null)
        @scala.annotation.tailrec
        def fill(idx: Int): Unit = {
            if (idx < A.length) {
                val radius = A(idx).toLong
                val open = DiskBorder(idx.toLong - radius, true)
                borders(2 * idx) = open
                val close = DiskBorder(idx.toLong + radius, false)
                borders(2 * idx + 1) = close
                fill(idx + 1)
            }
        }
        
        fill(0)
        
        val f: DiskBorder => (Long, Int) = {
            case DiskBorder(location, isOpen) =>
                val openFirst = if (isOpen) 0 else 1
                (location, openFirst)
        }
        
        scala.util.Sorting.stableSort(borders, f)
        
        @scala.annotation.tailrec
        def go(idx: Int, currentlyOpen: Int, accum: Int): Int = {
            if (accum > 10000000) -1
            else if (idx >= borders.length) accum
            else {
                if (borders(idx).isOpen) {
                    go(idx + 1, currentlyOpen + 1, accum + currentlyOpen)
                } else {
                    go(idx + 1, currentlyOpen - 1, accum)
                }
            }
        }
        
        go(0, 0, 0)
    }
}

Analysis

▶

example1
example test

✔

Code: 22:34:01 UTC, scala, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

import scala.collection.JavaConversions._

// you can use println for debugging purposes, e.g.
// println("this is a debug message")

object Solution {
    def solution(A: Array[Int]): Int = {
        case class DiskBorder(location: Long, isOpen: Boolean)
        
        val borders = Array.fill[DiskBorder](A.length * 2)(null)
        @scala.annotation.tailrec
        def fill(idx: Int): Unit = {
            if (idx < A.length) {
                val radius = A(idx).toLong
                val open = DiskBorder(idx.toLong - radius, true)
                borders(2 * idx) = open
                val close = DiskBorder(idx.toLong + radius, false)
                borders(2 * idx + 1) = close
                fill(idx + 1)
            }
        }
        
        fill(0)
        
        val f: DiskBorder => (Long, Int) = {
            case DiskBorder(location, isOpen) =>
                val openFirst = if (isOpen) 0 else 1
                (location, openFirst)
        }
        
        scala.util.Sorting.stableSort(borders, f)
        
        @scala.annotation.tailrec
        def go(idx: Int, currentlyOpen: Int, accum: Int): Int = {
            if (accum > 10000000) -1
            else if (idx >= borders.length) accum
            else {
                if (borders(idx).isOpen) {
                    go(idx + 1, currentlyOpen + 1, accum + currentlyOpen)
                } else {
                    go(idx + 1, currentlyOpen - 1, accum)
                }
            }
        }
        
        go(0, 0, 0)
    }
}

Analysis

▶

example1
example test

✔

Code: 22:34:14 UTC, scala, final, score: 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

import scala.collection.JavaConversions._

// you can use println for debugging purposes, e.g.
// println("this is a debug message")

object Solution {
    def solution(A: Array[Int]): Int = {
        case class DiskBorder(location: Long, isOpen: Boolean)
        
        val borders = Array.fill[DiskBorder](A.length * 2)(null)
        @scala.annotation.tailrec
        def fill(idx: Int): Unit = {
            if (idx < A.length) {
                val radius = A(idx).toLong
                val open = DiskBorder(idx.toLong - radius, true)
                borders(2 * idx) = open
                val close = DiskBorder(idx.toLong + radius, false)
                borders(2 * idx + 1) = close
                fill(idx + 1)
            }
        }
        
        fill(0)
        
        val f: DiskBorder => (Long, Int) = {
            case DiskBorder(location, isOpen) =>
                val openFirst = if (isOpen) 0 else 1
                (location, openFirst)
        }
        
        scala.util.Sorting.stableSort(borders, f)
        
        @scala.annotation.tailrec
        def go(idx: Int, currentlyOpen: Int, accum: Int): Int = {
            if (accum > 10000000) -1
            else if (idx >= borders.length) accum
            else {
                if (borders(idx).isOpen) {
                    go(idx + 1, currentlyOpen + 1, accum + currentlyOpen)
                } else {
                    go(idx + 1, currentlyOpen - 1, accum)
                }
            }
        }
        
        go(0, 0, 0)
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N)) or O(N)

▶

example1
example test

✔

▶

simple1

✔

▶

simple2

✔

▶

simple3

✔

▶

extreme_small
empty and [10]

✔

▶

small1

✔

▶

small2

✔

▶

small3

✔

▶

overflow
arithmetic overflow tests

✔

▶

medium1

✔

▶

medium2

✔

▶

medium3

✔

▶

medium4

✔

▶

10M_intersections
10.000.000 intersections

✔

▶

big1

✔

▶

big2

✔

▶

big3
[0]*50000

✔