BST – Двоичные деревья поиска

Задача

Разработать класс, реализующий функциональность дерева двоичного поиска.

Ссылка на условие http://java.mazurok.com/word-of-week/bst

Тесты

input output
put S 11.11 Ok
put E 22.22 Ok
put A 33.33 Ok
put R 44.44 Ok
put H 55.55 Ok
put C 66.66 Ok
put X 77.77 Ok
put M 88.88 Ok
size 8
min (A->33.33)/2
max (X->77.77)/1
print L0: (S->11.11)/8
.L1: (E->22.22)/6
..L2: (A->33.33)/2
…L3: (C->66.66)/1
..L2: (R->44.44)/3
…L3: (H->55.55)/2
….L4: (M->88.88)/1
.L1: (X->77.77)/1
delete E Ok
size 7
min (A->33.33)/2
max (X->77.77)/1
print L0: (S->11.11)/7
.L1: (H->55.55)/5
..L2: (A->33.33)/2
…L3: (C->66.66)/1
..L2: (R->44.44)/2
…L3: (M->88.88)/1
.L1: (X->77.77)/1
exit N/A

Критерий тестирования

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

Формат вывода:

Команды min и max выводят одиночный узел в следующем формате: (ключ->значение)/кол-во узлов

Команда print выводит дерево по уровням, каждая строчка имеет следующий формат: уровень: (ключ->значение)/кол-во узлов

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

  1. Класс CountingBST, реализующий функциональность дерева двоичного поиска с подсчетом количества узлов в дереве
  2. Класс CountingBSTTestApp, реализующий тестовое приложение

Класс CountingBST

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

  1. put — помещает ключ и значение в дерево
  2. get — извлекает значение по клчу
  3. size — возвращает количество узлов дерева
  4. min — находит узел с минимальным ключом
  5. max — находит узел с максимальным ключом
  6. delete — удаление по Хиббарду ( Coursera presentation )
  7. print — печать дерева

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

Класс CountingBSTTestApp

Данный класс реализует тестовое приложение для класса CountingBST. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста. Он реализует командный интерпритатор, где каждая команда вызывает соответствующий публичный метод тестируемого класса. По-этому тест представляет собой текстовый файл с командами для стандартного потока ввода с консоли.

Ссылка на Ideone: https://ideone.com/b0xrPX

 

acm.timus.ru №2002. Тестовое задание

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время: 0.5 секунды
Память 64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…
Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!
Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:
  1. «register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
  2. «login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
  3. «logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».
Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!
И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq n\leq 100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

Исходные данные Результат
6register vasya 12345

login vasya 1234

login vasya 12345

login anakin C-3PO

logout vasya

logout vasya

success: new user addedfail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Код

Данная программа представляет собой типичный пример использования таблицы символов, согласно терминологии Coursera. Для доступа к учетным записям используется интерфейс Map, а для реализации самой базы данных учетных записей — объект типа TreeMap. Учетная запись пользователей реализована в виде одного элемента типа Map.entry, где имя пользователя — это ключ, а атрибуты учетной записи — пароль и флаг подключен/отключен — реализованы в виде отдельной структуры AccountInfo, которая является значением этого ключа.

Время работы Выделено памяти
0.124 1 928 КБ
 Ссылка на Ideone: https://ideone.com/3Y2W4z

Segmented Array

Задача

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

При написании класса, реализующего данный интерфейс необходимо стремиться к максимальной эффективности выполнения наиболее частых операций и учитывать особенности использования отражённые в следующей таблице с заданиями:

Big
array
Small
|T|
Often Student
get() set() indexOf() min()/max()
1 0 0 0 1 0 Швандт

 


Тест

input output
set 2 2 H ok
set 3 3 E ok
set 4 5 L ok
set 6 6 O ok
set8 8 W ok
set 9 9 O ok
set 10 10 R ok
set  11 11 L ok
set 12 12 D ok
set 13 13 ! ok
set 14 14 ! ok
set 15 15 ! ok
show segment#0 { null null H E }
segment#1 { L L O null }
segment#2 { W O R L }
segment#3 { D ! ! ! }
exit   N/A

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

  1. Интерфейс SegmentedArray, который описывает заданную функциональность доступа к сегментированному массиву
  2. Класс SegmentedArrayImpl, имплементирует данный интерфейс
  3. Класс SegmentedArrayApp, который имплементирует тестевое приложение, он содержит метод main и вспомогательные методы ввода данных и вывода результата.

Интерфейс SegmentedArray

Методы интерфейса:

  • indexOf — возвращает абсолютный индекс элемента в массиве начиная с заданного индекса.
  • set — присваивает последовательности элементов массива одно и тоже значение в заданном диапазоне
  • min — возвращает минимальный элемент в заданном диапазоне

Класс SegmentedArrayImpl

Данный класс реализует интерфейс SegmentedArray с учетом требования задачи, а именно:

  • Допускаются массивы очень большого размера
  • Методы indexOf и max должны работать максимально быстро

Используемый алгоритм

С учетом условий задачи был выбран алгориnм, описанный в статье Segmented Tree.

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

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

Алгоритм поиска нужного сегмента реализован с помощью методов findSegmentIndex и compareIndexToSegment.

Первый метод — это обычный двоичный поиск в массиве отсортированных элементов, которыми являются номера сегментов в порядке их следования. Данный метод заимствован из Coursera. Внутри он использует второй метод compareIndexToSegment для проверки попадания заданного абсолютного индекса в сегмент с заданным номером, т. е. он реализует нобходимый для бинарного поиска метод сравнения, где фактически абсолютный индекс сравнивается с сегментом с целью его выбора.

Методы родительского интерфейса

  • indexOf — находит нужный сегмент посредством findSegmentIndex и далее — индекс в сегменте, затем производит поиск в этом и последующих сегментах нужного значения
  • set — находит первый и последний сегменты посредством findSegmentIndex, которые покрывают входные индексы диапазона, затем выполняет запись начиная с начального сегмента и индекса в нем, и заканчивая последним сегментом и индексом в нем.
  • min — находит диапазон сегментов для поиска таким же образом, как и метод set и находит минимальное значения в данном диапазоне сегментов

Собственные методы

  • конструктор — принимает 2 аргумента — размер и количество сегментов
  • compareIndexToSegment — проверяет, попадает ли абсолютный индекс в данный сегмент и возвращает одно из значений: -1 — если индекс перед сегментом, 0 — если попадает в сегмент, 1 — если после сегмента
  • findSegmentIndex — находит сегмент, который содержит данный абсолютный индекс используя бинарный поиск в массиве
  • show — диагностическая печать содержимого

Класс SegmentedArrayApp

Данный класс реализует тестовое приложение для интерфейса. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста.

Методы класса

  1. parseTextToTokens — разбирает входной текст на слова используя известный класс StringTokenizer и возвращает вектор слов
  2. strToInt — превращает строку в число с подавлением исключения NumberFormatException
  3. main — реализует простейший интерпритатор команд, в котором каждая команда представляет соостветствующий интерфейсный метод, состоит из цикла, где в каждом цикле посредством объекта Scanner читается полностью входная строка, которая затем разбирается на команду и ее аргументы посредством parseTextToTokens, это в дальнейшем превращается в соответствующие вызовы интерфейсных методов.

Ссылка на Ideone: https://ideone.com/BknxiN

Java Collections Framework: Map. Частотный словарь.

Задача 1:

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

Задача 2:

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


 

Тест

input output
aaa for bbb aaa for if
%EOF%
 Word frequency statistics:

aaa    ,    2,    0.250000
bbb    ,    1,    0.125000
for    ,    2,    0.250000
if    ,    1,    0.125000
—————————————

Select max frequent token from:  for do to while if
=> selected is: for

To be, or not to be: that is the question:
Whether ’tis nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles,
And by opposing end them? To die: to sleep;
No more; and by a sleep to say we end
The heart-ache and the thousand natural shocks
That flesh is heir to, ’tis a consummation
Devoutly to be wish’d. To die, to sleep;
To sleep: perchance to dream: ay, there’s the rub;
For in that sleep of death what dreams may come
When we have shuffled off this mortal coil,
Must give us pause: there’s the respect
That makes calamity of so long life;
For who would bear the whips and scorns of time,
The oppressor’s wrong, the proud man’s contumely,
The pangs of despised love, the law’s delay,
The insolence of office and the spurns
That patient merit of the unworthy takes,
When he himself might his quietus make
With a bare bodkin? who would fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death,
The undiscover’d country from whose bourn
No traveller returns, puzzles the will
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all;
And thus the native hue of resolution
Is sicklied o’er with the pale cast of thought,
And enterprises of great pith and moment
With this regard their currents turn awry,
And lose the name of action. — Soft you now!
The fair Ophelia! Nymph, in thy orisons
Be all my sins remember’d.

%EOF%

Word frequency statistics:

And    ,    5,    0.007321
Be    ,    1,    0.001464
But    ,    1,    0.001464
Devoutly    ,    1,    0.001464
For    ,    2,    0.002928
Is    ,    1,    0.001464
Must    ,    1,    0.001464
No    ,    2,    0.002928
Nymph    ,    1,    0.001464
Ophelia    ,    1,    0.001464
Or    ,    1,    0.001464
Soft    ,    1,    0.001464
Than    ,    1,    0.001464
That    ,    3,    0.004392
The    ,    7,    0.010249
Thus    ,    1,    0.001464
To    ,    5,    0.007321
When    ,    2,    0.002928
Whether    ,    1,    0.001464
With    ,    2,    0.002928
a    ,    5,    0.007321
ache    ,    1,    0.001464
action    ,    1,    0.001464
after    ,    1,    0.001464
against    ,    1,    0.001464
all    ,    2,    0.002928
and    ,    7,    0.010249
arms    ,    1,    0.001464
arrows    ,    1,    0.001464
awry    ,    1,    0.001464
ay    ,    1,    0.001464
bare    ,    1,    0.001464
be    ,    3,    0.004392
bear    ,    3,    0.004392
bodkin    ,    1,    0.001464
bourn    ,    1,    0.001464
by    ,    2,    0.002928
calamity    ,    1,    0.001464
cast    ,    1,    0.001464
coil    ,    1,    0.001464
come    ,    1,    0.001464
conscience    ,    1,    0.001464
consummation    ,    1,    0.001464
contumely    ,    1,    0.001464
country    ,    1,    0.001464
cowards    ,    1,    0.001464
currents    ,    1,    0.001464
d    ,    3,    0.004392
death    ,    2,    0.002928
delay    ,    1,    0.001464
despised    ,    1,    0.001464
die    ,    2,    0.002928
does    ,    1,    0.001464
dread    ,    1,    0.001464
dream    ,    1,    0.001464
dreams    ,    1,    0.001464
end    ,    2,    0.002928
enterprises    ,    1,    0.001464
er    ,    1,    0.001464
fair    ,    1,    0.001464
fardels    ,    1,    0.001464
flesh    ,    1,    0.001464
fly    ,    1,    0.001464
fortune    ,    1,    0.001464
from    ,    1,    0.001464
give    ,    1,    0.001464
great    ,    1,    0.001464
grunt    ,    1,    0.001464
have    ,    2,    0.002928
he    ,    1,    0.001464
heart    ,    1,    0.001464
heir    ,    1,    0.001464
himself    ,    1,    0.001464
his    ,    1,    0.001464
hue    ,    1,    0.001464
ills    ,    1,    0.001464
in    ,    3,    0.004392
insolence    ,    1,    0.001464
is    ,    2,    0.002928
know    ,    1,    0.001464
law    ,    1,    0.001464
life    ,    2,    0.002928
long    ,    1,    0.001464
lose    ,    1,    0.001464
love    ,    1,    0.001464
make    ,    2,    0.002928
makes    ,    2,    0.002928
man    ,    1,    0.001464
may    ,    1,    0.001464
merit    ,    1,    0.001464
might    ,    1,    0.001464
mind    ,    1,    0.001464
moment    ,    1,    0.001464
more    ,    1,    0.001464
mortal    ,    1,    0.001464
my    ,    1,    0.001464
name    ,    1,    0.001464
native    ,    1,    0.001464
natural    ,    1,    0.001464
nobler    ,    1,    0.001464
not    ,    2,    0.002928
now    ,    1,    0.001464
o    ,    1,    0.001464
of    ,    15,    0.021962
off    ,    1,    0.001464
office    ,    1,    0.001464
opposing    ,    1,    0.001464
oppressor    ,    1,    0.001464
or    ,    1,    0.001464
orisons    ,    1,    0.001464
others    ,    1,    0.001464
outrageous    ,    1,    0.001464
pale    ,    1,    0.001464
pangs    ,    1,    0.001464
patient    ,    1,    0.001464
pause    ,    1,    0.001464
perchance    ,    1,    0.001464
pith    ,    1,    0.001464
proud    ,    1,    0.001464
puzzles    ,    1,    0.001464
question    ,    1,    0.001464
quietus    ,    1,    0.001464
rather    ,    1,    0.001464
regard    ,    1,    0.001464
remember    ,    1,    0.001464
resolution    ,    1,    0.001464
respect    ,    1,    0.001464
returns    ,    1,    0.001464
rub    ,    1,    0.001464
s    ,    5,    0.007321
say    ,    1,    0.001464
scorns    ,    1,    0.001464
sea    ,    1,    0.001464
shocks    ,    1,    0.001464
shuffled    ,    1,    0.001464
sicklied    ,    1,    0.001464
sins    ,    1,    0.001464
sleep    ,    5,    0.007321
slings    ,    1,    0.001464
so    ,    1,    0.001464
something    ,    1,    0.001464
spurns    ,    1,    0.001464
suffer    ,    1,    0.001464
sweat    ,    1,    0.001464
take    ,    1,    0.001464
takes    ,    1,    0.001464
that    ,    4,    0.005857
the    ,    15,    0.021962
their    ,    1,    0.001464
them    ,    1,    0.001464
there    ,    2,    0.002928
this    ,    2,    0.002928
those    ,    1,    0.001464
thought    ,    1,    0.001464
thousand    ,    1,    0.001464
thus    ,    1,    0.001464
thy    ,    1,    0.001464
time    ,    1,    0.001464
tis    ,    2,    0.002928
to    ,    10,    0.014641
traveller    ,    1,    0.001464
troubles    ,    1,    0.001464
turn    ,    1,    0.001464
under    ,    1,    0.001464
undiscover    ,    1,    0.001464
unworthy    ,    1,    0.001464
us    ,    3,    0.004392
we    ,    4,    0.005857
weary    ,    1,    0.001464
what    ,    1,    0.001464
whips    ,    1,    0.001464
who    ,    2,    0.002928
whose    ,    1,    0.001464
will    ,    1,    0.001464
wish    ,    1,    0.001464
with    ,    1,    0.001464
would    ,    2,    0.002928
wrong    ,    1,    0.001464
you    ,    1,    0.001464
—————————————

Select max frequent token from:  else for do to while if
=> selected is: to

#include <iostream>
using namespace std;

int main() {

for( int i = 0; i < 10; i++ )
{
if( i % 2 == 0 )
{
cout << «Even» << endl;
}
else
{
cout << «Odd» << endl;
}
}
return 0;
}

%EOF%

Word frequency statistics:

Even    ,    1,    0.032258
Odd    ,    1,    0.032258
cout    ,    2,    0.064516
else    ,    1,    0.032258
endl    ,    2,    0.064516
for    ,    1,    0.032258
i    ,    4,    0.129032
if    ,    1,    0.032258
include    ,    1,    0.032258
int    ,    2,    0.064516
iostream    ,    1,    0.032258
main    ,    1,    0.032258
namespace    ,    1,    0.032258
return    ,    1,    0.032258
std    ,    1,    0.032258
using    ,    1,    0.032258
—————————————

Select max frequent token from:  else for do to while if
=> selected is: else

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

  1. Интерфейс FrequencyVocabulary, который описывает заданную функциональность доступа к частотному словарю
  2. Класс FrequencyVocabularyImpl, имплементирует данный интерфейс
  3. Класс FrequencyVocabularyTest, который имплементирует тестевое приложение, он содержит метод main и вспомогательные методы ввода данных и вывода результата.

Интерфейс FrequencyVocabulary:

Интерфейс подразумевает, что частотный словарь представлен в виде стандартного класса TreeMap. В качестве ключа типа String выступает само слово, а в качестве значения — специальная структура Statistic, содержащая статистику по данному слову, а именно — число вхождений count и частоту frequency.

Интерфейс содержит два метода:

  1. getMap — возвращает сам частотный словарь как TreeMap объект.
  2. selectMaxFreqToken — выполняет условие 2-го задания, а именно — выбирает наиболее часто встречаемое слово из заданного набора, передаваемого как аргумент типа Set

Класс FrequencyVocabularyImpl:

Класс строит частотный словарь на основе входного текста. Словарь храниться в виде приватного члена типа TreeMap. Для разбора текста на слова используется известный класс StringTokenizer. Конструктор создает класс в 2 прохода. За первый проход заполняется словарь, где для каждого слова заносится статистика с подсчитанным счетчиком вхождений count и пока еще нулевым frequency, однако, вычисляется общий счетчик всех слов totalCount. За второй проход по уже известной статистике каждого слова рассчитывается его frequency как count /totalCount.

Метод containsDigits добавляет проверку для отсеивания лекскм, содержащих цифры согласно требованию 1-й задачи.

Выборка слова с максимальной частотой согласно второй задаче реализована в методе selectMaxFreqToken, где выполняется цикл по всем заданным словам и выбирается слово с максимальным count.

Класс FrequencyVocabularyTest

В данном классе реализуется приложение, которое тестирует интерфейсные методы частотного словаря. Он состоит из следующих этапов:

  1. Ввод исходного текста, так как текст может допускать любое количество символов новой строки, и поскольку затруднительно определить признак конца текста как конец файла, в качестве признака конца текста используется спец. лексема %EOF% , которая должна быть после последней строки текста.
  2. Создание объекта частотного словаря на основе введенного текста, в качестве разделителей используются все известные символы, которые не явл. буквой или цифрой.
  3. Проход по элементам словаря и печать статистики.
  4. Тестирование метода, определяющего максимально встречающиеся слова из набора заданных

Примечание: Ввиду того, что затруднительно за один раз ввести с консоли исходный текст для 1-го задания и список слов для 2-го, набор слов для 2-го задания задается в коде непосредственно, а именно do, to, for, while и if.

Код на Ideone: https://ideone.com/jxJ4rU