Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Задачи на собеседованиях #208  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
https://xakep.ru/2016/05/11/coding-challenges-208/
11 май 16, 16:40    [19159509]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Lepsik,

а вопрос, собственно, в чем?
11 май 16, 17:53    [19159934]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
В первой задаче очень долго выпоняется запрос, не вижу где могу соптимизировать.

declare @tmp table (id int, parent_id int)
insert into @tmp
    SELECT * FROM (VALUES (1, 2), (1, 3), (4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (8, 7), (8, 10), (9, 9), (12, 11)) x(id, parent_id);

declare @input_node int = 1;
declare @cnt int = (select count(*) from @tmp);

with cte as
(
   select id, parent_id, 0 as depth from @tmp where id = @input_node or parent_id = @input_node
   union all
   select t.id, t.parent_id, depth + 1 as depth
    from cte join @tmp t on (t.id in (cte.id, cte.parent_id) or t.parent_id in (cte.id, cte.parent_id)) where cte.depth < @cnt
)select distinct id from cte
  union
 select distinct parent_id from cte
11 май 16, 18:01    [19159992]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Lepsik,

Lepsik,

ну и это. судя по некоторым косвенным признакам, в тестах по ссылке подразумевается, что ты владеешь Oracle SQL.

З.Ы.
упоминание о connect by и автор статьи DBMS_PHOTOSHOP как бы намекают...
11 май 16, 18:04    [19160021]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Гавриленко Сергей Алексеевич
Member

Откуда:
Сообщений: 37254
Lepsik
В первой задаче очень долго выпоняется запрос, не вижу где могу соптимизировать.

declare @tmp table (id int, parent_id int)
insert into @tmp
    SELECT * FROM (VALUES (1, 2), (1, 3), (4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (8, 7), (8, 10), (9, 9), (12, 11)) x(id, parent_id);
Ускорить можно как минимум убрав дубликаты из иходных данных.
11 май 16, 18:11    [19160055]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Lepsik
В первой задаче очень долго выпоняется запрос, не вижу где могу соптимизировать.

declare @tmp table (id int, parent_id int)
insert into @tmp
    SELECT * FROM (VALUES (1, 2), (1, 3), (4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (8, 7), (8, 10), (9, 9), (12, 11)) x(id, parent_id);

declare @input_node int = 1;
declare @cnt int = (select count(*) from @tmp);

with cte as
(
   select id, parent_id, 0 as depth from @tmp where id = @input_node or parent_id = @input_node
   union all
   select t.id, t.parent_id, depth + 1 as depth
    from cte join @tmp t on (t.id in (cte.id, cte.parent_id) or t.parent_id in (cte.id, cte.parent_id)) where cte.depth < @cnt
)select distinct id from cte
  union
 select distinct parent_id from cte

ещё раз - задачи затачивались под оракловые фичи SQL.
в первой задаче подразумевалось использование иерархических запросов (start with ... connect by prior), для исключения циклов из рассмотрения - добавочная проверка на NOCYCLE (это все встроенные нативные возможности ораклового диалекта SQL).
Видимо, на рекурсивном CTE нужно закладывать несколько иную логику, нежели "лобовое" решение поставленной задачи
11 май 16, 18:15    [19160076]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
>>>Добрый Э - Эх
--- с минимальными изменениями могут быть приспособлены для MS SQL Server

Вот я и думаю что значит с минимальными изменениями ?
11 май 16, 18:16    [19160087]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6802
Lepsik,

кстати, ради любопытства, а можно 3-ю (по Фибоначчи) решить в рамках одного cte? а то с наскока не получается :(
11 май 16, 18:24    [19160134]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Lepsik
>>>Добрый Э - Эх
--- с минимальными изменениями могут быть приспособлены для MS SQL Server

Вот я и думаю что значит с минимальными изменениями ?
это из серии - "программисты шутят" :)
но в целом, близко к правде. рекурсивный CTE по своим возможностям - более мощная и гибкая штука, чем "чистокровные" оракловые иерархические запросы. просто ты его стал немного неправильно готовить :)
В целом, задачи интересные, но ничего сложного в них нет. В статье верно подмечено: они позволяют достаточно просто определить, что "человeк не имеет базовых знаний"
11 май 16, 18:25    [19160139]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
TaPaK
Lepsik,

кстати, ради любопытства, а можно 3-ю (по Фибоначчи) решить в рамках одного cte? а то с наскока не получается :(

ну, Фибоначчи - рекурсия же в чистом виде? Результат вычислений на текущем шаге зависит от таковых на предыдущем. Стало быть, одной рекурсии достаточно
11 май 16, 18:28    [19160150]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
Из задачи не сказано какую цель преследуют.

Сделать красиво или быстро или показать знания CS?
Я могу и супербыстро но выглядеть будет не красиво
11 май 16, 18:29    [19160153]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6802
Добрый Э - Эх,

тут бы пример, так то я знаю и что такое Фибоначчи и что одной рекурсии достаточно :)
11 май 16, 18:29    [19160156]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
Добрый Э - Эх
. В статье верно подмечено: они позволяют достаточно просто определить, что "человeк не имеет базовых знаний"


declare @tmp table (id int, parent_id int, num int identity, unique (id, parent_id))
insert into @tmp
    SELECT * FROM (VALUES (1, 2), (1, 3), (4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (7, 8), (8, 10), (9, 9), (12, 11)) x(id, parent_id);

declare @input_node int = 1;

with cte as
(
   select id, parent_id, 0 as depth from @tmp where id = @input_node or parent_id = @input_node
   union all
   select t.id, t.parent_id, depth + 1 as depth
    from cte join @tmp t on (t.id in (cte.id, cte.parent_id) or t.parent_id in (cte.id, cte.parent_id)) where depth < num
)select distinct id from cte
  union
 select distinct parent_id from ctee


Ну хорошo вот решение - нo в лоб. Что значит базовые знания?
11 май 16, 18:49    [19160263]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Lepsik
Что значит базовые знания?
Именно то и значит - минимально необходимый уровень. В Oracle считается, что этот минимум должен включать в себя :
1) Знание иерархических запросов (start with ... connect by ... prior ... nocycle ... sys_connect_by_path, etc.) - задача №1, №5, с натяжкой - №3
2) Аналитические функции (в MS SQL - оконные, в данном случае - расчет накопительной суммы посредством sum() over (ORDER BY ...) ) - задача №2 (по сути, требуется рассчитать Эрланг сети)
3) Рекурсивные subquery factoring (в MS SQL - [рекурсивный] CTE) - задача №3
4) Расширенные групповые операции (group by [ rollup | cube | grouping set ]) - задача № 4
11 май 16, 19:15    [19160363]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Lepsik,

касательно первой задачи... у автора графическое представление задачи слегка расходится с "табличным".
на логику решение, конечно, не влияет, но немного подрывает "авторитет" составителя задачи ;)
11 май 16, 19:19    [19160382]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6802
Добрый Э - Эх,

Вообщем реализаций на вопрос нет, одни слова, завтра поиграюсь
11 май 16, 21:45    [19160843]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
qwrqwr
Member

Откуда: Msk
Сообщений: 1684
TaPaK,


TaPaK
кстати, ради любопытства, а можно 3-ю (по Фибоначчи) решить в рамках одного cte? а то с наскока не получается :(


тут посмотрите
11 май 16, 21:50    [19160859]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6802
qwrqwr,

О, спасибо, не часто надо но увлекательно :)
11 май 16, 23:09    [19161130]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Lepsik,

Вот тебе решение всех задач на оракловом диалекте SQL (под каждой задачей есть ссылка на on-line проверку запроса).
Насколько "с минимальными изменениями могут быть приспособлены для MS SQL Server"(с) - решай сам... :)

+ Задача №1
--
-- Задача №1, начало.
--
-- Тестовые данные:
with graph as
    (         select  1 id,  2 parent_id from dual
    union all select  1 id,  3 parent_id from dual
    union all select  4 id,  3 parent_id from dual
    union all select  5 id,  4 parent_id from dual
    union all select  6 id,  5 parent_id from dual
    union all select  7 id,  6 parent_id from dual
    union all select  8 id,  7 parent_id from dual
    union all select  7 id,  6 parent_id from dual
    union all select  8 id, 10 parent_id from dual
    union all select  9 id,  9 parent_id from dual
    union all select 12 id, 11 parent_id from dual)
--
-- Начало основной части запроса:
--
-- Входные параметры:
 , input_parameter as
     (-- Задаем начальный узел:
       select 1 as start_id from dual
     )
--
-- Построение связанного графа:
 , x_graph as
     (
       select *
         from graph
        start with (select start_id from input_parameter) in (id, parent_id)
      connect by nocycle
               (    prior id = id 
                 or prior parent_id = parent_id 
                 or prior id = parent_id 
                 or prior parent_id = id
               )
     )
-- 
-- Вывод узлов графа, связанных с заданным:
select id from x_graph
union
select parent_id from x_graph;
-- Задача №1, кончало.
--
on-line проверка на sqlfiddle.com
+ Задача №2
--
-- Задача №2, начало.
--
-- Тестовые данные:
 with log as
    (select 'U1' username, date '2013-08-08'+1/24 logon_time,
     date '2013-08-08'+10/24 logoff_time from dual
    union all select 'U1' username, date '2013-08-08'+6/24 logon_time,
     date '2013-08-08'+14/24 logoff_time from dual
    union all select 'U1' username, date '2013-08-08'+4/24 logon_time,
     date '2013-08-08'+12/24 logoff_time from dual
    union all select 'U1' username, date '2013-08-08'+8/24 logon_time,
     date '2013-08-08'+17/24 logoff_time from dual
   union all select 'U1' username, date '2013-08-08'+16/24 logon_time,
    date '2013-08-08'+18/24 logoff_time from dual
   union all select 'U1' username, date '2013-08-08'+9/24 logon_time,
    date '2013-08-08'+16/24 logoff_time from dual
   union all select 'U2' username, date '2013-08-08'+1/24 logon_time,
    date '2013-08-08'+3/24 logoff_time from dual
   union all select 'U2' username, date '2013-08-08'+2/24 logon_time,
    date '2013-08-08'+12/24 logoff_time from dual
   union all select 'U2' username, date '2013-08-08'+11/24 logon_time,
    date '2013-08-08'+13/24 logoff_time from dual
   union all select 'U2' username, date '2013-08-08'+10/24 logon_time,
    date '2013-08-08'+14/24 logoff_time from dual)
--
-- Основной запрос:
select username
     , max(erlang) as erlang
     , min(time) keep(dense_rank first order by erlang desc) as min_time
  from (
         select username
              , time
              , sum(flag) over(partition by username order by time ) as erlang
           from (
                  select username,  1 as flag, logon_time as time from log
                  union all
                  select username, -1 as flag, logoff_time as time from log
                ) v0
       ) v1
 group by username;
-- Задача №2, кончало.
--
on-line проверка на sqlfiddle.com
+ Задача №3
--
-- Задача №3, начало.
--
-- Основная часть запроса:
with
-- Входные параметры:
  input_parameter as
    (-- Количество N-первых членов чисел Фибоначчи:
      select 10 as n_first_num from dual
    )
--
-- Рекурсивный subquery factoring:
, fib (rec_num, summ, n_fib) as
    (
      select 1 rec_num, 1 summ, 1 n_fib from dual
      union all
      select rec_num + 1, summ + n_fib, summ from fib, input_parameter ip
       where rec_num < ip.n_first_num
    )
--
-- Вывод результата рекурсии:
select rec_num, n_fib from fib;
-- Задача №3, кончало.
--
on-line проверка на sqlfiddle.com
+ Задача №4
--
-- Задача №4, начало.
--
-- Тестовые данные:
with
    master as
    (select 1 as id_m, 111 as value  from dual union all
    select 2 as id_m, 222 as value  from dual union all
    select 3 as id_m, 333 as value  from dual union all
    select 4 as id_m, 444 as value  from dual union all
    select 5 as id_m, 555 as value  from dual union all
    select 6 as id_m, 666 as value  from dual),
    detail as
   (select 1 as id_m, 1 as grp from dual union all
   select 1 as id_m, 2 as grp from dual union all
   select 1 as id_m, 4 as grp from dual union all
   select 2 as id_m, 3 as grp from dual union all
   select 2 as id_m, 4 as grp from dual union all
   select 3 as id_m, 1 as grp from dual union all
   select 3 as id_m, 3 as grp from dual union all
   select 3 as id_m, 5 as grp from dual)
--
-- Основной запрос:
select grp
     , decode(GROUPING_ID(grp),0,sum(value),max(total_sum)) allsum
  from (
         select m.*, sum(value) over() as total_sum
           from master m
       ) m
  left join detail d
    on m.id_m = d.id_m
 group by rollup(grp)
having (
         grp is not null or GROUPING_ID(grp) = 1
       )
 order by GROUPING_ID(grp) desc, grp nulls first;
-- Задача №4, кончало. 
--
on-line проверка на sqlfiddle.com
+ Задача №5
--
-- Задача №5, начало.
--
-- Тестовые данные:
with tree as
    (select 3 id, 1 parent_id, 0 sign from dual
    union all select 4 id, 2 parent_id, 0 sign from dual
    union all select 5 id, 2 parent_id, 0 sign from dual
    union all select 6 id, 3 parent_id, 0 sign from dual
    union all select 7 id, 3 parent_id, 0 sign from dual
    union all select 8 id, 3 parent_id, 0 sign from dual
    union all select 9 id, 4 parent_id, 0 sign from dual
    union all select 10 id, 4 parent_id, 1 sign from dual
   union all select 11 id, 7 parent_id, 1 sign from dual
   union all select 12 id, 7 parent_id, 0 sign from dual
   union all select 13 id, 9 parent_id, 0 sign from dual
   union all select 14 id, 9 parent_id, 1 sign from dual
   union all select 15 id, 9 parent_id, 1 sign from dual
   union all select 2 id, null parent_id, 0 sign from dual
   union all select 1 id, null parent_id, 0 sign from dual)
--
-- Основной запрос:
select is_root
     , substr(full_path,1,instr(full_path,',',1,1)-1) as id_lvl1
     , substr(full_path,instr(full_path,',',1,1)+1,instr(full_path,',',1,2)-instr(full_path,',',1,1) - 1) as id_lvl2
     , substr(full_path,instr(full_path,',',1,2)+1,instr(full_path,',',1,3)-instr(full_path,',',1,2) - 1) as id_lvl2
  from (
         select is_root, max(x_path)keep(dense_rank last order by length(x_path)) full_path
           from (
                  select connect_by_root(id) is_root
                       , reverse(sys_connect_by_path(reverse(cast(id as varchar2(10))),',')) as x_path
                    from tree t
                   start with sign = 1
                 -- В соответствии с требованиями задачи CONNECT BY использовано ровно один раз:
                 connect by id = prior parent_id
                ) v0
          group by is_root
       )v1;
-- Задача №5, кончало. 
--
on-line проверка на sqlfiddle.com
12 май 16, 08:53    [19161692]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
TaPaK
Добрый Э - Эх,

Вообщем реализаций на вопрос нет, одни слова, завтра поиграюсь
ты даже погуглить поленился, а я вот ночью всё бросил и кинулся тебе писать запросы на смартфоне...
12 май 16, 08:55    [19161695]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Добрый Э - Эх
Lepsik,

Вот тебе решение всех задач на оракловом диалекте SQL (под каждой задачей есть ссылка на on-line проверку запроса).
Насколько "с минимальными изменениями могут быть приспособлены для MS SQL Server"(с) - решай сам... :)

+ Задача №1
--
-- Задача №1, начало.
--
-- Тестовые данные:
with graph as
    (         select  1 id,  2 parent_id from dual
    union all select  1 id,  3 parent_id from dual
    union all select  4 id,  3 parent_id from dual
    union all select  5 id,  4 parent_id from dual
    union all select  6 id,  5 parent_id from dual
    union all select  7 id,  6 parent_id from dual
    union all select  8 id,  7 parent_id from dual
    union all select  7 id,  6 parent_id from dual
    union all select  8 id, 10 parent_id from dual
    union all select  9 id,  9 parent_id from dual
    union all select 12 id, 11 parent_id from dual)
--
-- Начало основной части запроса:
--
-- Входные параметры:
 , input_parameter as
     (-- Задаем начальный узел:
       select 1 as start_id from dual
     )
--
-- Построение связанного графа:
 , x_graph as
     (
       select *
         from graph
        start with (select start_id from input_parameter) in (id, parent_id)
      connect by nocycle
               (    prior id = id 
                 or prior parent_id = parent_id 
                 or prior id = parent_id 
                 or prior parent_id = id
               )
     )
-- 
-- Вывод узлов графа, связанных с заданным:
select id from x_graph
union
select parent_id from x_graph;
-- Задача №1, кончало.
--
on-line проверка на sqlfiddle.com
+ Задача №2
--
-- Задача №2, начало.
--
-- Тестовые данные:
 with log as
    (select 'U1' username, date '2013-08-08'+1/24 logon_time,
     date '2013-08-08'+10/24 logoff_time from dual
    union all select 'U1' username, date '2013-08-08'+6/24 logon_time,
     date '2013-08-08'+14/24 logoff_time from dual
    union all select 'U1' username, date '2013-08-08'+4/24 logon_time,
     date '2013-08-08'+12/24 logoff_time from dual
    union all select 'U1' username, date '2013-08-08'+8/24 logon_time,
     date '2013-08-08'+17/24 logoff_time from dual
   union all select 'U1' username, date '2013-08-08'+16/24 logon_time,
    date '2013-08-08'+18/24 logoff_time from dual
   union all select 'U1' username, date '2013-08-08'+9/24 logon_time,
    date '2013-08-08'+16/24 logoff_time from dual
   union all select 'U2' username, date '2013-08-08'+1/24 logon_time,
    date '2013-08-08'+3/24 logoff_time from dual
   union all select 'U2' username, date '2013-08-08'+2/24 logon_time,
    date '2013-08-08'+12/24 logoff_time from dual
   union all select 'U2' username, date '2013-08-08'+11/24 logon_time,
    date '2013-08-08'+13/24 logoff_time from dual
   union all select 'U2' username, date '2013-08-08'+10/24 logon_time,
    date '2013-08-08'+14/24 logoff_time from dual)
--
-- Основной запрос:
select username
     , max(erlang) as erlang
     , min(time) keep(dense_rank first order by erlang desc) as min_time
  from (
         select username
              , time
              , sum(flag) over(partition by username order by time ) as erlang
           from (
                  select username,  1 as flag, logon_time as time from log
                  union all
                  select username, -1 as flag, logoff_time as time from log
                ) v0
       ) v1
 group by username;
-- Задача №2, кончало.
--
on-line проверка на sqlfiddle.com
+ Задача №3
--
-- Задача №3, начало.
--
-- Основная часть запроса:
with
-- Входные параметры:
  input_parameter as
    (-- Количество N-первых членов чисел Фибоначчи:
      select 10 as n_first_num from dual
    )
--
-- Рекурсивный subquery factoring:
, fib (rec_num, summ, n_fib) as
    (
      select 1 rec_num, 1 summ, 1 n_fib from dual
      union all
      select rec_num + 1, summ + n_fib, summ from fib, input_parameter ip
       where rec_num < ip.n_first_num
    )
--
-- Вывод результата рекурсии:
select rec_num, n_fib from fib;
-- Задача №3, кончало.
--
on-line проверка на sqlfiddle.com
+ Задача №4
--
-- Задача №4, начало.
--
-- Тестовые данные:
with
    master as
    (select 1 as id_m, 111 as value  from dual union all
    select 2 as id_m, 222 as value  from dual union all
    select 3 as id_m, 333 as value  from dual union all
    select 4 as id_m, 444 as value  from dual union all
    select 5 as id_m, 555 as value  from dual union all
    select 6 as id_m, 666 as value  from dual),
    detail as
   (select 1 as id_m, 1 as grp from dual union all
   select 1 as id_m, 2 as grp from dual union all
   select 1 as id_m, 4 as grp from dual union all
   select 2 as id_m, 3 as grp from dual union all
   select 2 as id_m, 4 as grp from dual union all
   select 3 as id_m, 1 as grp from dual union all
   select 3 as id_m, 3 as grp from dual union all
   select 3 as id_m, 5 as grp from dual)
--
-- Основной запрос:
select grp
     , decode(GROUPING_ID(grp),0,sum(value),max(total_sum)) allsum
  from (
         select m.*, sum(value) over() as total_sum
           from master m
       ) m
  left join detail d
    on m.id_m = d.id_m
 group by rollup(grp)
having (
         grp is not null or GROUPING_ID(grp) = 1
       )
 order by GROUPING_ID(grp) desc, grp nulls first;
-- Задача №4, кончало. 
--
on-line проверка на sqlfiddle.com
+ Задача №5
--
-- Задача №5, начало.
--
-- Тестовые данные:
with tree as
    (select 3 id, 1 parent_id, 0 sign from dual
    union all select 4 id, 2 parent_id, 0 sign from dual
    union all select 5 id, 2 parent_id, 0 sign from dual
    union all select 6 id, 3 parent_id, 0 sign from dual
    union all select 7 id, 3 parent_id, 0 sign from dual
    union all select 8 id, 3 parent_id, 0 sign from dual
    union all select 9 id, 4 parent_id, 0 sign from dual
    union all select 10 id, 4 parent_id, 1 sign from dual
   union all select 11 id, 7 parent_id, 1 sign from dual
   union all select 12 id, 7 parent_id, 0 sign from dual
   union all select 13 id, 9 parent_id, 0 sign from dual
   union all select 14 id, 9 parent_id, 1 sign from dual
   union all select 15 id, 9 parent_id, 1 sign from dual
   union all select 2 id, null parent_id, 0 sign from dual
   union all select 1 id, null parent_id, 0 sign from dual)
--
-- Основной запрос:
select is_root
     , substr(full_path,1,instr(full_path,',',1,1)-1) as id_lvl1
     , substr(full_path,instr(full_path,',',1,1)+1,instr(full_path,',',1,2)-instr(full_path,',',1,1) - 1) as id_lvl2
     , substr(full_path,instr(full_path,',',1,2)+1,instr(full_path,',',1,3)-instr(full_path,',',1,2) - 1) as id_lvl2
  from (
         select is_root, max(x_path)keep(dense_rank last order by length(x_path)) full_path
           from (
                  select connect_by_root(id) is_root
                       , reverse(sys_connect_by_path(reverse(cast(id as varchar2(10))),',')) as x_path
                    from tree t
                   start with sign = 1
                 -- В соответствии с требованиями задачи CONNECT BY использовано ровно один раз:
                 connect by id = prior parent_id
                ) v0
          group by is_root
       )v1;
-- Задача №5, кончало. 
--
on-line проверка на sqlfiddle.com

Хотя, задачу №5 можно решить чуть проще, если изменить направление построения дерева:
+ Задача №5, вариант №2
--
-- Задача №5, начало.
--
-- Тестовые данные:
with tree as
    (select 3 id, 1 parent_id, 0 sign from dual
    union all select 4 id, 2 parent_id, 0 sign from dual
    union all select 5 id, 2 parent_id, 0 sign from dual
    union all select 6 id, 3 parent_id, 0 sign from dual
    union all select 7 id, 3 parent_id, 0 sign from dual
    union all select 8 id, 3 parent_id, 0 sign from dual
    union all select 9 id, 4 parent_id, 0 sign from dual
    union all select 10 id, 4 parent_id, 1 sign from dual
   union all select 11 id, 7 parent_id, 1 sign from dual
   union all select 12 id, 7 parent_id, 0 sign from dual
   union all select 13 id, 9 parent_id, 0 sign from dual
   union all select 14 id, 9 parent_id, 1 sign from dual
   union all select 15 id, 9 parent_id, 1 sign from dual
   union all select 2 id, null parent_id, 0 sign from dual
   union all select 1 id, null parent_id, 0 sign from dual)
--
-- Основной запрос:
select id
     , replace(max(sys_connect_by_path(decode(level,1,id),','))keep(dense_rank last order by level),',') as id_lv1
     , replace(max(sys_connect_by_path(decode(level,2,id),','))keep(dense_rank last order by level),',') as id_lv2
     , replace(max(sys_connect_by_path(decode(level,3,id),','))keep(dense_rank last order by level),',') as id_lv3
  from tree t
 where sign = 1
 -- В соответствии с требованиями задачи CONNECT BY использовано ровно один раз:
  connect by prior id = parent_id
  group by id;
-- Задача №5, кончало. 
--
on-line проверка на sqlfiddle.com
12 май 16, 11:23    [19162514]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
Добрый Э - Эх,

в задаче №4 можно заменить left join на inner и выкинуть секцию having.
+ Задача №4, вариант №2
--
-- Задача №4, начало.
--
-- Тестовые данные:
with
    master as
    (select 1 as id_m, 111 as value  from dual union all
    select 2 as id_m, 222 as value  from dual union all
    select 3 as id_m, 333 as value  from dual union all
    select 4 as id_m, 444 as value  from dual union all
    select 5 as id_m, 555 as value  from dual union all
    select 6 as id_m, 666 as value  from dual),
    detail as
   (select 1 as id_m, 1 as grp from dual union all
   select 1 as id_m, 2 as grp from dual union all
   select 1 as id_m, 4 as grp from dual union all
   select 2 as id_m, 3 as grp from dual union all
   select 2 as id_m, 4 as grp from dual union all
   select 3 as id_m, 1 as grp from dual union all
   select 3 as id_m, 3 as grp from dual union all
   select 3 as id_m, 5 as grp from dual)
--
-- Основной запрос:
select grp
     , decode(GROUPING_ID(grp),0,sum(value),max(total_sum)) allsum
  from (
         select m.*, sum(value) over() as total_sum
           from master m
       ) m
  join detail d
    on m.id_m = d.id_m
 group by rollup(grp)
 order by GROUPING_ID(grp) desc, grp;
-- Задача №4, кончало. 
--
on-line проверка наsqlfiddle.com
чего-то сайт зашкварился, поэтому верим на слово
12 май 16, 14:01    [19163709]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
tomcat2
Member

Откуда:
Сообщений: 69
в SQL-standard задачу 1 методом СТЕ не решить ввиду ограниченной рекурсивной функциональности оного. только курсором.
13 май 16, 09:05    [19167367]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
tomcat2
Member

Откуда:
Сообщений: 69
разве что сократить время выполнения доп-проверкой типа

автор
where not (cte.id=t.id and cte.parent_id=t.parent_id) and not (cte.id=t.parent_id and cte.parent_id=t.id) and cte.depth < @cnt


пс. вопрос - а что, в этом форуме нельзя редактировать свои сообщения?
13 май 16, 09:14    [19167384]     Ответить | Цитировать Сообщить модератору
 Re: Задачи на собеседованиях #208  [new]
Добрый Э - Эх
Guest
tomcat2
в SQL-standard задачу 1 методом СТЕ не решить ввиду ограниченной рекурсивной функциональности оного. только курсором.
в стандарт опять забыли положить обработку циклов?
так-то в некоторых СУБД можно "срезать" циклы в рекурсивном СТЕ
+
--
-- Тестовые данные из задачи №1:
with graph as
    (select 1 id, 2 parent_id from dual 
    union all select 1 id, 3 parent_id from dual 
    union all select 4 id, 3 parent_id from dual 
    union all select 5 id, 4 parent_id from dual 
    union all select 6 id, 5 parent_id from dual 
    union all select 7 id, 6 parent_id from dual 
    union all select 8 id, 7 parent_id from dual 
    union all select 7 id, 6 parent_id from dual 
   union all select 8 id, 10 parent_id from dual 
   union all select 9 id, 9 parent_id  from dual 
   union all select 12 id, 11 parent_id from dual ),
--
-- Начало основного запроса на рекурсивном СТЕ (для Oracle только):
tree (id, parent_id, lv, pathstr)
as (select id, parent_id,  0, '' 
   from graph
   where 1 in (parent_id,id)
union all
   select graph.id, graph.parent_id, tree.lv + 1, tree.pathstr || graph.id
   from graph 
     inner join tree 
     on tree.id = graph.parent_id
        or tree.id = graph.id
        or tree.parent_id = graph.parent_id
        or tree.parent_id = graph.id        
     ) 
-- Говорим, что "пометь циклы и не бегай по ним":
 CYCLE id SET cyclemark TO 'X' DEFAULT '-'
select id from tree 
union
select parent_id from tree
on-line проверка на sqlfiddle.com
13 май 16, 09:19    [19167403]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить