Тестовое задание для разработчика

1. Есть таблица платежей пользователей:

CREATE TABLE payments (
`id` INT AUTO_INCREMENT PRIMARY KEY NOT NULL,
`student_id` INT NOT NULL,
`datetime` DATETIME NOT NULL,
`amount` FLOAT DEFAULT 0,
INDEX `student_id` (`student_id`)
);

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

Решение:

SELECT student_id FROM payments
GROUP BY student_id
ORDER BY SUM(amount) DESC
LIMIT 1,1

2. Есть две таблицы. Первая содержит основные данные по студентам:

CREATE TABLE student (
`id` INT AUTO_INCREMENT PRIMARY KEY NOT NULL,
`name` VARCHAR(20) NOT NULL,
`surname` VARCHAR(20) DEFAULT '' NOT NULL,
`gender` ENUM('male', 'female', 'unknown') DEFAULT 'unknown',
INDEX `gender` (`gender`)
);

Вторая содержит историю статусов студентов, где последний по хронологии статус является текущим:

CREATE TABLE student_status (
`id` INT AUTO_INCREMENT PRIMARY KEY NOT NULL,
`student_id` INT NOT NULL,
`status` ENUM('new', 'studying', 'vacation', 'testing', 'lost') DEFAULT 'new' NOT NULL,
`datetime` DATETIME NOT NULL,
INDEX `student_id` (`student_id`),
INDEX `datetime` (`datetime`)
);

Необходимо показать имена и фамилии всех студентов, чей пол до сих не известен (gender = 'unknown') и они сейчас находятся на каникулах (status = ‘vacation’).

Решение:

SELECT name, surname
FROM student s
JOIN student_status ss ON (s.id = ss.student_id)
JOIN (SELECT max(id) AS id FROM student_status GROUP BY student_id) maxid ON (maxid.id = ss.id)
WHERE gender = 'unknown' AND status = 'vacation'

3. Используя три предыдущие таблицы, найти имена и фамилии всех студентов, которые заплатили не больше трех раз и перестали учиться (status = ‘lost’). Нулевые платежи (amount = 0) не учитывать.

Решение:

SELECT name, surname
FROM student s
JOIN student_status ss ON (s.id = ss.student_id)
JOIN (SELECT max(id) AS id FROM student_status GROUP BY student_id) maxid ON (maxid.id = ss.id)
JOIN (SELECT student_id FROM payments WHERE amount != 0 GROUP BY student_id HAVING count(*) <= 3) p ON (p.student_id = s.id)
WHERE status = 'lost'

И еще одна задача

В одном файле хранятся ID пользователей и время их заходов на сайт за 5 лет существования сайта в произвольном порядке. Известно, что существует порядка миллиона пользователей, четверть из которых были активными. Активные пользователи в среднем по 100 раз в день заходили на какую-либо страницу сайта.

Необходимо описать в понятной форме наиболее оптимальный алгоритм создания нового файла, в котором записи из первого файла будут отсортированы по поряду возрастания ID, а для одинаковых ID по хронологии. (Можно написать небольшую программу на PHP, но не обязательно)

Например, если в исходном файле:

1234567890 2013-03-08 12:26:09
0987654321 2013-03-09 09:23:17
1234567890 2014-01-01 00:00:34
0087645544 2015-02-03 17:45:01
0087645544 2015-01-03 11:05:06

В результирующем должно быть:

0087645544 2015-01-03 11:05:06
0087645544 2015-01-03 17:45:01
0987654321 2013-03-09 09:23:17
1234567890 2013-03-08 12:26:09
1234567890 2014-01-01 00:00:34

Решение:

Посчитаем кол-во записей и размер файла:

1000000 + 250000 * 100 * 365 * 5 = 45626000000 записей

45626000000 * 31 = 1414406000000 байт ~ 1286 гб

1000000 + 250000 = 1250000 разных ID

ID различаются только в 0.0027% записей, значит оптимальнее сортировать сравнивая строки не целоком, а сначала отсортировать по ID.

Если делать на PHP, то надо использовать функции: fopen, fseek, fwrite, fgets. То есть целиком файл в память не считывать.

Алгоритм:

Используя fgets, делаем один проход по файлу, из каждой строки берем ID, собираем массив уникальных ID с их количеством таким образом:

@$ids[$id]++; // для оптимизации if(isset()) не используем

ksort($ids); // сортируем

// Такой массив должен занять в ОЗУ не более 200 мб (согласно моим тестам).
// Если каждый ID занимает 10 байт: 10 * 1250000 * 18 (коэффициент памяти массивов PHP) = 225 мб.

// записываем второй файл отсортированный по ID:

foreach($ids AS $id => $num) {
	$need_to_find = $num;
	// делаем проход по файлу, если находим запись с $id, то $need_to_find уменьшаем на 1 и копируем запись во второй файл.
	if ($need_to_find == 0)
		continue; // завершаем проход по файлу
}

Так образуется второй файл, равный по размеру первому, но отсортированный по ID.

В массиве $ids сохранились границы разных ID в новом файле.

Используя $ids, можно делать сортировку внутри каждого блока из одинаковых ID.

Это длительный процесс, поэтому $ids лучше сохранить в отдельный файл в виде var_export($ids), чтобы процесс сортировки можно было приостанавливать и возобновлять между сортировками блоков. Также нужно хранить массив [ID => true|false] означающий состояние отсортированности каждого блока.

Чтобы получить границы N-ного блока, надо сложить значения первых N-1 элементов $ids и умножить на 31 (длинна одной записи в файле) - это будет начало блока, прибавить значение $ids[N]*31 - это будет конец блока.

Записи в файле можно менять местами используя fopen('file.txt', 'c'), fseek() и fwrite().

Подойдет любой алгоритм внешней сортировки, то есть когда данные не помещаются целиком в ОЗУ.

Оптимальным вариантом сортировки внутри блоков, на мой взгляд, будет использование алгоритма "QuickSort" - https://ru.wikipedia.org/wiki/Быстрая_сортировка

А самым простым в реализации и не самым медленным будет алгоритм "Двунаправленного выбора": Делается проход по списку и отыскивается минимальное и максимальное значения, в файле они меняются местами с первым и последним элементами. Затем операция с проходом повторяется для элементов от 2-го до N-1, потом для элементов от 3-го до N-2 и так далее, пока указатели не встретятся.