💻 Coding interviews in a nutshell

Forwarded from Ivan Finaev

Навеяно дебагом бинпоиска в сегодняшнем видео. Мне кажется, когда его пишешь, нужно на бумажке прописать инварианты:
* что такой успех?
* как этот успех связан с левыми и правыми границами в начале, до запуска цикла
* как условие на левую и правую границу сохраняется во время цикла

Кроме инвариантов ещё нужно вручную проверить поведение алгоритма, когда между левой и правой границей мало элементов — меньше трех четырех. После каждой итерации расстояние между итерациями должно уменьшаться. Я, чтобы быть уверенным, что это так, начиная с отрезка длиной четыре элемента и меньше, проверяю ветвления вручную, на бумажке.

В итоге у меня таким получилось решение этой задачи на плюсах (не претендую на скорость, я больше беспокоился о том, чтобы все прошло без ошибок с минимальным количеством тестовых запусков). Стрессы тесты не писал, но решение на литкоде проходит
https://gist.github.com/IvanFin/4578b9a4e8be6be0adcedac67696e39b

👍4👎2👏1

www.tgoop.com/coding_interviews/198

3.58K viewsJun 23, 2022 at 17:56

Навеяно дебагом бинпоиска в сегодняшнем видео. Мне кажется, когда его пишешь, нужно на бумажке прописать инварианты:
* что такой успех?
* как этот успех связан с левыми и правыми границами в начале, до запуска цикла
* как условие на левую и правую границу сохраняется во время цикла

Кроме инвариантов ещё нужно вручную проверить поведение алгоритма, когда между левой и правой границей мало элементов — меньше трех четырех. После каждой итерации расстояние между итерациями должно уменьшаться. Я, чтобы быть уверенным, что это так, начиная с отрезка длиной четыре элемента и меньше, проверяю ветвления вручную, на бумажке.

В итоге у меня таким получилось решение этой задачи на плюсах (не претендую на скорость, я больше беспокоился о том, чтобы все прошло без ошибок с минимальным количеством тестовых запусков). Стрессы тесты не писал, но решение на литкоде проходит
https://gist.github.com/IvanFin/4578b9a4e8be6be0adcedac67696e39b

BY 💻 Coding interviews in a nutshell