Как стать программистом

Задачи с собеседований: Новостная лента

No votes yet.
Please wait...

Давно я не писал ничего в свой блог, а потому у меня было время посмотреть, какие статьи накопились в разделе для начинающих программистов. Я решил уделить чуть больше времени практике и поразбирать задачи, которые люблю давать на собеседованиях сам и которые дают мои коллеги. Решая задачу, не спешите сразу же смотреть решение. Попробуйте минут 15 подумать. Можете даже написать мне наводящие вопросы вот тут. Потом сравните своё решение с тем, что предложено. Надеюсь, формат будет удобен и интересен моим читателям 😉

Задача не прямо чтобы простая, но и не уровня Хабра. Вообще, я не очень люблю давать людям заумные задачи в без того стрессовой атмосфере. Мне больше интересно посмотреть на то, как человек думает и строит свои мысли, чем на то, как он умеет решать олимпиадные задачи.

У Вас есть следующие вводные:

1. Есть новостной сайт, который показывает новости в каком-то порядке (это не столь важно для задачи)
2. Перейдя по ссылке /news/123, Вы откроете страницу новости с ID 123, на которой будет располагаться заголовок новости, её тело и лента комментариев
3. Комментарии идут от самого нового к самому старому. Пусть пока в них не будет ветвления.

Задачи:

1. Спроектировать хранение новостей и комментариев в реляционной БД.
2. Организовать удобный вывод комментариев к новости.

Показать решение

Первая часть задачи направлена на то, чтобы выявить Ваши навыки проектирования БД в нормальных формах. Самое главное здесь — рассуждать вслух о том, как Вы строите схему таблиц. Приемлемой будет логика следующего рода.

Поскольку у нас есть две сущности (Новость и Комментарий), то нам потребуется две таблицы для хранения непосредственно их без связки между собой. Из постановки задачи следует, что у одной новости может быть несколько комментариев, поэтому связь будет «один-ко-многим». Из этого следует, что создавать третью таблицу для связки не нужно — достаточно будет только указать в таблице Комментариев ID новости, к которой привязан конкретный комментарий.

Теперь стоит расписать таблицы точнее. Здесь можно немного порисовать, чтобы получить примерно следующую картинку

1 шаг

Если присмотреться, то мы увидим, что на схеме не хватает таблицы пользователей. В рамках задачи её можно опустить, так как для выполнения условий вполне достаточно наличия ссылки на пользователя в виде его ID, но в реальной системе разумеется эта связь должна быть на месте.

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

  1. Поле используется в качестве фильтра в WHERE
  2. Поле является связующим в JOIN

У нас это поля id_news и id_user в таблице comments. При этом, если очень хочется совсем правильного решения, то можно сделать эти ключи внешними. Только не забудьте принципы их работы, ведь Вас наверняка спросят о том, чем обычный индекс отличается от внешнего ключа.

В итоге у нас получится уже обновлённая картинка, где уже видны связи (внешние ключи в comments имеют фиолетовый маркер).

2 шаг

Разумеется, при рассуждениях Вам будут задавать дополнительные вопросы, и Вы должны быть к ним готовы. Это могут быть вопросы рода:

  • Какие типы индексов Вы знаете?
  • Как быть, если комментарии нужно выводить в виде дерева?
  • Какую СУБД Вы бы использовали и почему?

Следующий вопрос уже с подвохом. Сама задача содержит определение «удобный вывод», поэтому прежде чем бросаться за проектирование, нужно задать наводящие вопросы. Что есть «удобный вывод»? Скорее всего, это UI, который показывает по N комментариев, подгружая остальные посредством AJAX.

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

Самое явное решение здесь в том, чтобы ответить: «Мы будем отдавать комментарии по ID новости и номеру подгружаемой порции, используя SQL-конструкцию LIMIT с указанием offset». Запрос будет выглядеть примерно вот так:

SELECT * FROM comments WHERE id_news = 123 LIMIT 500, 25

Кажется, что это тривиальное решение уже не отделяет Вас от успешного завершения данной задачи. Но не тут-то было. Если для решения Вы выбрали MySQL, то загвоздка состоит в том, что такая конструкция будет хорошо работать на небольших сайтах. Если же у Вас количество комментариев будет достаточно большим и измеряться десятками тысяч, то загрузка новых страниц будет тормозить сильнее и сильнее. Если мы получим конструкцию LIMIT 100000, 25, то MYSQL будет пробегать все 100000 строк, а только затем возвращать Вам ограниченные 25. Это известная проблема, и решений тут много. Например, можно решить эту проблему на уровне кода.

Одно из возможных решений состоит в том, чтобы отсекать «хвост» комментариев через условие WHERE, которое будет фильтровать записи по ID комментария, который был последним в предыдущем пакете комментариев, отправленных пользователю. Нас интересуют комментарии в порядке их старения, а значит, если пользователю уже был показан комментарий с ID, например 10000, то все ID > 10000 будут содержать только более новые комментарии (ведь ID — это автоинкрементальное поле). Значит при каждом новом запросе мы должны будем добавлять в запрос условие

WHERE id < $lastId

У Вас могут спросить, есть ли другие решения для данной задачи. Ещё одно решение базируется на чистом перестроении запроса

SELECT * FROM comments JOIN (SELECT id FROM comments ORDER BY id LIMIT 100000, 25) AS c ON c.id_comments = comments.id_comments

Хитрость здесь состоит в том, что для построения ограниченной выборки MySQL в таком случае уже не лезет в саму таблицу, а начинает принудительно строить выборку по более быстрым индексам, так как работа уже идет с вложенным запросом. Но это особенность исключительно MySQL. В других СУБД оптимизатор работает иначе.

Надеюсь, что статья была для Вас интересна и полезна! Я постараюсь уделять время разбору и других интересных задач. Буду рад, если Вы тоже будете присылать мне задачи, с которыми столкнулись на собеседованиях для того, чтобы мы разобрали их решение здесь.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *