About Teletype
Join
Adab
@adab
hexlet-challenges
October 2, 2020

JS: Введение в ООП Испытания

Поиск в двоичном дереве

Node.js

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

Реализуйте и экспортируйте по умолчанию класс, который реализует представление узла. Конструктор класса принимает на вход значение ключа (число), и двух детей, которые в свою очередь также являются узлами. Дерево может быть создано пустым.

Класс должен содержать методы:

  • Геттер getKey() — возвращает ключ. Если дерево пустое, возвращает null.
  • Геттеры getLeft(), getRight() — возвращают соответственно левого и правого ребёнка. Если ребёнок в узле отсутствует, геттер возвращает null.
  • search(key) — выполняет поиск узла в правильном двоичном дереве по ключу и возвращает узел. Если узел не найден, возвращается null.

Примеры

const tree = new Node(9,
  new Node(4,
    new Node(3),
    new Node(6,
      new Node(5),
      new Node(7))),
  new Node(17,
    null,
    new Node(22,
      new Node(20),
      null)));

const node = tree.search(6);
node.getKey(); // 6
node.getLeft().getKey(); // 5
node.getRight().getKey(); // 7

tree.search(35); // null
tree.search(3).getLeft(); // null

Подсказки

Успешных завершений: 86%

Построение двоичного дерева

Двоичное дерево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

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

Node.js

Реализуйте и экспортируйте по умолчанию класс, который реализует представление узла.

Класс должен содержать:

  • Геттер getKey() — возвращает ключ.
  • Геттеры getLeft(), getRight() — возвращают соответственно левого и правого ребёнка. Если ребёнок в узле отсутствует, геттер возвращает null.
  • Метод insert(key) — выполняет добавление узла, формируя правильное двоичное дерево.

Примеры

const tree = new Node();
tree.insert(9);
tree.insert(17);
tree.insert(4);
tree.insert(3);
tree.insert(6);

tree.getKey(); // 9
tree.getLeft().getKey(); // 4
tree.getRight().getKey(); // 17
tree.getLeft().getLeft().getKey(); // 3
tree.getLeft().getRight().getKey(); // 6

Подсказки

Успешных завершений: 85%

Агрегация в двоичном дереве

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

Node.js

Реализуйте следующие методы в классе:

  • getCount() — возвращает количество узлов в дереве.
  • getSum() — возвращает сумму всех ключей дерева.
  • toArray() — возвращает одномерный массив содержащий все ключи.
  • toString() — возвращает строковое представление дерева.
  • every(fn) — проверяет, удовлетворяют ли все ключи дерева условию, заданному в передаваемой функции.
  • some(fn) - проверяет, удовлетворяет ли какой-либо ключ дерева условию, заданному в передаваемой функции.

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

Примеры

const tree = new Node(9,
    new Node(4,
      new Node(8),
      new Node(6,
        new Node(3),
        new Node(7))),
    new Node(17,
      null,
      new Node(22,
        null,
        new Node(20))));

tree.getCount() // 9
tree.getSum(); // 96
tree.toArray(); // [9, 4, 8, 6, 3, 7, 17, 22, 20]
tree.toString(); // '(9, 4, 8, 6, 3, 7, 17, 22, 20)'

tree.every((key) => key <= 22); // true
tree.every((key) => key < 22); // false
tree.some((key) => key < 4); // true
tree.some((key) => key > 22); // false

Подсказки

  • Двоичное дерево
  • Для реализации каждого из методов потребуется выполнить обход всех узлов дерева.
  • Вспомните принцип работы метода reduce для массивов.

Успешных завершений: 81%

Сбалансированное двоичное дерево

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

Node.js

Реализуйте метод isBalanced(), который проверяет дерево на сбалансированность. Он возвращает true, если количество узлов в левом и правом поддеревьях каждого узла отличается не более, чем на 2. В ином случае метод должен вернуть false.

Сбалансированное дерево

Несбалансированное дерево

В узле 5 количество узлов в левом поддереве равно 4, а в правом — 1. Разница составляет 3. Это больше, чем максимально допустимая разница по условию задачи (2).

Примеры

const tree1 = new Node(4,
  new Node(3,
    new Node(2)));

tree1.isBalanced(); // true

const tree2 = new Node(4,
  new Node(3,
    new Node(2,
      new Node(1))));

tree2.isBalanced(); // false

Успешных завершений: 80%

Круг

Circle.js

Реализуйте и экспортируйте по умолчанию класс Circle описывающий круг. У круга есть только одно свойство - его радиус. Реализуйте методы getArea() и getCircumference(), которые вычисляют и возвращают площадь и длину окружности соответственно.

Примеры

const circle = new Circle(3);
circle.getArea(); // 28.274...

Подсказки

  • Площадь круга: πr2
  • Длина окружности: 2*πR

Успешных завершений: 96%

Генератор случайных чисел

Random.js

Реализуйте генератор случайных чисел, представленный классом Random. Интерфейс объекта включает в себя три функции:

  • Конструктор. Принимает на вход seed, начальное число генератора псевдослучайных чисел.
  • getNext() — метод, возвращающий новое случайное число.
  • reset() — метод, сбрасывающий генератор на начальное значение.

Экспортируйте класс по умолчанию.

Примеры

const seq = new Random(100);
const result1 = seq.getNext();
const result2 = seq.getNext();

result1 !== result2; // true

seq.reset();

const result21 = seq.getNext();
const result22 = seq.getNext();

result1 === result21; // true
result2 === result22; // true

Подсказки

Успешных завершений: 87%

Генератор квадратов

Square.js

Реализуйте и экспортируйте по умолчанию класс Square для представления квадрата. У квадрата есть только одно свойство — сторона. Реализуйте метод getSide(), возвращающий значение стороны.

Пример

const square = new Square(10);
square.getSide(); // 10

SquaresGenerator.js

Реализуйте класс SquaresGenerator со статическим методом generate(), принимающим два параметра: сторону и количество экземпляров квадрата (по умолчанию 5 штук), которые нужно создать. Функция должна вернуть массив из квадратов. Экспортируйте класс по умолчанию.

Пример

const squares = SquaresGenerator.generate(3, 2);
// [new Square(3), new Square(3)];

Успешных завершений: 92%

Url

Url.js

В данном испытании вам предстоит реализовать класс Url, который позволяет извлекать из HTTP адреса, представленного строкой, его части. Экспортируйте класс по умолчанию.

Класс должен содержать конструктор и методы:

  • конструктор - принимает на вход HTTP адрес в виде строки.
  • getScheme() - возвращает протокол передачи данных (без двоеточия).
  • getHostName() - возвращает имя хоста.
  • getQueryParams() - возвращает параметры запроса в виде пар ключ-значение объекта.
  • getQueryParam() - получает значение параметра запроса по имени. Если параметр с переданным именем не существует, метод возвращает значение заданное вторым параметром (по умолчанию равно null).

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

Примеры

const url = new Url('http://yandex.ru:80?key=value&key2=value2');
url.getScheme(); // 'http'
url.getHostName(); // 'yandex.ru'
url.getQueryParams();
// {
//   key: 'value',
//   key2: 'value2',
// };
url.getQueryParam('key'); // 'value'
// второй параметр - значение по умолчанию
url.getQueryParam('key2', 'lala'); // 'value2'
url.getQueryParam('new', 'ehu'); // 'ehu'
url.getQueryParam('new'); // null

Подсказки

  • Не используйте в решении устаревшие возможности (Legacy URL API).

Успешных завершений: 82%

#courses#hexlet#hexlet_challenges#hexlet_js_introduction_to_oop#js_introduction_to_oop#js_introduction_to_oop_lessons
Adab
October 2, 2020, 07:18
0 reactions
0 views