Практика по Java

202 (АУ, MIT-2016) группа

Юрий Литвинов

Студент TODO №1 №2 №3 №4 №5 Тест 1 №6 №7 №9 №10 №12 Тест 2 Тест 3 №13 Тест 4
108 Хеш-таблица Хеш-таблица-2 Матрицы Trie ZipFile! Maybe Дерево LinkedHashMap FP MyTreeSet Стековый калькулятор Streams Reflector Injector SmartList Допзадача MyPriorityQueue
Varfolomeev Alexander 15
Абрамов Дмитрий 4
Алфёров Василий 5
Бартош Григорий 4
Василенко Елизавета 11
Вишняков Кирилл 4
Гладков Александр 17
Голубцов Владислав 4
Ерохина Алина 5
Казаков Дмитрий 4
Казначеев Дмитрий 3
Киракосян Александр 6
Кириленко Андрей 4
Купоросов Василий 3
Недиков Костя 4
Смирдин Андрей 4
Тух Игорь 6
Ютман Михаил 5

Задачи

Тест 4. 27.12.17
  1. MyPriorityQueue

    Реализовать очередь с приоритетами, имеющую следующие операции:

    • add(E e) --- добавляет элемент в очередь
    • poll() --- возвращает элемент с наибольшим приоритетом и удаляет его из очереди
    • size() --- возвращает число элементов в очереди
    • clear() --- очищает очередь
    • iterator() --- возвращает итератор, обхоящий элементы в порядке приоритета
    • Конструктор без параметров
    • Конструктор, принимающий Comparator<? super E>

    Если очередь создана конструктором без параметров, в качестве приоритетов
    должен использоваться натуральный порядок (определяемый Comparable<E>), если с компаратором, то
    приоритет определяется компаратором. Наивысшим считается приоритет элемента, наименьший
    с точки зрения порядка. Для элементов с одинаковым приоритетом должно выполняться правило "первым вошёл - первым вышел". PriorityQueue из стандартной библиотеки использовать нельзя.

    Ожидается максимум логарифмическая трудоёмкость основных операций.

Домашняя работа 13. 23.12.17
  1. Допзадача
    • С помощью рефлексии реализовать класс Serialization с двумя статическими функциями:
      • void serialize(Object, OutputStream)
      • Записывает состояние полей переданного объекта в поток
      • T deserialize(InputStream, Class<T>)
      • Создаёт экземпляр класса и инициализирует его поля данными из потока
    • Считается, что в сериализации/десериализации используются объекты:
      • классы которых имеют публичный конструктор без параметров
      • типы полей ограничены примитивными типами и строками
Тест 3. 20.12.17
Юнит-тесты, которые должны проходить
  1. SmartList
    • Необходимо создать класс SmartList, реализующий интерфейс java.util.List.
    public class SmartList<E> implements List<E> {
        ...
    }
    
    • Основная идея — реализовать изменяемый список так, чтобы он был оптимизирован для хранения небольшого количества элементов, но при этом в него можно было добавить произвольное их число.

    • В классе должно быть объявлено ровно два поля:

      • типа int для хранения размера
      • ссылочного типа для хранения данных
    • В зависимости от текущего размера списка в поле для данных хранятся значения разных типов:

      • Если список пуст, то значение этого поля должно быть null
      • Если в списке ровно один элемент, то в этом поле должна храниться ссылка на него
      • Если в списке от 2 до 5 элементов, то в этом поле хранится массив размера 5, элементы которого указывают на соответствующие элементы списка
      • Иначе в этом поле хранится ссылка на обычный ArrayList, в котором хранятся все элементы
    • В классе должно быть определено два конструктора:

      • По умолчанию (без параметров), создает пустой список
      • Принимающий один параметр — коллекцию, элементы которой должны быть добавлены в список
    • Maven/Gradle проект

    • При реализации рекомендуется наследовать ваш класс от AbstractList (хотя он добавляет еще одно поле), и нельзя наследоваться от ArrayList.

    • Стандартные операции коллекций (add/contains/remove и т.д.) должны работать за то же время, что и аналогичные методы в стандартной реализации ArrayList.

Тест 2. 13.12.17
Классы Injector и исключения
Презентация с условием
  1. Injector

    Необходимо реализовать статический метод Injector.initialize, эмулирующий работу контейнера Dependency Injection. Его основная задача – создать объект класса, полное имя которого передано в параметре rootClassName. Также в метод передается набор доступных классов реализаций. Для каждого такого класса за один initialize должно быть создано не более одного экземпляра. Гарантируется, что каждый класс содержит ровно один конструктор.

Домашняя работа 12. 06.12.17
Презентация с пары (задача про рефлексию)
  1. Reflector

    Реализовать класс Reflector с методами

    • printStructure(Class<?> someClass) -- создаёт файл с именем someClass.java.
      • В нём описан класс SomeClass со всеми полями, методами, внутренними и вложенными классами и интерфейсами
      • Методы без реализации
      • Модификаторы видимости и static должны быть такими, как в переданном классе
      • Объявления полей, методов и вложенных классов должны сохранить генериковость
    • diffClasses(Class<?> a, Class<?> b)
      • Выводит все поля и методы, различающиеся в двух классах

    Реализовать тест, печатающий класс, компилирующий полученный файл, грузящий то, что получилось и сравнивающий с исходным

    При этом:

    • Работаем только с классами – интерфейсы, enum-ы и т.д. можно не обрабатывать
    • Можно считать, что внутри нет enum-ов и аннотаций
    • При сравнении двух классов учтите, что <E extends Object> и <E> – это одно и то же

    Дедлайн: 21.12.2017 23:59

Домашняя работа 11. 29.11.17
Базы данных и Java (туториал)
Базы данных и Java (презентация)
Домашняя работа 10. 22.11.17
Особенности Java 7 (презентация)
  1. Streams

    Дедлайн: 06.12.2017, 10:00

Домашняя работа 9. 15.11.17
Enum-ы и mock-объекты (презентация)
  1. Стековый калькулятор

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

    • должен быть класс Calculator, который, собственно, занимается вычислением выражения в обратной польской записи
    • Calculator должен принимать в конструктор стек
    • Calculator в тестах должен тестироваться независимо, принимая mock-объект, симулирующий стек

    Дедлайн: 29 ноября, 10:00

Домашняя работа 8. 08.11.17
Экосистема open source-проектов (презентация)
Домашняя работа 7. 25.10.17
Интерфейс, который надо реализовать
Презентация с пары
  1. MyTreeSet

    Необходимо реализовать интерфейс MyTreeSet с использованием бинарного дерева:

    • в реализации должны быть конструктор без параметров и конструктор с параметром типа Comparator<...>
    • методы descendingIterator и descendingSet не должны копировать данные
    • удаление по итератору можно не реализовывать
    • стандартную библиотеку использовать нельзя, разрешается пользоваться Abstract* классами
    • дополнительная задача (+2 балла)
      • инвалидация итератора при модификации дерева

    Дедлайн – 14 ноября, 23:59

Домашняя работа 6. 18.10.17
Разбор контрольной, задача
  1. FP

    Реализовать аналоги стандартных интерфейсов для работы с лямбда-функциями:

    • Абстрактные классы (или интерфейсы)
      • Function1 — функция одного аргумента (“f(x)”)
      • Function2 — функция от двух аргументов (“f(x, y)”)
      • Predicate — предикат для одного аргумента
      • Нужна какая-нибудь иерархия, связывающая эти классы (интерфейсы)
      • Сигнатуры всех классов и методов должны быть максимально общими
    • Должны быть реализованы методы:
      • Function1.compose — композиция — принимает “Function1 g”, возвращает “g(f(x))”, например, int x = f.compose(g).apply(239);
      • Function2.compose — композиция — принимает “Function1 g”, возвращает “g(f(x, y))”
      • Function2.bind1 — bind первого аргумента — принимает первый аргумент, возвращает “f(_, y)”
      • Function2.bind2 — bind второго аргумента — принимает второй аргумент, возвращает “f(x, _)”
      • Function2.curry — каррирование, конвертация в “Function1” — например, f = (x, y) -> x + y, f(5) = x -> x + 5
    • Предикаты:
      • Predicate.or и Predicate.and
      • принимают один предикат в качестве аргумента, возвращают предикат, который ведет себя, как дизъюнкция/конъюнкция текущего предиката и предиката-аргумента
      • семантика ленивая, как у || и &&
      • Predicate.not принимает 0 аргументов, возвращает предикат-отрицание текущего предиката
      • Константные предикаты:
      • Predicate.ALWAYS_TRUE
      • Predicate.ALWAYS_FALSE
      • Можно не поля, а методы
    • Отдельный класс Collections с методами:
      • map — принимает f и a, применяет f к каждому элементу ai и возвращает список [f(a1), ..., f(an)]
      • filter — принимает p и a, возвращает список, содержащий элементы ai, на которых p(ai) == true
      • takeWhile — принимает p и a, возвращает список с началом a до первого элемента ai, для которого p(ai) == false
      • takeUnless — то же, что и takeWhile, только для p(ai) == true
      • foldr / foldl — принимает функцию двух аргументов, начальное значение и коллекцию, работает так: https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%91%D1%80%D1%82%D0%BA%D0%B0_%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D0%B0
      • a – Iterable

    Дедлайн – 8 ноября, 23:59

Тест 1. 11.10.17
  1. LinkedHashMap

    Необходимо реализовать интерфейс Map так, чтобы во время итерации объекты выдавались в порядке добавления.
    Пользоваться LinkedHashMap и другими библиотечными контейнерами нельзя, Abstract* можно.
    Удаление по итератору можно не реализовывать, в возвращаемом Set<Entry<E>> должны работать только iterator и size.
    Инвалидацию итераторов можно не реализовывать.
    Асимптотика всех операций должна соответствовать ожидаемой от HashMap-а.

Домашняя работа 5. 04.10.17
IDEA static analyzers, задачи
  1. Maybe

    Реализовать generic-класс Maybe (контейнер из одного элемента, в котором может быть, а может и не быть значение) со следующими методами:

    • public static <T> Maybe<T> just(T t) --- создаёт новый объект типа Maybe, хранящий в себе значение t
    • public static <T> Maybe<T> nothing() --- создаёт новый объект типа Maybe без хранимого значения
    • public T get() --- возвращает хранимое значение, если оно есть, бросает исключение (своё), если значения нет
    • public boolean isPresent() --- возвращает true, если значение есть, и false, если нет
    • public <U> Maybe<U> map(Function<?, ?> mapper) --- принимает функцию и возвращает новый объект Maybe со значением, полученным применением функции к хранимому значению, или пустой Maybe, если текущий Maybe пустой. Например, Maybe.just(2).map(x -> x * 2) == Maybe.just(4), Maybe.nothing().map(x -> x * 2) == Maybe.nothing(). Подумать, что надо подставить на место вопросиков в Function<?, ?>, чтобы было хорошо.

    Прочитать числа из файла:

    • если на строке действительно число, возвращается “Maybe” с числом
    • если на строке записано не число, возвращается “Maybe” с null

    Возвести в квадрат прочитанные числа и сохранить их в новый файл

    • Записать в новый файл "null", если в исходном файле на этой строке было не число
  2. Дерево

    Реализовать generic-множество с использованием двоичного дерева поиска (не обязательно сбалансированного) с операциями

    • add
    • contains
    • size

    Дедлайн --- 18 октября

Домашняя работа 4. 27.09.17
Система штрафов
Задача про архивацию
  1. ZipFile!

    Программе на вход подается путь и регулярное выражение. По указанному пути надо найти все zip-архивы и извлечь все файлы, имена которых удовлетворяют регулярному выражению.

    Дедлайн: 23:59 11.10.2017

Домашняя работа 3. 20.09.17
Потоки в Java, Git (презентация)
  1. Trie

    Реализовать бор (http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D0%BE%D1%80)
    Должны быть поддержаны следующие методы:

    • boolean add(String element); (возвращает true, если такой строки ещё не было, работает за O(|element|))
    • boolean contains(String element); (работает за O(|element|))
    • boolean remove(String element); (возвращает true, если элемент реально был в дереве, работает за O(|element|))
    • int size(); (работает за O(1))
    • int howManyStartsWithPrefix(String prefix); (работает за O(|prefix|))

    Также бор должен реализовывать интерфейс с методами:

    • void serialize(OutputStream out) throws IOException;
    • void deserialize(InputStream in) throws IOException; (заменяет старое дерево данными из стрима)

    Дедлайн: 04.10.2017

Домашняя работа 2. 13.09.17
Стайлгайд Google (рекомендую использовать, только отступы пусть будут 4 пробела, а не 2)
Годная документация по Maven
Юнит-тестирование и системы сборки (конспект)
Юнит-тестирование и системы сборки (презентация)
  1. Хеш-таблица-2

    Написать юнит-тесты и комментарии к задаче про хеш-таблицу.

  2. Матрицы
    • Вывести элементы двумерного массива NxN (N - нечетное) в порядке обхода по спирали с началом в центре.
    • Отсортировать столбцы матрицы по первым элементам.

    Написать скрипт сборки для этой задачи на Maven или Gradle, научиться собирать и запускать из консоли.
    Юнит-тесты и комментарии обязательны.

Домашняя работа 1. 06.09.17
Презентация с пары
Конспект с пары
  1. Хеш-таблица

    Реализовать хеш-таблицу с ключами и значениями типа String, у которой есть следующие функции:

    • int size() --- количество ключей в хеш-таблице
    • boolean contains(String key) --- true, если данный ключ содержится в хеш-таблице
    • String get(String key) --- возвращает значение по ключу, или null, если такого значения нет
    • String put(String key, String value) --- положить в хеш-таблицу значение value по ключу key и вернуть то, что было по этому ключу раньше, либо null, если ничего не было
    • String remove(String key) --- удалить значение по заданному ключу из хеш-таблицы и вернуть удалённое значение, либо null, если такого значения не было
    • void clear() --- очистить хеш-таблицу

    Классы стандартной библиотеки типа HashMap или List использовать нельзя, список надо реализовать вручную отдельным классом.

    Задание надо сдать в виде пуллреквеста из отдельной ветки в собственный репозиторий, в который меня надо добавить как коллаборатора. Мой профиль на гитхабе: https://github.com/yurii-litvinov. Ожидаются комментарии в формате JavaDoc. Ссылку на пуллреквест надо скинуть сюда.

    Жесткий дедлайн: 23:59:59 20 сентября, но начинать пытаться сдавать надо гораздо раньше.

© 2014-2018 HwProj