Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Задача на собеседование / 25 сообщений из 65, страница 1 из 3
  1  все
15.10.2018, 13:14
    #39717570
KDA_666
KDA_666
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Приветствую всех знатоков :)

Недавно увидел непростую задачу, знаний на которую пока что не хватает для решения.
Сама задача: есть дорога, на которой стоит N заправок. Также известно расстоянием между заправками.
Данные представлены в табличке с двумя колонками, где в первой - простая нумерация заправок от 1 до N, а во второй - расстояние до заправки (считать, что для первой заправки расстояние считается от начала отправления пользователя, например - из дома)
Пример:
1 10
2 10
3 30
Нужно расположить на искомом отрезке L новых заправок так, чтобы минимизировать максимальное расстояние между соседними заправками. (например, на вышеупомянутом наборе данных, при количестве новых заправок L = 1 нужно поставить новую заправку ровно посередине дороги между 2ой и 3ей заправкой, а при количестве L = 2 новых заправок нужно поставить между 2ой и 3ей заправкой на расстоянии 1/3 и 2/3, то есть чтобы расстояние разбилось на три десятки, так как данное решение минимизирует максимальное расстояние между любыми соседними заправками)

P.S. интересует решение без использования model, рекурсий, циклов, а также pl/sql, так как требованием было не использовать ранее сказанное, а также был дан намёк в сторону спецификации типов данных oracle.

Заранее спасибо!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 13:22
    #39717582
AmKad
AmKad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
KDA_666,

Признавайся, куда ходил.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 13:24
    #39717586
Dshedoo
Dshedoo
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
KDA_666,

У меня даже Яреклама выдаёт Тинькова в этой теме.
В разделе "работа" уже разбирали эту задачу, но только через циклы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 13:30
    #39717594
AmKad
AmKad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Dshedoo,

К гадалке не ходи: в связи с ростом цен на бензин, Олег решил перейти с банковского бизнеса на розничную торговлю ГСМ.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 14:26
    #39717655
KDA_666
KDA_666
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Dshedoo,

как раз такие там и увидел данную задачу, но не увидел ни одного нормального алгоритма/решения.
А ещё хотелось бы с теми ограничениями, что я написал, узнать, есть ли решение.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 16:10
    #39717730
-2-
-2-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
KDA_666есть ли решение.Если количество новоколонок меньше суммы целоотношений ненулевых расстояний, то решается в один проход. Иначе, решается перебором подмножеств количеством добавляемых колонок с выбором первого (минимального) макс.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 16:21
    #39717739
Dshedoo
Dshedoo
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Можно попробовать симплекс-метод или ОПГ, мб проканает.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 16:44
    #39717746
Кобанчег
Кобанчег
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
KDA_666Пример:
1 10
2 10
3 30Если заправки находятся на одном отрезке, то непонятен смысл указывать те, что попадают в одну точку.
Вторая заправка убирается группировкой, что никоим образом не влияет не итоговое решение.
KDA_666Нужно расположить на искомом отрезке L новых заправок так, чтобы минимизировать максимальное расстояние между соседними заправками. (например, на вышеупомянутом наборе данных, при количестве новых заправок L = 1 нужно поставить новую заправку ровно посередине дороги между 2ой и 3ей заправкой, а при количестве L = 2 новых заправок нужно поставить между 2ой и 3ей заправкой на расстоянии 1/3 и 2/3, то есть чтобы расстояние разбилось на три десятки, так как данное решение минимизирует максимальное расстояние между любыми соседними заправками)
Если разположить две новых между 2 и 3, то дистанции будут 10, 6.66, 6.66, 6.66.
Если расположить одну между пользователем и 1/2, а вторую между 1/2 и 3, то дистанции будут 5, 5, 10, 10.
Максимальное в обоих случаях 10.
Отсюда вопрос почему нужно , а не можно .

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

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

after_allocation, max_after_allocation - просто для информации, их можно убрать.
Код: 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.
with t0 (distance) as
(
select 4 from dual
union all select 14 from dual
union all select 34 from dual
union all select 134 from dual
)
, t as
(
select rownum id, distance, 0 allocated
  from (select distance - lag(distance, 1, 0) over (order by distance) distance from t0 order by 1)
)
select *
from t
model
dimension by (id)
measures (distance, allocated, allocated tmp_allocated, 0 after_allocation, 0 max_after_allocation)
rules iterate (&to_allocate)
(
  tmp_allocated[any] order by id =
    case when
         -- расстояние между добавленными заправками равно максимальному
         distance[cv()]/(allocated[cv()]+1) = max(distance/(allocated+1))[any]
         and
         -- еще ну было выделено новой заправки на текущей итерации
         sum(allocated)[any] = sum(tmp_allocated)[any]
         -- тогда выделяем новую на текущем участке
         then allocated[cv()]+1 else allocated[cv()]
    end,
  allocated[any] = tmp_allocated[cv()],
  after_allocation[any] order by id = distance[cv()]/(allocated[cv()]+1),
  max_after_allocation[any] order by id = max(distance/(allocated+1))[any]
)
order by 1 desc;
Enter value for to_allocate: 12
old  18: rules iterate (&to_allocate)
new  18: rules iterate (12)

        ID   DISTANCE  ALLOCATED TMP_ALLOCATED AFTER_ALLOCATION MAX_AFTER_ALLOCATION
---------- ---------- ---------- ------------- ---------------- --------------------
         4        100          9             9               10                   10
         3         20          2             2       6.66666667                   10
         2         10          1             1                5                   10
         1          4          0             0                4                   10


Неитеративно решается только при определенных ограничениях.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 16:50
    #39717751
123йй
123йй
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Кобанчег,

и вы предоставите(напишите) этот код на листочке во время собеседования ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 16:59
    #39717757
Кобанчег
Кобанчег
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Мои вопросы отпали.
В условии сразу указывается расстояние между соседними, а не до исходной точки.

Тогда не нужен подзапрос с lag.

Алгоритм для модели не меняется.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
    case when
         -- расстояние между добавленными заправками на текущем участке равно максимальному
         distance[cv()]/(allocated[cv()]+1) = max(distance/(allocated+1))[any]
         and
         -- еще не было выделено новой заправки на текущей итерации
         sum(allocated)[any] = sum(tmp_allocated)[any]
         -- тогда выделяем новую на текущем участке
         then allocated[cv()]+1 else allocated[cv()]
    end,
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 17:01
    #39717760
merch
merch
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Кобанчег,

KDA_666 интересует решение без использования model
?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 17:12
    #39717766
Кобанчег
Кобанчег
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
123йй,

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

merch,

Каюсь, в общем случае пока затрудняюсь решить неитеративно.
Даже мышление в сторону "спецификации типов данных oracle" не помогает.
Может это просто вброс ТС или собеседователей?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 17:16
    #39717767
KDA_666
KDA_666
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Кобанчег,

Спасибо за ответ)
Забыл в предложении "Данные представлены в табличке с двумя колонками, где в первой - простая нумерация заправок от 1 до N, а во второй - расстояние до заправки" явно указать "расстояние до СЛЕДУЮЩЕЙ заправки от предыдущей точки", что вносит дополнительное пояснение.

Покапавшись в некоторых решениях и типах наткнулся на коллекции, с помощью которых можно решить данную задачу, не используя то, что я говорил в ограничениях (по типу model), но ни разу не работал с данным типом.
Хотя основное направление я уже понял, был бы не против, если кто мог бы показать, как это примерно делается.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.10.2018, 17:45
    #39717784
Кобанчег
Кобанчег
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
KDA_666Покапавшись в некоторых решениях и типах наткнулся на коллекции, с помощью которых можно решить данную задачу, не используя то, что я говорил в ограничениях (по типу model)Слишком унылый вброс который лишь демонстрирует полное непонимание вопроса.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 01:01
    #39717878
Valergrad
Valergrad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
KDA_666Приветствую всех знатоков :)

P.S. интересует решение без использования model, рекурсий, циклов, а также pl/sql, так как требованием было не использовать ранее сказанное



Странное ограничение. Отказавшись от использования самых подходящих инструментов вы получаете неэффективное решение. Это так работают в Тинькове? С этими ограничениями задачка превращается в головоломку. Впрочем - несложную, минут на 15 ( признаюсь честно, синтаксис модели я бы дольше вспоминал-гуглил, уж очень редко использую).

Код: 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.
with test_data
     as (select 1 num_station, 4 dist_to_prev from dual
         union all
         select 2 num_station, 10 dist_to_prev from dual
         union all
         select 3 num_station, 20 dist_to_prev from dual
         union all
         select 4 num_station, 100 dist_to_prev from dual)
    ,generator
     as (    select level i
               from dual
         connect by level <= &num_stations)
    ,prep
     as (select t.num_station
               ,t.dist_to_prev / (g.i + 1) as min_dist
               ,g.i as num_additional_station
               ,row_number () over (order by t.dist_to_prev / (g.i + 1) desc) order_of_adding
           from test_data t, generator g)
    ,filtered_stations
     as (  select num_station, max (num_additional_station) num_added_stations, min (min_dist) dist_between_stations
             from prep
            where order_of_adding <= &num_stations
         group by num_station)
select num_station "Заправка", dist_between_stations * i as "Расстояние"
  from filtered_stations t, generator g
 where t.num_added_stations >= g.i




При &num_stations = 12:
Заправка Расстояние3 104 8.3333333334 16.666666674 254 33.333333334 41.666666674 504 58.333333334 66.666666674 754 83.333333334 91.66666667

Если собеседующий скажет, что connect by level - это та же рекурсия, обойдитесь старым добрым джойном к select * from dba_objects. Решение, очевидно не самое эффективное - его сложность равна N * K * log(n*k) где N - количество заправок существующих, K - количество заправок которых надо добавить, но если и тех и тех не многие тысячи вполне рабочее.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 02:19
    #39717883
Кобанчег
Кобанчег
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
ValergradПри &num_stations = 12При 13 и 14 макс расстояние остается 10 (между 1 и 2 ноль новых, между 2 и 3 - одна).
При 15 расстояние между 1 и 2 по прежнему остается 10... при 20 по прежнему ничего между 1 и 2 не вставлено => max = 10.
Если я правильно понимаю результат.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 02:38
    #39717884
Valergrad
Valergrad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
КобанчегValergradПри &num_stations = 12При 13 и 14 макс расстояние остается 10 (между 1 и 2 ноль новых, между 2 и 3 - одна).
При 15 расстояние между 1 и 2 по прежнему остается 10... при 20 по прежнему ничего между 1 и 2 не вставлено => max = 10.
Если я правильно понимаю результат.

Это была опечатка для проверки бдительности)). Нужно в одном месте не i+1, а i конечно же)

авторThere are two hard things in computer science: 0) Cache invalidation 1) Naming things 2) Off-by-one errors



Код: 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.
with test_data
     as (select 1 num_station, 4 dist_to_prev from dual
         union all
         select 2 num_station, 10 dist_to_prev from dual
         union all
         select 3 num_station, 20 dist_to_prev from dual
         union all
         select 4 num_station, 100 dist_to_prev from dual)
    ,generator
     as (    select level i
               from dual
         connect by level <= &num_stations)
    ,prep
     as (select t.num_station
               ,t.dist_to_prev / (g.i + 1) as min_dist
               ,g.i as num_additional_station
               ,row_number () over (order by t.dist_to_prev / (g.i) desc) order_of_adding
           from test_data t, generator g)
    ,filtered_stations
     as (  select num_station, max (num_additional_station) num_added_stations, min (min_dist) dist_between_stations
             from prep
            where order_of_adding <= &num_stations
         group by num_station)
select num_station "Заправка", dist_between_stations * i as "Расстояние"
  from filtered_stations t, generator g
 where t.num_added_stations >= g.i
 order by 1,2



Теперь для 15 результат:

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
2	5
3	6.66666666666666666666666666666666666667
3	13.33333333333333333333333333333333333334
4	7.69230769230769230769230769230769230769
4	15.38461538461538461538461538461538461538
4	23.07692307692307692307692307692307692307
4	30.76923076923076923076923076923076923076
4	38.46153846153846153846153846153846153845
4	46.15384615384615384615384615384615384614
4	53.84615384615384615384615384615384615383
4	61.53846153846153846153846153846153846152
4	69.23076923076923076923076923076923076921
4	76.9230769230769230769230769230769230769
4	84.61538461538461538461538461538461538459
4	92.30769230769230769230769230769230769228
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 02:41
    #39717885
982183
982183
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
123ййКобанчег, и вы предоставите(напишите) этот код на листочке во время собеседования ?
Я видел людей, которые могли это сделать.
Несколько человек.
Может быть именно их и ищут?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 08:54
    #39717921
123йй
123йй
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
982183,

Люди бывают разные. Раньше считалось нормой на asm писать на листочке.
Но на собеседовании кодировать от получаса это перебор.
Тут с согласен с Кобанчег 21704375 скорее это была теория и понять ход мысли ТС.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 10:07
    #39717947
982183
982183
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Я к тому, что есть действительно уникумы, достаточно сложно тестируемые на обычных задачах.
И если стоит задача найти именно таких. то выбор задания вполне обоснован.
Хотя, несомненно, для общей массы сложность слишком нестандартно.

Да и провернуть/проверить логику без теста на компе сложно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 12:24
    #39718054
Valergrad
Valergrad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
О чем вы, ребята? О каких уникумах? Задачка очень простая же.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 13:19
    #39718120
Кобанчег
Кобанчег
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Valergrad,

Изящно.
Я вчера тоже стал думать в этом направлении, начал с вопроса:
"сколько станций должно быть добавлено до первой станции на самом коротком отрезке (4)",
но итоговую формулу для порядка выводить было лень. :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 13:28
    #39718135
SkilledJunior
SkilledJunior
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Кобанчег,

А обратно отрезки в заправки развернуть?))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 13:44
    #39718148
Кобанчег
Кобанчег
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
SkilledJunior,

Опять бензина с утра нюхнул?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.10.2018, 14:02
    #39718157
KDA_666
KDA_666
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на собеседование
Valergrad,

Спасибо за ответ, очень помогло!

Кобанчег,
Вовсе не вброс.
Я, конечно, новичок в данной теме и может не так выразил свою мысль, но чуть позже предоставлю своё решение.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Задача на собеседование / 25 сообщений из 65, страница 1 из 3
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 425ms
Закрыть
start [/forum/topic.php?fid=52&mobile=1&tid=1883283]:
 0ms
get settings:
 7ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 136ms
get topic data:
 9ms
get forum data:
 3ms
get page messages:
 41ms
get tp. blocked users:
 1ms
others: 207ms
total:  425ms
x
x
Закрыть


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