Задача на собеседование / Oracle

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Oracle [игнор отключен] [закрыт для гостей] / Задача на собеседование

15 сообщений из 65, страница 3 из 3

все

Задача на собеседование

#39721176

SkilledJunior

Гость

КобанчегSkilledJunior,

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

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

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

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

...

Рейтинг:

0 / 0

23.10.2018, 00:13

| Ответить | Цитировать | Написать

Задача на собеседование

#39721178

SkilledJunior

Гость

КобанчегВыполняем k итераций, на кадой сортируем набор размером n.
Ты считаешь что сортировка n-записей дешевле однократного прямого прохода по n-записям для поиска максимального значения? Ты случаем не из параллельной вселенной?

...

Рейтинг:

0 / 0

23.10.2018, 00:20

| Ответить | Цитировать | Написать

Задача на собеседование

#39721186

Кобанчег

Участник

Откуда: Рахів

Сообщения: 924

Рейтинг: 0 / 0

SkilledJuniorКстати не забывай, что ваше решение недетерминированноеРешение недетерминироавнное у Valergrad. Детерминированность приобретается, если добвить еще одно поле в order by.
Модели обе детерминированнве некуда.
Единственное что, последнюю можно чуть упростить и обойтись first_value/last_value вместо трюкачества с keep.
SkilledJuniorТы считаешь что сортировка n-записей дешевле однократного прямого прохода по n-записям для поиска максимального значения?Нет, это ты счтаешь, что я считаю.
Из параллельной реальности это тот кто сам себе задачу поставил - сам спамит на форум свои шЫдевры и думает что с ним кто-то соревнуется.

...

Рейтинг:

0 / 0

23.10.2018, 01:11

| Ответить | Цитировать | Написать

Задача на собеседование

#39721187

SkilledJunior

Гость

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

...

Рейтинг:

0 / 0

23.10.2018, 01:14

| Ответить | Цитировать | Написать

Задача на собеседование

#39721230

-2-

Участник

Сообщения: 15 349

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

23.10.2018, 08:29

| Ответить | Цитировать | Написать

Задача на собеседование

#39721401

Valergrad

Участник

Сообщения: 601

Рейтинг: 0 / 0

SkilledJuniorно есть большое но, индекс очень быстро теряет свою селективность по максимальному значению и начинает стремиться к полному перебору, т.е. индекс нужно периодически полностью перестраивать

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

Я имел ввиду думать именно в сторону алгоритмических структур данных, реализованных на pl/sql, среди них есть множество структур данных поддерживающих апдейт значения и поиск максимума на отрезке одновременно за o(log n).

...

Рейтинг:

0 / 0

23.10.2018, 13:00

| Ответить | Цитировать | Написать

Задача на собеседование

#39721432

Elic

Участник

Сообщения: 30 360

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

23.10.2018, 13:43

| Ответить | Цитировать | Написать

Задача на собеседование

#39721615

Valergrad

Участник

Сообщения: 601

Рейтинг: 0 / 0

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

Это, конечно, интересно, но в нашем случае блоки же не будут пустые?

...

Рейтинг:

0 / 0

23.10.2018, 18:20

| Ответить | Цитировать | Написать

Задача на собеседование

#39721617

Valergrad

Участник

Сообщения: 601

Рейтинг: 0 / 0

ValergradElicпропущено...
В целом это не совсем так: RS с левой открытой границей читает пустые блоки индекса

Это, конечно, интересно, но в нашем случае блоки же не будут пустые?

Хотя если речь о моем утверждении "оно всегда находится за высоту индекса. " - согласен, был неправ.

...

Рейтинг:

0 / 0

23.10.2018, 18:21

| Ответить | Цитировать | Написать

Задача на собеседование

#39721723

SkilledJunior

Гость

ValergradЗдесь вы ошиблись - для нахождения максимального значения селективность индекса не влияет, оно всегда находится за высоту индекса. Впрочем, решение с индексом все равно плохое т.к. накладные расходы на dml-операции съедят все.
Какие такие dml-операции, дергать dml в функции на каждую итерацию это кирдык производительности сразу, нее только ручками, только хардкор. А ручками мы можем строить либо упрощенный вариант без сортировки внутри листьев, что быстро, но селективности не будет, либо с сортировкой внутри листьев, только подумайте что делать, если значение попадает куда то в начало блока, чтобы сохранить сортировку придется сдвинуть все значения в этом листе, как ни крути очень накладные операции и дадут ли они существенный прирост производительности большой вопрос.

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

Можно посмотреть на тестовом примере:

Код: plsql

select * from table(my_test_pkg.getAllocation(0))

NUM_STATIONDIST_TO_PREVALLOCATEDNEW_DIST23033505480852026707760681001091701710160161136036
диапазон 2-36

Код: plsql

select * from table(my_test_pkg.getAllocation(30))

NUM_STATIONDIST_TO_PREVALLOCATEDNEW_DIST23033512.54822.6666666666666666666666666666666666666752026722.33333333333333333333333333333333333333761381032.591752.83333333333333333333333333333333333333101652.666666666666666666666666666666666666671136113
всего тридцать заправок и диапазон уже 2-3

Код: plsql

select * from table(my_test_pkg.getAllocation(100))

NUM_STATIONDIST_TO_PREVALLOCATEDNEW_DIST2321354148715211676176518109191716110161511136351
Совпало так совпало))) 100 заправок и диапазон 1-1

ValergradЯ имел ввиду думать именно в сторону алгоритмических структур данных, реализованных на pl/sql, среди них есть множество структур данных поддерживающих апдейт значения и поиск максимума на отрезке одновременно за o(log n).
Пример?

...

Рейтинг:

0 / 0

23.10.2018, 23:04

| Ответить | Цитировать | Написать

Задача на собеседование

#39721956

Valergrad

Участник

Сообщения: 601

Рейтинг: 0 / 0

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

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

SkilledJuniorValergradЯ имел ввиду думать именно в сторону алгоритмических структур данных, реализованных на pl/sql, среди них есть множество структур данных поддерживающих апдейт значения и поиск максимума на отрезке одновременно за o(log n).
Пример?

Как пример ( я не говорю что это самая подходящая для данной задачи структура ) -
https://ru.wikipedia.org/wiki/Красно-чёрное_дерево

...

Рейтинг:

0 / 0

24.10.2018, 11:51

| Ответить | Цитировать | Написать

Задача на собеседование

#39722507

SkilledJunior

Гость

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

ValergradКак пример ( я не говорю что это самая подходящая для данной задачи структура ) -
https://ru.wikipedia.org/wiki/Красно-чёрное_дерево
Спасибо за ссылку, но хотелось бы:
Valergradреализованных на pl/sql

...

Рейтинг:

0 / 0

24.10.2018, 22:55

| Ответить | Цитировать | Написать

Задача на собеседование

#39723328

Est_vopros

Гость

Как обосновать, что ответ
Кобанчег

Код: plsql

1.
2.
3.
4.
5.
6.

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

лучше, чем например:

Код: plsql

1.
2.
3.
4.
5.
6.

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

...

Рейтинг:

0 / 0

26.10.2018, 10:37

| Ответить | Цитировать | Написать

Задача на собеседование

#39723352

-2-

Участник

Сообщения: 15 349

Рейтинг: 0 / 0

Est_voprosлучше, чемПо критерию max результат равнозначный.

...

Рейтинг:

0 / 0

26.10.2018, 11:32

| Ответить | Цитировать | Написать

Задача на собеседование

#39723439

Est_vopros

Гость

-2-По критерию max результат равнозначный.
А как это реализовать на SQL?
Если так:
Вычислить расстояния на отрезках.
Определить среднее.
просуммировать отклонения расстояний от средних, умноженные на кол-во отрезков
То решение
Кобанчег

Код: plsql

1.
2.
3.
4.
5.
6.

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

хуже, чем

Код: plsql

1.
2.
3.
4.
5.
6.

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

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

WITH
    t0
    AS
        (SELECT 100 len, 9 kol FROM DUAL
         UNION ALL
         SELECT 20 len, 2 kol FROM DUAL
         UNION ALL
         SELECT 10 len, 1 kol FROM DUAL
         UNION ALL
         SELECT 4 len, 0 kol FROM DUAL),
    t1
    AS
        (SELECT a.*,
                len / (kol + 1)
                    dist,
                AVG (len / (kol + 1)) OVER ()
                    avg_dist,
                ABS (len / (kol + 1) - AVG (len / (kol + 1)) OVER ())
                    delta_avg
           FROM t0 a)
SELECT SUM (delta_avg * (kol + 1)) SUM_DELTA_AVG_KOL
  FROM t1;

SUM_DELTA_AVG_KOL41.8333333333333

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

WITH
    t0
    AS
        (SELECT 100 len, 11 kol FROM DUAL
         UNION ALL
         SELECT 20 len, 1 kol FROM DUAL
         UNION ALL
         SELECT 10 len, 0 kol FROM DUAL
         UNION ALL
         SELECT 4 len, 0 kol FROM DUAL),
    t1
    AS
        (SELECT a.*,
                len / (kol + 1)
                    dist,
                AVG (len / (kol + 1)) OVER ()
                    avg_dist,
                ABS (len / (kol + 1) - AVG (len / (kol + 1)) OVER ())
                    delta_avg
           FROM t0 a)
SELECT SUM (delta_avg * (kol + 1)) SUM_DELTA_AVG_KOL
  FROM t1;

SUM_DELTA_AVG_KOL12.8333333333333

Кобанчег, парируйте!

...

Рейтинг:

0 / 0

26.10.2018, 12:56

| Ответить | Цитировать | Написать

15 сообщений из 65, страница 3 из 3

все

Форумы / Oracle [игнор отключен] [закрыт для гостей] / Задача на собеседование

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=52&msg=39722507&tid=1883283]:	0ms
get settings:	9ms
get forum list:	16ms
check forum access:	3ms
check topic access:	3ms
track hit:	148ms
get topic data:	13ms
get forum data:	3ms
get page messages:	74ms
get tp. blocked users:	1ms
others:	264ms

total:	534ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы