Задачка из жизни

[kot_begemot]

Реально из жизни, но теперь буду спрашивать на интервью

Comments

[efimg]

А чем это отличается от распределения heap-а памяти? В простейшем случае, система хранит список свободных блоков памяти (в виде пары - адрес, длина), и когда новый блок освобождается, должна вставить его в список свободных. И именно так, как требуется в задаче, т.е. присоединить к уже имеющимся, спереди и сзади.
Решение довольно простое.

[kot_begemot]

Ну это примерно оно и есть, только распределяется не память, а дисковое пространство.

[ctapnep]

в случае хипа задача чуть проще. Освобождаемый кусок памяти никогда не пересекается с уже свободными. Он может только прилегать к уже свободным. А в общем случае новый интервал может не только прилегать, но и пересекаться или даже перекрывать существующие. Но это таки детали, которые не сильно влияют на алгоритм (вернее на лагоритм не влияют вообще, только на реализацию).

[ykats]

Задал сегодня на интервью, поставив кандидата в полный тупик. Хорошая задачка, взял на вооружение!