Интересные задачки с собеседований — решения

10 декабря 2012

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

1. Задача про циклический поезд

С этой задачей справились очень многие. Вот одно из возможных решений:

Включаем свет в первом вагоне, если он еще не включен.
Идем по вагонам вперед, считая N = количество пройденных вагонов (первый не в счет), до тех пор, пока не войдем в очередной вагон с включенным светом. Поскольку поезд циклический, рано или поздно это случится.
Выключаем свет и идем на N вагонов назад.
Если по возвращению в начальный вагон свет оказывается выключенным, значит мы нашли ответ — в поезде N вагонов.
Перейти к шагу 2.

Другие возможные решения отличаются незначительно. Например, мы также могли бы считать первый вагон за пройденный, тогда ответом на 4-м шаге будет N-1.

2. Количество уникальных строк в большом файле

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

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

foldl max 0 [ min (256 ^ n) (500000000000 `div` n) | n <- [1..64]]

Получаем 100 миллиардов штук. Понятно, что на собеседовании вам не был бы доступен интерпретатор языка Haskell, однако можно сделать предположение, что количество уникальных строк не превышает количества бит свободной оперативной памяти. 100 миллиардов бит — это примерно 11.6 Гб памяти. Сейчас никого не удивишь 16-ю Гб оперативной памяти на домашнем компьютере. Таким образом, все хорошо, у нас действительно есть один бит памяти на одну строку, даже с запасом.

Теперь решение становится очевидным, не так ли? Заводим 64-х битный счетчик строк и фильтр (битовый массив) длиной порядка 16 Гб. Заполняем память, выделенную под фильтр, нулями. При считывании очередной строки считаем ее хэш. Если соответствующий бит фильтра равен нулю, инкрементируем счетчик и заменяем нолик на единичку. Если бит равен единице, значит мы уже посчитали эту сроку — ничего не делаем.

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

3. Рисование окружности с помощью функции putPixel

Как вы можете помнить со школьного курса геометрии, уравнение окружности выглядит так:

(x − x₀)² + (y − y₀)² = R²

Лично я не был прилежным учеником. На собеседовании я не мог точно вспомнить эту формулу, и чтобы не гадать вывел ее из теоремы Пифагора. Отсюда получаем:

y = y₀ ± sqrt(R² − (x − x₀)²)

Теперь перебираем значения x от (x₀ − R) до x₀ и рисуем верхнюю левую четверть круга. Разрывов по x, очевидно, быть не может, однако могут быть разрывы по y. Поэтому после каждого шага нужно сравнивать последние две полученные координаты по y и если они различаются больше, чем на единицу, устранять разрыв. Для этого просто закрашиваем пиксели, перемещаясь по очереди на один пиксель от (x_i−1;y_i−1) вверх, а от (x_i;y_i) — вниз, до тех пор, пока координаты по y не сравняются. Чтобы круг выглядел красивее, на последнем шаге должны быть закрашены два соседних пикселя.

Теперь, когда у нас есть четверть окружности, мы можем получить полную окружность, произведя два отражения. Более эффективное, но менее наглядное решение заключается в том, чтобы рисовать лишь 1/8 часть окружности, а затем делать два отражения и один поворот.

4. Считаем круглые скобочки

С этой задачей справились, кажется, все. Вот «простое» решение:

#!/usr/bin/perl

use strict;
use warnings;

my $str = "(()(()()))";
my @chars = split //, $str;
my $ctr = 0;
for (@chars) {
if($_ eq '(') {
$ctr++;
} elsif($_ eq ')') {
$ctr--;
} else {
die "Invalid char: $_";
}

die "Invalid format" if $ctr < 0;
}

die "Invalid format" if $ctr != 0;
print "OK!\n";

А вот — вариант с использованием регулярных выражений:

#!/usr/bin/perl

use strict;
use warnings;

my $str = "(()()(((()))))";
my $re;
$re = qr/$(??{$re})*$/;
if($str =~ /^$re$/) {
print "Ok!\n";
} else {
die "Invalid format";
}

Надеюсь, здесь все понятно. Идем дальше.

5. Сколько пользователей сейчас на сайте?

Здесь предлагались интересные варианты с отложенным парсингом access_log или подсчетом только каждого N’го пользователя. Однако решение, которое считается верным, намного проще. Лишь один из участников мыслил в верном направлении, да и тот, к сожалению, не привел окончательного решения.

Сначала рассмотрим не самый эффективный подход. Пусть у нас есть Memcached. Допустим, сегодня 21.12.2012, а на часах 12:21:12. В счетчике с именем online_users_21122012_1220 хранится текущее количество пользователей, находящихся онлайн. Это значение уже не меняется, его мы выводим в подвале сайта. Счетчик с именем online_users_21122012_1225 хранит количество пользователей онлайн, которое начнет выводится в подвале через 3 минуты 48 секунд. В настоящее время это значение активно изменяется.

Каждый раз, когда пользователь загружает страницу, мы идем в мемкэш и проверяем, существует ли ключ с именем user_id_online_21122012_1225. Если не существует, создаем его и увеличиваем счетчик online_users_21122012_1225 на единицу. Можно заморочится на тему атомарности, дескать мы же можем посчитать одного пользователя дважды, если он быстро загрузит две страницы. Но учитывая, что от нас не требуется точности, как в аптеке, в этом нет необходимости. В качестве id пользователя можно использовать собственно его id, если мы считаем залогиненых пользователей, или хэш от IP, UserAgent и сессии в противном случае.

По поводу эффективности. Два-три хождения в мемкэш на одну загрузку страницы — это очень дешево, во много раз дешевле одного хождения в MySQL. Сколько памяти потребуется для поддержания такого счетчика? Если к нам на сайт одновременно завалятся 20 млн пользователей, то из расчета 64 байта на пользователя получаем, что нам потребуется примерно 1.2 Гб оперативки. Это не много, можно даже не поднимать отдельный Memcached. Что будет, если мэмкеш упадет? Мы просто останемся без счетчика, большинство пользователей вообще ничего не заметят. Главное — прописать в коде таймауты на хождение в мемкэш.

Вместо Memcached для решения этой задачи также можно воспользоваться Redis. Redis поддерживает битовые массивы, благодаря чему позволяет сократить требования к памяти с 64 байт на пользователя до 1 бита на пользователя. В результате вместо 1.2 Гб оперативной памяти нам понадобится всего лишь около 2.4 Мб.

Кто же оказался победителем?

А никто не оказался. К моему глубочайшему разочарованию, никто не подошел достаточно близко к решению всех пяти задач. И после этого некоторые еще оскорбляются, когда им предлагают такие задачки на собеседованиях…

Тем не менее, из предложенных решений мне хотелось бы отметить следующие:

Даниил Хритошин был ближе всех к правильным ответам, однако предложенные решения задач #2 и #5 были слишком сложны, а решение задачи #3 можно было существенно оптимизировать;
Некто с ником щкфтешгы озвучил умные мысли в отношении пяти задач, но они были слишком умными и запутанными, чтобы я смог их понять =);
Руслан Ибрагимов, Екатерина Трефилова и Александр Гудулин были молодцами, но, увы, не справились со всеми пятью задачами;

Такие дела. А теперь скажите мне, господа, имеет ли смысл далее публиковать такие задачки, или это никому не интересно?

Метки: Жизнь, Работа, Разработка.

Вы можете прислать свой комментарий мне на почту, или воспользоваться комментариями в Telegram-группе.

Записки программиста