Предварительная подготовка к выполнению задания¶

Что нужно знать для того что бы выполнить тестовое задания:¶

1. Понимать что такое REST-сервисы, знать принципы реализации данных сервисов.
2. Знать и уметь работать с фреймворком Spring, в частности знать что такое Spring MVC и способы реализации REST-сервисов при помощи Spring Framework (Spring Boot)
3. Знать и понимать принципы работы с реляционными БД (как минимум уметь работать с СУБД postgres).
4. Знать и понимать технологию ORM, в частности уметь работать с Hibernate.

Сама задача, как понял и какие могут быть дополнительные вопросы¶

1. Какой должен быть вид графа? C условием того что не должны быть циклические связи между узлами графа, возможно граф может быть деревом, (простым бинарным деревом). Так же есть вопрос, граф должен быть ориентированным или нет?
2. Помимо свойств узла, который описан в задачи, должны быть связи этих узлов. По тем же условиям задачи, в БД должно быть две таблицы, таблица №1 в которой хранятся узлы графа, таблица №2 связи вершин графа. Есть несколько вопросов:
   1. Во входных данных в формате JSON что должно быть описано? Как минимум должны быть перечислены просто все узлы, без связей (так как в условиях задачи не сказано что помимо перечисленных параметров, должен быть список соседних узлов, с кем контактирует текущий узел).
   2. В условиях сказано, что POST запрос setNodes должен отправить на сервер список узлов, отсюда вопрос - программа сама должны создавать граф с автоматическим созданием связей между узлами? Возможно да, так и должно быть. Значит возникает другой вопрос, как строить граф и устанавливать связи между узлами, на основании чего устанавливать связи? Ответ скорее всего будет такой - граф строится из уникальных имён узлов, возможно вариант такой, что уникальным именем будет числовой идентификатор, а значит можно строить граф так: в корне должен быть идентификатор с минимальным значением и далее по логике строительства бинарного графа.
   3. Что значит уникальное имя узла? Возможно это порядковый номер узла, который был занесён в БД и автоматически назначен номер, но с другой стороны возможно уникальное имя должно быть приходить из вне.
   4. Что значит вероятность отказа? Возможно это число, которое зависит от счётчика посещения узлов, рандомное значение. Как только количество посещения сравняется со значением вероятности отказа, запускается нужный механизм. Отсюда вопросы: счетчик после сбоя должен быть сброшен? Вероятность отказа узла должна быть сгенерирована заново? Возможно ответы на эти вопросы одинаковы, Да - счётчик посещений должен быть сброшен. Да - заново должен быть перезапуск вероятности отказа.
   5. С какой БД можно работать? Можно ли например использовать СУБД http://hsqldb.org/ ? Или нужно использовать например postgresql или oracle?

---

Вопросы №1:¶

1. Уникальное имя узла, получаем из входного набора данных или же оно генерируется при внесении в БД?
2. Установка графа из узлов. Мы web-сервису отправляем в формате json просто набор узлов, а сервис сам автоматически строит граф из полученных узлов? Или граф в формате json в качестве входных данных попадает в web-сервис, а задача сервиса состоит в том что проверить входной граф, исключить циклические связи и занести данные в БД? Граф должен быть ориентированным или не ориентированным? По условию задачи, в графе должны быть исключены циклические связи узлов, значит граф должен быть неполносвязным (предполагаю что речь идёт о двоичном дереве поиска).
3. "checkRoute принимает набор вершин (или их идентификаторов) в формате JSON", вопрос, откуда мы берём этот набор вершин? Данный вопрос напрямую связан с вопросом 1. Если мы автоматически генерируем уникальное имя узлов, то должно быть что-но на подобии showNodes, который возвращает набор узлов в формате json, в том виде, как он хранится в БД и от туда можно в выбрать узлы для проверки пути. Под идентификатором подразумевается уникальное имя узла или id которое генерируется в БД для каждого занесённого узла?
4. Путь в графе это путь между узлами, которые мы получили в качестве входных данных в формате json? Между узлами могут быть промежуточные узлы или подразумевается что путь должен состоять именно из тех узлов, которые были получены на вход?
5. Если в одном из входных узлов произошёл сбой и он недоступен? Что должно происходить дальше с этим узлом? Варианты:
   1. он остаётся в графе, но он в дальнейшем отмечается как нерабочий;
   2. он удалятся из графа автоматически;
   3. у него обнуляется счётчик и он снова в рабочем состоянии.
6. Можно ли при реализации тестового задания воспользоваться вот такой БД http://hsqldb.org/ или же надо из разряда postgresql или oracle?

Ответы¶

1. думаю, что лучше из входного набора, т.к. оно нужно для задания связей, хотя как удобнее.
2. граф в формате json в качестве входных данных попадает в web-сервис, а задача сервиса состоит в том что проверить входной граф, исключить циклические связи и занести данные в БД; неориентированный; любой.
3. либо show nodes, либо по базе смотреть и формировать запросы, явно делать show nodes никто не просит.
4. только из тех, что на вход поступили, в апи нет функции "добавить узел"
5. просто ничего не меняется и при следующем вызове он может отказать с такой же вероятностью.
6. можно.

---

Вопросы №2:¶

1. Если в одном из входных узлов произошёл сбой, то ничего не меняется. Т.е. счётчик у такой вершины не сбрасывается?
2. checkRoute. Ещё раз нужно прояснить.
   1. Под фразой “принимает набор вершин (или их идентификаторов) в формате JSON” подразумевается, то что набор вершин мы берём уже из БД (например через тот же showNodes, от туда просто копипастим нужные значения для проверки, ну или делаем выборку руками из БД, но тут надо так же руками сформировать данные в формате json), формируем запрос, вкладываем набор выбранных вершин в формате JSON и отправляем их сервису через вызов checkRoute, так?
   2. Фраза “Проход по вершина... Если путь существует в графе и ни один из узлов пути не отказал, следует увеличить счетчик в каждом из узлов пути.” Интересует конкретно что подразумевается под словом путь. Верно ли утверждение, которое описано на картинке с примером графа и выбранными вершинами?

Ответы¶

1. не сбрасывается
2. 2.1 да и 2.2 да, верно

Дополнительно:

Вопрос :

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

Ответ :

не любой граф можно в бинарное дерево преобразовать (например у вершины может быть 4 и более смежных вершин)

Вопрос :

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

Ответ:

да, правильно.