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

Как некоторые из вас уже знают, недавно я устроился на новую работу. Перед этим я проходил собеседование в нескольких компаниях. Это напомнило мне, что на собеседованиях помимо обычных вопросов типа «что умеете» и «почему хотите сменить место работы» любят давать всякие-разные задачки.

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

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

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

Других людей и прочих живых или неживых существ в поезде нет. Лампочки нельзя выкручивать, они не перегорают и не нагреваются, рисовать на стенах мелом нельзя, окон у вагонов нет. В общем, состояние поезда — это только лампочки. Кстати, начальное состояние поезда неизвестно, то есть изначально какие-то лампочки могут гореть, а какие-то не гореть. Единственный способ узнать, горит ли лампочка в определенном вагоне — это войти в него и посмотреть.

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

Есть текстовый файл, в нем есть строки. Файл большой, скажем, один терайбайт. Про длину строк ничего не известно. Возможно, все строки состоят из одного символа, а может быть, весь файл — это одна большая строка. Нужно определить количество уникальных строк в файле. Как вы будете решать эту задачу?

Десяти машин с Redis’ом, Hadoop-кластера или вроде того у вас нет. В вашем распоряжении есть только обычный компьютер с обычным процессором, оперативной памятью и диском. Есть какое-то количество свободной памяти и места на диске, но не много. Можете считать, что большой файл хранится в вашем персональном компьютере и решить задачу требуется, используя только ресурсы этого компьютера.

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

Есть холст (экран, плоскость, …), заполненный белыми пикселями. Имеется функция putPixel(int x, int y), которая делает пиксель с заданными координатами черным. Требуется написать с ее помощью функцию, рисующую окружность с заданным радиусом и центром в заданных координатах. Для простоты будем считать, что холст у нас бесконечный, то есть вызов putPixel(-9999, 9999) не считается ошибочным и действительно рисует пиксель в заданных координатах.

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

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

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

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

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

У вас есть сайт с очень большой посещаемостью. Скажем, на него заходит два миллиона человек в сутки. Требуется отображать в подвале сайта количество пользователей, находящихся в данный момент онлайн. Допускается небольшая неточность. Если счетчик отвалится, он не должен потянуть за собой весь сайт. Решение должно быть простым и эффективным.

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

Предлагайте свои решения!

А знаете, давайте попробуем провести небольшой конкурс. Оставляйте в комментариях ссылки на ваше решение приведенных задач. Решения я вас попрошу публиковать в своем блоге (по-моему, у всех они нынче есть) или, например, на pastebin.com. А то решение пяти задач наверняка будет занимать немало места.

Решения, которые считаются правильными, я опубликую через неделю (или лучше через две?). К сожалению, призов у меня нет, но обещаю опубликовать имена и ссылки на блоги тех, кто по моему мнению лучше всех справился с задачами.

А какие интересные задачи на собеседованиях попадались вам?

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

Метки: Работа.