Всем привет!
Краткое предисловие: я счастливый обладатель замечательного саундбара YAS-109 от Yamaha, на момент написания пользуюсь им уже целый год, и всё в целом хорошо. Но однажды я решил узнать: не подслушивает ли меня мой музыкальный друг? Ведь у него есть встроенная поддержка Alexa, а ещё Bluetooth, WiFi, Ethernet и другие прелести… Так и начинается история моего ресёрча.
Есть целая куча популярных задач для собеседований, которые можно решить одним из двух способов: или логичным применением стандартных структур данных и алгоритмов, или использованием некоторых свойств XOR сложным для понимания способом.
Хоть и непривычно ожидать решения с XOR на собеседованиях, довольно забавно разбираться, как они работают. Оказывается, все они основаны на одном фундаментальном трюке, который я постепенно раскрою в этом посте. Далее мы рассмотрим множество способов применения этого трюка с XOR, например, при решении популярной задачи с собеседований:
Дан массив из n — 1 целых чисел, находящихся в интервале от 1 и n. Все числа встречаются только один раз, за исключением одного числа, которого нет. Найдите отсутствующее число.
Разумеется, существует множество прямолинейных способов решения этой задачи, однако есть и довольно неожиданный, в котором применяется XOR.
Читать полностью »
Новые инструменты, старые методы. Проводим обратную разработку и находим фатальный недостаток 1Password.
Все любят менеджеры паролей. Они великолепны по многим причинам. Лично у меня в менеджере более 200 записей. С таким большим количеством конфиденциальных данных в одном месте важно понимать масштаб ущерба в случае компрометации вашей записи, будь то вредоносные программы, эксплоиты или просто компьютер, оставленный без присмотра на несколько минут. Washington Post недавно опубликовала статью, основанную на нашем исследовании. Эта статья помогает довести людей, что не все менеджеры паролей одинаковы.
Я свято верил, что заблокированный парольный менеджер надёжно защищён. Если кто-то получит доступ к моему компьютеру, то максимум может рассчитывать на кучку случайных байтов, поскольку информация надёжно вычищается из памяти.
Читать полностью »
Существует классическая задача для собеседований, часто формулируемая следующим образом:
Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза, и только одно из чисел не имеет пары. Необходимо предложить алгоритм, который за минимальное число проходов по массиву определяет число, не имеющее пары.
Полагаю, никто не обидится, если я тут же приведу и решение задачи: уникальный элемент будет совпадать с 
-суммой всех элементов массива, вычисляемой за линейное время.
Предлагаю поразмыслить над другой вариацией данной задачи. Что, если все элементы, кроме искомого, будут присутствовать в массиве не парами, а тройками? Насколько при этом усложнится решение и останется ли оно линейным?
В современном мире наблюдается экспоненциальный рост объемов данных. Перед вендорами СХД возникает целый ряд задач, связанных с колоссальными объемами информации. Среди них — защита пользовательских данных от потери и максимально быстрое восстановление данных в случае выхода из строя сервера или диска.
Читать полностью »
Яндекс, как и любая другая большая интернет-компания, хранит много, а точнее очень много данных. Это и пользовательские данные из разных сервисов, и намайненные сайты, и промежуточные данные для расчёта погоды, и резервные копии баз данных. Стоимость хранения ($/ГБ) — один из важных показателей системы. В этой статье я хочу рассказать вам про один из методов, который позволил нам серьезно удешевить хранилище.
В 2015 году, как вы все помните, сильно вырос курс доллара. Точнее, расти-то он начал в конце 2014-го, но новые партии железа мы заказывали уже в 2015-м. Яндекс зарабатывает в рублях, и поэтому вместе с курсом выросла и стоимость железа для нас. Это заставило нас в очередной раз подумать о том, как сделать, чтобы в текущий кластер можно было положить больше данных. Мы такое, конечно, делаем регулярно, но в этот раз мотивация была особенно сильной. Кстати, если после поста у вас останутся вопросы, которые бы вы хотели обсудить лично, приходите на нашу встречу.
Каждый сервер кластера предоставляет для нас следующие ресурсы: процессор, оперативную память, жёсткие диски и сеть. Сеть здесь — более сложное понятие, чем просто сетевая плата. Это ещё и вся инфраструктура внутри дата-центра, и связность между разными дата-центрами и точками обмена трафиком. В кластере для обеспечения надёжности применялась репликация, и суммарный объём кластера определялся исключительно через суммарную ёмкость жёстких дисков. Нужно было придумать, как обменять оставшиеся ресурсы на увеличение места.
NQ Vault — довольно популярное (30 млн. пользователей) Android приложение (есть версия и для iOS), позволяющее зашифровать выбранные SMS, фотографии и видео на устройстве. Просмотреть зашифрованный контент можно через приложение, введя пароль. Приложение получило хорошие отзывы и обзоры в ведущих ИТ изданиях.
Пользователь GitHub ninjadoge24 решил проверить, насколько хорошо приложение защищает приватные данные.
Читать полностью »
Здравствуй. И сразу к делу.
Задача:
Есть два целых числа: L и R. Нужно найти максимальное значение A xor B на промежутке [L; R], где L ≤ A ≤ B ≤ R.
Казалось бы ничего сложного. Сразу напрашивается решение простым перебором.
public int BruteForce(int one, int two)
{
int maxXor = 0;
while (one < two)
{
int oneTemp = one + 1;
while (oneTemp <= two)
{
int curXor = one ^ oneTemp;
if (maxXor < curXor) maxXor = curXor;
oneTemp++;
}
one++;
}
return maxXor;
}
Сложность этого решения O(n) = n2.
А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд.
Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье.
Читать полностью »
Некоторое время назад, читая хабр, натолкнулся на статью, в которой автор говорит о необходимости шифрования файлов, загружаемых в облако. Будучи тем, кому неприятна одна только мысль о том, что «дядя», предоставляющий услугу облачного хранения данных, имеет возможность использовать по своему усмотрению мои файлы, я стал размышлять об их шифровании. Подталкивало к этим размышлениям и то, что облако предоставляется бесплатно. Разумеется, использование архива с паролем было жутко неудобным решением, когда речь шла о большом количестве загружаемых файлов. Давно как раз для этой цели создал себе специальную утилиту, и сейчас, коли был поднял вопрос, решил об этом рассказать.
Читать полностью »
Инженер-физик Эшер Лэнгтон (Asher Langton) из Ливерморской национальной лаборатории был очень опечален, когда купил цифровое видео в онлайне — и не смог воспроизвести его на своём смартфоне. Оказалось, что видео в файлах .mov закодировано и проигрывается только в фирменном медиаплеере MOD Player производства Leaping Brain. Это обычное дело: такие DRM-схемы часто встречаются в интернете.
К чести учёного, он решил разобраться и взглянул на этот видеоплеер. Оказалось, что это обычный Open Source плеер VLC с прикрученным скриптом Python на некоторых библиотеках. При попытке воспроизвести видео в онлайне программа скачивает файлы на диск в зашифрованном виде — и декодирует их в момент воспроизведения.
Читать полностью »