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.

  • Martin C.

    WITH recursive
    min_max as (select min(l) min_l,max(r) max_r from segments),
    cnt(x) AS (select min_l as x from min_max UNION ALL SELECT x+1 FROM cnt WHERE x<( select max_r from min_max))
    SELECT count(distinct x) FROM cnt
    JOIN segments s on cnt.x between s.l and s.r-1

  • Sakthi Pitchaiah

    SELECT sum(CASE
    WHEN seg_status = ‘same’
    THEN r – l
    WHEN seg_status = ‘beginoverlap’
    THEN (r-s2_l)*-1
    ELSE
    0
    END) AS total_segments
    from
    (
    SELECT s1.l
    ,s1.r
    ,s2.l AS s2_l
    ,s2.r AS s2_r
    ,CASE
    WHEN s1.l = s2.l AND s1.r = s2.r
    THEN ‘same’
    WHEN s2.l >= s1.l AND s2.r s1.l AND s2.l = s3.l AND s.r <= s3.r
    AND (s.l s3.l OR s.r s3.r)
    AND s.seg_status=’same’
    )
    ;