# Codility ‘SqlSegmentsSum’ Kalium 2015 Solution

##### Short Problem Definition:

Compute the total length covered by 1-dimensional segments.

SqlSegmentSum

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.

• 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.

• I used a regular CREATE TABLE.

• ping. I posted the solution

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.

• To my knowledge this is the only one they have. I would also appreciate some more ðŸ™‚

• 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’
)
;

• valli sathappan

select count(distinct(n)) from (select 1+d+c*10+b*100+a*1000 as n from
(
(select 0 as a 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),
(select 0 as b 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),
(select 0 as c 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),
(select 0 as d 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))) natural_numbers, segments
where n between l+1 and r;