face-finder

Тестовое задание на вакансию php-разработчика в ООО "Пикабу"

От разработчика

1. Задача

1.1. Требования

Необходимо разработать компонент регистрации и быстрого поиска похожих лиц по заданным параметрам. Лицо выражается четырьмя параметрами:

1. id - уникальный идентификатор (если 0, то это новое лицо);
2. Раса - значение от 0 до 100, где 0 - европеец, 20 - азиат, 40 - негр и тд, а промежуточные значения - это различные градации;
3. Эмоция - значение от 0 до 1000, где 0 - грустное лицо, 100 - веселое, 200 - задумчивое и тд;
4. Старость - значение от 0 до 1000, где 0 - лицо младенца, 1000 - лицо старика; Если в компонент для поиска приходит ранее не сохраненное лицо (id=0), то компонент должен его сохранить в БД. Поиск выполняется по последним 10 000 сохраненным лицам. Задача поиска - найти 5 наиболее похожих лиц по параметрам, причем среди этих пяти лиц должно быть и то, которое ищется. Для определения уровня схожести двух лиц стоит применить векторное расстояние:

$l = sqrt(($race1 - $race2) ** 2 + ($emotion1 - $emotion2) ** 2 + ($oldness1 - $oldness2) ** 2);

Чем меньше $l - тем больше схожесть между лицами. По задумке компонент используется больше для поиска лиц, чем для добавления новых лиц. Примерно на 1 добавление лица приходится 5000 поисков лиц. Т.е. класс поиска должен, по возможности, учитывать особенность его использования и стараться искать схожие лица максимально быстро, и при этом процедура добавления лица может занимать больше времени. Также стоит учитывать, что на 1 экземпляр класса может приходиться неограниченное количество операций поиска и добавления лиц (например, если компонент будет использоваться в демонизированом процессе). Компонент также должен уметь удалять все ранее добавленные лица в БД и при этом сбрасывать генератор id до начального значения.

1.2. Структура классов

Компонент должен быть построен всего на двух классах:

1. FaceFinder - класс поиска, добавления и удаления все лиц;
2. Face - класс параметров лица. Интерфейсы обоих классов описаны в приложении А, также доступны по следующей ссылке. Автоподключение классов не использовать.

1.3. Структура БД

Конструктор класса FaceFinder должен подключаться к MySQL и создавать (если не существует) базу данных с названием face_finder. В этой БД должна быть 1 таблица для хранения лиц, добавленных через класс FaceFinder. Эта таблица также создается в конструкторе класса (если есть необходимость в этом). Название и структура таблицы выбирается вами.

1.4. Регламенты

Для реализации задачи стоит использовать php 7+, без сторонних (не SPL) библиотек, MySQL 5.6+.

2. Проверка

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

1. сперва оценивается насколько реализация соответствует заданию, т.е. выполнены ли требования;
2. оценивается выбор способа (алгоритма) быстрого поиска, выполняются замеры скорости поиска и сравнивается с результатами эталонного решения;
3. оценивается культура написания кода: читаемость, структура, форматирование;
4. оцениваются выбранные решения (приемы, методы и тд).

Приложение А - интерфейсы классов

interface FaceInterface {
  /**
  * Returns face id or 0, if face is new
  */
  public function getId(): int;
  /**
  * Returns race parameter: from 0 to 100.
  */
  public function getRace(): int;
  /**
  * Returns face emotion level: from 0 to 1000.
  */
  public function getEmotion(): int;
  /**
  * Returns face oldness level: from 0 to 1000.
  */
  public function getOldness(): int;
}

interface FaceFinderInterface {
  /**
  * Finds 5 most similar faces in DB.
  * If the specified face is new (id=0),
  * then it will be saved to DB.
  *
  * @param FaceInterface $face Face to find and save (if id=0)
  * @return FaceInterface[] List of 5 most similar faces,
  * including the searched one
  */
  public function resolve(FaceInterface $face): array;
  /**
  * Removes all faces in DB
  */
  public function flush(): void;
}

Приложение Б - пример проверки классов

Стоит заметить, что конструктор класса Face может отличаться в вашей реализации.

$ff = new FaceFinder();
$ff->flush();
# add and search first face
$faces = $ff->resolve(new Face(1, 200, 500));
assert(count($faces) === 1 && $faces[0]->getId() === 1);
# add +1 face
$faces = $ff->resolve(new Face(55, 100, 999));
assert(count($faces) === 2 && $faces[0]->getId() === 2);
# only search, not adding (because id != 0)
$faces = $ff->resolve(new Face(55, 100, 999, 2));
assert(count($faces) === 2 && $faces[0]->getId() === 2);
# add 1000 random faces
for ($a = 0; $a < 1000; $a++) {
  $ff->resolve(
    new Face(
      rand(0, 100),
      rand(0, 1000),
      rand(0, 1000)
    )
  );
}
# let's recreate instance
unset($ff);
$ff = new FaceFinder();
# find known similar face and check first 3 records to match
# Record with id=99999 not exists, this id is necessary to prevent
# adding new face into DB
$faces = $ff->resolve(new Face(54, 101, 998, 99999));
assert(
  count($faces) === 5
  && (
    $faces[0]->getId() === 2
    || $faces[1]->getId() === 2
    || $faces[2]->getId() === 2
  )
);
$ff->flush();