Установка и запуск
npm i
, чтобы установить модули.
npm test
, чтобы запустить тесты.
Если надо какие-то определенные тесты игнорировать, добавить x
в начало названия метода, т. е describe
-> xdescribe
, it
-> xit
.
Если надо запустить только какие-то определенные тесты, по аналогии добавить f
.
Single-linked list
Реализовать класс SingleLinkedList
и вспомогательный для него ListNode
. Экспортироваться из модуля будет только основной, так что вспомогательный можно назвать как угодно.
- вспомогательный класс, как следует из названия, является элементом списка, содержит в себе значение
value
и ссылку на следующий элементnext
; остальные детали реализации несущественны - конструктор основного класса принимает любое кол-во аргументов: если они присутствуют, из них сразу собирается список
- реализованы методы:
at(i)
- возвращает значение, лежащее в i-ом узле, либоundefined
, если длина списка меньшеget length
- геттер, который возвращает понятно чтоinsert(value, i)
- добавляет значение в список; еслиi
не указан, то вставляется в конец, если указан, то вставляется перед i-м узлом; еслиi
больше, чемlength + 1
, то кидает ошибкуremove(i)
- удаляет i-й узел и возвращает значение в нем; еслиi
не указан, то удаляется последний узел; кидает ошибку, если длина списка меньшеmap
filter
(возвращаютSingleLinkedList
)reduce
sort
(возвращает новый список, не модифицирует исходный)
- реализован метод
[Symbol.iterator]
, чтобы объект можно было использовать там, где ожидается Iterable, такой какArray
,Map
,Set
,NodeList
и т. д.
Sort strategy
Учимся применять ООП, знакомимся с паттерном Strategy.
Реализовать классы, в которых реализуется какой-нибудь вид сортировки, соответствующие такому интерфейсу (назовем его Sorter
):
- конструктор принимает функцию-компаратор, которая принимает два параметра
(a, b)
и возвращает число:- отрицательное, если
a
меньше; - положительное, если
a
больше; - 0, если они равны;
- отрицательное, если
- объект предоставляет метод
sort(array)
, который возвращает новый экземпляр массива, отсортированный согласно компаратору.
Т. е. можно будет сделать что-то вроде:
const numSorter = new Sorter((a, b) => a - b);
sorter.sort([3, 1, 2]); // [1, 2, 3]
Реализовать 2 таких класса: один сортирующий каким-нибудь алгоритмом со сложностью O(n^2)
, другой со сложностью O(n * log(n))
. Например, можно взять сортировку пузырьком и быструю сортировку.
Запуск тестов
В файле sort/test.js
сделать нужные импорты в строчках 7 и 8.
HashTable
Реализовать класс HashTable
классическим не-жс способом, через массив и самостоятельное хеширование ключа.
Ключами могут быть числа и строки.
Функцию хеширования выбрать самостоятельно.
Таблица должна балансироваться, поддерживать Load Factor не больше 8.
get(key)
- возвращает значение, соответствующее ключу, либоundefined
, если такого ключа нетset(key)
- добавить или заменить значение по ключуremove(key)
- удалить пару ключ-значениеfrom(iterable)
- статический метод, возвращает новый экземплярHashTable
, составленный из пар ключ-значение вiterable
(может быть, например, массивом). Пары могут быть представлены массивами из двух элементов либо объектами с полямиkey
иvalue
, надо поддерживать оба случая.[Symbol.iterator]
- обходит все пары ключ-значение, отдаёт их в виде массива из двух элементов,[key, value]
. Порядок обхода не важен, но должны быть пройдены все пары без повторов.