Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

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

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 50 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →