Pull to refresh

Comments 63

«Of course the system assumes that any bigger group may get bored of seeing smaller groups arrive and get their tables ahead of them, and then decide to leave, which would mean that they abandon the queue without being served.»
Насколько я понимаю, это значит что если есть стол только на 4 человека, а группа приходит на 6 — то она должна ждать пока не освободится стол на 6 человек. В это время меньшие группы могут садится.
Но в любой момент ожидающая группа может передумать (надоело ждать и смотреть как меньшие группы приходят и садятся), и уйти.
Поэтому если вы этот момент не реализовали (а похоже нет — тут как раз очередь к месту), то логично что вам отказали.
Глубоко не копал, но сразу бросилось в глаза

Нет проверки на null
public int compareTo(Table table) {
        boolean isEmpty1 = this.getFreeSpace() == this.getSize();
        boolean isEmpty2 = table.getFreeSpace() == table.getSize();


Ну и саму реализацию компаратора надо проверить на соблюдение рефлексивности, антисимметричности и транзитивность. Обычно рекомендуется максимально чаще использовать (в данном случае) штатный public int compareTo(Integer anotherInteger)

Синглетон лучше создавать так
  private static class ServiceHolder {
    private static final Service HOLDER_INSTANCE = new Service();
  }

  public static Service getInstance() {
    return ServiceHolder.HOLDER_INSTANCE;
  }

  private Service() { }
Теперь мои мысли про архитектуру. Может быть от Вас ожидалась решение на базе событий/listener-ов. Каждая пришедшая группа подписывается на те столы, которым она соответствует, плюс учитываются некие весовые коэффициенты. Например, группа из 6 человек подписывается на стол А (6 мест), коэффициент =1, Группа из 2 человек подписывается на стол «Б» 2 места (=1), на стол «С» 4 места (=0.5) и так далее… В итоге, в главном треде, освобождающийся стол оповещает всех подписчиков и выигрывает тот у которого максимальный коэффициент, плюс более раннее время регистрации… Мне кажется это более соответствует реальной ресторанной модели. Но это просто мои мысли после поверхностного чтения задачи. Могу быть неправ.
А почему минус то? :) Представьте себе расширение задачи до условия «бронирование столиков»? В текущей модели потребуются существенные изменения в коде, а в моей — всего навсего столу ставится коэффициент =2 и забронировавшей его группе тоже. «Вай нот» как грится?
Каждую задачу нужно решать наиболее простым способом, а не наиболее хитрым.

Да, иногда обеспечить гибкость кода — тоже задача, и её тоже надо как-то решать, но чтобы почему вы уверены, что верно угадали возможный путь развития «ресторанного» проекта?
Хорошо, а что такого сложного и запутанного в моей версии решения? Я не вижу явных минусов, зато вижу плюсы в части решения построения соотношений группа <-> стол. Код читаться будет уж явно легче, чем сейчас.

Из того, что в глаза бросилось:


Вы работаете с потоками, но используете не потокобезопасные коллекции.


127: group.getTable().setFreeSpace(-1 * group.getSize());

Здесь же будет NPE, если клиенты не за столом.


135: Iterator iterator = clientsQueue.iterator();

Зачем здесь вообще итератор?


138: if (searchTable(client)) {

А метод searchTable() у Вас не просто ищет, есть ли свободный стол, но и добавляет клиента. Во-первых, это нарушение CQRS, а во-вторых – как раз здесь отличный пример того, почему это плохо.


Ну и в общем, код скорее процедурный, нежели объектно-ориентированный.

А где там у него пример почему это плохо? Там как раз всё в порядке, пытаемся найти столик для каждой группы, те для которых нашли — удаляем из очереди.

И итератор там используется к месту: он же удаляет группы из очереди в процессе обхода очереди. Кроме как через итератор это по-нормальному не сделать.
А где там у него пример почему это плохо?

Мы спрашиваем, есть ли свободный столик, и если есть – удаляем клиента из очереди. А то, что клиент при этом привязывается к столику, скрыто в реализации searchTable.


И итератор там используется к месту

Да, это я затупил.

Ну так DRY же. Удалять клиента из очереди нужно только в одном месте, а привязывать к столику — в двух. Поэтому удаление из очереди снаружи searchTable, а привязка к столику — внутрях.

Название у метода можно поменять.

Не согласен, имхо здесь CQRS и SRP в целом важнее, чем DRY.

CQRS — это вообще архитектура, а не принцип (и она сюда не подходит).
SRP тоже важно, но ответственность у метода всё еще остается одна: назначение группе клиентов правильного столика.
CQRS — это вообще архитектура, а не принцип (и она сюда не подходит).

Скорее всего, имеется ввиду принцип CQS, на котором основана архитектура CQRS.

Да, конечно же, CQS имел в виду, прошу прощения.

Вы работаете с потоками, но используете не потокобезопасные коллекции.

Мне кажется, там вообще потоки не нужны. Если только явно не оговаривали.

Чёт вы перемудрили с сортировкой. Повторяете её на каждый чих, ещё и поверх списка. Т.о. у вас все операции минимум O(N × logN) с довольно большой константой, при том что тупой перебор дал бы O(N) с относительно малой — и этот перебор вы всё равно делаете.
Зачем вам вообще сортировка?
Дальше у вас SearchTable реализован просто с ошибкой. Он берёт первый попавшийся стол. А должен а) сначала убедиться, что нет пустых достаточно ёмких столов; и б) если пустых столов нет, то найти стол с минимально-необходимым количеством свободных мест.
Мне тоже сначала показалось что в SearchTable ошибка. Но на самом деле ее нет: список столов же упорядочен, так что первый попавшийся стол как раз является нужным.
Нет, в условии если есть пустой стол, то сажать за стол с другой группой нельзя.

Там написано "however if at the same time you have an empty table with the required number of chairs and enough empty chairs at a larger one" — то есть нельзя сажать за стол с другой группой, если есть пустой стол с достаточным количеством мест.


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

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

Пусть есть пустой стол на 4 места и частично занятый на 3, и пришла группа из 3 людей.
Поэтому просто искать первый стол с достаточным количеством мест нельзя.

Почему нельзя-то? По условию, надо выбрать стол на 4 места. Он как раз и будет первый.
Если я правильно понял, что «частично занятый на 3» означает стол на (икс+3) человека, за которым сидит икс человек, то можно выбирать любой (даже самый большой): запрещено только сажать группу не за «идеально подходящий стол», если такой стол свободен.

А «обидчивые группы», вероятно, обижаются в следующей ситуации.
Очередь: 2, 6.
Свободные места/вместимость столов: 6/6, 5/5.
Обслуживание: 2 за стол 6 (получается 4/6, 5/5 — свободных мест полно, а посадить их не могут. )

EDIT: Тут ещё одна тонкость может быть: группы не меньше двух, так что
не всегда ясно, какой стол (из свободных большего размера) лучше занять группой из 2 человек: [3/3, 4/4]
преобразовать в [1/3 (==(0/3)), 4/4]
(4 реально свободных места для набора групп {[4], [3], [2, 2], [2]})
или в [3/3, 2/4]
(5 реально свободных мест для набора групп {[3], [3, 2], [2, 2], [2]}) — первый вариант не сможет потом сразу обслужить две группы с 2 и 3 человеками,
а второй — одну группу из 4. ¯\_(ツ)_/¯
Тут ещё одна тонкость может быть: группы не меньше двух


Вот мы и проверили, кто внимательно читает условие:
Clients arrive alone or in groups, up to 6 persons
Да, действительно -_-'
Но если в коде это специально не учитывать, то могут и не заметить, кто неправильно прочитал.
Нет.
И вообще вот именно это место нужно вынести в класс-стратегию (с одной единственной функцией SearchTable). Так и тестировать проще, и это явное место, которое может измениться в будущем.
в джаве не разбираюсь, но прочтя код могу сказать что именования перееменных в классе Table оставляет желать лучшего. size — это что за размер? длина? ширина? тогда уж лучше использовать нечто вроде numberOfChairs, chairs, freeChairs или типа того

Table.setFreeSpace должен устанавливать пустое место в то значение которое передано, а не вычислять его. ибо как все привыкли если ты делаешь set* то оно будет именно таким.

RestManager.searchTable наверное будет лучше превратить в Table.getSuitable(group)

может быть в джаве это и нормально, я не знаю
for (Table table : tableList) {
            if (table.getFreeSpace() == 0) break;


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

для «иногда люди задолбались ждать в очереди и ушли» нужно использовать TTL — это стандартная задача на cache ttl
RestManager.searchTable лучше превратить в RestManager.tryToAssignTable

В класс Table его не перенести никак, он же работает со всеми столами сразу же.
Да, логично. Но тогда лучше сделать отдельный TableSearch или типа для поиска стола куда передавать список всех столов и размер группы. Потому как в теории Table класс это просто класс-сущность
Я бы отметил три момента в вашем коде.
1. Не выполнено условие, что клиент может уйти из очереди. В методе onLeave клиенты уходят только из-за стола. Попавший в очередь же будет стоять до последнего…
2. Метод setFreeSpace мягко говоря водит в заблуждение. По соглашению это должно бы быть присваивание. А у вас там неочевидная математика. Сделали бы методы add и remove например.
3. Если вы сдавали все вот так одним файлом, то опять же большой ай-я-яй. Помимо стиля. Ваши классы, которые вы сделали для проверки, в ответе присутствовать не должны. В итоге еще и нарушили поставленное условие на конструктор RestManager.

По сути задача не решена получается. Потому и отказ.

Есть некоторые основания предполагать, что автор просто помог какому-то нерадивому студенту (будущему эффективному манагеру) написать курсовик.


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


Короче, спасибо за статью!

Бесплатной рабочей силы? Мгм. А вы знаете расценки скажем hh.ru на размещение публикаций? Это слишком золотые выходят «бесплатные раб. силы»!!!
Вообще, на курсовик эта задачка явно не тянет :-)

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

1-2 часа на решение.
Не согласен о бессмысленности.
Типичная задача планировщика (приоритизация процессов, ресурсов, потоков, памяти, да чего угодно) под соусом ресторана.
бессмысленная — в том смысле, что сложно представить ситуацию, когда такой код пойдет в прод без изменений под реальную задачу
Ну как сказать… Для того, что такой планировщик представить в виде столиков ресторана надо ну оооочень много креативности. Если человек способен на то, чтобы увидеть тождественность подобных задач и разработать такое задание, то для написания планировщика в чистом виде ему потребуется гарантировано меньше времени. :-)
Да и условия предельно упрощены. Нет никаких указаний на необходимые оптимизации, размерности и т.п. Реального планировщика из этого не сделать.
Во-первых, не напрягайтесь, научитесь со времением. Советую использовать разные сервисы для code review.

Во-вторых, по примеру, тут много вещей характерны для начинающего в Java:

Все что ниже для обучения на будущее (это не значит, что вы плохой программист, просто пока еще не набрали реального опыта в Java, все через это проходили)

Список недочетов:
1. классы должны быть в отдельных файлах и пакетах, я не одном,
2. сингельтон и треды вас никто не просил делать, если уж сделали треды — нужно использовать потокобезопасные коллекции,
3. Exception'ы нельзя просто игнорировать по философии Java (точнее иногда можно, но редко и не в тестовом), хотя бы логирование ошибок должно быть,
4. System.out.println плохой способ, для логирования стоит использовать любой механизм логирования,
5. compareTo у Table выглядит плохо, постоянные пересортировки списка ужасно, во-первых, для постоянной сортировки можно использовать SortedSet, во-вторых, там намного логичнее использовать Map<Кол-во свободных мест, List>, тогда не нужны будут сортировки,
6. searchTable в реальности не только ищет, а еще и расаживает группы, это плохо (2 бизнес.функции в одном методе), ну и называться должна searchAndSetTable
7. Константы нужно сделать явно, они не должны быть магическими числами,
8. Похоже не выполнен пункт, если есть польностью пустые столики — то нельзя сажать группы в столик с другой группой,

Ну, насчет первого пункта я бы поспорил. У формата «один файл со всеми классами» есть свои плюсы: его можно передать по почте или через IM без помещения в архив
У формата «один файл со всеми классами» есть главный минус — он не принят в Java мире, поэтому именно для тестового задания я бы использовать его не стал, если ваш уровень не настолько офигенен, что вы можете плевать на условности, а на той стороне это оценят. Zip архив с проектом куда лучше (и если как задача открыть zip архив окажется сложной ревьюеру — нужна ли вам такая компания?).
Честно говоря, я воспринял «один файл» как попытку упростить чтение и анализ кода для этой статьи. Как то в голову даже не пришло, что автор это сделал по незнанию, а не специально. Надо просто уточнить, в каком виде он представил работодателю результат решения задачи. Так что за это ставить минус я бы не стал пока что.
А знаете… хорошее дело сделали. Мне кажется, что это лучше комментариев на хабре под статьёй.

А ведь это идея! В следующий раз перед тем, как отправить решение теста, запилю тему на хабре, где мне бесплатно и ошибки укажут и код отрефакторят.

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

Не думаю, по сути, задача не про ресторан, а про планировщик задач и про RTOS. Если приходит задача на обрадотку данных, то нужно её начинать сразу.
Вас, на самом деле, попросили написать «work-conservative, non-preemptive scheduler» для системы с несколькими обработчиками.
«work-conservative» — если есть задача на обработку данных и есть ресурс для её обработки, то необходимо сразу её (обработку) начать, ждать нельзя.
«non-preemptive» — нельзя выгнать людей из за стола и покормить других, а потом посадить первую группу обратно.

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

Очередь там в задании указана, вот в этой фразе:
Client groups must be served in the order of arrival ..


Значит, что если в очереди стоят группы из двух, шести и трёх человек (в таком порядке) и освободился стол на 3 места, то посадить нужно группу из двух человек (они пришли раньше).
Интересная задача, спасибо

Обычно в заданиях с частичным кодом предполагается что вы не должны его изменять, если в задании явно не указано обратное. В вашем случае явно говорится, что нужно только fill RestManager и вы можете add new methods


Please fill RestManager class with appropriate data structures and implement its constructor and three public methods. You are encouraged modify other classes too (to help us test them) and add new methods at your will.

Такие задания проверяют умение разработчика взаимодействовать с существующим кодом. Чтобы при выполнении любой задачи по модификации существующего кода (пусть даже и не оптимального) на реальном проекте новый разработчик не стремился переписать все как надо


К тому же зачастую подобные тестовые задания могут проверяться в автоматическом режиме и изменение изначального кода может просто зафейлить компиляцию/запуск автоматической проверки

Как-то я решал похожую задачу для иностранной компании, а потом увидел работающее приложение, которое продавалось за деньги на основе моего решения. Это я к тому, что когда мне присылают слишком комплексные задания, я начинаю задумываться о трех вещах: уважают ли мое личное время, не будут ли использовать мое решение задачи в своих корыстных целях и какого хрена надо давать такое задание, если навыки разработчика любого уровня можно проверить заданием, которое можно сделать за 20 минут?
А почему вы так уверены, что приложение было сделано на основе именно вашего решения? Может быть, было наоборот: вам дали тестовое задание, основанное на уже существующем приложении?
Честно признаться, на последнем месте работы за полтора года ничего кроме «форов» и «ифов» я не писал


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

в очереди группы 2, 3, 2 человек
и есть столы 4 и 3 места

В этом случае, группу из 2 человек лучше посадить за стол где 4 места (а не где 3), так как в этом случае можно рассадить всех.
Такая ситуация по условию невозможна. Если посмотреть на шаблон решения, то понятно, что группы приходят по одной и освобождают столы тоже по одному
Не совсем. Тут зависит от того как читать условие, запрос на удаление или добавления групп может придти практически одновременно. Более того, если идти от API важно только правильно обрабатывать onArrive, onLeave и lookup. По сути, до момента lookup клиенту не интересно и неизвестно состояние системы. На практике, регистратор может записать в интерфейсе прибытие трех групп, уход двух групп и только потом спросить за какой стол посадить первую группу. Другое дело это сильное усложнение условия, которое в общем-то необязательно (хотя я бы уточнил при получении задания такую возможность).
Типичная олимпиадная задачка же, на пару часов. По крайней мере, 25 лет назад было так.

Где тут можно увидеть какие-то «комплексные задания»?
А парень хорош, одним ударом 5 задачи решил:
1) Пополнил профиль на GitHub
2) Получил инвайт на хабре
3) Получил бесплатно консультации специалистов и поднял собственный уровень
4) Сделал полезное дело, так как консультации специалистов теперь общедоступны
5) Повысил собственную репутацию

Молодец, без иронии)
6. Показал новичкам в java типа меня, что существует область знаний, о которой я даже не подозревал.
По приведённому куску кода, который необходимо заполнить у меня возникло стойкое ощущение, что код написан не на джаве, а на шарпах.

По большей части зависит от стаилгайдов, но перенос открывающей фигурной скобки на новую строку я вижу крайне редко в джава-приложениях.
И так же размерность стола\группы задаётся переменной, доступ к которой идёт не через геттер, а просто по прямому обращению. Так, несомненно, удобнее. Однако это непривычно и не особо идиоматично для кода на джаве.
По второму пункту как минимум имхо метод public Table lookup не в своем классе. Мы можем получить стол геттером у клиента, который по идеи должен хранить ссылку на стол.

Интересная ответственность у клиента — сообщать, за каким он столом :)


Мне кажется, у вас ожидали, что логических методов у Table и у ClientsGroup не будет, потому что логика оказывается размазанной, и, кроме того, сущность, которая не должна знать о способе выбора столов, внезапно знает (метод compareTo у стола). Почему СТОЛ отвечает за алгоритм сортировки?

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

Нужна нормальная структура проекта как минимум, в идеале DDD и unit-тесты.
Sign up to leave a comment.

Articles