Пост подготовлен с целью помочь программистам при подготовке к собеседованиям по программированию. Здесь рассматриваются все основные темы, которые, как минимум, желательно знать перед собеседованием. Использован собственный опыт, опыт и рассказы коллег, специализированная литература.
Некоторые рассмотренные здесь темы могут вообще не пригодиться некоторым программистам, а могут и быть обязательными, решать вам. Мой совет – старайтесь как можно больше изучать темы/разделы/аспекты указанные здесь.
И так, в качестве обязательных знаний:

• Структуры данных
• Алгоритмы и «концепции»
• Язык программирования

В НГТУ, где я учусь на факультете энергетики, основная масса лабораторных работ проходит на очень старых стендах. Неверные показания измерительных приборов, постоянные сбои и поломки, да и просто неудобное управление вызывает массу неудобств и мешает изучению исследуемых физических процессов. В связи с этим у меня и моего преподавателя возникла идея усовершенствования таких стендов при помощи микроконтроллеров.

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

Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?

Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!

На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.

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

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

Основы программирования

• codebetter.com/karlseguin/2008/06/25/foundations-of-programming-ebook
• pine.fm/LearnToProgram
• netlib.bell-labs.com/cm/cs/pearls
• www.faqs.org/docs/artu
• savannah.nongnu.org/projects/pgubook

Вступление издалека

Недавно передо мной встала достаточно интересная задача, с которой я раньше никогда не сталкивался — борьба с шумом. Мы принимали сигнал с датчиков на аналогово-цифровой преобразователь (АЦП)
А так как данная тема для меня была (хотя и сейчас есть кое-где) темным лесом, я пошел мучить вопросами гугл, мне показалось освещена эта тема не очень подробно и доступно, поэтому решил написать статью с примером разработки и готовым исходником.

Написание makefile иногда становится головной болью. Однако, если разобраться, все становится на свои места, и написать мощнейший makefile длиной в 40 строк для сколь угодно большого проекта получается быстро и элегантно.

Внимание! Предполагаются базовые знания утилиты GNU make.

Настало, наконец, время вернуться к теме пакетирования в Debian и Ubuntu.
Начну я с оправданий. Причиной долгой паузы, между четвертой и этой частью была не моя лень, не диплом, который я никак не допишу, и даже не положение звёзд, а уже упомянутый мною в предыдущих статьях (раз, два, три, четыре) досадный баг в одном из пакетов Debian. Как я, наконец, понял, скорого исправления этого бага ждать не стоит, поэтому я предлагаю тем, кто уже освоил сборку пакетов, изучить интересное средство, облегчающее как тестирование вашего пакета, так и сборку его под разные архитектуры — pbuilder.

Один из самых известных Unix-программистов Мигель де Икаса (основатель проектов GNOME и Mono) в своём блоге дал парочку советов, как повысить продуктивность работы в шелле Unix. Он говорит, что иногда встречает молодых хакеров и бывает поражён, насколько мало трюков они знают.

Мигель де Икаса рекомендует ликбез по-быстрому:

1. Прочитать «Unix. Программное окружение» Кернигана и Пайка [русское издание], займёт несколько дней, от силы неделю. Книжка очень старая (1984), но лучше всех разъясняет автоматизацию различных действий в консоли. Вторая книжка — UNIX for the Impatient, чтобы прокачать навыки.

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

Уже с конца 1980-х годов музыкальные издательства постепенно оставляли ручной и переходили на компьютерный нотный набор. На данный момент список нотных редакторов огромен, но профессионалы используют Finale и Sibelius.

Холивары о том, кто из них лучше, не утихают уже лет десять, авторитетное издательство Bärenreiter (музыканты его очень любят, хоть и ругаются на дорогие ноты) тем временем используют написанную на Фортране SCORE, а музыканты — любители свободных программ смотрят на LilyPond и ужасаются, потому что как же обычному человеку жить без WYSIWYG'а?

Если бы не TeX-подобный синтаксис, я уверен, многие бы использовали этот engraver. Именно engraver — переводы «гравировщик» и «наборщик» не подходят здесь, потому что этими словами обозначаются профессии. LilyPond лучше других коммерческих и бесплатных программ располагает нотный текст равномерно по странице.

Сравнение с популярными программами

Это мелодия небезызвестной темы, набранная в трёх разных программах (LilyPond, Finale, Sibelius)


В LilyPond не делалось ничего кроме набора, в Сибелиусе и Finale удалены лишние такты, также в последней ноты принудительно автоматически расставлены по горизонтали.

Любой приказ, который может быть неправильно понят, понимается неправильно (Армейская аксиома)

Редкий скрипт лишен необходимости общения с пользователем. Мы ожидаем, что программа (утилита) будет выполнять то, что нам от нее хочется. Следовательно, нужны инструменты влияния на них, да и программа сама должна объяснить, как продвигается ее работа.
Данным топиком я хочу рассмотреть несколько способов взаимодействия bash-скриптов с пользователем. Статья рассчитана на новичков в скриптинге, но, надеюсь, люди опытные тоже найдут что-нибудь интересное для себя.

О чём это я?

Задачи бывают разные… Бывают простые, бывают сложные, а бывают такие, на решение которых может уйти не одна неделя и достаточное количество нервных клеток. Одной из подобных задач как можно считать разворачивание чего-то серьёзного на большом количестве слабого железа. А именно…

(Здесь и далее будет говориться о немного специфичной и оптимизированной настройке LTSP и поднятии на его основе кластера серверов).

Всем доброго времени суток!

Сегодня я расскажу вам об одной интересной структуре данных, про которую слышали лишь немногие и про которую очень незаслуженно мало написано в рунете, да и в англоязычном информации, в общем-то, тоже негусто. Решено было исправить ситуацию и поделиться с общественностью в доступной форме этой достаточно экзотической структурой данных.

Дерево ван Эмде Боаса (van Emde Boas tree) — ассоциативный массив, который позволяет хранить целые числа в диапазоне [0; U), где U = 2^k, проще говоря, числа, состоящие не более чем из k бит. Казалось бы, зачем нужно еще какое-то дерево, да еще позволяющее хранить только целые числа, когда существует множество различных сбалансриованных двоичных деревьев поиска, позволяющих выполнять операции вставки, удаления и прочие за O(log n), где n — количество элементов в дереве?

Главная особенность этой структуры — выполнение всех операций за время O(log(log(U))) независимо от количества хранящихся в ней элементов.

Введение

Кажется, монады в программировании стали загадкой века. И для этого есть две причины:

• недостаточное знание теории категорий;
• многие авторы стараюстся не упоминать категории вообще.

Это как говорить об электричестве не используя мат. анализ. Достаточно для замены предохранителя, не хватит, чтобы спроектировать усилитель.

Мы начнём с простого введения в категории и функторы, затем дадим определение монады, приведём простые примеры монад в категориях и в конце приведём монадическую терминологию используемую в языках программирования.

Я уверен, что монады с точки зрения категорий почти элементарны.

Содержание

1. Категория
2. Функтор
3. Естественное преобразование
4. Монада
5. Монады исключения и состояния
6. Монады в программировании
7. Ссылки

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

Всем привет!
Прочел статью про «Все тонкости настройки Wine», оказалось, что там далеко не все тонкости. Поэтому написал этот пост как дополнение тому.

В данном посте в основном вольный перевод оф. документации, а так же несколько своих и чужих хитростей при работе с вайн.
Скорее всего данный пост будет интересен новичкам и обычным пользователям GNU\Linux. Тем не менее добротные советы от специалистов не будут лишними.

Рано или поздно в любой профессиональной деятельности наступает этап подведения промежуточных итогов, когда человек задумывается о перспективах и отвечает на многие важные для себя вопросы о будущем в профессии и желательном направлении дальнейшего развития. Куда двигаться? Что ждет нас дальше?

Введение

Так уж сложилось, что моя работа тесно связана с математическим моделированием физических процессов. Математическое моделирование — это совершенно особенная область программирования. Расчет даже относительно простого физического процесса может занимать несколько дней и даже недель. Поэтому на первый план выходит производительность программы, пускай даже в ущерб удобству написания и чтения кода. Однако до недавнего времени быстродействие моих программ меня мало заботило: вполне хватало грубых сеток, для которых расчеты занимали что-то около суток. Но постепенно сетки становились все подробнее, и время работы программ неуклонно росло. Тогда я стал искать узкие места в своей программе. Сначала в алгоритмах. Потом дело дошло до структур данных. И тут меня очень заинтересовал вопрос «а что же лучше использовать для хранения векторов: массивы или контейнеры?»

Сегодня мы поговорим об отечественных стандартах на проектную документацию. Как эти стандарты работают на практике, чем они плохи и чем хороши. При разработке документации для государственных и серьезных частных заказчиков у нас обычно нет выбора — в требования по документированию ТЗ вписано соблюдение стандартов. На практике мне приходилось сталкиваться с различными примерами недопонимания структуры стандартов, того, что должно быть в документах и зачем эти документы нужны. В итоге из-под пера техписателей, аналитиков и специалистов выходят порой такие перлы, что непонятно, в каком состоянии сознания они писались. А ведь на самом деле все достаточно просто. Поиск по Хабру не вернул ссылок на более-менее целостный материал на данную тему, потому предлагаю закрасить этот досадный пробел.

Я думаю, любой руководитель проекта или ведущий программист хотя бы однажды сталкивался с ситуацией, когда код приложения вдруг оказывался совершенно запутанным, непонятным, а люди, его поддерживающие, в ответ на просьбу исправить ошибку или добавить новую функциональность отправлялись «в астрал» на несколько дней, прихватив с собой изрядную долю бюджета и, возвращаясь, предъявляли ещё более запутанный код с исправленной ошибкой, но добавленной парой других.

И у вас, как у человека, ответственного за проект, при этом возникало смешанное чувство досады, неудовлетворённости работой своих программистов и ожидания неприятных последствий, которые обязательно следуют за провальным проектом, вышедшим из любых вменяемых рамок и практически бесконтрольно расходующим бюджет.

Большинство провальных проектов обладают одной закономерностью. Они абсолютно лишены структуры. Я называю архитектуру таких систем «пластилиновой».