Задачки про деку и сферку
Задачку про деку задал elephantum во времена, когда работал в Невале, кодал Героев5, вел перепалки за Петон и в общем и целом сколько-то относился к геймдев-тусовке (как это я забыл его зафрендить). Вот пусть расскажет о том, как ему тот геймдев и Невал видиццо столько времени опосля.
Задачка типа сложная и на просветление. Помнится, первый решил zemedelec минут кажется за 15. Ну шо, я в Z никогда и не сомневался!
Итак, дана двустороняя очередь (deque), которая хранит бинарные данные, т.е. каждый элемент - 0 или 1. Единственные операции, которые дека поддерживает - push_front, push_back, pop_front, pop_back. Push значение принимает, pop - возвращает, все как обычно. Еще у деки есть функция isempty(), чтобы узнать пустая она или нет. Других функций у деки нет.
Задача стоит в том, чтобы узнать размер данной деки, да побыстрее и не испортив данных внутри. Более того, с константными затратами памяти с учетом того, что сама дека память не возвращает (т.е. если вытащить из нее все элементы через pop, она не освободит ни байта памяти).
Решение by jakobz
Задачка на похожий перелом мышления - классика computational geometry, найти наименьшую охватывающую сферу для набора точек в 3D. Без ограничений по скорости работы и затратам памяти. (Геймдев-пипл - молчать! Кто скажет Welzl - будет объяснять, как он работает!)
Решение by captain_tylor
Обе задачи про то, как тяжело мозгу перестать думать в пределах O(n) и O(n log(n)). Первая на самом деле O(n log(n)), но чтобы додуматься до этого, сначала надо додуматься до O(n^2). Вторая - вообще O(n^4), тяжелейший перебор вариантов. На него согласиться вообще почти невозможно, даже если прямо сказано - не имеет значения, какая скорость. К тому же, хочется народу из 3D-графики найти геометрическое решение, а его нет, есть только перебор.
И вот мозг не принимает такие решения и не желает до них догадываться, мы привыкли к тому, что почти всегда есть O(n) и уж в крайнем случае O(n log(n)), которое достигается деревом и никак иначе.
Это иллюстрация к тому, что принцип - "premature optimization is a pure evil" не так прост, как кажется. "Думать не о производительности" - ничуть не легче, чем думать о ней. Проблемы не когда думаешь ты о производительности или нет, а когда просто не думаешь.
Про сферку я спрашивал на собеседованиях и стыжусь этого. Не задавайте на собеседованиях ни одну из этих задач, пожалуйста.
Задачка типа сложная и на просветление. Помнится, первый решил zemedelec минут кажется за 15. Ну шо, я в Z никогда и не сомневался!
Итак, дана двустороняя очередь (deque), которая хранит бинарные данные, т.е. каждый элемент - 0 или 1. Единственные операции, которые дека поддерживает - push_front, push_back, pop_front, pop_back. Push значение принимает, pop - возвращает, все как обычно. Еще у деки есть функция isempty(), чтобы узнать пустая она или нет. Других функций у деки нет.
Задача стоит в том, чтобы узнать размер данной деки, да побыстрее и не испортив данных внутри. Более того, с константными затратами памяти с учетом того, что сама дека память не возвращает (т.е. если вытащить из нее все элементы через pop, она не освободит ни байта памяти).
Решение by jakobz
Задачка на похожий перелом мышления - классика computational geometry, найти наименьшую охватывающую сферу для набора точек в 3D. Без ограничений по скорости работы и затратам памяти. (Геймдев-пипл - молчать! Кто скажет Welzl - будет объяснять, как он работает!)
Решение by captain_tylor
Обе задачи про то, как тяжело мозгу перестать думать в пределах O(n) и O(n log(n)). Первая на самом деле O(n log(n)), но чтобы додуматься до этого, сначала надо додуматься до O(n^2). Вторая - вообще O(n^4), тяжелейший перебор вариантов. На него согласиться вообще почти невозможно, даже если прямо сказано - не имеет значения, какая скорость. К тому же, хочется народу из 3D-графики найти геометрическое решение, а его нет, есть только перебор.
И вот мозг не принимает такие решения и не желает до них догадываться, мы привыкли к тому, что почти всегда есть O(n) и уж в крайнем случае O(n log(n)), которое достигается деревом и никак иначе.
Это иллюстрация к тому, что принцип - "premature optimization is a pure evil" не так прост, как кажется. "Думать не о производительности" - ничуть не легче, чем думать о ней. Проблемы не когда думаешь ты о производительности или нет, а когда просто не думаешь.
Про сферку я спрашивал на собеседованиях и стыжусь этого. Не задавайте на собеседованиях ни одну из этих задач, пожалуйста.