1) Посмотрел условия пары задач, которых не узнал по названию. Как по мне в видосе они довольно неточно описываются. 2) Увидел код на Line reflection. map добавляет лишний логарифм на асимптотику, можно ведь хэш таблицей (либо вложенной, либо определить hash::operator()(...)). И на double переменную (которую потом обратно на 2 умножают) на собесе бы поругали. 3) "Найти два одинаковых поддерева" - помню, мне давали её, я сам себе придумал забавный фолоуап: решить за O(n*log(n)) (n - размер дерева), если в вершинах не буквы, а инты.
Привет! 1) Условия задач взяты ровно из базы задач Яндекса, на собеседовании можно и нужно задать уточняющие вопросы, чтобы получить бОльшую определенность 2) Да, действительно map добавляет лишний логарифм в асимптотику, но в pdf файле я точно об этом упомянул, в видео мне было просто удобно использовать map. Конечно, можно просто переопределить хэш-функцию 3) С double переменной согласен, сделал для бОльшей определенности, чтобы точно код был понятен, можно вообще удвоить все координаты и с ними работать) Но действительно, наверное, стоит все это проговаривать прямо в видео, и не только в текстовых разборах Спасибо за замечания, буду стараться улучшать контент!
Кстати, в комментариях предложили усложненную версию задачи про деревья. Версию, где вместо символов в вершинах стоят произвольные вершины. Решение за O(nlogn): Давайте поддерживать множество чисел поддерева вершины с помощью std::unordered_set. Теперь, для каждой вершины нам нужно научиться быстро объединять два множества ее детей и быстро считать хеш-функцию от этого множества (чтобы потом можно было сравнивать несколько вершин). Объединять два множества можно с помощью техники small to large (usaco.guide/plat/merging?lang=cpp), и при добавлении в большое множество числа, которого в нем еще не было, просто обновим хеш-функцию этого большого множества. Итого, получаем асимптотику O(nlogn). Хешировать можно например, пользуясь идеей XOR-hashing (codeforces.com/blog/entry/85900)
Таймкоды: 00:00 - Intro 01:20 - Найти k ближайших элементов 06:34 - Максимальный подмассив из единиц 12:57 - Найти два одинаковых поддерева 26:04 - Сложение ступенчатых графиков 32:36 - Существует ли разделяющая прямая? Line Reflection 48:14 - Посетители гостиницы 1:10:30 - Подотрезок с суммой k 1:21:50 - Поиск подстроки в строке без учета порядка букв. Find First Anagram 1:38:21 - Проверка строк на исправление 1:44:48 - Оптимизация маршрута 2 1:53:58 - Заключение
1) Посмотрел условия пары задач, которых не узнал по названию. Как по мне в видосе они довольно неточно описываются.
2) Увидел код на Line reflection. map добавляет лишний логарифм на асимптотику, можно ведь хэш таблицей (либо вложенной, либо определить hash::operator()(...)). И на double переменную (которую потом обратно на 2 умножают) на собесе бы поругали.
3) "Найти два одинаковых поддерева" - помню, мне давали её, я сам себе придумал забавный фолоуап: решить за O(n*log(n)) (n - размер дерева), если в вершинах не буквы, а инты.
Привет!
1) Условия задач взяты ровно из базы задач Яндекса, на собеседовании можно и нужно задать уточняющие вопросы, чтобы получить бОльшую определенность
2) Да, действительно map добавляет лишний логарифм в асимптотику, но в pdf файле я точно об этом упомянул, в видео мне было просто удобно использовать map. Конечно, можно просто переопределить хэш-функцию
3) С double переменной согласен, сделал для бОльшей определенности, чтобы точно код был понятен, можно вообще удвоить все координаты и с ними работать)
Но действительно, наверное, стоит все это проговаривать прямо в видео, и не только в текстовых разборах
Спасибо за замечания, буду стараться улучшать контент!
Кстати, в комментариях предложили усложненную версию задачи про деревья. Версию, где вместо символов в вершинах стоят произвольные вершины.
Решение за O(nlogn): Давайте поддерживать множество чисел поддерева вершины с помощью std::unordered_set. Теперь, для каждой вершины нам нужно научиться быстро объединять два множества ее детей и быстро считать хеш-функцию от этого множества (чтобы потом можно было сравнивать несколько вершин). Объединять два множества можно с помощью техники small to large (usaco.guide/plat/merging?lang=cpp), и при добавлении в большое множество числа, которого в нем еще не было, просто обновим хеш-функцию этого большого множества. Итого, получаем асимптотику O(nlogn).
Хешировать можно например, пользуясь идеей XOR-hashing (codeforces.com/blog/entry/85900)
Таймкоды:
00:00 - Intro
01:20 - Найти k ближайших элементов
06:34 - Максимальный подмассив из единиц
12:57 - Найти два одинаковых поддерева
26:04 - Сложение ступенчатых графиков
32:36 - Существует ли разделяющая прямая? Line Reflection
48:14 - Посетители гостиницы
1:10:30 - Подотрезок с суммой k
1:21:50 - Поиск подстроки в строке без учета порядка букв. Find First Anagram
1:38:21 - Проверка строк на исправление
1:44:48 - Оптимизация маршрута 2
1:53:58 - Заключение