Как найти два элемента с максимальным количеством общих связей?

Question

[square]

Всем привет, на интервью попалась задачка, есть три таблицы: teacher(id, name), student (id, name) и teacher_student (teacher_id, student_id). Причем, без составного индекса на таблице связей, т.е. у любого учителя может быть любой набор учеников и наоборот.

Нужно вывести двух учителей имеющих максимальное кол-во общих студентов. Весь мозг поломал, со всеми задачами смог справится, а на этой вот случился затуп и никак. Подскажите в какую сторону копать? А-то мне уже кажется, что это невозможно)

Answer 1

[Rsa97]

SELECT `t1`.`name`, `t2`.`name`, COUNT(*) AS `count`
  FROM `teacher` AS `t1`
  JOIN (
    SELECT DISTINCT `teacher_id`, `student_id`
      FROM `teacher_student` 
  ) AS `s1` ON `s`.`teacher_id` = `t1`.`id`
  JOIN (
    SELECT DISTINCT `teacher_id`, `student_id`
      FROM `teacher_student` 
  ) AS `s2` ON `s2`.`student_id` = `s1`.`student_id` AND `s2`.`teacher_id` > `s1`.`teacher_id`
  JOIN `teacher` AS `t2` ON `t2`.`id` = `s2`.`teacher_id`
  GROUP BY `t1`.`id`, `t2`.`id`
  ORDER BY `count`
  LIMIT 1

Comments

[square]

забыли DESC, а в целом вроде работает, сейчас постараюсь вникнуть в идею

Answer 2

[Cage]

как то так
SELECT t.*, count( ts.teacher_id) as c
FROM teacher t
INNER JOIN teacher_student ts ON t.id= ts.teacher_id
GROUP BY t.id
ORDER BY c DESC
LIMIT 2

Comments

[square]

Нет, так не работает, да ещё и каждый раз выдает новый ответ

[square]

count( td,teacher_id) это count(ts.teacher_id)?

[Cage]

square: Да, ошибочка затесалась, исправил

[Андрей]

square, то что ошибка тут - это да, но даже если бы ошибки не было бы, то всё равно может выдавать каждый раз разный результат. Например есть 5 учителей, у которых 20 общих учеников, а показать надо 2. база может каждый раз выдавать только 2-ух из 5-ти.

Answer 3

[Андрей]

Если я правильно понял весь прикол в
максимальное кол-во общих студентов
то:
select ts1.teacher_id,ts2.teacher_id, count(ts1.student_id) as cnt
from teacher_student ts1
left join teacher_student ts2
on ts1.teacher_id<>ts2.teacher_id and ts1.student_id=ts2.student_id
group by ts1.teacher_id,ts2.teacher_id
order by cnt
limit 2