• Разбор задачи с собеседования Google: поиск соотношения

    • Перевод


    Добро пожаловать в очередную из серии статей с разбором задачек, которые я задавал на собеседованиях в Google, прежде чем их запретили после утечки. С тех пор я оставил работу инженера-программиста в Google и перешёл на должность менеджера по разработке в Reddit, но у меня всё ещё осталось несколько замечательных тем. К настоящему моменту мы разобрали динамическое программирование, возведение матриц в степень и синонимичность запросов. На этот раз совершенно новый вопрос.
    Читать дальше →
  • Стажёр Вася и его истории об идемпотентности API

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


      Меня зовут Денис Исаев, и я руковожу одной из бэкенд групп в Яндекс.Такси. Сегодня я поделюсь с читателями Хабра описанием проблем, которые могут возникнуть, если не учитывать идемпотентность распределенных систем в своем проекте. Для этого я выбрал формат вымышленных историй о стажёре Васе, который только-только учится работать с API. Так будет нагляднее и полезнее. Поехали.


      image

      Читать дальше →
    • Пользовательское вознаграждение авторам Хабра

        Хабр уже давно поощряет активных авторов в рамках ППА (Программа Поощрения Авторов). Однако в ней могут участвовать далеко не все желающие — сначала нужно «наработать» определённый стаж. И далеко не всем хватает терпения, чтобы пройти эту дистанцию.



        Разгребая бэклог хотелок, мы обратили внимание на функцию пользовательского поощрения (доната), в рамках которого вознаградить автора (любого) могли бы сами пользователи. Опрос показал, что эта функция действительно будет востребованной, поэтому мы решили её реализовать.
        Читать дальше →
      • Как это работает: Деревья Меркла в биткойн сети

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

          Что это такое, как используется, какие существуют альтернативы — расскажем далее.

          Читать дальше →
        • Интуитивная разработка алгоритмов

          • Перевод
          image

          Если вы программист, то, возможно, у вас возникали ситуации, когда в выбранном игровом движке или библиотеке нет нужной функции. За этим следовал ужасающий момент, когда вам приходилось обыскивать весь Интернет в поисках кода, написанного людьми, решавшими эту проблему до вас (я говорю о вас, пользователи StackOverflow). Конечно, в этом нет ничего плохого (я и сам так поступаю), но очень часто вы можете сделать это самостоятельно, даже когда речь идёт о таких теоретических задачах, как геометрия или перетасовка. Я один из тех людей, которые всегда пытаются понять, как всё работает, и разве есть способ понимания лучше, чем прийти к нему самому, заново изобретя решение на лету (если, конечно, оно существует)?

          Ставим перед собой пример задачи


          В этой статье я опишу несколько этапов, которые, как мне кажется, довольно эффективны для самостоятельного выведения решающего задачу алгоритма. Чтобы применить их к чему-то конкретному, мы рассмотрим пример задачи: выпуклое разбиение простых многоугольников. Это звучит сложно и по-научному, но на самом деле это не так трудно.
          Читать дальше →
        • Доступно о криптографии на эллиптических кривых

          • Перевод
          image


          Тем, кто знаком с криптографией с открытым ключом, наверно известны аббревиатуры ECC, ECDH и ECDSA. Первая — это сокращение от Elliptic Curve Cryptography (криптография на эллиптических кривых), остальные — это названия основанных на ней алгоритмов.

          Сегодня криптосистемы на эллиптических кривых используются в TLS, PGP и SSH, важнейших технологиях, на которых базируются современный веб и мир ИТ. Я уже не говорю о Bitcoin и других криптовалютах.

          До того, как ECC стала популярной, почти все алгоритмы с открытым ключом основывались на RSA, DSA и DH, альтернативных криптосистемах на основе модулярной арифметики. RSA и компания по-прежнему популярны, и часто используются вместе с ECC. Однако несмотря на то, что магия, лежащая в фундаменте RSA и подобных ей алгоритмов легко объяснима и понятна многим, а грубые реализации пишутся довольно просто, основы ECC всё ещё являются для большинства людей загадкой.

          В этой серии статей я познакомлю вас с основами мира криптографии на эллиптических кривых. Моя цель — не создание полного и подробного руководства по ECC (в Интернете полно информации по этой теме), а простой обзор ECC и объяснение того, почему её считают безопасной. Я не буду тратить время на долгие математические доказательства или скучные подробности реализации. Также я представлю полезные примеры с визуальными интерактивными инструментами и скриптами.
          Читать дальше →
        • Статический анализ → уязвимость → профит

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

            Читать дальше →
          • Синхронизация состояний в многопользовательских играх

            • Перевод
            image

            Проблема многопользовательских игр


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

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

            Обычно программа игры должна симулировать следующее:

            изменения в окружении с учётом времени и вводимых игроками данных.

            Игра — это программа, хранящая состояние, поэтому она зависит от времени (реального или логического). Например, PACMAN симулирует окружение, в котором постоянно перемещаются призраки.

            Многопользовательская игра не является исключением, однако из-за взаимодействия игроков её сложность намного выше.
            Читать дальше →
          • Android runtime permissions. Почему, зачем и как

            Часто при установке приложения на Android нам приходилось видеть, что оно запрашивает какое-то немыслимое количество разрешений. Например:



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

            Некоторые разработчики, чтобы уменьшить недоверие, добавляют в описание приложения на Google Play информацию о том, зачем нужно то или иное разрешение.

            К шестой версии Android ситуация поменялась. Теперь разрешения нужно запрашивать в процессе работы. О том, как этой новой возможностью пользоваться и ее некоторых подводных камнях будет рассказано далее.
            Читать дальше →
          • Тестирование веб-сервиса на Go

            • Tutorial
            В этой статье хотелось бы поделиться одним из способов простого и удобного интеграционного тестирования http-сервиса, написанного на Go. Интеграционные тесты бывает непросто создавать так, чтобы обходиться без сложных скриптов, но на помощь нам придет Docker, пакет из стандартной библиотеки httptest и билд-теги. Для примера мы будем использовать MySQL базу данных с миграциями, управляемыми пакетом goose. Финальной целью является получить простое и удобное кроссплатформенное интеграционное тестирование простым запуском команды go test, будь это рабочий ноутбук или Continuous Integration сервер.

            image
            Читать дальше →
          • Налоговый суслик. Особенности упрощенной системы налогообложения при работе по договорам с Apple, Google и другими

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

            Прочтите внимательно эту статью, если вы применяете упрощенную систему налогообложения с объектом налогообложения «доход» по ставке 6 процентов и продаете игры или приложения в Google Play, Apple App Store, а также прочий цифровой контент — например, 3D-модели — в Steam, Unity Asset Store или на других площадках, в условиях договоров с которыми фигурируют комиссии, агентские вознаграждения и прочие формы разделения выручки между сторонами.

            Из материала вы узнаете:

            • Почему разработчику желательно обладать хотя бы базовой юридической грамотностью
            • Чем с точки зрения Гражданского кодекса являются игры и приложения и какие права на них есть у разработчиков помимо авторского права
            • Что такое агентский договор и почему все это важно при работе по договору с Apple или Google
            • Кто такой налоговый суслик и почему он может превратиться в пушного зверя
            • Какой «подвох» существует для применяющих «упрощенку» в части определения налоговой базы
            • Почему налог на добавленную стоимость (НДС) продолжает преследовать нас, даже когда мы не являемся его плательщиками
            • Как, с точки зрения Федеральной налоговой службы, облагаются НДС внутриигровые покупки (InApp Purchases)
            Покажите мне суслика!
          • Медиана: точно, иногда точно и почти точно

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



              Для таких целей подойдет оценка медианы. То есть такая статистика, что половина значений выборки меньше, а половина больше. Более формально: упорядочим значения выборки X=(x_1,..., x_n) по порядку (x_{[1]}, ..., x_{[n]}) и выберем среди них с порядковым номером floor(n/2). У такой оценки есть несколько преимуществ. Она менее подвержена влиянию ошибочных данных, значение всегда будет из того множества, что встречалось в выборке, но есть и неприятные недостатки, главный из них, это сложность подсчета, даже для довольно распространенных распределений не существует общей формулы расчета (точнее есть, но ее сложно применить на практике, смотрите Распределение порядковой статистики).
              Читать дальше →
              • +36
              • 26,6k
              • 6
            • Шпионские штучки в Wolfram Language, или как спрятать в картинке всё что угодно

              • Перевод

              Перевод поста Джона Маклуна (Jon McLoone) "Doing Spy Stuff with Mathematica".
              Код, приведенный в статье, можно скачать здесь.
              Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе.

              Я читал о IT проблемах недавно арестованных, как заявлялось, русских шпионов. Говорилось, что они пользовались не самыми надёжными инструментами цифровой стеганографии (вики). И мне стало интересно — насколько быстро я смогу реализовать стеганографию через цифровые изображения в Mathematica, используя метод, известный как "вставка младшего бита" (least significant bit insertion).

              Идея стеганографии основывается на том, чтобы спрятать сообщения в какой-то другой информации таким образом, чтобы никто факта коммуникации не заметил. Само слово происходит от латино-греческий комбинации, означающей «скрытное письмо»; данным термином назывался процесс нанесения секретного сообщения на лысую голову человека, на которой затем отрастали волосы и, тем самым, прятали сообщение. В случае цифровой стеганографии всё делается посредством математики.
              Читать дальше →
              • +19
              • 24,6k
              • 3
            • Умножение Карацубы и C++ 11

              Хочу в очередной раз затронуть метод реализации умножения Карацубы с использованием возможностей стандарта C++11. Данный алгоритм неоднократно рассматривался здесь («Умножение длинных чисел методом Карацубы», «Алгоритм Карацубы для умножения двух чисел»), но видимо из-за того, что я не умею их готовить, первый вариант не работал с числами разной длины, а второй делает не совсем то, что было нужно.

              Для тех, кто не устал от этой заезженной темы, а также всех, кто испытывает трудности с реализацией этого простого, но очень эффективного алгоритма, прошу читать дальше.
              Читать дальше →
            • Тестируем инфраструктуру как код


                Всем привет, недавно мы начали цикл статей о тестировании в Chef, но сегодня я расскажу о более вводных и универсальных вещах: зачем тестировать инфраструктуру, какие инструменты для этого есть и как все это автоматизировать. Также затрону тему публикации инфраструктурного кода в open source. Статья будет интересна пользователям любой из популярных систем управления конфигурацией — Chef, Puppet, Ansible или SaltStack.
                Читать дальше →
              • Именованные параметры C++. Не пригодились

                  Время от времени вдруг начинает хотеться именованных параметров в C++. Не так давно была статья, да и сам какое-то время назад писал на эту тему. И вот что удивительно — со времен той своей статьи я участвую в новом проекте без необходимости тащить за собой старый код, и как-то удивительным образом всего этого описанного собой же не использую. Т.е. в вопросе разобрался, восхитился перспективами… и продолжил работать по-старинке! Как же так? Лень? Инерция? Ответ постараюсь дать под катом.
                  Читать дальше →
                • Уютный книжный пост для вас и вашего проекта

                    Как заработать миллион за день, стать искусным оратором за неделю, похудеть на 100 кг за 2 дня, стать успешным в тысяча ста начинаниях и прочая мишура регулярно засоряет наше информационное пространство. А порой так хочется взять в руки книгу, которая не просто съест кусок вашего свободного времени повествуя о неприменимых в отечественных реалиях вещах, но и подкинет хотя бы несколько полезных советов, способных оказать позитивное влияние на развитие вашей личности и вашего проекта.

                    Если вы хотите найти и/или поделиться хорошими книгами, добро пожаловать под кат.

                    image

                    Читать дальше →
                  • Как я училась в вузе

                      Данная статья для тех, кто еще не знает, нужно или ему высшее образование. Я ни в коем случае не пытаюсь сказать, что оно не нужно. Каждый сам для себя делает выводы. И возможно так не во всех ВУЗах, как было у меня.

                      О поступлении


                      image

                      В далеком 2010 году поступила я в ВУЗ. Моих несчастных 166 баллов (по 3 предметам) хватило только на МГУПИ. Такое количество баллов из-за того, что в ВУЗ пошла после 2-х курсов колледжа и вечерней школы, и так вышло, что на подготовку к ЕГЭ по всем 3 предметам у меня было что-то около 2 недель в перемешку с сессией колледжа.

                      Мама хотела, чтобы я училась в МГТУ СТАНКИН, и поэтому туда сразу отдали оригинал аттестата. Но моих баллов в первую волну на бюджет не хватало. Было несколько попыток забрать аттестат, но приемка морозилась, убеждая подождать 2-й волны. В итоге, почти с боем, аттестат отдали.
                      Читать дальше →
                    • Пополняем шпаргалки по C++: неявно-генерируемые перемещающий конструктор и оператор присваивания

                      • Tutorial
                      Когда не так часто, как хотелось бы, приходится работать с языком, некоторые аспекты забываются. А некоторые никогда и не откладываются в голове. Поэтому, когда возникают вопросы, приходится отвлекаться и лезть в документацию.

                      Чтобы сэкономить время в последующем, а также, чтобы лучше понять в ходе обучения, крайне помогает вести конспекты и делать наглядные шпаргалки. Шпаргалку можно повесить рядом на стену. Хороши шпаргалки в виде блок-схем, по которым можно легко, по шагам, получить нужный результат (например выбрать правильный контейнер).

                      Под катом я решил опубликовать пару шпаргалок для определения условия когда будет создан компилятором неявно-генерируемый перемещающий конструктор и перемещающий оператор присваивания.

                      Читать дальше →
                    • Делаем качественный переплёт для любимой книги

                      Вступление


                      Приветствую всех.

                      Люди любят читать. Но не все, и не всё. А то, что любят, не всегда можно найти в магазинах. А если и можно найти, то не всегда это по карману. Из этого следует один элементарный факт: что-то с этим надо делать. Конечно, можно читать с экрана монитора/ноутбука/телефона. Или распечатать и читать в разрозненных, пусть и упорядоченных, листочках. Кроме того (это более затратный вариант, но для любителя чтения он лучше), можно купить специализированную читалку на электронных чернилах. Да, она решает проблему, но… Спустя какое-то время начинаешь скучать по весу настоящей книги, по шелесту перелистывания бумажных страниц, и по кипе других подобных маловажных, но таких приятных сердцу мелочей.
                      И из этой неприятности тоже есть свой выход. Просто-напросто надо самому сделать нужную книгу.
                      Осторожно, под катом очень много фотографий.
                      Читать дальше →