Monday 11 November 2013

Code Troopers

В прошлом году в виду каких-то дел, а может быть и лени,  не участвовал в первом конкурсе на программирование AI от Mail.ru. Ребята писали стратегии для танков, судя по всему было забавно.

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



Sunday 3 November 2013

Вопросы на собеседовании #5


«
На углу двое юношей возились с каким-то механическим устройством. Один убежденно говорил: «Конструкторская мысль не может стоять на месте. Это закон развития общества. Мы изобретём его. Обязательно изобретём. Вопреки бюрократам вроде Чинушина и консерваторам вроде Твердолобова». Другой юноша нёс свое: «Я нашел, как применить здесь нестирающиеся шины из полиструктурного волокна с вырожденными аминными связями и неполными кислородными группами. Но я не знаю пока, как использовать регенерирующий реактор на субтепловых нейтронах. Миша, Мишок! Как быть с реактором?» Присмотревшись к устройству, я без труда узнал велосипед.
»
— Братья Стругацкие, «Понедельник начинается в субботу»

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

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

Tuesday 29 October 2013

Tree inclusion problem

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

Включенное дерево(Inclusion tree) - это маркированное дерево P, которое можно получить из маркированного дерева T путем удаления его узлов, если узел v дерева T удален, то все ребра идущие из него заменяются на ребра из родителя v к его детям.

Красный узел -- узел который удаляем.

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

Можно почитать:

  1. http://www.cs.ucr.edu/~stelo/cpm/cpm03/Valiente.pdf
  2. http://www.mathnet.ru/links/1140e3926c2d8debfd832352d2bd60df/znsl2144.pdf
  3. http://link.springer.com/chapter/10.1007%2F3-540-57182-5_13#page-1(хотят бабосы)
  4. http://www2.imm.dtu.dk/~inge/treeInclusion.pdf


Alarm!!! Этого поста не должно было быть, я перепутал понятия Tree inclusion problem и Inclusion tree. Хоть понятия и пересекаются, но не совсем о том :) Но не удалять же пост

Sunday 27 October 2013

Вопросы на собеседовании #4

Собеседование производилось на позицию Python разработчика, было очень весело и классно.

Вопрос взят с тестовых заданий Yandex.

Задача:
В системе авторизации есть ограничение — логин должен начинаться с латинской буквы, он может состоять из латинских букв, цифр, точки и минуса, но заканчиваться только латинской буквой или цифрой; минимальная длина логина составляет 1 символ, максимальная — 20 символов. Пожалуйста, напишите код, проверяющий соответствие входной строки этому правилу. Придумайте несколько способов решения задачи и сравните их.

Friday 25 October 2013

Каптча promzona.kg и смех и грех

Доброй ночи!

Писал уже как-то о обходе каптчи на сайте бишкекского клуба Промзона. Вот тута: Обход капчи: promzona.kg.

Но разработчики не сидят на месте, а улучшают свой код! =) Встречайте!



Sunday 20 October 2013

Bloom Filter

Наткнулся случайно на такую вероятностную структуру, как фильтр Блума.
Вот ее описание:
Мой код собственно и есть подобная реализация, с таким же семейством хэш-функций.
Встречайте, https://github.com/frydaykg/Bloom!

Я накидал там парочку issues, если у кого есть время и идеи -- форкайте или комментите, я если что поправлю.

А вообще очень здоровская структура, пописать бы проект с ее применением...

Вопрос на собеседовании #3

Задача до "верного" решения которой я вряд ли бы додумался :)

Задача
Есть функция
byte f(byte b);

Надо ее реализовать так, чтобы она возвращала тот же байт, только порядок битов в них должен быть реверснут, то есть:
01100011 ==> 11000110

Функция должна работать максимально быстро, по памяти мы не ограничены.

Saturday 19 October 2013

Как меня насильно окультуривали или Самокат + Биеналле

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

Условия выдачи самокатов таковы:
1. Предъявить паспорт (или другой документ, удостоверяющий личность).
2. Показать входной билет от текущей даты на любую выставку МВО «Манеж».
3. Оставить залог в размере 2000 рублей.

Паспорт, деньги -- есть! Билета нет, но почему бы и не посетить допустим "5 Московская биеннале современного искусства"

На входе ждала нас "приятная радость", Beeline за имя, отчество, дату рождения, номер телефона, электронную почту и отпечатки пальцев делился билетами на биеннале.

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

Самокат -- устройство антивандальной, две регулировки, простой складной механизм и приемлемый вес. Едет здорово! Только рассказом это не описать, берем и пробуем!



Также дают культурные маршруты, таких 10 штук от 15 минут до 2 часов, но мы поехали своим путем и в итоге намотали 19 км. В итоге мы поняли, что плитка -- сакс, асфальт -- тема! Спасибо Собянину)

К часам 8 вернули самокаты и пошли смотреть выставку, я как всегда обнаружил тут слабую часть в обеспечении безопасности)) Beeline предлагает установить приложение Bee In и найти на выставке 7 граффити с QR-кодом, отсканить их приложением и получить приз! Теперь у нас есть две хипстерских сумки)

По искусству: я в нем не секу, и даже в самом слове без практики стал ошибаться %) большая часть треш, но есть вещи симпатичные и интересные! Варит же у кого то голова!

 


Всем посетить биеналле и покататься на самокатах, времени у вас немного осталось! Всем мир!

[upd]
а мы еще во вторник нормально так покатали =)

[upd2]
а еще мы завтра покатаем!

[upd3]
нет Picasa для Ubuntu! Фото ищите в фейсбуке.
Ну и долго же я писал этот пост :)

Monday 7 October 2013

Вопрос на собеседовании #2

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

Задача:
Условие взял отсюда.
Есть односвязный список
struct List {
    int value;
    struct List *next;
} _list;

требуется написать функцию
bool isCycled(struct List *head);

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



Saturday 5 October 2013

Вопрос на собеседовании #1

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

Задали вот этот в крупной(даже очень на мой взгляд) компании.
Вопрос:
Есть три точки в пространстве. Нужно найти уравнение нормали к плоскости ими образованной.


Wednesday 30 January 2013

Facebook Hacker Cup: Qualification

Второй год пытаю шансы в данном соревновании. Почему пытаю? Да потому что вся надежда только на призрачные шансы, что кто-то лажанет и я пройду в уровень выше =) Как всегда никакой подготовки...вообщем пытаю шансы =)



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

Потом перед вторым уходом решил написать вторую задачу, так как боялся глупого бага в первой. Долго тупил с решением, знал, что динамика...но динамику решать я не умею, в итоге написал рекурсивную штуку, которая по моим оценкам должна работать за максимум O(N*N). Но iensen, говорит, что там возможно O(N^3). В точной оценки сомневаюсь, но с ограничением N<=100, это не страшно :)
Судя по всему мое решение верное, но я спешил, накосячил с выводом и заговорился. И плакали в итоге мои 6 минут =)
Авторское решение прикольное, какое-то интуитивное, но не до конца понятное.

Вечером после написания второго, я просмотрел третье задание, и решил, что там надо искать циклы. Но было лень, и  я даже не стал притрагиваться к IDE.
Как показало, авторское решение, там действительно циклы. Вот она сила интуиции!.

Поздравляю с прохождение квалы: Андрея Мохова, Евгения Балая и Александра Никифорова.

Увидимся в первом раунде. Надеюсь пройду его =)

P.S. футболок мало, до нее точно не доберусь =((

Monday 14 January 2013

Обход капчи: promzona.kg

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



Зашел я зачем-то на сайт промы, а они дизайн поменяли, ну я и решился побродить по разделам. Зашел в курилку. Посмотрел на предмет XSS, комменты модерируются. Каптча --- простой пример. Вспомнил статью Антона Кирсанова об "обходе" капчи на сайте какой-то онлайн игрушки. На первый взгляд тут разброс результатов побольше.  Залез в код странички, опа:

<img src="../images/ciferki/1.gif" border="0" Alt="Введите ответ указанный на картинке" Title="Введите ответ указанный на картинке">

<input style="FONT-SIZE: 10px" type="hidden" size="10" name="kod_ciferki" value="1">

Ага! Хоть по названию картинки результат определяй, хоть по хайденному полю! Смотрим сколько всего картинок...22, от 1 до 21. Зная элементарную арифметику, скрипт написанный за 5 минут, может заспамить администрацию клубу. Лекарства для мужской силы конечно не порекламируешь, так как капча, но насолить можно.

Написал в курилку, заботит ли их безопасность каптчи на сайте. Жду ответа =)

Нашел еще одну багу, как такое использовать не знаю.
Вот она: http://promzona.kg/photo?id=8
Может даже и не как и нельзя, но не комильфо, в любом случае, какое-никакое раскрытие. Если кто знает, напишите. Мне интересно =)

Всем мир!