CODEWITHSUNDEEP
sqlgaps-and-islands
Krns
Krns

Reputation: 178

SQL interview question

I got following question on an interview: Given a table of natural numbers with some missing ones, provide output of two tables, beginning of number gap in first table and ending in second. Example:

 ____    ________
|    |   |   |   |
| 1  |   | 3 | 3 |
| 2  |   | 6 | 7 |
| 4  |   | 10| 12|
| 5  |   |___|___|
| 8  |
| 9  |
| 13 |
|____|

Upvotes: 12

Views: 4567

Answers (8)

Raghvendra
Raghvendra

Reputation: 134

create table sequence_table(seq integer);

insert into sequence_table values(1);
insert into sequence_table values(2);
insert into sequence_table values(4);
insert into sequence_table values(5);
insert into sequence_table values(8);
insert into sequence_table values(9);
insert into sequence_table values(13);
insert into sequence_table values(14);
insert into sequence_table values(15);

with tmp_next_seq as
(
  select s.seq,
       (lead(s.seq) over(order by s.seq) - s.seq) next_seq_gap
  from sequence_table s
)
select t.seq+1 missing_seq_start,
       t.seq+t.next_seq_gap-1 missing_seq_end
  from tmp_next_seq t
where next_seq_gap > 1;

Upvotes: 0

Winkey
Winkey

Reputation: 56

SQL Fiddle Setup and Solution

1. Step1

From the list of IDs get the current id and all the next ids available

select l1.id curr_id,l2.id next_id from
id_list l1,id_List l2
where l1.id < l2.id;

2. Step 2

From the above list we will see all the combinations but filter only the one combination per current ID with immediate smallest next ID and for that, get min current ID and min next ID for each current ID. Use group by per current ID

with id_combinations as
(
 select l1.id curr_id,l2.id next_id from
 id_list l1,id_List l2
 where l1.id < l2.id
)
select min(curr_id)+1 missing_id_start -- Need to add 1 from current available id
       ,min(next_id)-1 missing_id_end -- Need to subtract 1 from next available id 
from id_combinations
group by curr_id
having min(curr_id)+1 < min(next_id) -- Filter to get only the missing ranges

Upvotes: 0

stop-cran
stop-cran

Reputation: 4408

You can use Lag function to access previous row:

create table #a (n int)

insert #a values(1)
insert #a values(2)
insert #a values(4)
insert #a values(5)
insert #a values(8)
insert #a values(9)
insert #a values(13)

select  prev + 1, n - 1 from
(select lag(n) over(order by n) as prev, n
from    #a) a
where   prev < n - 1

Result:

|3  |3  |

|6  |7  |

|10 |12 |

Upvotes: 0

Conrad Frix
Conrad Frix

Reputation: 52665

This works without DB Specific SQL and it could probably be made a little cleaner but it does work

EDIT: You can see this working at on this Query at StackExchange Data Explorer 

SELECT low,high FROM 

(

SELECT col1, low 

FROM
(Select n1.col1 col1, min(n2.col1) + 1 low
 from numbers n1
inner join numbers n2
on n1.col1 < n2.col1 

Group by n1.col1) t
WHERE t.low not in (SELECT col1 FROM NUMBERS)
and t.low < (Select MAX(col1) from numbers) 
) t

INNER JOIN 
(

SELECT col1 - 1 col1, high
 FROM
(Select n1.col1 col1 , min(n2.col1) - 1 high
 from numbers n1
inner join numbers n2
on n1.col1 < n2.col1 

Group by n1.col1) t
WHERE t.high not in (SELECT col1 FROM NUMBERS) 
) t2
ON t.col1 = t2.col1

Upvotes: 2

egrunin
egrunin

Reputation: 25073

Something like this:

SELECT col1, col2 FROM
(
    SELECT x + 1 as col1, 
        ROW_NUMBER() OVER(ORDER BY x) AS 'rownum'  
    FROM tbl y 
    WHERE NOT EXISTS (SELECT x FROM tbl z WHERE z.x = y.x + 1) 
        AND x <> (SELECT MAX(x) FROM tbl)
) a
INNER JOIN
(
    SELECT x - 1 as col2,
        ROW_NUMBER() OVER(ORDER BY x) AS 'rownum'  
    FROM tbl y 
    WHERE NOT EXISTS (SELECT x FROM tbl z WHERE z.x = y.x - 1) 
        AND x <> (SELECT MIN(x) FROM tbl)
) b
ON a.rownum = b.rownum

The "rownum" syntax will be different for different DBMS. The above might work for SQL Server, but I haven't tested it.

As one of the comments pointed out, many DBMS's have analytics that will make this easier.

Upvotes: 1

stack
stack

Reputation: 638

While this is pretty much the same as Phil Sandler's answer, this should return two separate tables (and I think it looks cleaner) (it works in SQL Server, at least):

DECLARE @temp TABLE (num int)
INSERT INTO @temp VALUES (1),(2),(4),(5),(8),(9),(13)

DECLARE @min INT, @max INT
SELECT @min = MIN(num), @max = MAX(num) FROM @temp

SELECT t.num + 1 AS range_start
    FROM @temp t
    LEFT JOIN @temp t2 ON t.num + 1 = t2.num
    WHERE t.num < @max AND t2.num IS NULL

SELECT t.num - 1 AS range_end
    FROM @temp t
    LEFT JOIN @temp t2 ON t.num - 1 = t2.num
    WHERE t.num > @min AND t2.num IS NULL

Upvotes: 7

Martin Smith
Martin Smith

Reputation: 453453

Itzik Ben Gan writes a lot about these "gaps and islands" problems. His row_number solution to this is

WITH C AS
(
SELECT N, ROW_NUMBER() OVER (ORDER BY N) AS RN
FROM t
)
SELECT Cur.N+1,Nxt.N-1
FROM C AS Cur 
JOIN C AS Nxt ON Nxt.RN = Cur.RN+1
WHERE Nxt.N-Cur.N>1

And a solution without row_number from the same source.

SELECT N+1 AS start_range,
(SELECT MIN(B.N) FROM t AS B WHERE B.N > A.N)-1 AS end_range
FROM t AS A
WHERE NOT EXISTS(SELECT * FROM t AS B WHERE B.N = A.N+1)
AND N< (SELECT MAX(N) FROM t)

Upvotes: 2

Phil Sandler
Phil Sandler

Reputation: 28026

This is SQL Server syntax:

CREATE TABLE #temp (columnA int)

INSERT INTO #temp VALUES(1)
INSERT INTO #temp VALUES(2)
INSERT INTO #temp VALUES(4)
INSERT INTO #temp VALUES(5)
INSERT INTO #temp VALUES(8)
INSERT INTO #temp VALUES(9)
INSERT INTO #temp VALUES(13)

SELECT 
    t1.columnA - 1
FROM 
    #temp t1
    LEFT JOIN #temp t2 ON t1.columnA = t2.ColumnA + 1
WHERE 
    t2.ColumnA IS NULL
    AND t1.ColumnA != (SELECT MIN(ColumnA) from #temp)  

SELECT 
    t1.columnA + 1
FROM 
    #temp t1
    LEFT JOIN #temp t2 ON t1.columnA = t2.ColumnA - 1
WHERE 
    t2.ColumnA IS NULL  
    AND t1.ColumnA != (SELECT MAX(ColumnA) from #temp)  

DROP table #temp

Upvotes: 2

Related Questions