Тестовое задание Postgre-SQL программист от компании LightSoft

Продолжаем обсуждение различных тестовых заданий предлагаемых различными компаниямия на должность программистов. Данное задание предлагалось российской компанией LightSoft на вакансию Postge-SQL программиста. Сразу скажу что ответы на данное задние получили положительную оценку. Многие ответы на вопросы были взяты с сайта ru.Wikipedia.org в силу их краткости и емкости содержания и содержат соответствующие ссылки. Кроме того данный материал не является панацеей и публикуется для ознакомления читателей с интересными полезными вопросами которые касаются всего SQL вцелом,  а не только СУБД Postge.

1. Что такое сложность алгоритма? Какова сложность алгоритма вычисления определителя матрицы nxn через миноры, если вычисляется он следующим образом: detA = СУММА((-1)^(1+j)*a1j*Mj) по j=1..n где Mj – дополнительный минор к j-ому элементу (т.е. определитель матрицы (n-1)x(n-1))?

Нужно определиться какую сложность считаем. Временную или емкостну. А так же определиться с каких единицах его считаем (т.е. Что будет считать за одну единицу сложности). Судя оп всему имеется ввиду сложность алгоритма по количеству операций сложения и умножения. Эта сложность равна O(n!).  Так каждый минор Mj вычисляется как определитель матрицы, у которой удалена  j  – ая строка (столбец, в зависимости оттого как считается минор).  Таким образом, получается сумма из n detMj . Для вычисления каждого Mj потребуется выполнить n-1 следующего порядка. Продолжая уменьшать размерность миноров придем к матрице размером 1х1, определитель которого вычисляется за одну единицу времени. Там образом суммарно O(n!) операций и сложения.

2. Существуют внутренние и внешние алгоритмы сортировки и поиска данных. Внутренние – в оперативной памяти, внешние – на внешних носителях. Какие на ваш взгляд требования должны предъявляться к тем и другим алгоритмам?

Внутренний

http://ru.wikipedia.org/wiki/%D0%92%D0%BD%D1%83%D1%82%D1%80%D0%B5%D0%BD%D0%BD%D1%8F%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0

Требования:

  1. Простота реализации
  2. Обеспечение требуемой скорости при заранее известном числе элементов в сортируемом массиве.
  3. Быстрый (и всегда за одно и тоже время ) доступ к любому элементу массива.

Внешние

http://ru.wikipedia.org/wiki/%D0%92%D0%BD%D0%B5%D1%88%D0%BD%D1%8F%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0

Требования

  1. Длительное и не всегда одинаковое обращение по времени к каждому элементу массива.
  2. Поскольку весь массив разбивается на отрезки к которым будет применяться внутренняя сортировка. То весь массив будет раз бит на части, чем больше длина отдельных частей, тем быстрее будет он выполнен.
  3. Выбор алгоритма определяется параметрами «внешнего устройства», так на различных устройствах в различных их конфигурациях и операционных системах будет реализована различная скорость доступа к данным.

3. Какие операции позволяет ускорить B-tree индекс? Какие не позволяет? Почему?

http://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

B-дерево (по-русски произносится как Б-дерево)— структура данных, дерево поиска. С точки зрения внешнего логического представления, сбалансированное, сильно ветвистое дерево во внешней памяти.

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

Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков.

Основной недостаток В-деревьев состоит в отсутствии для них эффективных средств выборки данных (т.е. метода обхода дерева), упорядоченных по отличному от выбранного ключу.

Т.е. операции выборки, в которых не задействован ключ.

4. Что такое R-tree индекс, для чего используется?

http://ru.wikipedia.org/wiki/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

R-дерево (англ.R-trees)— древовидная структура данных (дерево), предложенная в 1984 году Антонином Гуттманом. Оно подобно B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами (широтой и долготой). Типичным запросом с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения».

5. Что такое hash join, merge join, nested loop join?

hash join http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_%D1%85%D1%8D%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC

Алгоритм соединения хэшированием (hash join) разновидность алгоритма соединения.

Алгоритм получает на вход 2 таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.

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

merge join

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D0%BE%D0%B2

Алгоритм соединения слиянием сортированных списков (merge join, sort merge join, sort-merge join) — разновидность алгоритма соединения.

Алгоритм получает на вход 2 таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.

Входные таблицы должны быть отсортированы по столбцам, участвующим в условии соединения. Соединение осуществляется за одно сканирование (проход по) каждой из входных таблиц. То есть одна и та же строка считывается только один раз, что даёт преимущество перед соединением вложенными циклами.

nested loop join

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B2%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%BC%D0%B8_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0%D0%BC%D0%B8

6. Какие преимущества есть у применения последовательностей по сравнению с автоинкрементными полями?

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

7. Опишите механизм появления взаимной блокировки для двух процессов.

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

http://ru.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D0%B8%D0%BC%D0%BD%D0%B0%D1%8F_%D0%B1%D0%BB%D0%BE%D0%BA%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0

8. Предположим что есть таблица с полем date_create типа date (только дата). В таблице есть индекс по этому полю. Будет ли он использоваться в запросе с условием WHERE date_create>=’2010-09-18 12:10:11′ ? Если нет, то что нужно сделать чтобы использовался?

Индекс использоваться не будет, так как в условии тип данных, дата время. Для того тчо бы он использовался необходимо использовать условие вида date_create>’2010-09-18′ или date_create>=’2010-09-19′

9. Предположим есть две таблицы, tbl_countries и tbl_cities. В каждой есть числовое поле id и первичный ключ по нему. В таблице tbl_cities есть поле country_id, которое связано с id из таблицы tbl_countries отношением многие к одному. Напишите своими словами наиболее типичный план который мог бы быть для запроса SELECT * FROM tbl_cities ct JOIN tbl_countries co ON co.id=ct.country_id WHERE ct.id>100 and ct.id<200;

Будет происходить Full join , а следовательно будет  построено декартово произведение двух таблиц по условию co.id=ct.country_id, после чего будут отобраны записи удовлетворяющие условию WHERE ct.id>100 and ct.id<200;

10. Для схемы из предыдущего вопроса. Пусть есть запрос – SELECT * FROM tbl_countries WHERE id<=100 ORDER by name LIMIT 50, с каким максимальным объемом записей придется работать БД во время выполнения запроса, если считать что всего стран в таблице 200, и все идентификаторы для них идут последовательно от 1 до 200?

С 200 так как для отбора всех записей id<=100 потребуется перебрать все 200 а потом из 100 удовлетворяющих условию не обходимо выбрать 50.

Share

Tags: , ,

2 Responses to “Тестовое задание Postgre-SQL программист от компании LightSoft”

  1. Иван пишет:

    Интересная статья. Спасибо за инфу.

  2. Рад что вам пригодилась информация

Leave a Reply