среда, июля 02, 2008

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

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

  • Как выполнить проход по графу вглубь/вширь без использования рекурсии? (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 различных способа решения этой задачи. Все никак руки не дойдут до того, чтоб в коде эти решения проверить.

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

9 комментариев:

alexey.babik комментирует...

Можешь поделиться по поводу поддержки динамических языков? Чрезвычайно интересно :)

kpumuk комментирует...

"Есть у нас такой паттерн, как MVC": Архитектура корпоративных программных приложений, Мартин Фаулер. Вроде у меня где-то была, если никто не взял, так что если че - обращайтесь.

COTOHA комментирует...

2 alexey.babik

вот например:
http://groovy.codehaus.org/
Groovy...

* is an agile and dynamic language for the Java Virtual Machine
* builds upon the strengths of Java but has additional power features inspired by languages like Python, Ruby and Smalltalk
* makes modern programming features available to Java developers with almost-zero learning curve
* supports Domain-Specific Languages and other compact syntax so your code becomes easy to read and maintain
* makes writing shell and build scripts easy with its powerful processing primitives, OO abilities and an Ant DSL
* increases developer productivity by reducing scaffolding code when developing web, GUI, database or console applications
* simplifies testing by supporting unit testing and mocking out-of-the-box
* seamlessly integrates with all existing Java objects and libraries
* compiles straight to Java bytecode so you can use it anywhere you can use Java


или вот
http://www.artima.com/lejava/articles/dynamic_languages.html
Java SE 6 is no longer only about the Java language: SE 6 can be used to execute dynamic scripting language code as well. According to Danny Coward, Sun's Java SE platform lead, scripting language support is merely the first step in turning the JVM into the best possible execution platform for any dynamic language. Artima spoke with Coward about his new JSR 292, Supporting Dynamically Typed Languages on the Java Platform.

уже б давно сам поглядел, если и правда "чрезвычайно интересно".

Ikar комментирует...

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

Ikar комментирует...

хотя я вспомнил, как мы в Java-отделе разбирали Open4Biz и там наличие скриптовых конструкций служило одной из основных причин отказа от этой либы :).

alexey.babik комментирует...

понятно.. спасибо.

diez комментирует...

Круто... А по поводу задачек логических -- я в своё время потусил на acm.uva.es, пока ум за разум заходить не начал :) Все задачки на собеседованиях оттуда корни имеют.

А что в QArea тебя спрашивали? Кстати, я так и не понял, ты в QArea пошел или куда?

Ikar комментирует...

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

Работать я пошел в Тимдев

Kettenblatt комментирует...

"Как выполнить проход по графу вглубь/вширь без использования рекурсии?"

Собственный стек и машина состояний?

"Есть у нас город на линии горизонта в лучах заходящего солнца."


class House
{
int x1;
int x2;
int h;

int height(int x)
{
if(x < x1 || x > x2) return 0;
return h;
}
}

class City
{
House[] houses;

Point[] Profile()
{
List<Point> answer = new List<Point>();
Point currentPoint = new Point(xMin, 0);
answer.Add(currentPoint);
for(x = xMin; x <= xMax; x++)
{
int maxHeight = 0;
foreach(House h in houses)
{
maxHeight = Math.Max(maxHeight, h.Height(x));
}
if(maxHeight != currentPoint.y)
{
currentPoint = new Point(x, maxHeight);
answer.Add(currentPoint);
}
}
return answer.ToArray();
}
}