Братец Кролик

Задача: Дано бинарное дерево поиска и два значения. Вывести все элементы бинарного дерева поиска, находящиеся в заданном значениями интервале. Решение: Решением будет модифицированный вариант обхода дерева, в котором мы исключим из обхода/проигнорируем значения некоторых нод. Для примера, рассмотрим следующее дерево: Предположим, нас интересуют ноды в диапазоне 3 - 7. В этом случае, мы исключаем из обхода ноды 1, 9 и 10. Ноды 2 и 8, несмотря на то, что они не принадлежат искомому диапазону, исключать из обхода нельзя, т.к. ноды 3 и 7 являются потомками нод 2 и 8, соответственно. Мы просто проигнорируем их значения, т.к. они не входят в диапазон. В качестве алгоритма обхода я выбрал inorder, т.к. для бинарного дерева поиска данный алгоритм выведет значения в возрастающем порядке. Обход мож…

Задача: Дана строка, требуется найти самую длинную подстроку, являющуюся палиндромом. Решение: Для поиска подстрок-палиндромов можно использовать следующий способ - начнем процесс поиска с центра строки. Для различных палиндромов центром может являться 1 либо 2 символа. К примеру: 1) "роз узор" - центром является символ "у"; 2) "барокко раб" - центром являются два символа "кк". Для того, чтобы найти самый длинный палиндром с центром на произвольной позиции N, нужно произвести две проверки, для случаев 1 и 2. 1) Строка из одного символа сама по себе является палиндромом. Для того, чтобы выяснить, есть ли более длинный палиндром с центром в символе N, нужно начать сравнивать попарно символы на позициях [N-1, N+1], [N-2, N+2], и т. д. Продолжая сравнение таким образом до первой несовпадающей…

Задача стоит следующим образом: Дана строка и словарь, возможно ли разбить данную строку на слова из словаря? Например, при входных данных: String s = "cчастливтотктосчастливусебядома"; String[] dictionary = new String[] { "счастлив", "тот", "кто", "у", "себя", "дома" }; возвратит true, т.к. строку можно разбить "cчастлив"+"тот"+"кто"+"счастлив"+"у"+"себя"+"дома"; Обдумав проблему, можно понять, что теоретически возможен более чем один вариант разбиения. При этом не каждое разбиение является удачным. Таким образом, если мы добавим в словарь слова "себ" и "яд", то у нас будет два варианта: "cчастлив"+"тот"+"кто"+"счастлив"+"у"+"себя"+"дома" - удачное разбиение. "cчастлив"+"тот"+"кто"+"счастлив"+"у"+"себ" + "яд" ["ома"] - неудачное разбиение, т.к. слово "ома" отсутствует в словаре, а также…

В посте 2008, oбходы деревьев и Microsoft Denmark я рассмотрел "классические" решения итеративного обхода бинарного дерева для различных типов обхода: preorder, inorder и postorder. Однако, из трех алгоритмов простым и понятным является лишь preorder обход, который можно написать абсолютно бездумно. Алгоритмы для inorder и postorder обходов требуют большего времени на размышление, более вдумчивого написания кода, и, в общем, с ними больше мороки. В условиях интервью с топовой компанией вам, как правило, необходимо написать решения для двух подобных задач, затратив приблизительно 15 минут на решение каждой из них. В таких условиях чрезвычайно важно быстро и четко представить код, буквально за считанные минуты, сохранив как можно больше времени на собственно его написание на whiteboard. Кро…

В далеком 2008 году произошло мое первое интервью с крупной софтверной компанией, которое я (неудивительно) бездарно провалил еще на стадии телефонного интервью, т.к. интервьюировался до того только в Казахстане, да и вообще, имел довольно слабое представление о том, как интервьюируют серьезные компании, и к чему следует быть готовым. И вот, когда меня попросили открыть систему для совместного редактирования кода и писать там решение задачи в процессе интервью, это для меня стало _очень_ большим сюрпризом. Тем не менее, это был, пожалуй, самый полезный фейл в моей жизни, после которого я сделал ряд важных выводов. Тем не менее, возвращаясь к тому событию, хотелось бы рассмотреть задачу, которую я зафейлил, а также сходные задачи и их решения. Задача довольно стандартная, реализовать обход…

Основной пост. Код алгоритма:https://gist.github.com/codekrolik/6f8fef669154f75b6316 Тесты:https://gist.github.com/codekrolik/ab806962e7e381c41cbf В данном дереве ноды пронумерованы в соответствие с порядком обхода (inorder). Ниже шаги алгоритма, а также состояние стека, доп.ноды и действия на каждом шаге. Шаг Состояние доп.ноды Состояние стека Действие на данном шаге 1 6 - Инициализация доп.ноды корнем дерева 2 4 6 доп.нода = левый ребенок 6 (4), 6 в стек 3 2 6, 4 доп.нода = левый ребенок 4 (2), 4 в стек 4 1 6, 4, 2 доп.нода = левый ребенок 2 (1), 2 в стек 5 NULL 6, 4, 2, 1 доп.нода = левый ребенок 1 (NULL), 1 в стек 6 NULL 6, 4, 2 доп.нода была NULL; процессим 1 (из стека), доп.нода = правый ребенок 1 (NULL) 7 3 6, 4 доп.нода была NULL; процессим 2 (из стека), доп.нода = правый ребенок…

Основной пост. Код алгоритма:https://gist.github.com/codekrolik/916286dac0524caee4f6 Тесты:https://gist.github.com/codekrolik/ab806962e7e381c41cbf В данном дереве ноды пронумерованы в соответствие с порядком обхода (postorder). Ниже шаги алгоритма, а также состояние стека и действия на каждом шаге. Шаг Состояние стека Действия на данном шаге 1 10, 9, 5 инициализация - корень (10) и его дети (9, 5) 2 10, 9, 5, 4, 3 берем 5, передобавляем 5 и его детей (4, 3) 3 10, 9, 5, 4, 3, 2, 1 берем 3, передобавляем 3 и его детей (2, 1) 3 10, 9, 5, 4, 3, 2 процессим 1 - лист дерева 4 10, 9, 5, 4, 3 процессим 2 - лист дерева 5 10, 9, 5, 4 процессим 3 - родитель 2 6 10, 9, 5 процессим 4 - лист дерева 7 10, 9 процессим 5 - родитель 4 8 10, 9, 8, 6 берем 9, передобавляем 9 и его детей (6, 8) 9 10, 9, 8 про…

Возвращаясь к способам решения проблемы наименьшего общего предка в бинарном дереве (lowest common ancestor), затронутым в Телефонное интервью с Facebook 2014.07.21, 2-й вопрос, хотелось бы прокомментировать освещение данного вопроса в книге Cracking The Coding Interview. У меня есть два издания данной книги, v4 и v5. В обоих, как один из вариантов, предлагается решение следующим путем: начиная с корня дерева, выяснить, находятся ли обе ноды в одном и том же поддереве (слева или справа). В случае, если ноды в разных поддеревьях, проверяемая нода является их наименьшим общим предком. В противном случае, проверить таким же образом корень поддерева, в котором находятся обе искомые ноды. Проблема этого решения в том, что для каждой такой проверки требуется проход по всему дереву, корень котор…

Телефонное интервью с Facebook 07/21/2014: Задача 2 2) Hайти наименьшего общего предка (lowest common ancestor) для двух нод дерева. Ссылки на родителей не являются частью ноды дерева. Это "простое" бинарное дерево, т.е. не являющееся бинарным деревом поиска. Мое решение: получить путь к двум нодам от корня, затем пройти от первого элемента листа до первого отличающегося элемента. Time complexity O(N) где N - количество элементов дерева. https://gist.github.com/codekrolik/ec86d6fcbf6c223b9dc9 Тесты для всех решений https://gist.github.com/codekrolik/2c2b9badeb45bb72fc3f Слабость моего решения в необходимости двух проходов по дереву для формирования путей к нодам. Книга Cracking the coding interview дает несколько другое решение данной проблемы. Этот подход я планирую реализовать в качеств…

Телефонное интервью с Facebook 07/21/2014:

Задача 1
1) Найти количество повторений определенного числа в отсортированном массиве

Мое решение 1:
Бинарным поиском найти одно из чисел, затем пройти по массиву влево и вправо и выяснить, сколько таких элементов существует. Time complexity в худшем случае O(N), в среднем O(log N).
https://gist.github.com/codekrolik/b631aeefc8cde0208b46

Мое решение (2): Бинарным поиском найти число, затем рекурсивно найти левую и правую границу также бинарным поиском на подмассивах. На интервью реализовано не было, словесно описан алгоритм.

Time complexity в худшем случае O(log^2 N).

https://gist.github.com/codekrolik/fbd99a7099c00f9d9edc

Тесты для обоих решений:

https://gist.github.com/codekrolik/19172393b3c6468c0a37