Вы собираетесь совершить долгое путешествие через множество населенных пунктов. Чтобы не запутаться, вы сделали карточки вашего путешествия. Каждая карточка содержит в себе пункт отправления и пункт назначения.
Гарантируется, что если упорядочить эти карточки так, чтобы для каждой карточки в упорядоченном списке пункт назначения на ней совпадал с пунктом отправления в следующей карточке в списке, получится один список карточек без циклов и пропусков. Например, у нас есть карточки
- Мельбурн > Кельн
- Москва > Париж
- Кельн > Москва
Если упорядочить их в соответствии с требованиями выше, то получится следующий список: Мельбурн > Кельн, Кельн > Москва, Москва > Париж
Требуется:
Написать функцию, которая принимает набор неупорядоченных карточек и возвращает набор упорядоченных карточек в соответствии с требованиями выше, то есть в возвращаемом из функции списке карточек для каждой карточки пункт назначения на ней должен совпадать с пунктом отправления на следующей карточке.
- Дать оценку сложности получившегося алгоритма сортировки
- Написать тесты
- Оценивается правильность работы, производительность и читабельность кода
- Сложность алгоритма получения головного узла O(N). Сложность алгоритма сборки цепочки O(N^2). Результирующая сложность полученного алгоритма сортировки O(N^2). Думаю, что можно снизить сложность, но "с ходу" не нашел, пробовал вставками, однако сложность алгоритма не снизилась.
- Входные данные (цепочка карточек) генерируются случайным образом из набора названий городов и перемешиваются. Проверки на пустое множество входного списка нет, так как программа в таком случае не имеет смысла, а данную проверку следует производить в коде на уровень выше, чтобы не допустить лишних вызовов.
- [Ссылка на код] (https://github.com/Ktvfylh/Test/blob/master/TestApp1.cs) - комментариев нет, в текущей компании политика не "засорять" код, добавлю если потребуется
Есть таблица хранящая покупки (линии чека): Sales: salesid, productid, datetime, customerid. Мы хотим понять, через какие продукты клиенты «попадают» к нам в магазин. Напишите запрос, который выводит продукт и количество случаев, когда он был первой покупкой клиента.
- Запрос реализован в одну строку с выборкой данных из списка. С использованием входных данных из таблицы SQL структура запроса сохранится.
- Данные для проверки решения как и в предыдущем примере случайно генерируемые, productid и customerid объявлены строковыми для наглядности, datetime сведена к разнице дней для просторы генерации списка.
- При желании, запрос можно быстро дописать для выборки не только количества первых покупок, но и кем они были произведены.
- [Ссылка на код] (https://github.com/Ktvfylh/Test/blob/master/TestApp2.cs) - комментариев нет, в текущей компании политика не "засорять" код, добавлю если потребуется