Удобное место, чтобы написать свою статью или просто почитать


Интересная задача на собеседовании

Однажды, на собеседовании в крупной российской IT компании, было предложено решить одну интересную задачу. Точный текст условия, к сожалению, привести нет возможности, однако суть задачи простая. 

Задача

Пусть дана последовательность целых чисел. Длина последовательности известна. Числа не отсортированы и могут повторяться. Необходимо найти в данной последовательности такие два числа M и N, чтобы их сумма была равна целому числу K ( M + N = K ). Будем считать, что K равно 5. Хотя можно выбрать любое другое целое число.

Для примера, возьмем последовательность (1):

7, -1, 1, -7, 0, -4, 3, 2, -5, -6, 8, -2  (1)

Тогда M = 3, а N = 2 ( 3 + 2 = 5 ), 
или   M = 7, а N = -2 ( 7 + (-2) = 5 )

Для решения задачи достаточно найти хотя бы одну подходящую пару чисел M и N. Ограничения по памяти не накладываются и главным критерием является асимптотическая сложность алгоритма. Решим эту задачу.

Читать полностью | | | | 4253



Про size() у std::list, в чем сложность?

Практически все контейнеры из стандартной библиотеки STL реализуют метод size. Всем известно, что данная функция-член возвращает количество элементов в контейнере. Однако,  сложность такой операции для известного контейнера std::list не определена однозначно. В реализации STL от Microsoft сложность операции size равна O(1), то есть константная, и не зависит от количества элементов. Напротив, в GCC сложность операции size равна O(N) - линейная, что существенно ограничивает возможности её применения, особенно там, где важна производительность. Ведь каждый раз при вызове size, Вы фактически будете инициировать полный проход по всему списку. В чем же причина такой неоднозначности?

Материал статьи основан на публикации Howard Hinnant: 

http://howardhinnant.github.io/On_list_size.html

Howard Hinnant работает в компании Apple, и является членом комитета по стандартизации C++ от компании Apple. Также он занимается разработкой библиотеки Boost.

Читать полностью | | | | 1678



Данная статья рассчитана на неискушенного программиста C++. С другой стороны любой, кто программирует на C++ обязан знать то, что описывается ниже. Речь пойдет об одном из самых популярных контейнеров в STL. А именно, о векторе (std::vector). С него, обычно, начинается описание контейнеров в книгах по языку C++ и STL. Считается, что это наиболее простой контейнер, с понятным интерфейсом и предсказуемым временем операций. Однако, за описанием интерфейса часто "теряются" основные правила при работе с вектором, которые могут быть не так очевидны  для начинающего программиста. Но, обо всем попорядку.

Читать полностью | | | | 12341