**Задание по мотивам реального тестового в Сбере.**
**Данные:** Записи клиентов в формате `key;id;phone;mail`:
[см. код в задании]
Два клиента считаются **одним лицом**, если у них совпадает хотя бы один телефон ИЛИ email. Транзитивность: если A связан с B, а B связан с C, то A, B, C — одно лицо.
**Задание:**
1. Реализуйте алгоритм поиска связных компонент (Union-Find или BFS/DFS)
2. Для каждой группы выведите все записи + объединённый набор телефонов и email
3. Оцените сложность алгоритма
4. Обработайте edge cases: пустые поля, дубли id
Структура для ориентира — реальные значения из эталонного решения.
from collections import defaultdict
# --- Данные ---
raw_data = """key;id;phone;mail
1;user1;+79001234567;user1@mail.ru
2;user2;+79007654321;user1@mail.ru
3;user3;+79001234567;user3@gmail.com
4;user4;+79119876543;user4@ya.ru
5;user5;+79119876543;user2@mail.ru
6;user2;+79007654321;user6@gmail.com"""
lines = raw_data.strip().split('\n')
header = lines[0].split(';')
records = []
for line in lines[1:]:
parts = line.split(';')
records.append({
'key': int(parts[0]),
'id': parts[1],
'phone': parts[2] if len(parts) > 2 else '',
'mail': parts[3] if len(parts) > 3 else '',
})
# =============================================
# Подход 1: Union-Find (Disjoint Set Union)
# =============================================
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
# Path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return
# Union by rank
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
def deduplicate_uf(records):
n = len(records)
uf = UnionFind(n)
# Индекс: значение → первый индекс записи с таким значением
phone_index = {}
mail_index = {}
for i, rec in enumerate(records):
phone = rec['phone'].strip()
mail = rec['mail'].strip().lower()
if phone:
if phone in phone_index:
uf.union(i, phone_index[phone])
else:
phone_index[phone] = i
if mail:
if mail in mail_index:
uf.union(i, mail_index[mail])
else:
mail_index[mail] = i
# Собираем группы
groups = defaultdict(list)
for i in range(n):
groups[uf.find(i)].append(i)
return groups
# =============================================
# Подход 2: BFS на графе (альтернатива)
# =============================================
def deduplicate_bfs(records):
from collections import deque
n = len(records)
# Строим граф: запись → список смежных записей
adj = defaultdict(set)
phone_map = defaultdict(list)
mail_map = defaultdict(list)
for i, rec in enumerate(records):
phone = rec['phone'].strip()
mail = rec['mail'].strip().lower()
if phone:
phone_map[phone].append(i)
if mail:
mail_map[mail].append(i)
# Рёбра: все записи с одинаковым phone/mail связаны
for indices in list(phone_map.values()) + list(mail_map.values()):
for j in range(1, len(indices)):
adj[indices[0]].add(indices[j])
adj[indices[j]].add(indices[0])
# BFS по компонентам
visited = set()
groups = {}
group_id = 0
for start in range(n):
if start in visited:
continue
queue = deque([start])
visited.add(start)
component = []
while queue:
node = queue.popleft()
component.append(node)
for neighbor in adj[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
groups[group_id] = component
group_id += 1
return groups
# --- Запуск ---
print("=== Union-Find ===")
uf_groups = deduplicate_uf(records)
for root, indices in sorted(uf_groups.items()):
phones = set()
mails = set()
ids = set()
for i in indices:
r = records[i]
ids.add(r['id'])
if r['phone']:
phones.add(r['phone'])
if r['mail']:
mails.add(r['mail'])
print(f"\nГруппа (записи: {[records[i]['key'] for i in indices]}):")
print(f" IDs: {ids}")
print(f" Телефоны: {phones}")
print(f" Email: {mails}")
print("\n=== BFS ===")
bfs_groups = deduplicate_bfs(records)
for gid, indices in sorted(bfs_groups.items()):
keys = [records[i]['key'] for i in indices]
print(f"Группа {gid}: записи {keys}")
# --- Сложность ---
print("\n=== Сложность ===")
print("Union-Find: O(N × α(N)) ≈ O(N) — почти линейная")
print(" α(N) — обратная функция Аккермана, < 5 для любых реальных N")
print("BFS: O(N + E), где E — число рёбер (общих phone/email)")
print(" Для плотных данных E может быть O(N²) → Union-Find лучше")python Union-Find графы дедупликация BFS Сбер
Это задание для уровня Senior. Senior-уровень — глубокое понимание темы, опыт решения нестандартных задач, обсуждение trade-off на собеседовании.
Подобные задания в категории «Python» регулярно дают на собеседованиях аналитика данных в Яндекс, Сбер, Ozon, Авито, Тинькофф, Wildberries, T-Bank, X5, ВТБ и других крупных IT-компаниях. Тематика: python, Union-Find, графы, дедупликация, BFS.
На реальном собеседовании на подобную задачу отводится 30-60 минут с обсуждением подходов, оптимизаций и trade-off. Для тренировки рекомендуем сначала решить самостоятельно, потом сверить с эталонным решением и подсказками.
На zasqlpython.ru есть 482 Python задачи с проверкой через Pyodide, конспекты Python и pandas, AI мок-собеседование с разбором ваших ответов.
← Все задания