SibEDGE sums up the "IT-Planet 2014/15"

SibEDGE sums up the "IT-Planet 2014/15"

Вадим, старший разработчик's picture
Вадим, старший разработчик
23 June 2015

Вот и подоспела обещанная нами статья по задачам отборочного тура IT-Планеты и тому, как они составлялись и оценивались. Уверены, что обратная связь будет полезна не только участникам олимпиады, уже выполнившим задания, но и всем, интересующимся программированием, особенно новичкам.

Команда «SibEDGE» выражает благодарность организаторам и всем конкурсантам!
Итак, переходим к делу и передаем слово Вадиму, ответственному за техническую часть олимпиады:

«У участников была неделя на то, чтобы сделать задания отборочного этапа. При планировании задач на отборочный тур учитывалось два аспекта:

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

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

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

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

Теперь подробнее по задачам и подходам, к их решению:

1. Задача «Точки на плоскости»

Текст задачи:

На плоскости задан выпуклый N-угольник – D и точка P. Определить является ли точка P внешней или внутренней (граничной) точкой многоугольника D. Создать WindowsForm либо WPF проект, дающий решение задачи. Построить графический образ задачи.

На входе:
N + 1 точка. Первые N точек задают вершины многоугольника. Последняя точка – точка P, принадлежность которой внутренней области многоугольника проверяется.

На выходе:
Ответ и рисунок, иллюстрирующий корректность ответа.

Указание:
Можно использовать любой известный Вам алгоритм принадлежности точки выпуклому многоугольнику. Например, можно проверять, равна ли сумма площадей треугольников Ti площади многоугольника D. Треугольники Ti одной из вершин имеют точку P, две другие вершины – это вершины многоугольника с номерами i и i+1. Для внутренних точек равенство выполняется, для внешних – сумма площадей больше площади многоугольника.

Решение:

Что нужно для успешного выполнения данной задачи? Реализовать алгоритм принадлежности точки к многоугольнику? – Да. Это сложно? – Нет. Ссылка на алгоритм есть в тексте задачи, без проблем можно найти альтернативный вариант с помощью поиска в интернете. Идем дальше. Необходимо построить графический образ задачи? – Да. – Это сложно? – Нет. Любой квалифицированный программист, я думаю, способен нарисовать многоугольник в настольном приложении. Тогда в чем смысл задачи? – Сделать и первое и второе, и самое главное сделать это удобно для потенциального пользователя программы! Раз, мы создаем графический образ решения, то напрашивается сделать графический интерфейс пользователя (а не забивать список или, не дай Бог, формировать файл какого-нибудь странного формата). Чтобы пользователь мог мышкой натыкать проверяемый многоугольник и, желательно, без дополнительных действий узнать о принадлежности точки к многоугольнику. (Задавать точки многоугольника левой кнопкой мышки, проверяемую – правой не догадался, к сожалению, никто.) Естественно, при реализации надо не забыть проверять исходные данные на корректность. (Многоугольник на выпуклость и т.д.)

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

2. Задача «Как идут дела?»

Текст задачи:

При управлении программным проектом часто используют такой инструмент, как восходящая диаграмма выполнения. Предположим, что мы можем оценить трудоемкость выполнения предстоящих работ в некоторых единицах. Пусть значение трудоемкости равно N. Срок выполнения всех работ также известен и равен T. Ход выполнения работ можно представить в виде графика (восходящей диаграммы выполнения) с осью абсцисс, задающей время, и осью ординат, задающей объем выполненных работ. На этом графике прямая линия, соединяющая точку (0, 0) и точку (T, N), характеризует среднюю скорость выполнения работ. Каждодневные отметки на графике реально выполненной работы позволяют судить о том, как идут дела. Точки под прямой свидетельствуют об отставании от «нормального» процесса выполнения. Точки над прямой свидетельствуют о превышении планов.

Подобные диаграммы встречаются при управлении различными производственными процессами.

Сформулируем задачу. Дана конечная точка (T, N) и последовательность текущих точек (Tk, Nk), где

k = 1, 2, … m;                    0 < Tk-1 < Tk < T;                    0 < Nk-1 < Nk < N;

Требуется определить максимальный интервал успешного управления – интервал [Ti, Tj], на котором суммарное превышение работ максимально.

Указание:
Следует построить эффективное по времени решение, учитывающее, что число точек m может быть велико, а ответ начальство требует незамедлительно.

Решение:

Что требуется для успешного выполнения этого задания? – Указание в конце задачи, говорит нам о том, что прежде всего важна эффективность решения. То есть мы имеем стандартную задачу на эффективную реализацию алгоритма.

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

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

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

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

3. Задача «Фигуры, фигуры»

Текст задачи:

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

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

Указание:
При построении семейства классов используйте механизм полиморфизма, включив, например, полиморфный метод Show – показа фигуры.

Решение:

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

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

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

4. Коллекция для многопоточности

Текст задачи:

Создать собственный класс-коллекцию (класс должен реализовывать интерфейс Ilist) пригодный для многопоточного использования. При реализации запрещается использовать классы из Task Parallel Library (TPL) в частности из пространства имен System.Collections.Concurrent.

Написать пример кода демонстрирующий использование класса в многопоточном сценарии.

Решение:

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

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

Рассмотрим возможные подходы к решению этой задачи:

  1. Реализуем в нашем классе интерфейс Ilist. В реализации каждого метода делаем обращение через объект синхронизации. Приблизительно вот таким образом:

    lock (lockObject)
    {

    }

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

  2. Другой вариант – так же использовать общий объект синхронизации, но использовать для блокировки не lock, а класс ReaderWriterLockSlim. Данный класс позволяет раздельно ставить блокировку на чтение и запись и допускает одновременное чтение несколькими потоками, до тех пор, пока не будет сделана блокировка на запись. Решение с использованием этого класса гораздо эффективнее предыдущего, поэтому участники предложившие такое решение получили 80 баллов за задачу.

  3. А есть ли варианты лучше? На самом деле, если подумать, элементы коллекции фактически независимы друг от друга, запись условно в пятого элемента никак не влияет на чтение четвертого или какого-то еще (кроме пятого). Таким образом мы подходим к идее раздельной блокировки доступа к каждому элементу коллекции. Конечное решение выглядит примерно следующим образом: есть внутренняя коллекция элементов, согласованно с ней существует внутренняя коллекция объектов синхронизации. Доступ к каждому элементу разграничивается своим объектом синхронизации с раздельной блокировкой на чтение и запись (как в варианте два, но для каждого элемента коллекции). Исключением является реализация методов таких как Insert, Remove и Clear – затрагивающих всю коллекцию, только для них надо делать массовую блокировку.

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

5. Автогенерация столбцов таблицы

Текст задачи:

Такие элементы управления как DataGrid в WPF и WinForms имеют способность генерировать столбцы для загруженного в них источника данных. Не используя встроенную функциональность сделать свою реализацию.

Детали задания:
Необходимо сделать программу с графическим интерфейсом умеющую отображать список данных произвольного типа.

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

Детали задания: Есть список объектов типа T.

Для каждого открытого свойства класса T простого типа должен быть сгенерирован один текстовый столбец. Для открытых свойств сложных типов, должны генерироваться столбцы для всех открытых свойств по тем же правилам, что и для объекта контейнера.

Написать дополнительно два своих (не использовать встроенные!) атрибута для управления процессом генерации столбцов.

Необходима возможность с помощью атрибутов управлять:
а) заголовком сгенерированного столбца;
б) форматом отображения данных в столбце.

Ключевая технология для выполнения данного задания: рефлексия.

Решение:

Для успешного выполнения данного задания надо продемонстрировать умения работать с метаданными среды .Net Framework и аккуратно выполнить задание. Кроме того, в задании есть два «подводных камня», которые не все смогли обойти.

Во-первых, нигде не сказано, что свойства сложных типов объектов, отображаемых в таблице, не могут иметь значение null. Таким образом, если не учесть этот фактор, при корректно сгенерированных столбцах, во время самого процесса отображения данных в таблицу мы можем получить NullReferenceException. Участники корректно сгенерировавшие столбцы для отображения, но у которых возникала подобная ошибка получали не более 60 баллов за задание.

Во-вторых, объекты, которые мы отображаем в таблице, благодаря тому, что мы так же разворачиваем и их свойства, фактически образуют у нас граф объектов. А раз мы идем по графу никто нам не гарантировал, что у нас не может возникнуть ситуации само-зацикливания. Участники, не предусмотревшие этого в своей реализации, получили за задачу максимум 80 баллов. К большому сожалению в работе только одного участника было полностью отработана ситуация с само-зацикливанием графа объектов. (Он получил 100 баллов за задачу.) Участники, предусмотревшие максимальную глубину рекурсии, при генерации столбцов получили дополнительные баллы, но не максимум».

Ну что, уважаемые конкурсанты, удалось ли после таких развернутых комментариев провести «работу над ошибками»:)? Если у вас еще остались какие-либо вопросы по заданиям – смело задавайте их Вадиму по адресу: marenkovvv@sibedge.com

Надеемся, что данная статья была полезна Вам и помогла ответить на интересующие вопросы. Рады будем снова поучаствовать в мероприятиях такого масштаба, ведь очень круто, что есть такие люди, которым не все равно (это мы про организаторов и конкурсантов) …и нам в том числе! :)

До новых встреч!