Codility ‘SqlSegmentsSum’ Kalium 2015 Solution

Short Problem Definition:

Compute the total length covered by 1-dimensional segments.

Link

SqlSegmentSum

Complexity:

time complexity

space complexity

Execution:

I first create a numbers table from 1 to 1.000.000, this could be done just once when creating the DB. In this challenge it adds a flat 0.3sec runtime to all testcases.

In the second step I simply unique join the segments and number tables.

Solution:
-- create numbers utility structure, very basic integer primary key column n
create table numbers(n integer not null, primary key(n asc));
-- insert generated sequential integers
insert into numbers(n)
select rowid
from (

-- build 1,000,000 rows using Cartesian product
select 1
from (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) a, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) b, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) c, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) d, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) e, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) f

) derived;

select count(distinct n) from numbers inner join segments
on numbers.n between segments.l+1 and segments.r

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Oskar J

    Hi Martin! I’m trying to solve this by myself, but 3 hours and still no luck. Are we actually allowed to create temporary tables or views in Codility solutions? Or only 1 select query with e.g. nested sub-queries and joins is allowed? I already have a programming solution which is pretty straightforward, but translating this into an SQL syntax seems to be quite hard, because of a need to keep previous value per row.. A reference programming solution which may be helpful: http://stackoverflow.com/questions/14797377/finding-union-length-of-many-line-segments

    • Hi Oskar, there will be a new challenge in 5 days, so I will post the code to this one.

      As for your question: I did create temporary tables. It took about 0.3sec constant time but decreased the runtime for all the tests significantly (especially the big ones). You don’t need any views.

      • Oskar J

        Hi. That explains everything. Codility won’t color syntax of the CREATE TEMP TABLE instruction, so I thought we’re not allowed to do that. I tried to make a solution with one multinested SELECT instruction only, but I find that difficult with restrictions of the SQLITE language. Now with temporary tables it should be easy.

  • Sitapriyanka Peddada

    WITH Sales_CTE(l,r,x) AS

    (

    select (select min(l) from segments) as l, (select max(r) from segments) as r , -1

    union all

    select c.l+1, c.r ,

    case

    when

    (exists(select 1 from segments s where c.l + 1 = s.l and not exists(select 1 from segments s1 where c.l + 1 > s1.l and c.l+1 <=s1.r))) then -1

    when

    (exists(select 1 from segments s where c.l + 1 between s.l and s.r)) then -2 end

    from Sales_CTE c

    where l+1 <=c.r

    ),

    T(s,x) as

    (

    select (select sum(1) from Sales_CTE where x is not null), (select count(*) from Sales_CTE where x = -1)

    )

    select s-x from T

  • Roland Fermi

    The test link to codility https://codility.com/c/intro/demoPP4HFW-UHB says the test is closed. Are there any other SQL tests that are open?

    • Fixed the link. Thanks for pointing it out

      • Roland Fermi

        How do I find more SQL tests in Codility? Tried searching to no avail.