coding_tasks_description.txt

+00) Для строки найдите первое слово четной длины.

+0) Напишите Java-программу, чтобы определить, является ли строка или число палиндромом, или нет

+1) Написать функцию, которая принимает на вход 3 целых числа и возвращает их медиану.
Медиана — средний элемент коллекции, если бы она была отсортирована.

+2) Задача. Дана строка из слов, разделённых пробелом. Нужно поменять порядок слов в строке на противоположный. Например, для строки cats are funny нужно вернуть funny are cats.

+3) Даны два массива: [1, 2, 3, 2, 0] и [5, 1, 2, 7, 3, 2]
Нужно вернуть пересечение множеств, но с повторением элементов [1, 2, 2, 3] (порядок неважен)

+4) Дана строка (возможно, пустая), состоящая из букв A-Z: AAAABBBCCXYZDDDDEEEFFFAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBB
Нужно написать функцию RLE, которая на выходе даст строку вида:
A4B3C2XYZD4E3F3A6B28
И сгенерирует ошибку, если на вход пришла невалидная строка.
Пояснения: Если символ встречается 1 раз, он остается без изменений; Если символ повторяется более 1 раза, к нему добавляется количество повторений.

+5) Дан список интов, повторяющихся элементов в списке нет. Нужно преобразовать это множество в строку, сворачивая соседние по числовому ряду числа в диапазоны. Примеры:
[1,4,5,2,3,9,8,11,0] => "0-5,8-9,11"
[1,4,3,2] => "1-4"
[1,4] => "1,4"

+6) Дан массив из нулей и единиц. Нужно определить, какой максимальный по длине подинтервал единиц можно получить, удалив ровно один элемент массива.
[1, 1, 0]

-7) Даны даты заезда и отъезда каждого гостя. Для каждого гостя дата заезда строго раньше даты отъезда (то есть каждый гость останавливается хотя бы на одну ночь).
В пределах одного дня считается, что сначала старые гости выезжают, а затем въезжают новые.
Найти максимальное число постояльцев, которые одновременно проживали в гостинице (считаем, что измерение количества постояльцев происходит в конце дня).
sample = [ (1, 2), (1, 3), (2, 4), (2, 3)]

+8) Sample Input ["eat", "tea", "tan", "ate", "nat", "bat"]
Sample Output [ ["ate", "eat", "tea"], ["nat", "tan"], ["bat"] ]
Т.е. сгруппировать слова по "общим буквам".

9) Слияние отрезков:
Вход: [1, 3] [100, 200] [2, 4]
Выход: [1, 4] [100, 200]

10) Дан массив точек с целочисленными координатами (x, y). Определить, существует ли вертикальная прямая, делящая точки на 2 симметричных относительно этой прямой множества.
Note: Для удобства точку можно представлять не как массив [x, y], а как объект {x, y}

+11) Даны две строки.
Написать функцию, которая вернёт True, если из первой строки можно получить вторую, совершив не более 1 изменения (== удаление / замена символа).

12) Дан список интов и число-цель. Нужно найти такой range, чтобы сумма его элементов давала число-цель.
elements = [1, -3, 4, 5]
target = 9
result = range(2, 3) # because elements[2] + elements[3] == target

+13) Даны две строки строчных латинских символов: строка J и строка S. Символы, входящие в строку J, — «драгоценности», входящие в строку S — «камни».
Нужно определить, какое количество символов из S одновременно являются «драгоценностями». Проще говоря, нужно проверить, какое количество символов из S входит в J.
Это очень простая разминочная задача, к которой прилагаются решения на нескольких языках программирования, чтобы участники могли освоиться с проверяющей системой.
Алгоритм достаточно простой: из строки с «драгоценностями» необходимо построить множество,
затем пройтись по строке с «камнями» и каждый символ проверить на вхождение в это множество.
Используйте такую реализацию множества, чтобы гарантировать линейную сложность полученного решения, несмотря на то,
 что входные строки очень короткие и поэтому возможно сдать даже квадратичный по сложности алгоритм.

14) Требуется найти в бинарном векторе самую длинную последовательность единиц и вывести её длину.
Алгоритм решения следующий: пройтись по всем элементам массива; встретив единицу, нужно увеличить счётчик длины текущей последовательности, а, встретив ноль, нужно обнулить этот счётчик. В конце нужно вывести максимальное из значений, которые принимал счётчик.
Проверьте, что правильно обрабатываете ситуацию, когда массив заканчивается на искомую последовательность единиц. При аккуратной реализации такая ситуация не потребует специальной обработки.
Постарайтесь использовать лишь константный объём дополнительной памяти.
15) Дан упорядоченный по неубыванию массив целых 32-разрядных чисел. Требуется удалить из него все повторения.

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

При решении этой задачи также не нужно использовать дополнительную память.

16) Дано целое число n. Требуется вывести все правильные скобочные последовательности длины 2 ⋅ n, упорядоченные лексикографически (см. https://ru.wikipedia.org/wiki/Лексикографический_порядок).
В задаче используются только круглые скобки.
Пример 1
Ввод: 2
Вывод:
(())
()()
Пример 2
Ввод: 3
Вывод:
((()))
(()())
(())()
()(())
()()()
Это пример относительно сложной алгоритмической задачи. Будем генерировать последовательность по одному символу; в каждый момент мы можем к текущей последовательности приписать либо открывающую скобку, либо закрывающую. Открывающую скобку можно дописать, если до этого было добавлено менее n открывающих скобок, а закрывающую — если в текущей последовательности количество открывающих скобок превосходит количество закрывающих. Такой алгоритм при аккуратной реализации автоматически гарантирует лексикографический порядок в ответе; работает за время, пропорциональное произведению количества элементов в ответе на n; при этом требует линейное количество дополнительной памяти.

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

17) Эта достаточно простая задача — типичный пример задачи, для решения которой необходимо использовать ассоциативные массивы. При решении нужно учитывать, что символы могут повторяться, поэтому необходимо использовать не множества, а словари. Поэтому решение будет следующим: составим из каждой строки по словарю, который для каждого символа будет хранить количество его повторений; затем сравним получившиеся словари. Если они совпадают, необходимо вывести единицу, в противном случае — ноль.

Альтернативное решение: отсортируем входные строки, а затем сравним их. Это решение хуже в том, что оно работает медленнее, а также меняет входные данные. Зато такое решение не использует дополнительной памяти.

18) Даны k отсортированных в порядке неубывания массивов неотрицательных целых чисел, каждое из которых не превосходит 100. Требуется построить результат их слияния: отсортированный в порядке неубывания массив, содержащий все элементы исходных k массивов.

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

-19) Морской бой. Посчитать кол-во кораблей на поле.

20) Заполнить квадратное поле возрастающей последовательностью цифр "улиткой" по спирали от краёв к центру.

21) Список точек на плоскости задан координатами (x,y). Верните K точек наиболее близких к началу координат (0,0).

Вход: (0,1), (2,2), (5,5); K=2
Выход: (0,1), (2,2)

- https://leetcode.com/problems/counting-bits/

- https://leetcode.com/problems/3sum/description/

-22) Из Яндекса
/**
 * Some implementation of this interface is assumed to be predefined.
 */
interface PagedStreamReader {

    /**
     * Read next bytes from stream into `atLeastKibibyteArray`, at most 1024 bytes are read.
     *
     * @param atLeastKibibyteArray output array, at least 1024 bytes in size.
     * @return < 0 on error, == 0 on eof, > 0 - bytes read, no more than 1024.
     */
    int readAtMostKibibyte(byte[] atLeastKibibyteArray);
}

/**
 * This class needs to be implemented.
 */
public class BufferedStreamReader {

    public BufferedStreamReader(PagedStreamReader pagedStreamReader) {
        this.pagedStreamReader = pagedStreamReader;
    }

    /**
     * Read next bytes from `pagedStreamReader` into `atLeastSizeArray`, at most `size` bytes are read.
     *
     * @param atLeastSizeArray output array, at least `size` bytes in size.
     * @param size attempt to read at most this many bytes, greater than zero.
     * @return < 0 on error, == 0 on eof, > 0 - bytes read, no more than `size`.
     */
    public int readSize(byte[] atLeastSizeArray, int size) {
    }
}

//public static void System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)