Добрый вечер, у меня есть такая задача:
Вам дана стопка посадочных карточек на различные виды транспорта, которые доставят вас из точки A в точку B. Карточки перепутаны, и вы не знаете,где начинается и где заканчивается ваше путешествие. Каждая карточка содержит информацию о том, откуда и куда вы едете на данном отрезке маршрута, а также о типе транспорта (номер рейса, номер места и прочее). Предоставьте JavaScript API, который отсортирует такой список карточек и вернет словесное описание, как проделать ваше путешествие. API должен принимать на вход несортированный список карточек в формате придуманном вами и возвращать, например, такое описание: (a) Take train 78A from Madrid to Barcelona. Seat 45B. (b) Take the airport bus from Barcelona to Gerona Airport. No seat assignment. (c) From Gerona Airport, take flight SK455 to Stockholm. Gate 45B. Seat 3A. Baggage drop at ticket counter 344. (d) From Stockholm, take flight SK22 to New York JFK. Gate 22. Seat 7B. Baggage will be automatically transferred from your last leg.
Сам до конца не представляю ситуацию в задаче. Объясните пожалуйста этапы решения данной задачи. Я не прошу написать за меня код, а просто объяснить, что и зачем нужно делать.
Буду очень благодарен.
Самое главное при постановке задачи это ограничения, которых в постановке нету.
Если представить города вершинами, а билеты ребрами, то какой путь найти нужно кратчайший/длиннейший/гамильтонов/эйлеров (все ли ребра задействовать)?
Дан ориентированный граф, который представляет из себя один единственный путь. Требуется вывести ребра в порядке их появления на этом пути.
С собеседования в какую фирму задача?
Летняя стажировка в яндексе
Хорошо хоть Вы частично признались. Нужно было еще уточнить, что это тестовое задание стажеров-разработчиков интерфейса Яндекс-карт.
Судя по всему, у вас не олимпиадная задача, а практическая. К тому же вы не указали ограничения. Исходя из этого, предполагаю, вам важнее не самый-самый эффективный алгоритм, а читабельность кода.
Если у вас маршрут однозначный, без разветвлений, то есть от каждого промежуточного пункта есть ровно один путь в строго определенный следующий пункт, то есть формально у вас изначально был путь 1 -> 2 -> 3 -> 4 -> 5, но вы получили на вход пары (2 -> 3), (1 -> 2), (4 -> 5), (3 -> 4), то задача вообще элементарная, не требующая никаких специальных алгоритмов (если у вас небольшие ограничения). Я думаю, вы сами вполне можете придумать здесь решение, хотя бы просто два вложенных цикла.
Если маршрут неоднозначный, требующий оптимизации (например, найти кратчайший путь) — примените теорию графов. Считайте каждый пункт за вершину, а карточку между двумя пунктами — за ребро между этими вершинами. И после построения графа используйте алгоритм Дейкстры для нахождения кратчайшего пути.
Ну а пример словесного вывода, который вы привели — это и вовсе к алгоритмической части не относится. Либо используете switch case (в зависимости от типа карточки выводить нужное словесное описание), либо методами ООП (переопределение методов в классах-наследниках, полиморфизм), если вас интересует читабельность.
А может быть так, что входные данные не верны, и граф получиться более, чем из одной компоненты связнойстей?
В задаче не написано об этом ничего.
Ну, если даже в задаче об этом не написано, то нам здесь тем более это неизвестно :)
Теоретически, конечно может быть. По уму, вам надо уточнить строгий формат входных данных, а также какого вида граф допускается на входе, и как программа должна обрабатывать каждый случай, иначе это будет гадание на кофейной гуще.
К тому же, наличие нескольких компонент связности не мешает алгоритму Дейкстры, вы ведь ищете конкретно путь из А в Б.
На всякий случай приведу ссылку на алгоритм подсчета кол-ва компонент.