ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Задача на собеседование
25 сообщений из 65, страница 2 из 3
  2  все
Задача на собеседование
    #39718470
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
авторДанные представлены в табличке с двумя колонками, где в первой - простая нумерация заправок от 1 до N, а во второй - расстояние до заправки (считать, что для первой заправки расстояние считается от начала отправления пользователя, например - из дома)
Выбирать точку отсчета начала маршрута непонятно где для решения задачи неудобно и ни на что не влияет, поэтому на первом шаге имеет смысл сделать первую заправку точкой отсчета, соответственно точка отправления пользователя уйдет в минус на координатной оси, куда ей и дорога.

Второй момент, если есть или получаются одинаковые расстояния между заправками, куда помещать новую заправку? Этот момент необходимо конкретизировать для получения детерменированного решения задачи. Добавляем условие, если есть несколько отрезков (расстояний между соседними заправками) одинаковой величины, то новая заправка помещается на максимально удаленном от первой заправки отрезке.

Сделаем тестовый пример:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
with t
     as (
        select 1  num_station, 0   dist_abs, 0  dist_to_prev from dual union all
        select 2  num_station, 3   dist_abs, 3  dist_to_prev from dual union all
        select 3  num_station, 8   dist_abs, 5  dist_to_prev from dual union all
        select 4  num_station, 14  dist_abs, 6  dist_to_prev from dual union all
        select 5  num_station, 16  dist_abs, 2  dist_to_prev from dual union all
        select 6  num_station, 23  dist_abs, 7  dist_to_prev from dual union all
        select 7  num_station, 31  dist_abs, 8  dist_to_prev from dual union all
        select 8  num_station, 41  dist_abs, 10 dist_to_prev from dual union all
        select 9  num_station, 57  dist_abs, 16 dist_to_prev from dual union all
        select 10 num_station, 74  dist_abs, 17 dist_to_prev from dual union all
        select 11 num_station, 110 dist_abs, 36 dist_to_prev from dual
        )




Результат добавления L новых заправок представить в виде таблицы, содержащей столбцы - номер заправки, расстояние до первой заправки, расстояние до предыдущей заправки, номера заправок должны быть последовательные и следовать в порядке увеличения расстояния от первой заправки.

В таком виде задача приобретает более осмысленный вид и пригодна для решения, дерзайте))
...
Рейтинг: 0 / 0
16.10.2018, 22:47
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718476
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кобанчег
Участник
SkilledJuniorВ таком виде задача приобретает более осмысленный вид и пригодна для решения, дерзайте))Нужно быть очень неордиарной личонстью, чтоб после уточненных условий и предоставленных решений написать этот поток сознания да еще с таким апломбом.

Есть вполне конкретные входные данные и четкий критерий минимизации. Если что-то непонятно - лучше просто уточнить.
...
Рейтинг: 0 / 0
16.10.2018, 22:58
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718507
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
ValergradО чем вы, ребята? О каких уникумах? Задачка очень простая же.
Речь не о сложности самого алгоритма, а о способности человека записать программный код "на бумажке".
...
Рейтинг: 0 / 0
17.10.2018, 02:10
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718699
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
982183Речь не о сложности самого алгоритма, а о способности человека записать программный код "на бумажке".
Может быть речь шла как раз о путях решения, сомнительно чтобы на собеседовании требовалось решить итерационную задачку на SQL, на процедурном языке нужны всего навсего массив и три цикла.
...
Рейтинг: 0 / 0
17.10.2018, 12:29
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718711
Фотография -2-
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
-2-
Участник
982183о способности человека записать программный код "на бумажке".Когда-то проще было написать на бумажке, чем сразу нащелкивать тумблерами адрес и значение, а потом гадать, что получилось.
Правда язык машинных кодов, в отличие от всяких наворотов над ним, прост для понимания. Даже тупые машины могут его исполнять без дополнительных манипуляций.
...
Рейтинг: 0 / 0
17.10.2018, 12:38
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718816
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
Одно дело описать алгоритм на бумажке, другое дело код, зачем подобную кракозябру писать на бумажке?

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
Declare
	TYPE StationAllocationTyp IS RECORD (
	num_station    NUMBER,
	dist_to_prev   NUMBER,
	allocated      NUMBER,
	new_dist       NUMBER
	);
	
	TYPE StAllocationArrTyp IS VARRAY(11) OF StationAllocationTyp;
	
	-- отсортированный по расстоянию между заправками массив
	st_allocation StAllocationArrTyp := StAllocationArrTyp(
	StationAllocationTyp(1,  0,  0, 0),
	StationAllocationTyp(5,  2,  0, 2),
	StationAllocationTyp(2,  3,  0, 3),
	StationAllocationTyp(3,  5,  0, 5),
	StationAllocationTyp(4,  6,  0, 6),
	StationAllocationTyp(6,  7,  0, 7),
	StationAllocationTyp(7,  8,  0, 8),
	StationAllocationTyp(8,  10, 0, 10),
	StationAllocationTyp(9,  16, 0, 16),
	StationAllocationTyp(10, 17, 0, 17),
	StationAllocationTyp(11, 36, 0, 36)
	);
	
	N NUMBER := 11;
	L NUMBER := 100000;
	
	l_max_dist_ind     NUMBER;
	l_max_dist_ind_tmp NUMBER;
Begin
	l_max_dist_ind := N;

	for i in 1 .. L loop
		l_max_dist_ind_tmp := N;
		for j in reverse 1 .. N loop
			if st_allocation(j).new_dist >= st_allocation(l_max_dist_ind).new_dist then
				-- размещение заправки
				st_allocation(j).allocated := st_allocation(j).allocated + 1;
				st_allocation(j).new_dist  := st_allocation(j).dist_to_prev / (st_allocation(j).allocated + 1);
				-- поиск нового максимального расстояния
				l_max_dist_ind := l_max_dist_ind_tmp;
				for k in reverse 1 .. j loop
					if st_allocation(k).new_dist > st_allocation(l_max_dist_ind).new_dist then
						l_max_dist_ind := k;
					end if;
				end loop k;

				exit;
				
			end if;

			if st_allocation(j).new_dist > st_allocation(l_max_dist_ind_tmp).new_dist then
				l_max_dist_ind_tmp := j;
			end if;
		end loop j;
	end loop i;
	
	for d in 1 .. N loop
		dbms_output.put_line(st_allocation(d).dist_to_prev || ',' || st_allocation(d).allocated || ',' || st_allocation(d).new_dist);
	end loop;
End;
...
Рейтинг: 0 / 0
17.10.2018, 14:38
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718825
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
Третий цикл даже лишний и сортировка исходных данных по расстоянию не нужна, сбили любители select-ов с их "бесплатной" сортировкой.
...
Рейтинг: 0 / 0
17.10.2018, 14:50
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718845
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
Declare
	TYPE StationAllocationTyp IS RECORD (
	num_station    NUMBER,
	dist_to_prev   NUMBER,
	allocated      NUMBER,
	new_dist       NUMBER
	);
	
	TYPE StAllocationArrTyp IS VARRAY(11) OF StationAllocationTyp;
	
	st_allocation StAllocationArrTyp := StAllocationArrTyp(
	StationAllocationTyp(1,  0,  0, 0),
	StationAllocationTyp(2,  3,  0, 3),
	StationAllocationTyp(3,  5,  0, 5),
	StationAllocationTyp(4,  6,  0, 6),
	StationAllocationTyp(5,  2,  0, 2),
	StationAllocationTyp(6,  7,  0, 7),
	StationAllocationTyp(7,  8,  0, 8),
	StationAllocationTyp(8,  10, 0, 10),
	StationAllocationTyp(9,  16, 0, 16),
	StationAllocationTyp(10, 17, 0, 17),
	StationAllocationTyp(11, 36, 0, 36)
	);
	
	N NUMBER := 11;
	L NUMBER := 100;
	
	l_max_dist_ind     NUMBER;
Begin
	for i in 1 .. L loop
		-- поиск максимального расстояния
		l_max_dist_ind := 1;
		for j in 2 .. N loop
			if st_allocation(j).new_dist > st_allocation(l_max_dist_ind).new_dist then
				l_max_dist_ind := j;
			end if;
		end loop j;
		-- размещение заправки
		st_allocation(l_max_dist_ind).allocated := st_allocation(l_max_dist_ind).allocated + 1;
		st_allocation(l_max_dist_ind).new_dist  := st_allocation(l_max_dist_ind).dist_to_prev / (st_allocation(l_max_dist_ind).allocated + 1);
	end loop i;
	
	
	for d in 1 .. N loop
		dbms_output.put_line(st_allocation(d).dist_to_prev || ',' || st_allocation(d).allocated || ',' || st_allocation(d).new_dist);
	end loop;
End;
...
Рейтинг: 0 / 0
17.10.2018, 15:06
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718856
123йй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
123йй
Участник
SkilledJunior,

Код: plsql
1.
2.
3.
4.
5.
6.
Connected to Oracle Database 12c Enterprise Edition Release 12.2.0.1.0 
....
ORA-06550: line 12, column 3:
PLS-00222: no function with name 'STATIONALLOCATIONTYP' exists in this scope
ORA-06550: line 11, column 17:
PL/SQL: Item ignored
...
Рейтинг: 0 / 0
17.10.2018, 15:20
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39718862
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
123йй,

18с))
...
Рейтинг: 0 / 0
17.10.2018, 15:28
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39719143
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
SkilledJuniorВторой момент, если есть или получаются одинаковые расстояния между заправками, куда помещать новую заправку? Этот момент необходимо конкретизировать для получения детерменированного решения задачи. Добавляем условие, если есть несколько отрезков (расстояний между соседними заправками) одинаковой величины, то новая заправка помещается на максимально удаленном от первой заправки отрезке.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
Declare
	TYPE StationAllocationTyp IS RECORD (
	num_station    NUMBER,
	dist_to_prev   NUMBER,
	allocated      NUMBER,
	new_dist       NUMBER
	);
	
	TYPE StAllocationArrTyp IS VARRAY(10) OF StationAllocationTyp;
	
	st_allocation StAllocationArrTyp;
	
	N   NUMBER := 10;
	L   NUMBER := 7;
	
	l_max_dist_ind     NUMBER;
Begin
	-- заполняем массив, сортировка по номеру заправки
	select num_station, dist_to_prev, 0 allocated, dist_to_prev as new_dist
	BULK COLLECT into st_allocation
	from
	(
	select 2  num_station, 3  dist_to_prev from dual union all
	select 3  num_station, 5  dist_to_prev from dual union all
	select 4  num_station, 8  dist_to_prev from dual union all
	select 5  num_station, 2  dist_to_prev from dual union all
	select 6  num_station, 7  dist_to_prev from dual union all
	select 7  num_station, 6  dist_to_prev from dual union all
	select 8  num_station, 10 dist_to_prev from dual union all
	select 9  num_station, 17 dist_to_prev from dual union all
	select 10 num_station, 16 dist_to_prev from dual union all
	select 11 num_station, 36 dist_to_prev from dual
	)
	order by num_station;

	for i in 1 .. L loop
		-- поиск максимального расстояния между заправками, начиная с наиболее удаленных
		l_max_dist_ind := N;
		if N > 1 then
			for j in reverse 1 .. (N-1) loop
				if st_allocation(j).new_dist > st_allocation(l_max_dist_ind).new_dist then
					l_max_dist_ind := j;
				end if;
			end loop j;
		end if;
		-- размещение заправки
		st_allocation(l_max_dist_ind).allocated := st_allocation(l_max_dist_ind).allocated + 1;
		st_allocation(l_max_dist_ind).new_dist  := st_allocation(l_max_dist_ind).dist_to_prev / (st_allocation(l_max_dist_ind).allocated + 1);
	end loop i;
	
	
	for d in 1 .. N loop
		dbms_output.put_line(st_allocation(d).num_station  || ', ' ||
		                     st_allocation(d).dist_to_prev || ', ' ||
		                     st_allocation(d).allocated    || ', ' ||
		                     st_allocation(d).new_dist);
	end loop d;
End;
...
Рейтинг: 0 / 0
18.10.2018, 00:28
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39719481
KDA_666
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
KDA_666
Гость
Спасибо всем за обсуждение данной задачи.
Подкину ещё один способ решения: довольно таки затратный, неоптимизированный и т.д., но делает то, что нужно.
Такое на бумажке не напишешь, конечно же, поэтому решение от Valergrad считаю оптимальным, при тех условиях, что я писал в начале темы.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
create type cte_set as object (interval_num number, length number);
drop type cte_set2 force;
create or replace type cte_set2 as table of cte_set;
create or replace type cte_set3 as table of number;

with cte as
 (select 1 num_interval, 10 length
    from dual
  union all
  select 2, 25
    from dual
  union all
  select 3, 60
    from dual ),
cte2 as
 (select 6 count_new from dual),
 
cte3 as ( select level - 1 as num from dual
          connect by level <= ( select * from cte2 ) + 1)
   
select * 
from table(
     select cast(
     multiset(
            select row_number() over( order by 1 ), t.length
            from table(next_state) t,
            table(split_variant) tt,
            table(
                 cast(
                 multiset(
                      select null
                      from dual
                      connect by level <= tt.length + 1) as sys.odcinumberlist)
                 )
            where t.interval_num = tt.interval_num)
      as cte_set2) as result_state
from (
     select tt.*, min(max_len) over( order by 1 ) as min_max_len
     from (
          select cast(
          multiset(
                 select t.interval_num, t.length / ( t1.length + 1 )
                 from table(beg_state) t, table(split_variant) t1
                 where t.interval_num = t1.interval_num)
                 as cte_set2) as next_state,
          (select max(length)
                 from table(
                 cast(
                 multiset(
                      select t.interval_num, t.length / ( t1.length + 1 )
                      from table(beg_state) t, table(split_variant) t1
                      where t.interval_num = t1.interval_num ) as cte_set2 ) ) ) as max_len,
           split_variant
           from (
                select beg_state,
                cast(
                multiset(
                       select row_number() over (order by 1) as rn, column_value
                       from table(split_variant) ) as cte_set2) as split_variant
                from (
                     select cast(
                     multiset(
                            select * from cte) as cte_set2) as beg_state,
                     column_value as split_variant,
                     (select sum(column_value)
                     from table(column_value) t) as sum_split_int
                     from table(powermultiset_by_cardinality(cast( multiset( select num from cte3 ) as cte_set3 ), ( select count(1) from cte ) ) ) )
                where sum_split_int = ( select count_new from cte2 )
                ) t
           ) tt
     )
where max_len = min_max_len and rownum = 1)
...
Рейтинг: 0 / 0
18.10.2018, 16:30
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39719547
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кобанчег
Участник
KDA_666делает то, что нужноОно даже приблизительно не делает то, что нужно.

Попытка использовать powermultiset_by_cardinality для генерации возможных распределений изначально неудачна,
т.к. число добавленных заправок не обязано быть уникальным по участкам.

Если делать полный перебор есть намного более вменяемые способы в SQL.

Чтоб убедиться в нерабочести достаточно заменить 60 на 600,
тогда все добавленные должны пойти на последний участок а на остальных участках будет по нулям.
...
Рейтинг: 0 / 0
18.10.2018, 18:19
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720458
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
Кто способен изобразить на листочке?

Код: plsql
1.
2.
3.
4.
5.
6.
create table MY_TEST_TABLE
    (
    NUM_STATION                   NUMBER not null primary key,
    DIST_TO_PREV                  NUMBER not null
    );
/



Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
insert into MY_TEST_TABLE
	select num_station, dist_to_prev
	from
	(
	select 2  num_station, 3  dist_to_prev from dual union all
	select 3  num_station, 5  dist_to_prev from dual union all
	select 4  num_station, 8  dist_to_prev from dual union all
	select 5  num_station, 2  dist_to_prev from dual union all
	select 6  num_station, 7  dist_to_prev from dual union all
	select 7  num_station, 6  dist_to_prev from dual union all
	select 8  num_station, 10 dist_to_prev from dual union all
	select 9  num_station, 17 dist_to_prev from dual union all
	select 10 num_station, 16 dist_to_prev from dual union all
	select 11 num_station, 36 dist_to_prev from dual
	);
/



Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
CREATE OR REPLACE TYPE my_st_all_typ AS OBJECT (
	NUM_STATION    NUMBER,
	DIST_TO_PREV   NUMBER,
	ALLOCATED      NUMBER,
	NEW_DIST       NUMBER);
/

CREATE OR REPLACE TYPE my_st_all_tab AS TABLE OF my_st_all_typ;
/



Код: plsql
1.
2.
3.
4.
5.
6.
CREATE OR REPLACE PACKAGE my_test_pkg AUTHID DEFINER AS
	TYPE st_add_tab IS TABLE OF MY_TEST_TABLE%ROWTYPE;
	FUNCTION getAllocation(p_L in NUMBER) RETURN my_st_all_tab;
	FUNCTION addStation(p_L in NUMBER)    RETURN st_add_tab PIPELINED;
END my_test_pkg;
/



Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
CREATE OR REPLACE PACKAGE BODY my_test_pkg AS

FUNCTION getAllocation(p_L in NUMBER) RETURN my_st_all_tab IS
	st_allocation      my_st_all_tab;
	N                  NUMBER;
	l_max_dist_ind     NUMBER;
	
	TYPE allcurtyp IS REF CURSOR;
	all_cv            allcurtyp;
BEGIN
	-- заполняем массив, сортировка по номеру заправки
	open all_cv for
		select my_st_all_typ(num_station, dist_to_prev, 0, dist_to_prev)
		from MY_TEST_TABLE
		where num_station > 1
		order by num_station;
	fetch all_cv BULK COLLECT into st_allocation;
	close all_cv;

	N := st_allocation.COUNT;
	
	if (p_L < 1) or (N = 0) then
		Return st_allocation;
	end if;
	
	for i in 1 .. p_L loop
		-- поиск максимального расстояния между заправками, начиная с наиболее удаленных
		l_max_dist_ind := N;
		if N > 1 then
			for j in reverse 1 .. (N-1) loop
				if st_allocation(j).new_dist > st_allocation(l_max_dist_ind).new_dist then
					l_max_dist_ind := j;
				end if;
			end loop j;
		end if;
		-- размещение заправки
		st_allocation(l_max_dist_ind).allocated := st_allocation(l_max_dist_ind).allocated + 1;
		st_allocation(l_max_dist_ind).new_dist  := st_allocation(l_max_dist_ind).dist_to_prev / (st_allocation(l_max_dist_ind).allocated + 1);
	end loop i;
	
	Return st_allocation;
END getAllocation;


FUNCTION addStation(p_L in NUMBER) RETURN st_add_tab PIPELINED IS
	st_allocation    my_st_all_tab;
	st_add_rec       MY_TEST_TABLE%ROWTYPE;
	N                NUMBER;
BEGIN
	st_allocation := getAllocation(p_L);
	
	N := st_allocation.COUNT;
	
	if N = 0 then
		Return;
	end if;
	
	st_add_rec.NUM_STATION  := 1;
	st_add_rec.DIST_TO_PREV := 0;
	PIPE ROW (st_add_rec);
	
	for i in 1 .. N loop
		for j in 1 .. (st_allocation(i).allocated + 1) loop
			st_add_rec.NUM_STATION  := st_add_rec.NUM_STATION + 1;
			st_add_rec.DIST_TO_PREV := st_allocation(i).new_dist;
			PIPE ROW (st_add_rec);
		end loop j;
	end loop i;
	
	Return;
END addStation;

END my_test_pkg;
/



Еще остался простор для оптимизации поиска максимального расстояния между заправками ...
...
Рейтинг: 0 / 0
21.10.2018, 14:40
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720586
Valergrad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valergrad
Участник
SkilledJuniorКто способен изобразить на листочке?


А что здесь сложного? Кроме излишней многословности не вижу ничего такого - но я не вчитывался. Можно узнать, чем этот фрагмент лучше лаконичного sql? Может быть он быстрее?
И еще у меня в памяти запомнилось, что вы говорили в исходном комменте о том, что задачу нельзя решать c помощью pl/sql, среди других ограничений. Именно такое было условие на собеседовании, если я вас правильно понял.
...
Рейтинг: 0 / 0
21.10.2018, 21:36
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720614
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
ValergradА что здесь сложного?
Абсолютно ничего, если не рисовать это на листочке.

Valergradчем этот фрагмент лучше лаконичного sql? Может быть он быстрее?
Итерационная задача оптимальным образом может быть решена с помощью соответствующих инструментов и SQL это не совсем подходящий инструмент, хотя если просто побаловаться или получить быстро и разово результат на небольшой выборке, то и SQL сойдет. По скорости нужно сравнивать, как правило процедурное решение работает на порядок, а то и на два быстрее.

ValergradИ еще у меня в памяти запомнилось, что вы говорили в исходном комменте о том, что задачу нельзя решать c помощью pl/sql, среди других ограничений. Именно такое было условие на собеседовании, если я вас правильно понял.
Подвела тебя память, я не автор темы.
...
Рейтинг: 0 / 0
21.10.2018, 22:49
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720656
Valergrad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valergrad
Участник
SkilledJuniorValergradА что здесь сложного?
По скорости нужно сравнивать, как правило процедурное решение работает на порядок, а то и на два быстрее.


Здесь не соглашусь. Дело не в процедурности-непроцедурности, а в алгоритме. Как я и написал, у моего запроса сложность - o(N*K*log(n*k)). У вашего, соответственно - o(N*K) ( в худшем случае, в среднем зависит от распределения данных). На малых значениях еще важна константа, которая для sql-решения будет, конечно, меньше за счет нативности операций и отсутсвия переключений контекста.

Поэтому сравнение запроса и кода на случайных данных показывает что
1) пока N и K до 1000 - запрос работает быстрее.
2) Далее, запрос начинает отставать , но зато его легко убыстрить, добавив просто хинт /*+ PARALLEL(n) */ - что дает запросу возможность работать быстрее еще до 5-10 тысяч N и K. В процедуру вы параллелизацию так просто не прикрутите - придется ее перерабатывать.
3) И только после 10 тысяч процедура начинает работать быстрее - за счет лучшей сложности алгоритма.

Впрочем, эта сложность не наилучшая. Скажем, есть несложное решение ( использующее как раз структуры данных ) у которого сложность алгоритма будет o( log(n) * k). Сможете найти?
...
Рейтинг: 0 / 0
22.10.2018, 02:55
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720657
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кобанчег
Участник
SkilledJunior,

Если представить, что задача была дана до интервью как тестовая, то возникает вопрос:
что для кандидата хуже : не прислать ничего или прислать твой бред.

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

Потому что ясность мышления приобретается заметно сложнее чем знания по продукту.
Если у кандидата каша в голове то какая разница, пусть он знает хоть все доки наизусть.

Теперь посмотрим, так ли монструозно выглядит остальное.

Пусть было n заправок, надо добавить k.

Вычислительная сложность первой модели O(k*n*n):
k итераций, на каждой проходим n строк, для каждой строки считаем агрегат(ы).
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
SQL> with t (id, distance) as
  2  (
  3  select 1, 4 from dual
  4  union all select 2, 10 from dual
  5  union all select 3, 20 from dual
  6  union all select 4, 100 from dual
  7  )
  8  select id, distance, a allocated
  9  from t
 10  model
 11  dimension by (id)
 12  measures (distance, 0 a, 0 tmp_allocated)
 13  rules iterate (12)
 14  (
 15    tmp_allocated[any] order by id =
 16    case when distance[cv()]/(a[cv()]+1) = max(distance/(a+1))[any] and sum(a)[any] = sum(tmp_allocated)[any]
 17         then a[cv()]+1
 18         else a[cv()]
 19    end,
 20    a[any] = tmp_allocated[cv()]
 21  )
 22  order by 1 desc;

        ID   DISTANCE  ALLOCATED
---------- ---------- ----------
         4        100          9
         3         20          2
         2         10          1
         1          4          0



Вычислительная сложность варианта Valergrad O((n*k)log(n*k)):
По сути требуется сортировка набора размером n*k.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
SQL> with test_data(num_station, dist_to_prev) as
  2  (
  3  select 1, 4 from dual
  4  union all select 2, 10 from dual
  5  union all select 3, 20 from dual
  6  union all select 4, 100 from dual
  7  ),
  8  generator as
  9   (select level i from dual connect by level <= 12),
 10  prep as
 11   (select t.*,
 12           t.dist_to_prev / (g.i + 1) as min_dist,
 13           g.i as num_additional_station,
 14           row_number() over(order by t.dist_to_prev / (g.i) desc) order_of_adding
 15      from test_data t, generator g)
 16  select num_station,
 17         dist_to_prev,
 18         count(case when order_of_adding <= 12 then 1 end) num_added_stations
 19    from prep
 20   group by num_station, dist_to_prev
 21   order by 1 desc;

NUM_STATION DIST_TO_PREV NUM_ADDED_STATIONS
----------- ------------ ------------------
          4          100                  9
          3           20                  2
          2           10                  1
          1            4                  0



Если больше подумать над моделью то можно додуматься что на каждой итераци
можно считать индекс для обновления на следующей итерации - r.
Вычислительная сложность O((k*(n*log(n))):
Выполняем k итераций, на кадой сортируем набор размером n.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
SQL> with t (id, distance) as
  2  (
  3  select 1, 4 from dual
  4  union all select 2, 10 from dual
  5  union all select 3, 20 from dual
  6  union all select 4, 100 from dual
  7  )
  8  select id, distance, a allocated
  9  from t
 10  model
 11  dimension by (id)
 12  measures (distance, 0 a, min(id) keep (dense_rank first order by distance desc) over () r)
 13  rules iterate (12)
 14  (
 15    a[r[1]] = a[r[1]] + 1,
 16    r[any] = min(id) keep (dense_rank first order by distance/(a+1) desc) over ()
 17  )
 18  order by 1 desc;

        ID   DISTANCE  ALLOCATED
---------- ---------- ----------
         4        100          9
         3         20          2
         2         10          1
         1          4          0



Очень много текста?

Это НЕ подходящая задача для интервью, но адекватное тестовое задание,
если требуется проверить алгоритмическую смекалку (для SQL разработчика ).

В силу специфики SQL движка, и особенно модели, накладные расходы могут достаточно сильно искажать картину.
В частности, вариант Valergrad скоее всего будет быстрее даже улучшенной модели
не смотря на его большую вычислительную сложность.

На PL/SQL можно решить заметно эффективнее и без простыни говно-кода.
...
Рейтинг: 0 / 0
22.10.2018, 02:56
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720658
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кобанчег
Участник
Valergrad...На минуту опередил! Зря я так расписывал...
...
Рейтинг: 0 / 0
22.10.2018, 03:00
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720675
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Elic
Участник
Кобанчегдля SQL разработчика Это кто такие?
...
Рейтинг: 0 / 0
22.10.2018, 07:46
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720812
Valergrad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valergrad
Участник
КобанчегValergrad...На минуту опередил! Зря я так расписывал...

Сорри...
...
Рейтинг: 0 / 0
22.10.2018, 11:49
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720819
Valergrad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valergrad
Участник
КобанчегНа PL/SQL можно решить заметно эффективнее и без простыни говно-кода.

Как-то сурово. Код как код, видал я ( и вижу на работе регулярно у коллег ) и похуже.
...
Рейтинг: 0 / 0
22.10.2018, 12:01
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720827
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кобанчег
Участник
ElicКобанчегдля SQL разработчика Это кто такие?Разработчику Оракла зачастую более важно уметь выражать мысли декларативно на SQL чем быть искусным в алгоритмах.
С другой стороны, задача могла бы быть уместной на собеседовании C++/Java.
Хотя никто доподлинно не может сказать на какую позицию была эта задача и была ли вообще.
ValergradКак-то сурово. Код как код, видал я ( и вижу на работе регулярно у коллег ) и похуже.Ну раз тех коллег кто-то нанимает и никто не увольняет, то и SkilledJunior не пропадет.
...
Рейтинг: 0 / 0
22.10.2018, 12:20
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39720844
Valergrad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valergrad
Участник
КобанчегНу раз тех коллег кто-то нанимает и никто не увольняет, то и SkilledJunior не пропадет.

А у вас таких нет? Что за компания, я тогда к вам пойду)))
...
Рейтинг: 0 / 0
22.10.2018, 12:49
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39721174
SkilledJunior
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SkilledJunior
Гость
ValergradЗдесь не соглашусь.
А не надо соглашаться или не соглашаться, тесты нужно написать и выполнить в одинаковых условиях, тогда будет более менее реальная картина.

ValergradНа малых значениях еще важна константа, которая для sql-решения будет, конечно, меньше за счет нативности операций и отсутсвия переключений контекста.

Ты уверен что PL/SQL не нативный?

Что касается переключения контекста, и накладных расходов, с этой точки зрения такой запрос: select my_st_all_typ(num_station, dist_to_prev, 0, dist_to_prev) это опа. Зачем я так сделал? Чтобы продемонстрировать табличные функции разных типов и поленился немного, конечно нужно было считывать исходные данные в коллекцию записей а не объектов, считывая в коллекцию объектов приходится дергать конструктор объекта, т.е. дергать функцию на каждую строку, в реальной системе так делать конечно не стоит.

ValergradВпрочем, эта сложность не наилучшая. Скажем, есть несложное решение ( использующее как раз структуры данных ) у которого сложность алгоритма будет o( log(n) * k). Сможете найти?
Слабое место это поиск максимального расстояния на каждой итерации, я прохожу в лоб циклом перебирая N строк, можно пытаться строить индекс и пользоваться индексом, но есть большое но, индекс очень быстро теряет свою селективность по максимальному значению и начинает стремиться к полному перебору, т.е. индекс нужно периодически полностью перестраивать, делать это на каждой итерации еще хуже чем простой перебор. Поэтому я надеюсь ты не хотел предложить ассоциативный массив с неуправляемой тобой индексацией и не совсем подходящим типом данных индекса?
...
Рейтинг: 0 / 0
23.10.2018, 00:00
| Ответить | Цитировать | Написать  
25 сообщений из 65, страница 2 из 3
  2  все
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Задача на собеседование
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&msg=39719547&tid=1883283]:
 0ms
get settings:
 6ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 157ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 65ms
get tp. blocked users:
 1ms
others: 201ms
total:  463ms
созд. / загр.: 463ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]