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

Решил эту штуку (https://www.hackerrank.com/challenges/even-tree, см репост ниже) на Rust-е, ушло около получаса на думание и часа 4 на программирование - правда заметную часть времени читал доки и боролся с borrow checker-ом.
Кстати, borrow checker действительно помогает. Обратите внимание на split_at_mut в calc_weights. Rust мне не позволил получить доступ на запись к элементам массива i и j вот таким образом:

let from = &mut v[i];
let to = &mut v[j];

что логично - это я про себя думаю, что это разные элементы массива. Но ведь возможно, что i == j и компилятор мне об этом напомнил. Пришлось сначала получить раздельный доступ к двум половинкам массива, гарантировав, что v[i] и v[j] различны

под катом решение
( код )

update: почитал другие решения - ну да, нет у меня опыта работы с графами, можно было куда лаконичнее сделать. Ну и ладно, и так неплохо получилось

Originally posted by avva at четное дерево

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

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

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

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

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

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