Есть вопросы, есть ответы

Изображение для привлечения внимания

Публикую свои ответы на статью Интересные задачки с собеседований из блога Записки программиста

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

Если просто выключать везде свет кроме одного вагона(в котором мы изначально находимся) и постоянно двигаться вперед, выключая свет – мы не сможем доказать что мы обошли весь поезд по кругу. Значит надо передвигаться другим, более изощренным способом. Наверно не самый элегантный способ но:

1. Место появления – точка отсчета (т.о.)
2. Двигаемся на F вагонов вперед – включаем свет.
3. Двигаемся на B вагонов назад выключаем свет.
4. Инкрементируем F и B, чтобы передвигаться на 1 вагон вперед в каждом направлении.
5. На каждой итерации проверяем свет в вагоне, предшествующему текущему вагону(в том котором включаем или выключаем свет)
6. Если свет в предшествующем вагоне поменялся на другой из F и B можно получить кол-во вагонов.

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

Возможно следует создать структуру вида: { номер_строки : длина_строки }, пройтись по всем строкам. Отсортировать структуру по длине строки и только потом сравнивать строки с одинаковой длиной.

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

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

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

Используюя выражение: \(\) заменяем все что попадает под это выражение, пока длина строки не перестанет меняться. Если длина строки > 0 - значит скобки стоят не верно.

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

Храним структуру вида { ip : timestamp }. При каждом запросе извне, получаем ip источника, лезем в структуру – ищем, если не находим – добавляем, в противном случае обновляем. Каждую минуту удаляем записи timestamp < current_timestamp – 5min.

ps. Отличный блог, автору большое спасибо!