SQL interview question
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
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
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)
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