**Задание по мотивам реального тестового в Сбере (расширенная версия).**
**Данные:** Таблица клиентов с множественными контактами:
[см. код в задании]
Два клиента — одно лицо, если пересекаются телефоны ИЛИ email. Транзитивно.
**Задание:**
1. Разверните множественные контакты в пары (client_id, contact_value)
2. Постройте граф и найдите связные компоненты через BFS
3. Для каждой группы: «мастер-запись» (самый старый client_id) + все контакты
4. Оцените качество: сколько записей дедуплицировано, средний размер группы
5. Масштабируемость: как обработать 10М записей?
Структура для ориентира — реальные значения из эталонного решения.
import pandas as pd
import numpy as np
from collections import defaultdict, deque
# --- Данные ---
data = [
{'client_id': 'C001', 'phones': '+79001234567, +79009876543', 'emails': 'ivan@mail.ru'},
{'client_id': 'C002', 'phones': '+79009876543', 'emails': 'ivan@mail.ru, ivan@gmail.com'},
{'client_id': 'C003', 'phones': '+79112223344', 'emails': 'ivan@gmail.com'},
{'client_id': 'C004', 'phones': '+79555666777', 'emails': 'anna@ya.ru'},
{'client_id': 'C005', 'phones': '+79555666777, +79888999000', 'emails': 'anna@ya.ru, anna@mail.ru'},
{'client_id': 'C006', 'phones': '+79888999000', 'emails': 'elena@inbox.ru'},
{'client_id': 'C007', 'phones': '+79333444555', 'emails': 'petr@ya.ru'},
]
df = pd.DataFrame(data)
print(f"Исходных записей: {len(df)}")
# --- 1. Развернуть множественные контакты ---
edges = [] # (client_id, contact_value)
for _, row in df.iterrows():
cid = row['client_id']
for phone in str(row['phones']).split(','):
phone = phone.strip()
if phone:
edges.append((cid, f'phone:{phone}'))
for email in str(row['emails']).split(','):
email = email.strip().lower()
if email:
edges.append((cid, f'email:{email}'))
print(f"Пар (client, contact): {len(edges)}")
# --- 2. Граф: contact → [clients] ---
contact_to_clients = defaultdict(set)
client_contacts = defaultdict(set)
for cid, contact in edges:
contact_to_clients[contact].add(cid)
client_contacts[cid].add(contact)
# Граф смежности: client → {related clients}
adj = defaultdict(set)
for contact, clients in contact_to_clients.items():
clients_list = list(clients)
for i in range(len(clients_list)):
for j in range(i + 1, len(clients_list)):
adj[clients_list[i]].add(clients_list[j])
adj[clients_list[j]].add(clients_list[i])
# --- 3. BFS: связные компоненты ---
visited = set()
groups = []
for client in df['client_id']:
if client in visited:
continue
# BFS
queue = deque([client])
visited.add(client)
component = []
while queue:
node = queue.popleft()
component.append(node)
for neighbor in adj.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
groups.append(sorted(component))
# --- Результат ---
print(f"\n=== Результат дедупликации ===")
print(f"Групп (уникальных клиентов): {len(groups)}")
for i, group in enumerate(groups):
all_phones = set()
all_emails = set()
for cid in group:
for contact in client_contacts[cid]:
if contact.startswith('phone:'):
all_phones.add(contact.replace('phone:', ''))
else:
all_emails.add(contact.replace('email:', ''))
master = group[0] # самый ранний ID
print(f"\nГруппа {i+1} (мастер: {master}):")
print(f" Записи: {group}")
print(f" Телефоны: {all_phones}")
print(f" Email: {all_emails}")
# --- 4. Метрики качества ---
sizes = [len(g) for g in groups]
dedup_count = len(df) - len(groups)
print(f"\n=== Качество дедупликации ===")
print(f"Записей до: {len(df)}")
print(f"Записей после: {len(groups)}")
print(f"Дедуплицировано: {dedup_count} ({dedup_count/len(df)*100:.0f}%)")
print(f"Средний размер группы: {np.mean(sizes):.1f}")
print(f"Макс группа: {max(sizes)} записей")
# --- 5. Масштабируемость ---
print(f"\n=== Масштабируемость (10M записей) ===")
print("""
Подход 1: Spark GraphFrames
- Загрузить edges (client_id, contact) в Spark DataFrame
- GraphFrame.connectedComponents() — distributed BFS
- Масштабируется горизонтально
Подход 2: Итеративный Union-Find с партиционированием
- Partition по hash(contact) % N_partitions
- Union-Find внутри каждой партиции → локальные группы
- Merge: связать группы из разных партиций через общие client_id
- 2-3 итерации до сходимости
Подход 3: MapReduce (классический)
- Map: (contact, client_id) pairs
- Reduce: для каждого contact → union всех client_id
- Итеративно до стабилизации
Рекомендация: GraphFrames для Spark-инфраструктуры,
Union-Find для однонодового решения до ~50M записей.
""")python графы BFS pandas дедупликация Сбер
Это задание для уровня Senior. Senior-уровень — глубокое понимание темы, опыт решения нестандартных задач, обсуждение trade-off на собеседовании.
Подобные задания в категории «Python» регулярно дают на собеседованиях аналитика данных в Яндекс, Сбер, Ozon, Авито, Тинькофф, Wildberries, T-Bank, X5, ВТБ и других крупных IT-компаниях. Тематика: python, графы, BFS, pandas, дедупликация.
На реальном собеседовании на подобную задачу отводится 30-60 минут с обсуждением подходов, оптимизаций и trade-off. Для тренировки рекомендуем сначала решить самостоятельно, потом сверить с эталонным решением и подсказками.
На zasqlpython.ru есть 482 Python задачи с проверкой через Pyodide, конспекты Python и pandas, AI мок-собеседование с разбором ваших ответов.
← Все задания