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

[avva]

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

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

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

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

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

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

Comments

[dragon-ru.livejournal.com]

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

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

[avva.livejournal.com]

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

[mister-bean.livejournal.com]

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

[tlkh.livejournal.com]

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

[hyperpov.livejournal.com]

Не прокатит.

[huzhepidarasa.livejournal.com]

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

[avva.livejournal.com]

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

[huzhepidarasa.livejournal.com]

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

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

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

[bakabaka.livejournal.com]

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

[neatfires.livejournal.com]

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

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

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

[avva.livejournal.com]

В Гугле пишут на бумажке или в текстовом редакторе, без запуска и отладки.

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

[hyperpov.livejournal.com]

Предлагаете вершины каждый раз пересчитывать? Долбежу многовато будет. Задача решается за линейное по размеру графа количество операций.

[xxxxx.livejournal.com]

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

[mikkim08.livejournal.com]

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

[(Anonymous)]

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

[kaathewise.livejournal.com]

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

[avva.livejournal.com]

Ага, мило.

[huzhepidarasa.livejournal.com]

На цацкеле тож довольно компактно

http://ideone.com/km5UAv

[(Anonymous)]

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

[(Anonymous)]

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

[xxxxx.livejournal.com]

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

[huzhepidarasa.livejournal.com]

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

[hyperpov.livejournal.com]

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

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

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

[66george.livejournal.com]

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

У меня, наверное, больше часа получилось

[bakabaka.livejournal.com]

https://gist.github.com/anonymous/7effb6529c43bf752711f1f7aeadbe4f

(А так как у них что попало нельзя импортировать,
пришлось заменить
from treelib import Node, Tree
на самодельную реализацию функциональности дерева.
(да, видимо, проще было бы обойтись без дерева вообще).
)

Идея в том, чтобы "приклеить" листья к их предкам, учитываю их (листьев) количество.

Повторять, пока не останется один корень, подсчитывая по дороге, сколько раз приклеивали лист чётного веса.

[cema.livejournal.com]

А я сперва ошибся с алгоритмом. Напрасно залез на тот сайт, у тебя лучше описание. Когда увидел, что алгоритм неправильный, переделал его за 10 минут, но в совокупности ушло больше часа, конечно.