вторник, 20 октября 2009 г.

SQL, задача. Найти минимальное натуральное число, которого нет в таблице

Один друг мне скинул сегодня интересную и странную задачку на знание SQL, вполне годится на собеседования выставлять. Условие следующее:

CREATE TABLE t (i int);
INSERT INTO t VALUES (1), (2), (3), (5), (8), (10), (13), (19);
Вывести минимальное натуральное число, которого нет в таблице t, т.е. 4.

Т.е., есть таблица с полем целого типа, надо найти наименьшее натуральное число, которое не присутствует в таблице, одним запросом. Задача из реальной жизни, например, нужно вместо генерации нового индекса попробовать использовать один из неиспользующихся.

Чем менее экзотические средства будут применены - тем лучше.
Варианты решения постим в комменты.

10 комментариев:

  1. SELECT IF((SELECT MIN(i) FROM t)>1,1,MIN(i+1)) FROM t WHERE i+1 NOT IN (SELECT i FROM t);

    ОтветитьУдалить
  2. Вот такое решение у меня, кто лучше?!

    SELECT MIN(a.i+1) FROM t AS a LEFT JOIN t as b ON a.i+1 = b.i WHERE b.i is null;

    ОтветитьУдалить
  3. SELECT MAX(t2.i)+1 FROM t AS t1 LEFT JOIN t AS t2 ON (t1.i+1=t2.i) ORDER BY t2.i ASC

    ОтветитьУдалить
  4. SELECT (`i`+1) as y FROM `t` WHERE (`i`+1) NOT IN (SELECT `i` from `t` WHERE 1) LIMIT 1;

    Не учитывает '1' если она является минимальным отсутствующим числом.

    ОтветитьУдалить
  5. Юрий, твой запрос неверный. поставь для эксперимента первой строкой в таблице 100.

    А на счет единицы, только у мну единственно верный запрос ;) 1 (наименьшее натуральное), если она не входит в таблицу, вы все проигнорили

    ОтветитьУдалить
  6. Да, неверный, спасибо.
    Внес уточнение в запрос.

    SELECT (`i`+1) as y FROM `t` WHERE (`i`+1) NOT IN (SELECT `i` from `t` WHERE 1) order by `i` LIMIT 1;

    А на счет единицы, у вас тоже в первом варианте она игнорировалась ;) Я его увидел после попытки добавления своего варианта. При наличии времени подправлю свой с учетом 1.

    ОтветитьУдалить
  7. Поведайте мне, убогой, какие практические знания и навыки можно протестировать решением такой задачи, что она "вполне годится на собеседования выставлять"?
    Как уебать базу одним запросом?

    ОтветитьУдалить
  8. Ув.Елена, если НЕ пытаться даже решать какие-либо нестандартные задачи, то практических знаний добиться решением такой задачи по SQL НЕ удастся. Из навыков можно проверить во-первых смекалку, во-вторых общий уровень знаний БД на примере реальной задачи.
    К примеру, вам нужно назначить встречу на какую-то дату, как можно раньше из свободных дней. - Вот вам уже реальной применение.

    Насчёт грохнуть базу одним запросом, это по-моему даже у первокурсника не составит труда. Так что ваш юмор неуместен.

    ОтветитьУдалить
  9. Если дополнить решение webaurum от 21 октября 2009 г. 9:35, чтобы обрабатывалась 1, то будет правильно
    SELECT IF((SELECT MIN(i) FROM t)>1,1,(SELECT MIN(a.i+1) FROM t AS a LEFT JOIN t as b ON a.i+1 = b.i WHERE b.i is null)) AS min_value

    ОтветитьУдалить
  10. Для MySQL:
    SELECT min(rn) FROM (SELECT t.i, @n:=@n+1 AS rn, t.i - @n AS gr FROM t, (SELECT @n:=0) y ORDER BY i) x
    WHERE gr > 0;

    Для Oracle:
    1)
    select min(rn)
    from (select t.i, row_number() over(order by i) rn from t) t
    where i - rn > 0;
    2)
    select rn
    from (select t.*, row_number() over(order by i) rn from t) x
    where id - rn > 0
    and rownum = 1

    ОтветитьУдалить

Рекоммендую

Попробуйте надёжный хостинг от Scala Hosting