Разработка / Еще раз про skiplist…
… или как я получил «Аленку» за консольное приложение
Существует довольно распространённое мнение, что выполнение различных тестовых заданий помогает очень быстро поднять свой профессиональный уровень. Я и сам люблю иногда откопать какое-нить мудреное тестовое и порешать его, чтобы быть постоянно в тонусе, как говорится. Как-то я выполнял конкурсное задание на стажировку в одну компанию, задачка показалась мне забавной и интересной, вот её краткий текст:
Представьте, что ваш коллега-нытик пришел рассказать о своей непростой задаче — ему нужно не просто упорядочить по возрастанию набор целых чисел, а выдать все элементы упорядоченного набора с L-го по R-й включительно!
Вы заявили, что это элементарная задача и, чтобы написать решение на языке C#, вам нужно десять минут. Ну, или час. Или два. Или шоколадка «Алёнка»
Предполагается, что в наборе допускаются дубликаты, и количество элементов будет не больше, чем 10^6.
К оценке решения есть несколько комментариев:
Ваш код будут оценивать и тестировать три программиста:Решение может быть очень интересным, поэтому я посчитал нужным его описать.
- Билл будет запускать ваше решение на тестах размером не больше 10Кб.
- В тестах Стивена количество запросов будет не больше 10^5, при этом количество запросов на добавление будет не больше 100.
- В тестах Марка количество запросов будет не больше 10^5.
Полный текст статьи читайте на Habrahabr.ru
