ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Задача на собеседование
25 сообщений из 65, страница 1 из 3
  1  все
Задача на собеседование
    #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:14
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39717582
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AmKad
Участник
KDA_666,

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

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

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

как раз такие там и увидел данную задачу, но не увидел ни одного нормального алгоритма/решения.
А ещё хотелось бы с теми ограничениями, что я написал, узнать, есть ли решение.
...
Рейтинг: 0 / 0
15.10.2018, 14:26
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39717730
Фотография -2-
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
-2-
Участник
KDA_666есть ли решение.Если количество новоколонок меньше суммы целоотношений ненулевых расстояний, то решается в один проход. Иначе, решается перебором подмножеств количеством добавляемых колонок с выбором первого (минимального) макс.
...
Рейтинг: 0 / 0
15.10.2018, 16:10
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39717739
Dshedoo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dshedoo
Участник
Можно попробовать симплекс-метод или ОПГ, мб проканает.
...
Рейтинг: 0 / 0
15.10.2018, 16:21
| Ответить | Цитировать | Написать  
Задача на собеседование
    #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:44
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39717751
123йй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
123йй
Участник
Кобанчег,

и вы предоставите(напишите) этот код на листочке во время собеседования ?
...
Рейтинг: 0 / 0
15.10.2018, 16:50
| Ответить | Цитировать | Написать  
Задача на собеседование
    #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, 16:59
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39717760
merch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
merch
Участник
Кобанчег,

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

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

merch,

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

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

Покапавшись в некоторых решениях и типах наткнулся на коллекции, с помощью которых можно решить данную задачу, не используя то, что я говорил в ограничениях (по типу model), но ни разу не работал с данным типом.
Хотя основное направление я уже понял, был бы не против, если кто мог бы показать, как это примерно делается.
...
Рейтинг: 0 / 0
15.10.2018, 17:16
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39717784
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кобанчег
Участник
KDA_666Покапавшись в некоторых решениях и типах наткнулся на коллекции, с помощью которых можно решить данную задачу, не используя то, что я говорил в ограничениях (по типу model)Слишком унылый вброс который лишь демонстрирует полное непонимание вопроса.
...
Рейтинг: 0 / 0
15.10.2018, 17:45
| Ответить | Цитировать | Написать  
Задача на собеседование
    #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, 01:01
| Ответить | Цитировать | Написать  
Задача на собеседование
    #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:19
| Ответить | Цитировать | Написать  
Задача на собеседование
    #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:38
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39717885
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
123ййКобанчег, и вы предоставите(напишите) этот код на листочке во время собеседования ?
Я видел людей, которые могли это сделать.
Несколько человек.
Может быть именно их и ищут?
...
Рейтинг: 0 / 0
16.10.2018, 02:41
| Ответить | Цитировать | Написать  
Задача на собеседование
    #39717921
123йй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
123йй
Участник
982183,

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

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

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

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

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

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

Кобанчег,
Вовсе не вброс.
Я, конечно, новичок в данной теме и может не так выразил свою мысль, но чуть позже предоставлю своё решение.
...
Рейтинг: 0 / 0
16.10.2018, 14:02
| Ответить | Цитировать | Написать  
25 сообщений из 65, страница 1 из 3
  1  все
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Задача на собеседование
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&msg=39717751&tid=1883283]:
 0ms
get settings:
 8ms
get forum list:
 30ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 375ms
get topic data:
 6ms
get forum data:
 2ms
get page messages:
 46ms
get tp. blocked users:
 1ms
others: 253ms
total:  725ms
созд. / загр.: 725ms
x
x
Закрыть


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