четное дерево

[avva]

https://www.hackerrank.com/challenges/even-tree

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

По-моему, неплохой пример задачи для программистов, которая где-то на уровне интервью в Гугле. Мне сразу несколько вещей в ней нравится:

- надо знать/помнить что-то из теории (граф, дерево, компонента связности), но не глубокие вещи и не сложные алгоритмы, а достаточно для того, чтобы могло включиться алгоритмическое мышление
- надо сначала подумать, как собственно найти искомое, подход "прямиком" слишком трудоемкий
- сам выбираешь структуры данных, нет очевидно верного выбора, можно по-разному
- нужно сесть и написать с нуля работающий код, проверка проблемы "не знаю, как начать"

Я думаю, что если кто-то садится за эту проблему и меньше чем за час у него есть работающий код, то этот человек находится в хорошей форме в плане идти на технические интервью в Гугл/Фейсбук/Амазон итд. Все равно стоит готовиться, плюс еще есть интервью по system design, но для алго/кодинг это неплохие шансы, мне кажется. Конечно, люди, которые занимаются программистскими соревнованиями, щелкают такие задачки за 5-10 минут без проблем, но это другой случай, они натасканы на это. Я говорю про "просто программиста", который сомневается, идти ли на интервью и что там будет.

(чтобы проверить себя, я сел за эту задачу вчера, когда прочитал про нее. У меня был готова программа за 45 минут, включая проверку и отладку. Я пользовался https://repl.it/ для отладки, т.к. под рукой не было компилятора).

Comments

[dragon-ru.livejournal.com]

/* надо сначала подумать, как собственно найти искомое, подход "прямиком" слишком трудоемкий */

Может, я чего-то не понимаю, но, как мне кажется, подход "прямиком" в худшем случае даст О(n^2). Обходим дерево. Если все вершины, дочерние для данной, просмотрены, проверяем, можно ли убрать ребро от данной вершины к родителю. Если хоть одно ребро убрано, по завершению обхода повторяем процедуру. (впрочем, надо подумать - нужен ли этот последний шаг)

[mister-bean.livejournal.com]

Основная идея: между вершиной и дочерним поддеревом можно убрать ребро, если в поддереве четное количество вершин. Один обход дерева (поиском в глубину или в ширину) дает нам количество ребер которые можно убрать.

[avva.livejournal.com]

Это не подход "прямиком". Предположим, что каждое из ребер A и B в отдельности можно удалить из исходного дерева, удовлетворив нужному условию. Вы неявно предполагаете, что если удалить A, то B все еще останется "хорошим" в этом смысле. Это, конечно, верно, но это нетривиальная мысль, которую нужно представить и продумать. Подход "прямиком" - это, например, выполнить процедуру "если лес хороший, перебрать все его ребра, и для каждого из них попробовать удалить его и рекурсивно проверить получившийся лес", возвращая в итоге максимальную достиженную глубину рекурсии.

[tlkh.livejournal.com]

Первая мысль - перебираем все ребра, одна из вершин которых терминальная, и обрываем все ребра, смежные с ними. Повторяем до победного конца.

[huzhepidarasa.livejournal.com]

Ну прямо уж такая нетривиальная.

[huzhepidarasa.livejournal.com]

А вот, например, другая задачка из интервью (не из Гугла): дано предложение и словарь, нужно побыстрее найти все (многословные) анаграммы предложения, состоящие из словарных слов. Задачка веселая, жызненная (http://wordsmith.org/anagram/) и никаких графьев в условии нет.

[huzhepidarasa.livejournal.com]

под рукой не было компилятора

Это странное состояние, не сразу обратил внимание. Как Вы дошли до жизни такой?

Или я чего-то не понимаю в условии, или

[bakabaka.livejournal.com]

можно удалить все рёбра: тогда про каждую (отсутствующую) компоненту связности можно сказать что угодно.
Да, я написал бред.

[neatfires.livejournal.com]

А в Гугле же, вроде, всё пишут на бумажке, без компа? Или нет? У меня в голове решение (https://gist.github.com/kirillkh/e31443c21f0e35a2462a5dbd8006f8b6) было готово за 5-10 минут (включая доказательство), но на написание/отладку _за компьютером_ ушло полчаса. Шансов успеть на бумажке у меня бы не было.

Кстати, как вам такое доказательство, хорошо или не очень?

0) Описание алгоритма: удаляем все те ребра, которые соединяют поддеревья с четным количеством вершин с их родителями.
1) Если дерево нечетное, то из него невозможно получить валидный (удовлетворяющий условиям задачи) вывод. Это очевидно.
2) Все те ребра, которые *вообще можно* удалить, чтобы получить на выходе только четные деревья, алгоритм удалит. Поэтому здесь нет никакой вариативности. А значит, этот алгоритм оптимален (удаляет максимальное число ребер).

[xxxxx.livejournal.com]

да, за чаем решили, но скукотища же это ещё и записывать

[(Anonymous)]

Что-то слишком просто для интервью -- один простой обход, и все.

[mikkim08.livejournal.com]

Наверное для этого и существует всякая функциональщина, чтобы записать решение в несколько строчек.

[neatfires.livejournal.com]

Решение здесь легкое и короткое, а вот на парсинг ввода требуется много строк, и не вижу, как здесь (https://gist.github.com/kirillkh/e31443c21f0e35a2462a5dbd8006f8b6) поможет ФП. Неудобный формат ввода...

[avva.livejournal.com]

По-моему, это NP-тяжелая проблема, в отличие от однословных анаграмм.

[(Anonymous)]

Perl to the rescue!

https://gist.github.com/kaathewise/2c838b74ce0000f81b2582f8b9d496f3

[kaathewise.livejournal.com]

Не пишу на перле в продакшене уже давно, но на нем (https://gist.github.com/kaathewise/2c838b74ce0000f81b2582f8b9d496f3) такие штуки очень лаконично получаются.

[huzhepidarasa.livejournal.com]

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

Edit ну то есть да, на алфавите из одной буквы это просто subset sum. Ну что, тем веселее.

[(Anonymous)]

А вот как назвать (с точки зрения профессии) человека, который даже условия задачи понять не может, но при этом регулярно пишет востребованные программы? (Это я про себя, если что)

[xxxxx.livejournal.com]

а вот замени там скажем слово "дерево" на "связный граф", будет куда интереснее

[huzhepidarasa.livejournal.com]

Ну так это. Находим в этом графе spanning tree, снимаем чайник с конфорки, выливаем воду...

[xxxxx.livejournal.com]

так надо ж не абы какое натяжное дерево, а такое, что из него побольше можно повыкидывать. Возьмите большую клику --- там можно звёздочкой всё натянуть, и из звёздочки нихрена не выкинуть. А можно змейкой, из неё половину рёбер можно выкинуть

[huzhepidarasa.livejournal.com]

Да, точно. Ну тогда можно так попробовать: https://en.wikipedia.org/wiki/Minimum_degree_spanning_tree

[xxxxx.livejournal.com]

да ну низачот. Смотри, во-первых там в википедии написано, что его найти NP-сложно, а за такие решения чай из гугля взашей погонят. Во-вторых это не поможет, вот скажем возьмём граф рёбер кубика-рубика, он не эйлеров, так что это остовное дерево с вершинами маленькой степени будет никак не со степенями 2, ну а раз там и так все вершины степени три, то получается любое остовное дерево будет заодно и деревом этой самой минимальной степени (равной трём). Ну а теперь с одной стороны очевидно как разбить кубик на 4 чётных компоненты (например рёбра от жёлтой грани к белой), а с другой стороны легко построить (упражнение читателям) остовное дерево с которого четыре компоненты не получаются.

[hyperpov.livejournal.com]

Хм, а что, просто так не пойдет?

Красим ребра в цвета 0 и 1 по правилу:
1) Ищем вершину, из которой выходит ровно одно некрашеное ребро (изначально все некрашеные). Если таких нет, удаляем ребра с цветом 1 и откланиваемся.
2) Единственное некрашеное ребро , выходящее из найденной вершины, красим в четность числа ребер, уже покрашенных в 0 и выходящих из той же вершины, и возвращаемся к пункту 1)

update Впрочем, начать нужно с проверки, что общее число вершин четное. Иначе задавший задачу посылается лесом.

[66george.livejournal.com]

Чуете ли Вы неладное в словах "про просто программиста"? Произнесите прочувствованно.