Практика по Java

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

Тимофей Брыксин

Студент TODO №1 №2 №3 №4 №5 Тест 1 №6 №7 №8 №9 №10 Тест 2 Тест 3 №11 Тест 4 №12 №13
100 ZipFile! Maybe Set HashMap FP TreeSet Mock Reflector Injector SmartList Serialization PQueue TF WAR!
Алехина Ольга 3
Егоров Владимир 4
Елисеева Мария 5
Ермилов Антон 5
Карлина Любовь 4
Крючков Максим
Лупуляк Ольга 5
Мурашкина Наташа 4
Никифоровская Анна 6
Орлова Александра 5
Парадовский Юрий 5
Правилов Михаил 5
Савон Юлия 12
Саютин Дмитрий 3
Соликов Павел 5
Фарутин Вадим 6
Федоров Александр 6
Федотов Александр 5
Шаркова Дарья 6
Швецова Анна 6

Задачи

Домашняя работа 13. 10.02.18
  1. WAR!

    В некоторой стране n городов, соединенных между собой дорогами различной длины. По каждой дороге можно проехать в обе стороны. В страну вторглась армия захватчиков и захватила город с номером 1. Далее каждый день они пытаются захватывать по одному городу, используя следующий алгоритм. Среди всех еще не захваченных городов выбирается ближайший к любому уже захваченному городу и захватывается. При этом по дорогам двигаются армии, размер которых с некоторым коэффициентом зависит от размера городов, и когда армия атакует город, успех битвы случаен, но зависит от соотношения численностей армий (армии защитников пропорциональны размеру города с таким же коэффициентом). Во входном файле в первой строчке заданы число городов и число дорог. Во второй строчке — коэффициент из условия. В третьей — размеры всех городов. Далее в файле следуют сами дороги в формате: "i j len", i и j — номера городов, len — длина дороги между ними. Задача: вывести результат всех попыток захвата, номера всех городов в порядке захвата, а также и расстояние и путь от каждого захваченного города до города 1. Города нумеруются с 1.

Домашняя работа 12. 05.02.18
  1. TF

    Реализовать Rule для JUnit, повторяющее по функциальности TemporaryFolder: возможность создания/удаления каталогов и файлов.

Тест 4. 27.12.17
  1. PQueue

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

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

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

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

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

    public class SmartList<E> implements List<E> {
    ...
    }

    • Основная идея — реализовать изменяемый список так, чтобы он был оптимизирован для хранения небольшого количества элементов, но при этом в него можно было добавить произвольное их число.

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

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

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

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

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

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

    Тесты, которые должны проходить: https://gist.github.com/yurii-litvinov/85cc529fa7037495af1fa23d350a6b2f.

Тест 2. 13.12.17
Примеры интерфейсов и тестов
  1. Injector

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

    Параметры конструктора определяют зависимости данного класса:

    public class A {
    public A(Interface1 x) {}
    }
    public class B implements Interface1 {}

    Класс A зависит от интерфейса Interface1 (так же зависимостью может быть абстрактный или конкретный класс). Таким образом, чтобы создать объект класса A, можно сначала создать объект класса B и передать его в конструктор. Понятно, что зависимости могут быть несколько более замысловатыми.

    Метод initialize() должен завершиться с исключением AmbiguousImplementationException, если найдено несколько разных классов-реализаций одной и той же зависимости (зависимости – это только те классы и интерфейсы, которые встречаются в конструкторах).
    Метод initialize() должен завершиться с исключением ImplementationNotFoundException, если для какой-то зависимости не найдено ни одной реализации.
    Метод initialize() должен завершиться с исключением InjectionCycleException, если зависимости прямо или косвенно образуют цикл.
    В остальных случаях метод должен вернуть объект класса rootClassName.

Домашняя работа 10. 06.12.17
  1. Reflector

    Реализуйте класс с методами printStructure() и diffClasses().

    Метод printStructure() должен принимать на вход объект someClass типа Class<?>, в результате его работы данного в текущем каталоге должен быть создан java файл c текстом данного класса:
    - Данный файл должен быть валидным, т.е. компилироваться.
    - В файле должен быть описан публичный класс с именем SomeClass.
    - В этом классе должны быть объявлены все поля, методы, внутренние, вложенные классы и интерфейсы.
    - У всех элементов класса должны быть проставлены модификаторы идентичные модификаторам исходного класса.
    - Тип возвращаемого значения у методов должен совпадать с оригинальным.
    - Generic методы и внутренние классы должны сохранить свою generic-сущность.

    Метод diffClasses() должен принимать на вход два класса и выводить на экран все различные поля и методы в этих классах. Должен также присутствовать тест, который получает на вход класс, создает по нему java-файл, компилирует этот файл, загружает полученный класс и сравнивает его с исходным.

    Некоторые замечания:
    - Уделите особое внимание использованию wildcard'ов (? super, ? extends).
    - Считайте, что внутри классов не встречаются enum и аннотации. Поддержка того или другого принесет вам по одному дополнительному баллу за каждое.
    - В метод printStructure() можно передавать только классы. Enum, интерфейсы, аннотации и т.д. можно не обрабатывать.
    - Обратите внимание на обработку примитивных типов, когда возвращаете значение.
    - При сравнении двух классов обратите внимание, что <E extends java.lang.Object> и <E> -- это одно и то же.

    Дедлайн 20 декабря 16:30

Домашняя работа 9. 22.11.17
Особенности Java 7
  1. Streams

    Реализовать с помощью Java Stream API:
    - Методы в FirstPartTasks и SecondPartTasks
    - Тесты в SecondPartTasksTest
    Тесты в FirstPartTasksTest и SecondPartTasksTest должны успешно завершаться. Зависимости для тестов:
    - com.google.guava:guava:19.0
    - junit:junit:4.12

    Дедлайн 6 декабря 16:30

Домашняя работа 8. 15.11.17
Enum и Mock-объекты
  1. Mock

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

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

    Дедлайн: 29 ноября 16:30

Домашняя работа 7. 25.10.17
Презентация
  1. TreeSet

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

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

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

Домашняя работа 6. 18.10.17
Разбор контрольной, Hamcrest
  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 к каждому элементу a_i и возвращает список [f(a_1), ..., f(a_n)]
      • filter() — принимает p и a, возвращает список, содержащий элементы a_i, на которых p(a_i) == true
      • takeWhile() — принимает p и a, возвращает список с началом a до первого элемента ai, для которого p(ai) == false
      • takeUnless() — то же, что и takeWhile, только для p(a_i) == 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

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

Тест 1. 11.10.17
  1. HashMap

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

Домашняя работа 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. Set

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

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

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

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

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

Домашняя работа 3. 20.09.17
  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 howManyStartWithPrefix(String prefix); (работает за O(|prefix|))

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

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

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

Домашняя работа 2. 13.09.17
Юнит-тестирование и системы сборки (презентация)
Юнит-тестирование и системы сборки (конспект)
  1. HashTable++

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

  2. Spiral

    Реализовать класс, который 1) выводит элементы двумерного массива NxN (N нечетное) в порядке обхода по спирали с началом в центре и 2) умеет сортировать столбцы матрицы по первым элементам. Написать скрипт сборки для этой задачи на Maven или Gradle, научиться собирать и запускать из консоли. Юнит-тесты и javadoc обязательны.

    Жесткий дедлайн на обе задачи: 23:59 27.09.17

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

    Реализовать хеш-таблицу с ключами и значениями типа 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/jzuken. Ожидаются комментарии в формате JavaDoc. Ссылку на пуллреквест надо скинуть сюда.

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

© 2014-2018 HwProj