Задачи на собеседованиях

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

• Как выполнить проход по графу вглубь/вширь без использования рекурсии? (Panraven)
• Представьте, что у вас есть кластер из нескольких веб-серверов. Они заняты тем, что получают от пользователя определенный запрос на картинку, находят ее в общем файловом хранилище, проверяют есть ли у нее thumbnail и если нет, то генерят его, а потом отдают thumbnail по запросу. Нужно написать фрагмент кода, который бы обеспечивал resize картинки только на одном из серваков, при этом остальные бы ждали thumbnail этой картинки, если она уже начала ресайзиться на одном из серваков. Можно упростить задачу до одного сервака, главное сделать выполнения ресайза определенной картинки только в рамках одного потока. (Panraven) Это реальная задача из проекта и естественно у автора вопроса было больше, чем 5 минут на решение :). Я во время собеседования нужный код написал, но упустил из виду его тормознутость из-за вызова wait() внутри синхронизированного блока.
• Зачем нужна поддержка динамических языков в Java? (TeamDev) Я не нашелся что ответить, мне интервьюверы объяснили :)
• Есть у нас такой паттерн, как MVC. А расскажите-ка, какие паттерны по-любому будут применяться в каждой части этого паттерна - в модели, контроллере и представлении? (Epam) Я не ответил. Автор вопроса сослался на книжку, в которой это подробно рассматривается, но ее названия я не запомнил.
• Есть у нас город на линии горизонта в лучах заходящего солнца. Солнце заходит за городом и он представляется вам в виде силуета. Представьте, что горизонт у вас является осью координат X, у вас есть координаты каждого здания - x1, x2 и h. Где x1 и x2 координаты начала и конца фундамента здания, а h - его высота. С вашей точки зрения здания могут перекрываться друг другом, так, что самое высокое и широкое здание будет видно на горизонте, а более мелкие, находящиеся в тех же x1, x2 будут не видны. Вам нужно имея набор координат этих зданий вернуть координаты силуэта города на горизонте. Т.е. набор точек (x,y) описывающих ломаную линию горизонта, которую образуют здания города. (Epam) На собеседовании я предложил одно решение, но для некоторых случаев оно не работало. Всю ночь мне приходили в голову различные варианты и я придумал как минимум 2 различных способа решения этой задачи. Все никак руки не дойдут до того, чтоб в коде эти решения проверить.

Если кому-то интересно, можем поискать решения для всех задач :)