Разбор заданий по аналитике или как Яндекс отнял почти 6 часов моей жизни / Хабр

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

Боже, как я ошибался.

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

Штош, не будем тянуть комп за шнур питания, погнали!

A - Последовательность штаммов

Грант - это хорошо, особенно если он большой (да, иногда размер всё-таки имеет значение). Так что не будем подводить лабораторию и приступим к решению.

Первоначальная идея алгоритма заключалась методе скользящего окна - проходе "окном" фиксированного размера по всем срезам массива с подсчетом штаммов в каждом срезе. Это была далеко не самая эффективная реализация решения из возможных, о чем мне и сказал красненький маркер TL (Time Limit) при тестировании алгоритма на платформе. Немного подумав (ну, минут 20), я хлопнул себя по лбу, поняв, насколько Йа криве́дко и сменил стратегию - теперь фиксируется именно элемент отсчета, а окно растягивается, пока количество уникальных элементов в нём не превышает порогового значения.

import sys
from collections import defaultdict, deque

N, K = map(int, sys.stdin.readline().split())

cnt = defaultdict(int)
window = deque()
distinct = 0
best = 0
read = 0  

for line in sys.stdin:
    for token in line.split():
        if read >= N:
            break

        x = int(token)
        read += 1

        window.append(x)
        if cnt[x] == 0:
            distinct += 1
            
        cnt[x] += 1

        while distinct > K:
            y = window.popleft()
            cnt[y] -= 1
            
            if cnt[y] == 0:
                distinct -= 1

        if len(window) > best:
            best = len(window)
            
    if read >= N:
        break

print(best)

Код проходит по всем числам последовательно (расширяет окно справа).
При добавлении нового числа x:
- Оно добавляется в window.
- Обновляется счетчик cnt[x].
- Если число встретилось в окне впервые (cnt[x] == 0 до увеличения), увеличивается счетчик уникальных элементов distinct.
Проверка условия: Если количество уникальных элементов distinct становится больше K:
- Окно начинает сужаться слева (popleft()).
- Удаляемые числа удаляются из счетчика cnt.
- Если счетчик числа становится 0, значит, это уникальное число полностью исчезло из окна, и distinct уменьшается.
- Это продолжается до тех пор, пока distinct не станет ≤K≤K.
После каждого шага проверяется, не стала ли текущая длина окна (len(window)) больше ранее зафиксированного максимума (best).

Получаем заветный зеленый OK и идем дальше.

B - Префиксы и суффиксы

Самое короткое по описанию, но самое времязатратное из всех заданий этого теста (по крайней мере лично для меня). Изначальная идея заключалась в том, что если наш массив A является суммой монотонно невозрастающего массива B и монотонно неубывающего массива C, то для каждого элемента А (кроме крайних) должно выполняться условие: сумма его соседей не меньше него самого.
Проблема появилась быстро - из 160 тестов данный подход осилил дай бог половину. Почему? Потому что, например, массив

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

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

def can_achieve(target):
    n = len(target)
    
    if n <= 1:
        return True
      
    g = [0] * n
    
    for i in range(1, n):
        g[i] = g[i - 1] + max(0, target[i] - target[i - 1])
        
    return all(g[i] <= target[i] for i in range(n))


N = int(input())
arr = list(map(int, input().split()))

if can_achieve(arr):
    print('YES')
    
else:
    print('NO')

Массив достижим тогда и только тогда, когда его можно представить в виде суммы двух последовательностей: нестрого убывающей (префиксные операции) и нестрого возрастающей (суффиксные). Эквивалентно: g[i] = сумма приростов (max(0, target[j]-target[j-1])) для j=1..i должна удовлетворять g[i] <= target[i] для всех i.
Звучит просто, но пока до меня дошло, прошел целый час. Ну, как минимум, до меня всё-таки дошло, что уже, в принципе, неплохо. Лутаем зеленую галочку и идем дальше.

C - Китайские фейерверки

Тут даже программировать не надо, надо лишь знать формулу условной вероятности:

$P(A∣B)=\frac{P(A∩B)}{P(B)}$

Событие А - успешный взрыв всех фейерверков, событие В - успешный взрыв первого случайно выбранного фейерверка. Так как B вложено в А, то:

$P(A∩B) = P(А) =0.9\cdot0.8\cdot0.6=0.432$ $P(B)=\frac{0.9}{3}+\frac{0.8}{3}+\frac{0.6}{3}=\frac{2.3}{3}$

Делим первое на второе, получаем 0.563478... Округляем до трех, записываем, радуемся галочке и идем дальше.

D - Автоматы с шоколадками

Пожалуй, самое конченое задание. Почему? Ведь казалось бы, тратим сначала N денег на выяснение ��ероятности выпадения шоколадок для каждого автомата, выбираем самый лояльный и позволяем Валере зарабатывать его заслуженный диабет. НО! Есть одно но.

Вместо фиксированной последовательности значений каждый запуск случайный, и даже один и тот же код на разных запусках проходит (или не проходит) разные тесты. И с одной стороны это круто, так как лучше отражает непредсказуемую реальность, но с другой - тест превращается в лютый рандом, проверяющий вашу удачу, а не знания.

wendings = {
    0: [0,0],
    1: [0,0],
    2: [0,0],
    3: [0,0],
    4: [0,0],
    5: [0,0],
    6: [0,0],
    7: [0,0],
    8: [0,0],
    9: [0,0]
    }

test_tries_per_wend = 8

for key in wendings.keys():
    
    for i in range(test_tries_per_wend):
        print(key)
        res = int(input())
        wendings[key][res] += 1

best_idx, best_rate = None, -1.0
second_idx, second_rate = None, -1.0

for key in wendings.keys():
    rate = wendings[key][1] / test_tries_per_wend
    
    if rate > best_rate:
        second_idx, second_rate = best_idx, best_rate
        best_idx, best_rate = key, rate
        
    elif rate > second_rate:
        second_idx, second_rate = key, rate

if second_idx is None:
    second_idx = 0

wend_first, wend_sec = best_idx, second_idx

for i in range(200 - 10 * test_tries_per_wend):
    print(wend_first)
    res = int(input())

Например, этот код сработал только с третьей попытки. Ну, как бы там не было, зелёненький "ОК" в кармане.

F - Сканворды Афанасия

Не самая сложная задача, которая у меня не работала корректно целый час. Я изнасиловал мозг себе, gpt, qwen, cursor и уже собрался подобраться к забившемуся в угол deepseek, когда заметил, что я неправильно округлял. Вместо стандартной функции округления я решил выпендриться и дополнительно добавил форматированный вывод print(f{result:.2f}), который некорректно отображал вещественные числа. Убрав форматирование, всё заработало.

from collections import defaultdict

first = input().strip()
N, M = map(int, first.split())

Solution = [list(map(int, input().split())) for _ in range(N)]
Original = [list(map(int, input().split())) for _ in range(N)]

cnt_sol = defaultdict(int)
cnt_orig = defaultdict(int)
inter = defaultdict(int)

for i in range(N):
    for j in range(M):
        s = Solution[i][j]
        o = Original[i][j]

        if s != 0:
            cnt_sol[s] += 1
            
        if o != 0:
            cnt_orig[o] += 1
            
        if s != 0 and s == o:
            inter[s] += 1

colors = [c for c in cnt_orig if c != 0]

if not colors:
    result = 0.0
    
else:
    total = 0.0
    
    for c in colors:
        num = inter[c]
        denom = cnt_orig[c] + cnt_sol[c] - inter[c]
        total += num / denom if denom > 0 else 0.0
        
    result = round(total / len(colors), 2)

print(result)

По алгоритму особо ничего сказать не могу, просто тупо следую ТЗ - для каждого цвета (кроме нуля) считаю, сколько раз он встречается в обоих массивах (если у обоих массивов один цвет при одинаковых индексах, такие считаю только один раз) складываю, делю. Формула:

$W = \frac{\sum_{i=1}^n \frac{A_i}{C_i}}{COL_{cnt}}$

Где W - наша оценка, A_i - количество пересечений цвета i, С_i - общее количество клеток цвета i в обеих матрицах (пересечения считаются только 1 раз), COL_cnt - общее количество цветов.

А где пункт E?

Самые внимательные из вас уже, наверно, заметили, что я пропустил один пункт. И, если честно, мне бы очень хотелось, чтобы вы смогли ответить на несколько вопросов, которые он у меня вызвал.

Но прежде всего к условиям:

И вроде бы тоже ничего сложного - оставляем в таблице только строки с городом А, делим её на две - с датой 2 августа и со всеми остальными, анализируем ежедневный трафик для каждого из сайтов, и если в эту дату он сильно просел - скорее всего, это легальный сайт. Если нет - сайт пользуется ботами для накрутки результатов. Логика проста, реализация тоже не должна была вызвать затруднений.

Но, перечитав условия несколько раз, я серьёзно засомневался в собственной адекватности.

Нам известно, что таблица называется logs. Но какого она формата? CSV? Паркет? База данных SQL? Что это? Как это читать? Я перепробовал несколько вариантов (каюсь, мне было впадлу писать код, я использовал cursor), но ничего не вышло.

Заключение

В целом, было достаточно интересно и, а в некоторых моментах и мозгодробительно, но я остался доволен. Теперь буду ждать, что ответит мне яндекс. А вы пожелайте удачи, если не сложно ;-)