---
title: "Телефонное интервью с Facebook 2014.07.21, 1-й вопрос"
description: "Телефонное интервью с Facebook 07/21/2014: Задача 1 1) Найти количество повторений определенного чис..."
author: "codekrolik"
published: "2014-07-23T02:16:29+00:00"
modified: "2014-07-24T00:32:07+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/telefonnoe-intervyu-s-facebook-2014-07-21-1-y-vopros-422354"
markdown_url: "https://yvision.kz/post/telefonnoe-intervyu-s-facebook-2014-07-21-1-y-vopros-422354/markdown"
site_name: "Yvision.kz"
---

# Телефонное интервью с Facebook 2014.07.21, 1-й вопрос

> Телефонное интервью с Facebook 07/21/2014: Задача 1 1) Найти количество повторений определенного чис...

Телефонное интервью с Facebook 07/21/2014:

Задача 1 1) Найти количество повторений определенного числа в отсортированном массиве

Мое решение 1: Бинарным поиском найти одно из чисел, затем пройти по массиву влево и вправо и выяснить, сколько таких элементов существует. Time complexity в худшем случае O(N), в среднем O(log N). [https://gist.github.com/codekrolik/b631aeefc8cde0208b46](https://gist.github.com/codekrolik/b631aeefc8cde0208b46)

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

Time complexity в худшем случае O(log^2 N).

[https://gist.github.com/codekrolik/fbd99a7099c00f9d9edc](https://gist.github.com/codekrolik/fbd99a7099c00f9d9edc)

Тесты для обоих решений:

[https://gist.github.com/codekrolik/19172393b3c6468c0a37](https://gist.github.com/codekrolik/19172393b3c6468c0a37)

---

Source: [https://yvision.kz/post/telefonnoe-intervyu-s-facebook-2014-07-21-1-y-vopros-422354](https://yvision.kz/post/telefonnoe-intervyu-s-facebook-2014-07-21-1-y-vopros-422354)