​​Вы не сможете сделать это тестовое задание… если не знакомы с теорией графов.

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

Если кратко, то задача звучит так: необходимо реализовать Android-приложение для конвертирования валют. Данные о курсах валют предоставляются в json-файле. Что может пойти не так? При этом тут стоит задуматься о нескольких моментах:

1) Когда есть несколько вариантов конвертации, лучше минимизировать количество конвертаций и сократить расходы. Вы можете представить, как работает обмен валют в реальном мире: чем больше промежуточных конвертаций вы делаете, тем больше денег теряете за каждую транзакцию. Например если известен курс USD -> GBP то лучше использовать его вместо USD -> EUR -> GBP
2) Если есть выбор, вы, вероятно, предпочтете более выгодные курсы вместо более дорогих, чтобы максимизировать прибыль.

И тут нам на помощь могут придти знания о графах. По сути, задача сводится к поиску оптимального пути конвертации: использование алгоритма для поиска оптимального пути конвертации между валютами с учетом обменных курсов и минимизации затрат.

📌 Моделирование задачи как графа
- Вершины графа представляют валюты.
- Рёбра графа представляют возможные конвертации между валютами. Вес ребра может быть равен комиссии или курсу конвертации (в зависимости от постановки задачи).

📌 Выбор алгоритма
Для поиска кратчайшего пути (минимального количества конвертаций) подходят следующие алгоритмы:

- Алгоритм Дейкстры — если учитываются веса рёбер (например, комиссии или курсы). Основным ограничением алгоритма является невозможность работы с отрицательными весами рёбер.
- Алгоритм поиска в ширину (BFS) — если веса рёбер не учитываются, а важно только количество конвертаций.
- Если есть отрицательные веса, можно использовать алгоритм Беллмана-Форда.

Ну а далее, уже в зависимости от конкретных деталей можно реализовать тот или иной алгоритм. Так что, в современных реалиях не достаточно знать особенности Android SDK или Kotlin, могут спросит как алгоритмы так и System Design, поэтому готовиться нужно тщательно. Как вам такое тестовое?