привет

#ЖИТЬ https://www.youtube.com/watch?v=X__GJAvZ4_M

Далее

Первое сентября Сегодня старший мой идет в первый класс.

Далее

Немного альтернативной истории — Да, победили, и что толку? — вздыхал Саня. — Столько крови пролили, в половине Европы социализм установили. Теперь нам никогда не войти в европейскую семью народов, мы не уважали их ценности. А знаешь, сколько немок изнасиловали наши солдаты, когда заняли Берлин? Миллион! Это же ужасно! Саня, либеральный сетевой журналист, отлично...

Далее

#котозависимость Та же проблема...

Далее

Креатив в Магнитогорске Как и раньше продолжаю замечать необычные вещи, когда гуляю по городу. Некоторые кеативные люди заставляют улыбаться. Лифт, на котором можно отправиться в "Ж". Магазин, в котором продается самая не свежая выпечка в городе.

Далее

Представление графа в виде реляционной БД.

Рубрика : Жизненное, Наш родной идиотизм, Разное

Недавно я вышла из отпуска по уходу за ребенком. Получилось так, что я попала на одно собеседование, на должность программиста. Заранее оформила резюме и отправила по почте. К моему удивлению, собеседование превратилось в университетский экзамен. Мне дали тест, потом 2 задачи, а, после разговора, еще одно задание. Хотелось еще сказать, что когда я пришла, человека, с которым была назначена встреча, почему-то не оказалось на месте. Собственно, про последнее задание я и хотела рассказать.

Задание: Представить нагруженный направленный граф в виде реляционной базы данных

Мое решение простое, и, как мне на тот момент показалось, самое очевидное. В ориентированном графе две сущности: вершины и ребра. Следовательно в нашей базе будет две таблицы, которые будут связанны между собой связями один-ко-много.

Честно говоря, когда мой собеседник предложил мне представить ориентированный граф в виде одной таблицы, которая будет содержать в себе матрицу инцидентности, я была немного удивлена. Его база-таблица должна была содержать в себе четыре поля: id — ключевое поле, номер начальной вершины, номер конечной вершины и вес ребра. Записать, конечно, все можно, и отправить в табличку, однако реляционной базой данных это не будет. Так как «Реляционная база данных — база данных, основанная на реляционной модели данных.» А реляционная модель данных в свою очередь включает несколько компонентов, в том числе и теорию  нормализации, о которой обязательно рассказывают всем в университете. Предложенный вариант ни коим образом не удовлетворяет даже первой нормальной форме. В предложенной базе (таблице) будет не атомарный атрибут — вершина графа, так как у вершины графа есть вес и характеристика (начальная или конечная). Я уж не буду говорить о том, что реализация алгоритмов удаления, добавления и изменения вершины достаточно проблематична.

Придя домой, я подтвердила свой вариант решения данной задачи несколькими источниками, с которыми вы можете ознакомится (1,2).

Данная задача очень проста для IT-специалиста со стажем. Очень жаль, что в наших IT-компаниях ведут собеседования такие «высококвалифицированные специалисты». Не удивительно, что мало хороших программных  продуктов пишется в России…

Комментарии: (1)

По 2ой ссылке описано иерархическое дерево подогнанное под реализацию графа. Рекомендованная вам таблица странна, зачем ключевое поле и тут же начала и конец? Может все же там были id вершины, id связной вершины, id след вершины, вес? Такая штука еще как удовлетворяет нормализации и уже тем более первой нормальной форме.

Прокомментировать