Pull to refresh
14
0
Алексей Кнышев @alexeyknyshev

system software engineer @ nvidia

Send message

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

Reading time 21 min
Views 39K


Добро пожаловать в очередную из серии статей с разбором задачек, которые я задавал на собеседованиях в Google, прежде чем их запретили после утечки. С тех пор я оставил работу инженера-программиста в Google и перешёл на должность менеджера по разработке в Reddit, но у меня всё ещё осталось несколько замечательных тем. К настоящему моменту мы разобрали динамическое программирование, возведение матриц в степень и синонимичность запросов. На этот раз совершенно новый вопрос.
Читать дальше →
Total votes 47: ↑41 and ↓6 +35
Comments 73

Стажёр Вася и его истории об идемпотентности API

Reading time 11 min
Views 220K

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


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


image

Читать дальше →
Total votes 219: ↑216 and ↓3 +213
Comments 163

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

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



Разгребая бэклог хотелок, мы обратили внимание на функцию пользовательского поощрения (доната), в рамках которого вознаградить автора (любого) могли бы сами пользователи. Опрос показал, что эта функция действительно будет востребованной, поэтому мы решили её реализовать.
Читать дальше →
Total votes 320: ↑320 and ↓0 +320
Comments 254

Как это работает: Деревья Меркла в биткойн сети

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

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

Читать дальше →
Total votes 37: ↑35 and ↓2 +33
Comments 18

Интуитивная разработка алгоритмов

Reading time 8 min
Views 19K
image

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

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


В этой статье я опишу несколько этапов, которые, как мне кажется, довольно эффективны для самостоятельного выведения решающего задачу алгоритма. Чтобы применить их к чему-то конкретному, мы рассмотрим пример задачи: выпуклое разбиение простых многоугольников. Это звучит сложно и по-научному, но на самом деле это не так трудно.
Читать дальше →
Total votes 25: ↑23 and ↓2 +21
Comments 19

Доступно о криптографии на эллиптических кривых

Reading time 37 min
Views 240K
image


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

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

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

В этой серии статей я познакомлю вас с основами мира криптографии на эллиптических кривых. Моя цель — не создание полного и подробного руководства по ECC (в Интернете полно информации по этой теме), а простой обзор ECC и объяснение того, почему её считают безопасной. Я не буду тратить время на долгие математические доказательства или скучные подробности реализации. Также я представлю полезные примеры с визуальными интерактивными инструментами и скриптами.
Читать дальше →
Total votes 127: ↑125 and ↓2 +123
Comments 72

Статический анализ → уязвимость → профит

Reading time 5 min
Views 10K

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

Читать дальше →
Total votes 43: ↑42 and ↓1 +41
Comments 11

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

Reading time 13 min
Views 45K
image

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


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

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

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

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

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

Многопользовательская игра не является исключением, однако из-за взаимодействия игроков её сложность намного выше.
Читать дальше →
Total votes 48: ↑48 and ↓0 +48
Comments 38

Android runtime permissions. Почему, зачем и как

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



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

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

К шестой версии Android ситуация поменялась. Теперь разрешения нужно запрашивать в процессе работы. О том, как этой новой возможностью пользоваться и ее некоторых подводных камнях будет рассказано далее.
Читать дальше →
Total votes 25: ↑25 and ↓0 +25
Comments 13

Тестирование веб-сервиса на Go

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

image
Читать дальше →
Total votes 32: ↑22 and ↓10 +12
Comments 33

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

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

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

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

  • Почему разработчику желательно обладать хотя бы базовой юридической грамотностью
  • Чем с точки зрения Гражданского кодекса являются игры и приложения и какие права на них есть у разработчиков помимо авторского права
  • Что такое агентский договор и почему все это важно при работе по договору с Apple или Google
  • Кто такой налоговый суслик и почему он может превратиться в пушного зверя
  • Какой «подвох» существует для применяющих «упрощенку» в части определения налоговой базы
  • Почему налог на добавленную стоимость (НДС) продолжает преследовать нас, даже когда мы не являемся его плательщиками
  • Как, с точки зрения Федеральной налоговой службы, облагаются НДС внутриигровые покупки (InApp Purchases)
Покажите мне суслика!
Total votes 40: ↑36 and ↓4 +32
Comments 84

Медиана: точно, иногда точно и почти точно

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



Для таких целей подойдет оценка медианы. То есть такая статистика, что половина значений выборки меньше, а половина больше. Более формально: упорядочим значения выборки X=(x_1,..., x_n) по порядку (x_{[1]}, ..., x_{[n]}) и выберем среди них с порядковым номером floor(n/2). У такой оценки есть несколько преимуществ. Она менее подвержена влиянию ошибочных данных, значение всегда будет из того множества, что встречалось в выборке, но есть и неприятные недостатки, главный из них, это сложность подсчета, даже для довольно распространенных распределений не существует общей формулы расчета (точнее есть, но ее сложно применить на практике, смотрите Распределение порядковой статистики).
Читать дальше →
Total votes 44: ↑40 and ↓4 +36
Comments 6

Шпионские штучки в Wolfram Language, или как спрятать в картинке всё что угодно

Reading time 4 min
Views 26K

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

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

Идея стеганографии основывается на том, чтобы спрятать сообщения в какой-то другой информации таким образом, чтобы никто факта коммуникации не заметил. Само слово происходит от латино-греческий комбинации, означающей «скрытное письмо»; данным термином назывался процесс нанесения секретного сообщения на лысую голову человека, на которой затем отрастали волосы и, тем самым, прятали сообщение. В случае цифровой стеганографии всё делается посредством математики.
Читать дальше →
Total votes 27: ↑23 and ↓4 +19
Comments 3

Умножение Карацубы и C++ 11

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

Для тех, кто не устал от этой заезженной темы, а также всех, кто испытывает трудности с реализацией этого простого, но очень эффективного алгоритма, прошу читать дальше.
Читать дальше →
Total votes 21: ↑20 and ↓1 +19
Comments 12

Тестируем инфраструктуру как код

Reading time 5 min
Views 12K

Всем привет, недавно мы начали цикл статей о тестировании в Chef, но сегодня я расскажу о более вводных и универсальных вещах: зачем тестировать инфраструктуру, какие инструменты для этого есть и как все это автоматизировать. Также затрону тему публикации инфраструктурного кода в open source. Статья будет интересна пользователям любой из популярных систем управления конфигурацией — Chef, Puppet, Ansible или SaltStack.
Читать дальше →
Total votes 16: ↑16 and ↓0 +16
Comments 14

Именованные параметры C++. Не пригодились

Reading time 5 min
Views 30K
Время от времени вдруг начинает хотеться именованных параметров в C++. Не так давно была статья, да и сам какое-то время назад писал на эту тему. И вот что удивительно — со времен той своей статьи я участвую в новом проекте без необходимости тащить за собой старый код, и как-то удивительным образом всего этого описанного собой же не использую. Т.е. в вопросе разобрался, восхитился перспективами… и продолжил работать по-старинке! Как же так? Лень? Инерция? Ответ постараюсь дать под катом.
Читать дальше →
Total votes 76: ↑64 and ↓12 +52
Comments 86

Уютный книжный пост для вас и вашего проекта

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

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

image

Читать дальше →
Total votes 76: ↑62 and ↓14 +48
Comments 45

Как я училась в вузе

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

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


image

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

Мама хотела, чтобы я училась в МГТУ СТАНКИН, и поэтому туда сразу отдали оригинал аттестата. Но моих баллов в первую волну на бюджет не хватало. Было несколько попыток забрать аттестат, но приемка морозилась, убеждая подождать 2-й волны. В итоге, почти с боем, аттестат отдали.
Читать дальше →
Total votes 219: ↑123 and ↓96 +27
Comments 331

Пополняем шпаргалки по C++: неявно-генерируемые перемещающий конструктор и оператор присваивания

Reading time 2 min
Views 25K
Когда не так часто, как хотелось бы, приходится работать с языком, некоторые аспекты забываются. А некоторые никогда и не откладываются в голове. Поэтому, когда возникают вопросы, приходится отвлекаться и лезть в документацию.

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

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

Читать дальше →
Total votes 31: ↑28 and ↓3 +25
Comments 19

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

Reading time 7 min
Views 204K

Вступление


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

Люди любят читать. Но не все, и не всё. А то, что любят, не всегда можно найти в магазинах. А если и можно найти, то не всегда это по карману. Из этого следует один элементарный факт: что-то с этим надо делать. Конечно, можно читать с экрана монитора/ноутбука/телефона. Или распечатать и читать в разрозненных, пусть и упорядоченных, листочках. Кроме того (это более затратный вариант, но для любителя чтения он лучше), можно купить специализированную читалку на электронных чернилах. Да, она решает проблему, но… Спустя какое-то время начинаешь скучать по весу настоящей книги, по шелесту перелистывания бумажных страниц, и по кипе других подобных маловажных, но таких приятных сердцу мелочей.
И из этой неприятности тоже есть свой выход. Просто-напросто надо самому сделать нужную книгу.
Осторожно, под катом очень много фотографий.
Читать дальше →
Total votes 310: ↑294 and ↓16 +278
Comments 157
1

Information

Rating
Does not participate
Location
Обнинск, Калужская обл., Россия
Date of birth
Registered
Activity