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. Хоть понятия и пересекаются, но не совсем о том :) Но не удалять же пост

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

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

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

Задача:

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

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

Доброй ночи!

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

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

Bloom Filter

Наткнулся случайно на такую вероятностную структуру, как фильтр Блума.

Вот ее описание:

• http://ru.wikipedia.org/wiki/Фильтр_Блума
• http://en.wikipedia.org/wiki/Bloom_filter

И пример реализации:  http://habrahabr.ru/post/112069/

Мой код собственно и есть подобная реализация, с таким же семейством хэш-функций.

Встречайте, https://github.com/frydaykg/Bloom!

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

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

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

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

Задача
Есть функция

byte f(byte b);

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

Задача:
Условие взял отсюда.
Есть односвязный список

struct List { int value; struct List *next; } _list;

требуется написать функцию

bool isCycled(struct List *head);

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

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

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

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

Вопрос:

Есть три точки в пространстве. Нужно найти уравнение нормали к плоскости ими образованной.