?

Log in

четное дерево - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

четное дерево [дек. 19, 2016|10:44 am]
Anatoly Vorobey
[Tags|]

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

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

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

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

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

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

Comments:
[User Picture]From: dragon_ru
2016-12-19 09:23 am
/* надо сначала подумать, как собственно найти искомое, подход "прямиком" слишком трудоемкий */

Может, я чего-то не понимаю, но, как мне кажется, подход "прямиком" в худшем случае даст О(n^2). Обходим дерево. Если все вершины, дочерние для данной, просмотрены, проверяем, можно ли убрать ребро от данной вершины к родителю. Если хоть одно ребро убрано, по завершению обхода повторяем процедуру. (впрочем, надо подумать - нужен ли этот последний шаг)
(Ответить) (Thread)
[User Picture]From: avva
2016-12-19 09:57 am
Это не подход "прямиком". Предположим, что каждое из ребер A и B в отдельности можно удалить из исходного дерева, удовлетворив нужному условию. Вы неявно предполагаете, что если удалить A, то B все еще останется "хорошим" в этом смысле. Это, конечно, верно, но это нетривиальная мысль, которую нужно представить и продумать. Подход "прямиком" - это, например, выполнить процедуру "если лес хороший, перебрать все его ребра, и для каждого из них попробовать удалить его и рекурсивно проверить получившийся лес", возвращая в итоге максимальную достиженную глубину рекурсии.


Edited at 2016-12-19 09:58 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
From: mister_bean
2016-12-19 09:56 am
Основная идея: между вершиной и дочерним поддеревом можно убрать ребро, если в поддереве четное количество вершин. Один обход дерева (поиском в глубину или в ширину) дает нам количество ребер которые можно убрать.
(Ответить) (Thread)
[User Picture]From: tlkh
2016-12-19 11:18 am
Первая мысль - перебираем все ребра, одна из вершин которых терминальная, и обрываем все ребра, смежные с ними. Повторяем до победного конца.

Edited at 2016-12-19 11:21 (UTC)
(Ответить) (Thread)
[User Picture]From: hyperpov
2016-12-19 10:25 pm
Не прокатит.
(Ответить) (Parent) (Thread) (Развернуть)
From: huzhepidarasa
2016-12-19 11:33 am
А вот, например, другая задачка из интервью (не из Гугла): дано предложение и словарь, нужно побыстрее найти все (многословные) анаграммы предложения, состоящие из словарных слов. Задачка веселая, жызненная и никаких графьев в условии нет.
(Ответить) (Thread)
[User Picture]From: avva
2016-12-19 02:13 pm
По-моему, это NP-тяжелая проблема, в отличие от однословных анаграмм.
(Ответить) (Parent) (Thread) (Развернуть)
From: huzhepidarasa
2016-12-19 11:36 am
под рукой не было компилятора


Это странное состояние, не сразу обратил внимание. Как Вы дошли до жизни такой?
(Ответить) (Thread)
From: bakabaka
2016-12-19 12:06 pm

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

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

Edited at 2016-12-19 12:09 (UTC)
(Ответить) (Thread)
[User Picture]From: neatfires
2016-12-19 12:12 pm
А в Гугле же, вроде, всё пишут на бумажке, без компа? Или нет? У меня в голове решение было готово за 5-10 минут (включая доказательство), но на написание/отладку _за компьютером_ ушло полчаса. Шансов успеть на бумажке у меня бы не было.

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

0) Описание алгоритма: удаляем все те ребра, которые соединяют поддеревья с четным количеством вершин с их родителями.
1) Если дерево нечетное, то из него невозможно получить валидный (удовлетворяющий условиям задачи) вывод. Это очевидно.
2) Все те ребра, которые *вообще можно* удалить, чтобы получить на выходе только четные деревья, алгоритм удалит. Поэтому здесь нет никакой вариативности. А значит, этот алгоритм оптимален (удаляет максимальное число ребер).
(Ответить) (Thread)
[User Picture]From: avva
2016-12-20 07:38 am
В Гугле пишут на бумажке или в текстовом редакторе, без запуска и отладки.

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

(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: hyperpov
2016-12-20 08:31 pm
Предлагаете вершины каждый раз пересчитывать? Долбежу многовато будет. Задача решается за линейное по размеру графа количество операций.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ilya_dogolazky
2016-12-19 12:54 pm
да, за чаем решили, но скукотища же это ещё и записывать
(Ответить) (Thread)
From: mikkim08
2016-12-19 01:09 pm
Наверное для этого и существует всякая функциональщина, чтобы записать решение в несколько строчек.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2016-12-19 01:08 pm
Что-то слишком просто для интервью -- один простой обход, и все.
(Ответить) (Thread)
[User Picture]From: kaathewise
2016-12-19 03:13 pm
Не пишу на перле в продакшене уже давно, но на нем такие штуки очень лаконично получаются.
(Ответить) (Thread)
[User Picture]From: avva
2016-12-20 07:32 am
Ага, мило.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2016-12-19 04:01 pm
А вот как назвать (с точки зрения профессии) человека, который даже условия задачи понять не может, но при этом регулярно пишет востребованные программы? (Это я про себя, если что)
(Ответить) (Thread)
From: (Anonymous)
2016-12-20 07:26 am
Программистов много, рабочих мест мало - на всех не хватит, учитесь кусать локти и лизать яйца. И вообще, кодеры за тридцатник слишком много просят, лучше нанять лоха с "неоконченным высшим", поиметь до нитки за еду и выбросить.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ilya_dogolazky
2016-12-19 05:38 pm
а вот замени там скажем слово "дерево" на "связный граф", будет куда интереснее
(Ответить) (Thread)
From: huzhepidarasa
2016-12-19 07:55 pm
Ну так это. Находим в этом графе spanning tree, снимаем чайник с конфорки, выливаем воду...
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: hyperpov
2016-12-19 10:19 pm
Хм, а что, просто так не пойдет?

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

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

Edited at 2016-12-19 22:23 (UTC)
(Ответить) (Thread)
[User Picture]From: 66george
2016-12-19 10:23 pm
Чуете ли Вы неладное в словах "про просто программиста"? Произнесите прочувствованно.
(Ответить) (Thread)
From: bakabaka
2016-12-20 10:16 am

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

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

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

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

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

Edited at 2016-12-20 10:20 (UTC)
(Ответить) (Thread)
[User Picture]From: cema
2016-12-20 06:54 pm
А я сперва ошибся с алгоритмом. Напрасно залез на тот сайт, у тебя лучше описание. Когда увидел, что алгоритм неправильный, переделал его за 10 минут, но в совокупности ушло больше часа, конечно.
(Ответить) (Thread)