Недавно в Самаре прошли два занимательных мероприятия: JavaOpen и JavaDay.
Первое представляло собой турнир по программированию с денежными призами. Второе — конференцию, на которой были озвучены победители турнира.
Конференция
К сожалению, удалось посетить только конференцию. Зал на 150 человек был заполнен наполовину, это при учете того, что мероприятие выпало на рабочий день. Доклады были отличные. Особенно порадовала демонстрация Java FX и Java ME Embedded на Raspberry Pi. И, конечно же, робот с Java ME Embedded на борту.
Материалы конференции доступны по ссылке.
Хочется отметить, что это первый JavaDay в Самаре. На местном телеканале даже показали соответствующий сюжет. Интересен тот факт, что Microsoft TechDays проходят уже достаточно давно, но уже не с тем размахом. Будем надеяться, что ИТ-мероприятия такого формата будут регулярным явлением. А Java-движение будет набирать обороты.
Ну и напоследок самое вкусное — задания турнира, любезно предоставленные их создателем — Павлом Васиным. Тексты заданий оставил без изменений. Ниже есть ответы.
Турнир
Задача турнира была выявить не просто кандидатов со знаниями математики и навыками в спортивном программировании, а людей, которые ближе к производству. Поэтому первое задание было академическим: на знание языка Java, знание хороших и особенно плохих практик при промышленной реализации задач, поддержке, объектно-ориентированном программировании и дизайне классов. Второе задание — практическое, на результат, трудоемкое и без всякого академизма. Как сделаешь, так и хорошо. Для него была разработана система подсказок. Тут задача была в том, чтобы люди сами себе поставили задачу и выбрали инструменты ее решения. При этом правильно оценили и распределили свое время, если не могут справиться или не успевают, то брали бы подсказки.
Задание 1
Представьте, что вы выполняете code review в очень крупной компании, выполняющей разработку программного обеспечения для нужд космической отрасли. Требования к надежности, быстродействию, качеству разработанного программного обеспечения высочайшие.
Просмотрите код, представленный на распечатке, и в таблице, шаблон которой прилагается, укажите все допущенные в данном коде ошибки, неточности, потенциальные проблемы и т.д. Чем больше вы найдете проблем — тем лучше. Каждая заложенная в код проблема, ошибка имеет определенный «вес» в баллах. Ваша задача — набрать в данном тесте максимальное количество баллов.
01 public class EmployeeList extends LinkedList implements List {
02 //Часовые ставки зарплат
03 public static final Float _baseHourSalary = new Float("36.60");
04 public static final Float _high_hour_salary = _maxHourSalary / 4;
05 public static final int _maxHourSalary = _high_hour_salary > 50 ? 110 : 55;
06 public Log log = LogFactory.getLog();
07 private float[] koefs;
08
09 public EmployeeList() {
10 LoadKoefficients();
11 }
12
13 @Override
14 public boolean add(Object o) {
15 for (Object obj : this) {
16 if (!(obj instanceof Employee)) continue;
17 if (o.equals(obj)) return false; //Тот же работник, нельзя добавить два раза
18 if (((Employee)o).getFio() == "Иванов Афанасий Петрович"
19 || ((Employee)o).getFio() == "Михайлова Иннеса Петровна") {
20 //Исправление бага 3244, эти люди уже давно не работают
21 return false;
22 }
23 }
24 return add(o);
25 }
26
27 public void LoadKoefficients() {
28 float[] arr1 = KoefStorage.getKoefArray("ifns_2003_god");
29 log.debug("Коэффициенты ИФНС загружены " + arr1.toString());
30 float[] arr2 = KoefStorage.getKoefArray("ufns_2003_god");
31 koefs = new Float[2000];
32 for (int i = 0; i < arr1.length; i++) koefs[i] = arr1[i];
33 for (int i = 0; i < arr2.length; i++) koefs[i + arr1.length] = arr2[i];
34 recalculateKoeffs(); //Пересчет коэффициентов на текущий месяц
35 }
36
37 public void recalculateKoeffs() {
38 for (int i = 0; i < koefs.length; i++)
39 koefs[i] = koefs[i] < 0.88 ? koefs[i] / 4 : koefs[i] / 6;
40 }
41
42 public ArrayList getSalaries(LinkedList<Employee> employee) {
43 ArrayList result = new ArrayList(5);
44 for (int i = 0; i < employee.size(); i++) {
45 Employee e = employee.get(i);
46 if (!this.contains(e)) {
47 //Если хотя бы одного человека нет. нам нужно вернуть пустой список
48 return new ArrayList(0);
49 }
50 Employee found = (Employee) this.get(this.indexOf(e));
51 result.add(
52 found.getFio() == "Брутасов Николай Павлович" //Наш директор
53 ? _maxHourSalary : _baseHourSalary);
54 }
55 return result;
56 }
57
58 public LinkedList getSortedView() {
59 DataCollectionsHelper.sortBubble(this, new Comparator() {
60 public int compare(Object o1, Object o2) {
61 if (o1 instanceof Employee && o2 instanceof Employee) {
62 return ((Employee)o1).getTableNumber() - ((Employee)o2).getTableNumber();
63 } else return -1;
64 }
65 });
66 return this;
67 }
68 }
Задание 2
В одном из рассказов Конан-Дойла великий сыщик столкнулся с делом, которое стало настоящей проверкой его дедуктивного метода. Ключом к расследованию оказалась разгадка специального шифрованного языка «пляшущих человечков», с помощью которого преступники вели свою переписку. В ходе дела Шерлок Холмс, используя свой метод, смог вычислить, сколько пляшущих человечков входят в одно слово, а также определил тех из них, которые встречались наиболее часто. Разгадав значение первого слова — «С чего начинаются сообщения? Конечно же с приветствия, дорогой Ватсон! Это элементарно!» — сыщик без труда вычислил и всех остальных. После этого он смог сам поучаствовать в их переписке и разоблачить банду.
Мы предлагаем вам повторить его действия, но с помощью современной техники.
У вас имеется:
1) Компьютер, язык Java, IDE
2) Зашифрованный несложным методом отрывок художественного текста на русском языке
3) Роман «Война и мир» Л.Н. Толстого (если у вас останется много времени после расшифровки, чтобы вам было чем себя занять — можете немного почитать)
4) Набор из 3 подсказок (№1, №2, №3), которые открываются по очереди. Вскрытие каждой подсказки уменьшает возможное количество баллов, которое вы можете получить. Всего 50 баллов, вскрытие каждой подсказки уменьшает эту сумму на 10 баллов.
Казалось бы, не зная ключа, по которому проводилась замена, вскрыть данный шифр невозможно… Но проблема в том, что в современных языках (в русском в том числе) разные буквы встречаются с разной частотой, какие-то часто, какие-то редко. Поэтому такие шифры поддаются т.н. «частотному анализу». При достаточно большом объеме текста частота практически однозначно определит закодированную букву. Но так как у нас зашифрован небольшой отрывок, то в нем возможны некие «перекосы» и для букв с близкими частотами останется неопределенность. Ну что тут поделаешь? Опять вспомнил Шерлока — подставлять, пробовать и пытаться разгадать какие-то характерные буквосочетания или слова, закреплять некоторые «разгаданные» буквы и пробовать снова. Каждое разгаданное слово будет сильно приближать вас к разгадке всего текста. И помните, чем удобнее вы сделаете для себя инструмент для такого анализа, тем быстрее вскроете шифр.
Еще очень поможет, если вы определите самый частый, встречающийся в русском тексте символ — пробел и его частоту.
Мы договорились, что в шифротаблице каждый символ исходного текста может быть зашифрован группой символов? Как узнать ее величину? Тут можно посоветовать несколько способов: проанализировать частоты встречаемости групп символов в зашифрованном тексте простым перебором, начиная с 1. Для правильного количества частоты будут «особенными». Можно попробовать найти самую часто-встречающуюся группу символов — это будет пробел и он вам ограничит слова. Ну а по средней длине слова узнать количество букв в шифрогруппе не составит труда (снова спасибо Толстому).
Ответы
Если задания решить не удалось или просто есть желание сверить результаты, то можно воспользоваться ответами:
Если вкратце:
За простые ошибки, вроде обнаружения зацикливания, объявления static-переменных, сравнивания строк на ==, бесконечных рекурсий и т.д. давался 1 балл.
За скрытие ошибки и производительность, вроде целочисленного деления там, где должно быть деление плавающих, или не использование Arrays.copy давалось 2-3 балла
За сложные тайм-бомбы, ошибки в дизайне класса 5 баллов.
Если развернуто (та самая таблица):
Ошибка в коде | Область знаний | Баллы |
Класс уже extends LinkedList писать implements List необязательно | Стиль | 1 |
Константы называются не по соглашению (HIGH_HOUR_SALARY должно быть примерно так все) | Стиль | 1 |
Циклическая зависимость при объявлении константы | Поверхность | 1 |
Константы типа Float ничем необоснованы, должно быть float | Поверхность | 1 |
Конструктор new Float(«36.60») ужасен | Поверхность | 1 |
Вычисление _maxHourSalary / 4 даст не ожидаемый результат (из-за целочисленного деления), необходимо явное приведение типа _maxHourSalary к float | Скрытая ошибка | 3 |
Название метода LoadKoefficients не по соглашению (loadKoefficients должно быть) | Стиль | 1 |
Если наследуем список, то должны быть generics (генерики), без них анахронизм | Стиль | 2 |
В конструкторе используется паблик-метод, это опасно в случае наследования | Скрытая ошибка | 3 |
Методы LoadKoefficients и recalculateKoeffs бессмысленно делать пабликами, так как они явно нужны только для внутренней логики работы метода. Их публикация нарушает инкапсуляцию | ООП | 3 |
Судя по методу add у нас ошибка в дизайне класса – это вообще не список, а множество (осуществляется проверка на повторное вхождение). | Дизайн класса | 5 |
Класс ведет себя непонятно как при добавлении НЕ Employee | Скрытая ошибка | 3 |
Сравнение строк на равенство (должно быть equals) | Поверхность | 1 |
Проверка o.getFio() == осуществляется внутри цикла (ничто не мешает проверить снаружи) | Поверхность | 1 |
Порочна сама практика такого исправления «бага 3244», таким образом исправлять баги нельзя никогда | Дизайн класса | 3 |
В список есть много способов добавить элемент, но переопределен только add. Значит приведенная в переопределенном методе логика будет срабатывать не всегда, что еще хуже самой ошибочной логики | Скрытая ошибка | 3 |
Return add(o) вызывает бесконечную рекурсию. Должно быть super.add(o) | Поверхность | 1 |
«ifns_2003_god» – должно быть вынесено в константу | Стиль | 2 |
В лог дебаг хотелось передать всю распечатку массива, а не ненужный указатель. Вместо arr1.toString() надо было использовать Arrays.deepToString | Логическая ошибка | 2 |
Распечатка всего массива – дело долгое, лучше сначала проверить, включен ли вообще режим дебага | Производительность | 3 |
Массив Float[] не дает нам ничего кроме постоянных боксингов/анбоксингов. Должно быть float[] | Поверхность | 1 |
Копирование массивов нужно делать с помощью Arrays.copy | Производительность | 3 |
Почему массив именно из 2000 элементов? А что если загруженных будет больше или меньше? | Логическая ошибка | 2 |
Куча magic numbers в recalculateKoeffs | Стиль | 2 |
Слишком жестко зашита логика в классе по обработке данных, эти части логики обычно сильно изменяются, так писать классы нельзя (логика зашита в recalculateKoeffs, .getFio() == ) | Дизайн класса | 5 |
Чем обусловлена любовь к LinkedList и наследование именно от него? Какие в данном классе есть к этому предпосылки? Никаких! | Дизайн класса | 5 |
Чем вообще обусловлено наследование? Здесь оно совсем не отвечает задаче класса (нужно было использовать композицию, а не наследование) | ООП | 5 |
Нет программирование к интерфейсу (очень много ссылок на конкретные реализации ArrayList, LinkedList, которых нужно было избежать) | ООП | 2 |
new ArrayList(5) — а почему именно 5? magic number | Стиль | 2 |
Проход по списку циклом for i=0 и последующий get непроизводительный (особенно для LinkedList). Надо использовать for each | Производительность | 3 |
Возвращение пустого списка ArrayList(0), правильно использовать константу EMPTY_LIST или метод emptyList в Collections (по куче причин) | Скрытая ошибка, Производительность | 3 |
Вообще логика возврата пустого списка, если один из элементов входного списка не найден внутри крайне сомнительная и корявая | Дизайн класса | 3 |
Недокументированные public-методы. Как вообще догадаться, что эти методы делают? | Стиль | 2 |
Это получение элемента из списка ужасно this.get(this.indexOf(e)) | Поверхность | 1 |
Почему sortBubble а не Collections.sort? | Поверхность | 1 |
Анонимный компаратор создается каждый раз при вызове метода. Можно было бы записать его в поле класса, а еще лучше в статическое поле | Производительность | 3 |
Если сравниваемые элементы не Employee, то выдается меньше. Это пример непонятно какого поведения класса (не говоря уж о нарушении контракта компаратора) | Логическая ошибка | 3 |
Компаратор в виде разности имеет в себе скрытую ошибку (для слишком больших или маленьких чисел) | Скрытая ошибка | 3 |
Возвращение некого внешнего View на ваш список методом сортировки вашего списка крайне корявый дизайн класса (не говоря уж о том, что это нарушает инкапсуляцию) | Дизайн класса | 4 |
ИТОГО | 95 |
P.S. Судя по всему, если в Самаре и был JUG, то давно не функционирует. Может ли кто-нибудь подсказать так ли это?
Автор: Twelver