Поиск знаменитости

Поиск знаменитости в группе людей

Это классическая задача оптимизации, требующая минимизации вызовов функции knows(). Рассмотрим несколько подходов с разными временными и пространственными сложностями.

1. Наивный подход — O(n²) вызовов

def find_celebrity_naive(n: int, knows) -> int:
    """Наивный подход: проверяем каждого человека полностью."""
    for i in range(n):
        is_celebrity = True
        
        # Проверяем, что i никого не знает
        for j in range(n):
            if i != j and knows(i, j):
                is_celebrity = False
                break
        
        if not is_celebrity:
            continue
        
        # Проверяем, что все знают i
        for j in range(n):
            if i != j and not knows(j, i):
                is_celebrity = False
                break
        
        if is_celebrity:
            return i
    
    return -1  # Знаменитости нет

Анализ: Количество вызовов: O(n²) в худшем случае, Пространство: O(1), Проблема: очень неэффективно для больших n

2. Оптимальный подход — O(n) вызовов с двумя указателями

Это лучшее решение — минимизирует количество вызовов функции.

def find_celebrity_optimal(n: int, knows) -> int:
    """Оптимальный подход: O(n) вызовов knows()."""
    
    # Этап 1: Исключение кандидатов (O(n) вызовов)
    left, right = 0, n - 1
    
    while left < right:
        if knows(left, right):
            left += 1
        else:
            right -= 1
    
    candidate = left
    
    # Этап 2: Проверка кандидата (O(n) вызовов)
    for i in range(n):
        if i != candidate and knows(candidate, i):
            return -1
    
    for i in range(n):
        if i != candidate and not knows(i, candidate):
            return -1
    
    return candidate

Почему это работает? Если knows(a, b) == True: a знает b, значит a не может быть знаменитостью. Если knows(a, b) == False: b не может быть знаменитостью. На каждом шаге исключаем ровно одного человека за один вызов!

Анализ сложности: Этап 1: O(n-1) вызовов, Этап 2: O(n) вызовов, Всего: O(n) вызовов, Пространство: O(1)

3. Пример работы алгоритма

def example_knows(a: int, b: int) -> bool:
    """Знаменитость — person 2."""
    return (a, b) in [(0, 2), (1, 2)]

result = find_celebrity_optimal(3, example_knows)
print(f"Знаменитость: {result}")  # Выведет: 2

4. Улучшенная версия с обработкой ошибок

from typing import Callable, Optional

def find_celebrity(
    n: int,
    knows: Callable[[int, int], bool],
    use_cache: bool = True
) -> Optional[int]:
    """Поиск знаменитости с опциональным кэшированием."""
    
    if n <= 1:
        return 0 if n == 1 else -1
    
    cache = {} if use_cache else None
    
    def knows_cached(a: int, b: int) -> bool:
        if cache is not None:
            key = (a, b)
            if key not in cache:
                cache[key] = knows(a, b)
            return cache[key]
        return knows(a, b)
    
    left, right = 0, n - 1
    
    while left < right:
        if knows_cached(left, right):
            left += 1
        else:
            right -= 1
    
    candidate = left
    
    for i in range(n):
        if i != candidate:
            if knows_cached(candidate, i):
                return -1
            if not knows_cached(i, candidate):
                return -1
    
    return candidate

5. Граничные случаи и тестирование

import unittest
from typing import Dict, Callable

class TestFindCelebrity(unittest.TestCase):
    
    def _create_knows_func(self, graph: Dict[int, set]) -> Callable:
        def knows(a: int, b: int) -> bool:
            return b in graph.get(a, set())
        return knows
    
    def test_single_person(self):
        knows = self._create_knows_func({})
        result = find_celebrity(1, knows)
        self.assertEqual(result, 0)
    
    def test_no_celebrity(self):
        graph = {0: {1}, 1: {0}}
        knows = self._create_knows_func(graph)
        result = find_celebrity(2, knows)
        self.assertEqual(result, -1)
    
    def test_celebrity_exists(self):
        graph = {0: {2}, 1: {2}, 2: set()}
        knows = self._create_knows_func(graph)
        result = find_celebrity(3, knows)
        self.assertEqual(result, 2)

Вывод

Оптимальное решение использует метод двух указателей: минимально O(n) вызовов функции, O(1) памяти, ясная логика исключения кандидатов. Это решение часто задают на собеседованиях в крупных технологических компаниях.