Задачи Код-Ката

2015-07-29

CL
code-kata

Строки и массивы

Реализуйте алгоритм, определяющий, все ли символы в строке встречаются один раз. При выполнении этого задания нельзя использовать дополнительные структуры данных.
Реализуйте функцию void reverse(char* str) на С или C++. Функция должна циклически сдвигать строку, заканчивающуюся символом null.
Для двух строк напишите метод, определяющий, является ли одна строка перестановкой другой.
Напишите метод, заменяющий все пробелы в строке символами ‘%20’. Можно предположить, что длина строки позволяет сохранить дополнительные символы и “истинная” длина строки известна, (Примечание: при реализации метода на Java используйте символьный массив.)

Пример:
	Ввод: "Mr John Smith "
	Вывод: "Mr%20John%20Smith"

Реализуйте метод, осуществляющий сжатие строки, на основе счетчика повторяющихся символов. Например, строка aabcccccaaa должна превратиться в а2b1с5аЗ. Если “сжатая” строка оказывается длиннее исходной, метод должен вернуть исходную строку.
Дано: изображение в виде матрицы размером NxN, где каждый пиксель занимает 4 байта. Напишите метод, поворачивающий изображение на 90°.
Напишите алгоритм, реализующий следующее условие: если элемент матрицы в точке MxN равен 0, то весь столбец и вся строка обнуляются.
Допустим, что существует метод isSubstring, проверяющий, является ли одно слово подстрокой другого. Для двух строк, S1 и S2, напишите код проверки, получена ли строка S2 циклическим сдвигом S1, используя только один вызов метода isSubstring (пример: слово waterbottle получено циклическим сдвигом erbottlewat).

Связные списки

Напишите код, удаляющий дубликаты из несортированного связного списка. Дополнительно: Как вы будете решать задачу, если запрещается использовать временный буфер?
Реализуйте алгоритм для поиска в односвязном списке k-го элемента с конца.
Реализуйте алгоритм, удаляющий узел из середины односвязного списка (доступ дан только к этому узлу).

Пример:
	Ввод: узел с из списка a->b->c->d->e
	Вывод: ничего не возвращается, но новый список имеет вид: a->b->d->e

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

Пример:
	Ввод: (7->1->6) + (5->9->2). Это означает 617 + 295.
	Вывод: 2->1->9, что означает 912.
Дополнительно:
	Решите задачу, предполагая, что цифры записаны в прямом порядке.
	Ввод: (6 -> 1 -> 7) + (2 -> 9 -> 5). Это означает 617 + 295.
	Вывод: 9 - > 1 - > 2, что означает 912.

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

Пример:
	Ввод: А- >в->с->о->Е->с (предыдущий узел с)
	Вывод: с

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

Стеки и очереди

Опишите, как можно использовать один одномерный массив для реализации трех стеков.
Как реализовать стек, в котором кроме стандартных функций push и pop будет использоваться функция min, возвращающая минимальный элемент? Оценка времени работы функций push, pop и min — 0(1).
Представьте стопку тарелок. Если стопка слишком высокая, она может развалиться. В реальной жизни, когда высота стопки превысила бы некоторое значение, мы начали бы складывать тарелки в новую стопку. Реализуйте структуру данных SetOfStacks, имитирующую реальную ситуацию. Структура SetOfStacks должна состоять из нескольких стеков, новый стек создастся, как только предыдущий достигнет порогового значения. Методы SetOfStacks.push() и SetOfStacks.рор() должны работать с общим стеком (со всей структурой) и должны возвращать те же значения, как если бы у нас был один большой стек. Дополнительно: Реализуйте функцию popAt(int index), которая осуществляет операцию pop в указанный под-стек.
В задаче про Ханойскую башню задействованы 3 башни и N дисков разных размеров, которые нужно переместить, (больший диск нельзя класть на меньший). Имеются следующие ограничения: 1. за один раз можно переместить только один диск; 2. диски перемещаются только с вершины одной башни на другую башню; 3. диск можно положить только поверх большего диска. Напишите программу перемещения дисков (с первой башни на последнюю) с использованием стеков.
Создайте класс MyQueue, который реализует очередь с использованием двух стеков.
Напишите программу сортировки стека но возрастанию. Можно использовать дополнительные стеки для хранения элементов, но нельзя копировать элементы в другие структуры данных (например, в массив). Стек поддерживает следующие операции: push, pop, peek, isEmpty.
В приюте для животных есть только собаки и кошки, а работа осуществляется в порядке очереди. Люди должны каждый раз забирать “самое старое” (по времени пребывания в питомнике) животное, но могут выбрать кошку или собаку (животное в любом случае будет “самым старым”). Нельзя выбрать любое понравившееся животное. Создайте структуру данных, обслуживающую эту систему и реализующую операции enqueue, dequeueAny, dequeueDog и dequeueCat. Вы должны использовать встроенную структуру данных LinkedList.

Деревья и графы

Реализуйте функцию, проверяющую сбалансированность бинарного дерева. Предположим, что дерево считается сбалансированным, если разница высот двух поддеревьев любого узла не превышает 1.
Разработайте алгоритм поиска маршрута между двумя узлами для направленного графа.
Напишите алгоритм создания бинарного дерева поиска с минимальной высотой для отсортированного (но возрастанию) массива.
Для бинарного дерева поиска разработайте алгоритм, создающий связный список, состоящий из всех узлов заданной глубины (для дерева с глубиной D должно получиться D связных списков).
Реализуйте функцию проверки, является ли бинарное дерево бинарным деревом поиска.
Напишите алгоритм поиска “следующего” узла для заданного узла в бинарном дереве поиска. Можно считать, что у каждого узла есть ссылка на его родителя.
Создайте алгоритм и напишите код поиска первого общего предка двух узлов бинарного дерева. Постарайтесь избежать хранения дополнительных узлов в структуре данных. Примечание: необязательно использовать бинарное дерево поиска.
Дано: два очень больших бинарных дерева: Т1 — с миллионами узлов и Т2 — с сотнями узлов. Создайте алгоритм, проверяющий, является ли Т2 поддеревом Т1. Дерево Т2 считается поддеревом Т1, если существует такой узел n в Т1, что поддерево, “растущее” из n, идентично дереву Т2. (Если вы вырежете дерево в узле n и сравните его с Т2, они окажутся идентичны.)
Дано бинарное дерево, в котором каждый узел содержит число. Разработайте алгоритм, выводящий на печать все пути, сумма значений которых соответствует заданной величине. Обратите внимание, что путь может начинаться и заканчиваться в любом месте дерева.

Поразрядная обработка

Дано: два 32-битных числа N и M и две позиции битов i и j. Напишите метод для вставки M в N так, чтобы число M занимало позицию с бита j по бит i. Можно считать, что j и i имеют такие значения, что число M обязательно поместится в этот промежуток. Если M = 10011, для его размещения понадобится 5 битов между j и i. Если j = 3 и i = 2, число м не поместится в указанный промежуток.

Пример:
	Ввод: N = 10000000000, M = 10011, i = 2, j = 6
	ВЫВОД: N = 10001001100

Дано: вещественное число в интервале между 0 и 1 (например, 0,72), которое было передано как double. Запишите его двоичное представление. Если для представления числа не хватает 32 разрядов, выведите сообщение об ошибке.
Дано: положительное число. Выведите ближайшие наименьшее и наибольшее числа, которые имеют такое же количество единичных битов в двоичном представлении.
Объясните, что делает код: ((n & (n-1)) == 0).
Напишите функцию, определяющую количество битов, которые необходимо изменить, чтобы из целого числа A получить целое число B.

Пример:
	Ввод: 31,14
	Вывод: 2

Напишите программу, меняющую местами четные и нечетные биты числа. Количество инструкций должно быть наименьшим (нужно поменять местами биты 0 и 1, 2 и 3 и т. д.).
Массив A[i…n] содержит целые числа от 0 до n, но одно число отсутствует. В этой задаче мы не можем получить доступ к любому числу в массиве A с помощью одной операции. Элементы массива А хранятся в двоичном виде, а доступ к ним осуществляется только при помощи команды извлечь j-й бит из A[i], имеющей фиксированное время выполнения. Напишите код, обнаруживающий отсутствующее целое число. Можно ли выполнить эту задачу за время O(n)?
Изображение с монохромного экрана сохранено как одномерный массив байтов, так что в одном байте хранится информация о восьми соседних пикселах. Ширина изображения w кратна 8 (байты соответствуют столбцам). Высоту экрана можно рассчитать, зная длину массива и ширину экрана. Реализуйте функцию drawHorizontalLine(byte[] screen, int width, int x1, int x2, int у), которая рисует горизонтальную линию из точки (x1, у) в точку (х2, у).

Головоломки

Дано: 20 баночек с таблетками. В 19 баночках лежат таблетки весом 1 г, а в одной — весом 1,1 г. Даны весы, показывающие точный вес. Как за одно взвешивание найти банку с тяжелыми таблетками?
Дано: шахматная доска размером 8x8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино: каждая кость домино может закрыть дна квадратика на поле. Можно ли вымостить костями всю доску? Обоснуйте свой ответ.
У вас есть пятилитровый и трехлитровый кувшины и неограниченное количество воды. Как отмерить ровно 4 литра воды? Кувшины имеют неправильную форму, поэтому точно отмерить “половину” кувшина невозможно.
На острове существует правило — голубоглазые люди не могут там находиться. Самолет улетает каждый вечер в 20:00. Каждый человек может видеть цвет глаз других людей, но не знает цвет собственных, никто не имеет права сказать человеку, какой у него цвет глаз. На острове находится не менее одного голубоглазого человека. Сколько дней потребуется, чтобы все голубоглазые уехали?
Дано 100-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с меньшего этажа, оно не разобьется. У вас есть два яйца, найдите N за минимальное количество бросков.
Дано. 100 закрытых замков расположены в длинном коридоре. Человек сначала открывает все сто. Затем он закрывает каждый второй замок. Затем он делает еще один проход - “переключает” каждый третий замок (если замок был открыт, то он его закрывает, и наоборот). На 100-м проходе человек должен “переключить” только замок №100. Сколько замков остались открытыми?

Математика и теория вероятностей

Вам предлагают бросить мяч в баскетбольное кольцо. Существует два варианта игры: Вариант 1: попасть в кольцо с одного броска. Вариант 2: у вас есть три попытки, и нужно попасть в кольцо два раза из трех. Если р - вероятность попадания, то как, в зависимости от значения р, выбрать более выигрышный вариант игры?
Три муравья находятся в вершинах треугольника. Какова вероятность столкновения между какими-либо двумя или всеми тремя муравьями, если муравьи начинают двигаться вдоль сторон треугольника? (Муравей выбирает любое направление с равной вероятностью, скорость движения муравьев одинакова.) Найдите вероятность столкновения для случая, когда n муравьев находятся в вершинах п-угольника.
Какова вероятность пересечения двух прямых, лежащих в одной плоскости?
Используя только оператор суммирования, напишите методы, реализующие операции умножения, вычитания и деления целых чисел.
Для двух квадратов, лежащих в одной плоскости, найдите прямую, которая делила бы эти квадраты пополам. (Стороны квадратов параллельны осям координат.)
Дано: набор точек на плоскости. Найдите прямую линию, которая проходит через большинство точек.
Разработайте алгоритм, позволяющий найти k-е число из упорядоченного числового ряда, в разложении элементов которого на простые множители присутствуют только числа 3, 5 и 7.

Объектно-ориентированное проектирование

Разработайте структуры данных для универсальной колоды карт. Объясните, как разделить структуры данных на подклассы, чтобы реализовать игру в блэкджек.
Предположим, что существует Call-центр с тремя уровнями сотрудников: оператор, менеджер и директор. Входящий телефонный звонок адресуется свободному оператору. Если оператор не может обработать звонок, он автоматически перенаправляется менеджеру. Если менеджер занят, звонок перенаправляется директору. Разработайте классы и структуры данных для этой задачи. Реализуйте метод dispatchCall(), который перенаправляет звонок первому свободному сотруднику.
Разработайте музыкальный автомат, используя принципы ООП.
Разработайте паркинг (автостоянку?), используя принципы ООП.
Разработайте структуры данных для онлайн-библиотеки.
Запрограммируйте игру в пазл. Разработайте структуры данных и объясните алгоритм, позволяющий решить задачу. Вы можете предположить, что существует метод fitsWith, возвращающий значение true в том случае, если два переданных кусочка пазла должны располагаться рядом.
Как вы будете разрабатывать чат-сервер? Предоставьте информацию о компонентах бэкэнда, классах и методах. Перечислите самые трудные задачи, которые необходимо решить.
Правила игры “реверси” следующие. Каждая фишка в игре с одной стороны белая, а с другой — черная. Когда ряд фишек оказывается ограничен фишками противника (слева и справа или сверху и снизу), его цвет меняется на противоположный. Цель - захватить по крайней мере одну из фишек противника. Игра заканчивается, когда у игрока не остается ходов. Побеждает тот, у которого больше фишек на поле. Реализуйте ООП-модель для этой игры.
Объясните, какие структуры данных и алгоритмы необходимо использовать для разработки файловой системы, хранящейся в оперативной памяти. Напишите программный код, иллюстрирующий использование этих алгоритмов.
Спроектируйте и реализуйте хэш-таблицу, использующую связные списки для обработки коллизий.

Рекурсия и динамическое программирование

Ребенок поднимается по лестнице из п ступенек, он может переместиться на одну, две или три ступеньки за один шаг. Реализуйте метод, рассчитывающий количество возможных вариантов прохождения ребенка по лестнице.
Представьте робота, сидящего в левом верхнем углу сетки с координатами X, Y. Робот может перемещаться в двух направлениях: вправо и вниз. Сколько существует маршрутов, проходящих от точки (0,0) до точки (X, Y). Дополнительно: Предположите, что на сетке существуют области, которые робот не может пересекать. Разработайте алгоритм построения маршрута от левого верхнего до правого нижнего угла.
В массиве А[0…n-1] задан “волшебный” индекс — A[i]=i. Учитывая, что массив отсортирован, напишите метод, чтобы найти этот “волшебный” индекс, если он существует в массиве А. Дополнительно: Что произойдет, если значения окажутся одинаковыми?
Напишите метод, возвращающий все подмножества одного множества.
Напишите метод, возвращающий все перестановки строки.
Реализуйте алгоритм, выводящий все корректные (правильно открытые и закрытые) комбинации пар круглых скобок.

Пример:
	Ввод: 3
	Вывод: ((())), (()()), (())(), ()(()), ()()()

Реализуйте функцию заливки краской, которая используется во многих графических редакторах. Дана плоскость (двумерный массив цветов), точка и цвет, которым нужно заполнить все окружающее пространство, окрашенное в другой цвет.
Дано неограниченное количество монет достоинством 25, 10, 5 и 1 цент. Напишите код, определяющий количество способов представления n центов.
Дана шахматная доска размером 8x8. Напишите алгоритм, находящий все варианты расстановки восьми ферзей так, чтобы никакие две фигуры не попадали на одну горизонталь, вертикаль или диагональ. Учитываются не только главные, но и все остальные диагонали.
Дан штабель из n ящиков шириной Wi высотой Hi и глубиной Di. Ящики нельзя поворачивать, добавлять ящики можно только наверх штабеля. Каждый нижний ящик в стопке по высоте, ширине и глубине больше ящика, который находится на нем. Реализуйте метод, позволяющий построить самый высокий штабель (высота штабеля равна сумме высот всех ящиков).
Дано логическое выражение, построенное из символов 0,1, &, | и ^, и имеющее значение result. Напишите функцию, подсчитывающую количество вариантов логических выражений, дающих значение result.

Пример:
	Выражение: 1^0|0|1
	Результат: result = false (0)
	Вывод: 2 способа: 1^((0|0)|1) и 1^(0|(0|1))

Сортировка и поиск

Дано: два отсортированных массива А и В. Размер массива А (свободное место в конце) позволяет поместить в него массив В. Напишите метод слияния массивов В и А, сохраняющий сортировку.
Напишите метод сортировки массива строк, при котором анаграммы группируются друг за другом.
Дано: отсортированный массив из n целых чисел, который был циклически сдвинут произвольное число раз. Напишите код для поиска элемента в массиве. Исходите из предположения, что массив изначально был отсортирован по возрастанию.

Пример:
	Ввод: найдите индекс элемента со значением 5 в {15,16,19,20,25,1,3,4,5,7,10,14)
	Вывод: 8.

Дано: файл размером 20 Гбайт, содержащий строки. Как выполнить сортировку такого файла?
Дано: отсортированный массив, состоящий из строк, разделенных пустыми строками. Напишите метод для обнаружения позиции заданной строки.

Пример:
	Ввод: найдите индекс элемента "ball" в массиве {"at","","","","ball","","","car","","","dad","",""}
	Вывод: 4

Дано: матрица размером MxN, строки и колонки которой отсортированы. Напишите метод нахождения элемента.
Цирк готовит новый аттракцион — пирамида из людей, стоящих на плечах друг у друга. Простая логика подсказывает, что люди, стоящие выше, должны быть ниже ростом и легче, чем люди, находящиеся в основании пирамиды. Учитывая информацию о росте и весе каждого человека, напишите метод, вычисляющий наибольшее число человек в пирамиде.

Пример:
	Ввод (Ht, Wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
	Вывод: максимальная высота пирамиды — 6 человек, сверху вниз: (56,90) (60,95) (65,100) (68,110) (70,150) (75,190)

Вы обрабатываете поток целых чисел. Периодически вам нужно находить ранг числа х (количество значений <= х). Какие структуры данных и алгоритмы необходимы для поддержки этих операций? Реализуйте метод track(int х), вызываемый при генерировании каждого символа, и метод getRankOfNumber(int х), возвращающий количество значений <=х (не включая х).

Пример:
	Поток (в порядке появления): 5,1,4,4,5,9,7,13,3
	getRankOfNumber(1) = 0
	getRankOfNumber(3) = 1
	getRankOfNumber(4) = 3

Масштабируемость и ограничения памяти

Представьте, что вы создаете службу, которая получает и обрабатывает простейшую информацию от 1000 клиентских приложений о курсе акций в конце торгового дня (открытие, закрытие, максимум, минимум). Предположим, что все данные получены, и вы можете сами выбрать формат для их хранения. Как должна выглядеть служба, предоставляющая информацию клиентским приложениям? Вы должны обеспечить развертывание, продвижение, мониторинг и обслуживание системы. Опишите различные варианты службы и обоснуйте свой подход. Вы можете использовать любые технологии и любой механизм предоставления информации клиентским приложениям.
Какие структуры данных вы бы стали использовать в очень больших социальных сетях вроде Facebook или Linkedln? Опишите, как вы будете разрабатывать алгоритм, демонстрирующий круг знакомств или связь человека с человеком (Я -> Боб -> Сюзи -> Джейсон -> Ты).
Дан входной файл, содержащий четыре миллиарда целых чисел. Создайте алгоритм, генерирующий целое число, отсутствующее в файле. У вас есть 1 Гбайт памяти для этой задачи. Дополнительно: а что если у вас есть всего 10 Мбайт?
Дано: массив целых чисел от 1 до N, где N не превышает 32 000. Значения в массиве могут повторяться, значение N - неизвестно. Выведите список всех повторяющихся элементов массива, имея в распоряжении 4 Кбайт оперативной памяти.
Как избежать зацикливаний при разработке поискового робота?
Дано: 10 миллиардов URL-адресов. Как обнаружить все дублирующиеся документы? Дубликатом считается совпадение URL-адреса.
Дано: веб-сервер самой простой поисковой системы. В системе есть 100 компьютеров. обрабатывающих поисковые запросы, которые могут генерировать запрос processSearch(string query) в другой кластер компьютеров, чтобы получить результат. Компьютер, отвечающий на запрос, выбирается случайным образом, вы не можете гарантировать, что одна и та же машина всегда будет получать один и тот же запрос. Метод processSearch очень затратный. Разработайте механизм кэширования новых запросов. Объясните, как при изменении данных будет обновляться кэш.

Тестирование

Найдите ошибку (ошибки) в следующем коде:

1 unsigned int i;
2 for (i - 100; i >= 0; --i)
3 prlntf("%d\n", i);

У вас есть исходный код приложения, которое аварийно завершается после запуска. После десяти запусков в отладчике вы обнаруживаете, что каждый раз программа завершается в разных местах. Приложение однопотоковое и использует только стандартную библиотеку С. Какие ошибки могут вызвать падение приложения? Как вы проверите каждую?
Дано: игра “Шахматы”. В ней реализован метод boolean canMoveTo(int х, int у). Этот метод (часть класса Piece) возвращает результат, по которому можно понять, возможно ли перемещение фигуры на позицию (х, у). Объясните, как вы будете тестировать данный метод.
Как вы проведете нагрузочный тест веб-страницы без использования специальных инструментов тестирования?
Как вы будете тестировать авторучку?
Как вы будете тестировать банкомат, подключенный к распределенной банковской системе?

C и C++ Java

SQL и базы данных

Напишите SQL-запрос для получения списка арендаторов, которые снимают более одной квартиры.
Напишите SQL-запрос для получения списка всех зданий и количества открытых запросов (запросов со статусом open).
Дом № 11 находится на капитальном ремонте. Напишите запрос, который закрывает все запросы на квартиры в этом здании.
Какие существуют типы связей? Объясните, чем они различаются и почему определенные типы лучше подходят для конкретных ситуаций.
Что такое денормализация? Поясните этот процесс.
Нарисуйте диаграмму связей для базы данных, в которой фигурируют компании, клиенты и сотрудники компаний.
Разработайте простую базу данных, содержащую данные об успеваемости студентов, и напишите запрос, возвращающий список лучших студентов (лучшие 10 %), отсортированный по их среднему баллу.

Потоки и блокировки

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

     public class Foo {
          public Foo() { ... }
          public void first() (...)
          public void second() (...)
          public void third() (...)
     }

Один и тот же экземпляр Foo передается трем различным потокам: сначала — ThreadA, потом ThreadB, потом — threadC. Разработайте механизм, гарантирующий, что сначала будет выполнен первый поток, после него - второй, а потом уже — третий.

Дано: класс с синхронизированным методом A и обычным методом С. Если у вас есть два потока в одном экземпляре программы, могут ли они оба выполнить A одновременно? Могут ли они вызвать A и C одновременно?

Задачи умеренной сложности

Напишите функцию, меняющую местами значения переменных, не используя временные переменные.
Разработайте алгоритм, проверяющий результат игры в крестики-нолики.
Напишите алгоритм, вычисляющий число конечных нулей в n!.
Напишите метод, находящий максимальное из двух чисел, не используя операторы if-else или любые другие операторы сравнения.
В игру “Гениальный отгадчик” играют следующим образом: У компьютера есть четыре слота, в каждом слоте находится шар красного (R), желтого (Y), зеленого (G) или синего (B) цвета. Последовательность rggb означает, что в слоте 1 - красный шар, в слотах 2 и 3 - зеленый, 4 — синий. Пользователь должен угадать цвета шаров, например предположить, что там YRGB. Если вы угадали правильный цвет, то вы получаете “хит”. Если вы назвали цвет, который присутствует в раскладе, но находится в другом слоте, вы получаете “псевдохит”. Слот с “хитом” не может быть назван “псевдохитом”. Например, если фактический расклад rgby, а ваше предположение ggrr, то ответдолжен быть: один “хит” и одни “псевдохит”. Напишите метод, который возвращает число “хитов” и “псевдохитов”.
Дано: массив целых чисел. Напишите метод, находящий индексы m и n такие, что для полной сортировки массива, достаточно будет отсортировать элементы от m до n. Минимизируйте m и n (то есть найдите наименьшую такую последовательность).

Пример:
	Ввод: 1, 2,4,7,10,11,7,12,6,7,16,18,19
	Вывод: (3,9)

Дано: целое число. Выведите его значение прописью (например, “одна тысяча двести тридцать четыре”).
Дано: массив целых чисел (положительных и отрицательных). Найдите непрерывную последовательность с самой большой суммой. Возвратите сумму.

Пример:
	Ввод: 2,-8,3,-2,4,-10
	Вывод: 5 (соответствующая последовательность: 3,-2,4)

Разработайте метод, вычисляющий частоту использования заданного слова в книге.
Поскольку XML излишне “многословен”, закодируйте его так, чтобы каждый тег преобразовывался в какое-либо целое значение:

Element --> Tag Attributes END Children END
Attribute --> Tag Value
END --> 0
Tag --> любое предопределенное целое значение
Value --> string value END

Преобразуем XML-код в сжатую форму, подразумевая, что family -> 1, person -> 2, firstName -> 3, lastName -> 4, state -> 5:

<family lastName="McDowell" state="CA">
   <person firstName="Gayle‘‘>Some Message</person>
</family>

После преобразования код будет иметь вид: 1 4 McDowell 5 СА 0 2 3 Gayle 0 Some Message 0 0 Напишите код, выводящий закодированную версию XML-элемента (переданного в объектах Element и Attributes).

Реализуйте метод rand7() на базе метода rand5(). Другими словами, имеется метод, генерирующий случайные числа в диапазоне от 0 до 4 (включительно). Напишите использующий его метод, генерирующий случайное число в диапазоне от 0 до 6 (включительно).
Разработайте алгоритм, обнаруживающий в массиве все пары целых чисел, сумма которых равна заданному значению.
Дано: простая графообразная структура данных BiNode, содержащая указатели на два других узла:

1 public class BiNode {
2 	public BiNode nodel, node2;
3 	public int data;
4 }

Структура данных BiNode может использоваться для представления бинарного дерева (где node1 — левый узел и node2 — правый узел) или двунаправленного связного списка (где node1 — предыдущий узел, a node2 — следующий узел). Реализуйте метод, преобразующий бинарное дерево поиска (реализованное с помощью BiNode) в вунаправленный связный список. Значения должны храниться упорядоченно, а работа алгоритма должна осуществляться в исходной структуре данных.

О, нет! Вы только что закончили длинный документ, но сделали неудачную операцию Поиск/Замена. Вы случайно удалили все пробелы, пунктуацию и все прописные буквы. Предложение I reset the computer. It still didn’t boot! превратилось в iresetthecomputeritstilldidntboot. После того как вы разделите строку на отдельные слова, можно будет восстановить пунктуацию. Большинство слов, кроме имен собственных, находятся в словаре. Для заданного словаря (списка слов) разработайте алгоритм, выполняющий оптимальную деконкатенацию строки. Алгоритм должен минимизировать число нераспознанных последовательностей символов. Строку “jesslookedjustliketimherbrother” необходимо оптимальным образом преобразовать в “JESS looked just like TIM her brother”. Парсер не справился с семью символами, которые были написаны в верхнем регистре.

Задачи повышенной сложности

Напишите функцию суммирования двух чисел без использования “+” и других арифметических операторов.
Напишите метод, тасующий карточную колоду. Колода должна быть идеально перемешана. Перестановки карт должны быть равновероятными. (Вы можете использовать идеальный генератор случайных чисел.)
Напишите метод, генерирующий случайную последовательность m целых чисел из массива размером n. Все элементы выбираются с одинаковой вероятностью.
Напишите метод, который будет подсчитывать количество цифр “2”, используемых в записи чисел от 0 до n (включительно).

Пример:
	Ввод: 25
	Вывод: 9 (2, 12, 20, 21, 22, 23, 24 и 25. Обратите внимание: в числе 22 — две двойки.)

Дано: большой текстовый файл, содержащий слова. Напишите код, который позволяет найти минимальное расстояние (выражаемое количеством слов) между любыми двумя словами в файле. Достаточно ли будет O(1) времени? Сколько памяти понадобится для решения?
Опишите алгоритм для нахождения миллиона наименьших чисел в наборе из миллиарда чисел. Память компьютера позволяет хранить весь миллиард чисел.
Для заданного списка слов напишите алгоритм поиска самого длинного слова, образованного другими словами, входящими в список.

Пример:
	Ввод: cat, banana, dog, папа, walk, walker, dogwalker
	Вывод: dogwalker

Дано: строка s и массив меньших строк T. Разработайте метод поиска s для каждой меньшей строки в T.
Сгенерированные случайным образом числа передаются методу. Напишите программу расчета среднего значения, динамически отслеживающую поступающие новые значения.
Для двух слов одинаковой длины напишите метод, трансформирующий одно слово в другое, изменяя одну букву за один шаг. Каждое новое слово должно присутствовать в словаре.

Пример:
	Ввод: DAMP, LIKE
	Вывод: DAMP -> LAMP -> LIMP -> LIME -> LIKE

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