Телефонное интервью с Facebook 2014.07.21, 1-й вопрос
Телефонное интервью с Facebook 07/21/2014:
Задача 1
1) Найти количество повторений определенного числа в отсортированном массиве
Мое решение 1:
Бинарным поиском найти одно из чисел, затем пройти по массиву влево и вправо и выяснить, сколько таких элементов существует. Time complexity в худшем случае O(N), в среднем O(log N).
https://gist.github.com/codekrolik/b631aeefc8cde0208b46
Мое решение (2): Бинарным поиском найти число, затем рекурсивно найти левую и правую границу также бинарным поиском на подмассивах. На интервью реализовано не было, словесно описан алгоритм.
Time complexity в худшем случае O(log^2 N).
https://gist.github.com/codekrolik/fbd99a7099c00f9d9edc
Тесты для обоих решений: