Friday, December 24, 2010

Вопросы с собеседований Google, часть 4

Судя по количеству комментариев тема вопросов с собеседований Google является наиболее востребованной. Что ж, продолжу. Предыдущие вопросы всегда можно посмотреть тут.




Вопросы:
16) Напишите функцию (и вспомогательные функции, если потребуется), которая берет на вход имя колонки из Excel (A,B,C,…AA,AB,AC...AAA) и возвращает соответствующее ему целочисленное значение (A=1,B=2,AA=27...)

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

18) Алгоритмы поиска по дереву. Напишите код BFS и DFS, оцените время выполнения и требования к памяти. Измените код BFS и DFS, так чтобы он работал с графами содержащими циклы и с графами со взвешенными ребрами. Сделайте так, чтобы код печатал путь от исходной вершины к искомой.

19) Вам дан циклический список чисел. Циклический, значит, что когда вы доходите до конца, вы снова возвращаетесь к началу. Напишите самый эффективный алгоритм поиска минимального числа в этом списке. Как найти заданное число в этом списке? Числа в списке упорядочены строго в порядке возрастания, но вы не знаете, в каком месте список начинается, например: 38, 40, 55, 89, 6, 13, 20, 23, 36.

20) В чем разница между локальными и глобальными переменными?


Возможные варианты решения...

Monday, December 20, 2010

Латентно-семантический анализ


Недавно я обещал рассказать об еще одном применении SVD. Выполняю данное обещание. В этой статье рассказывается о латентно-семантическом анализе и показывается на примере, как его можно использовать чтобы сгруппировать статьи из ленты новостей по разным тематикам. Модификации этого алгоритма применяются гигантами интернет поиска для классификации статей и вебсайтов.


Читать дальше >>>

Wednesday, December 15, 2010

Стеммер Портера для русского языка

Выделение основы слова это одна из задач, часто возникающая в процессе обработки текста. В школе нас конечно учили это делать, кто-нибудь помнит как? Я нет. К тому же, русский язык обладает особой сложностью и если в английском достаточно сделать несколько простых преобразований (вроде удаления ing-ового окончания) и мы уже с высокой степенью достоверности получаем требуемую основу. В русском языке эта задача намного сложней. В идеале, она решается путем составления больших морфологических словарей. Но это не путь ленивого программиста, словари надо поддерживать, ведь язык постоянно меняется, надо отдельно обрабатывать ошибки и опечатки. Путь ленивого программиста другой, специально для них, Мартин Портер в 1980 году изобрел алгоритм стемминга.

Главный плюс стеммера Портера заключается в том, что он не использует никаких словарей и выделение основы осуществляется путем преобразования слова согласно определенным правилам. В интернете полно реализаций этого алгоритма, в том числе и для Java, но, к сожалению, мне не удалось найти реализацию которая прошла бы тест самого Портера (внимание, большой документ) и в то же время сохраняла краткость и лаконичность. Поэтому, пришлось писать велосипед основываясь на PHP версии взятой здесь

Нет смысла переписывать описание алгоритма, оно, пусть и на английском, детально изложено на сайте самого Мартина Портера

Исходники на Java:
import java.util.regex.Matcher;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Porter {

    private static final Pattern PERFECTIVEGROUND = Pattern.compile("((ив|ивши|ившись|ыв|ывши|ывшись)|((?<=[ая])(в|вши|вшись)))$");

    private static final Pattern REFLEXIVE = Pattern.compile("(с[яь])$");

    private static final Pattern ADJECTIVE = Pattern.compile("(ее|ие|ые|ое|ими|ыми|ей|ий|ый|ой|ем|им|ым|ом|его|ого|ему|ому|их|ых|ую|юю|ая|яя|ою|ею)$");

    private static final Pattern PARTICIPLE = Pattern.compile("((ивш|ывш|ующ)|((?<=[ая])(ем|нн|вш|ющ|щ)))$");

    private static final Pattern VERB = Pattern.compile("((ила|ыла|ена|ейте|уйте|ите|или|ыли|ей|уй|ил|ыл|им|ым|ен|ило|ыло|ено|ят|ует|уют|ит|ыт|ены|ить|ыть|ишь|ую|ю)|((?<=[ая])(ла|на|ете|йте|ли|й|л|ем|н|ло|но|ет|ют|ны|ть|ешь|нно)))$");

    private static final Pattern NOUN = Pattern.compile("(а|ев|ов|ие|ье|е|иями|ями|ами|еи|ии|и|ией|ей|ой|ий|й|иям|ям|ием|ем|ам|ом|о|у|ах|иях|ях|ы|ь|ию|ью|ю|ия|ья|я)$");

    private static final Pattern RVRE = Pattern.compile("^(.*?[аеиоуыэюя])(.*)$");

    private static final Pattern DERIVATIONAL = Pattern.compile(".*[^аеиоуыэюя]+[аеиоуыэюя].*ость?$");

    private static final Pattern DER = Pattern.compile("ость?$");

    private static final Pattern SUPERLATIVE = Pattern.compile("(ейше|ейш)$");

    private static final Pattern I = Pattern.compile("и$");
    private static final Pattern P = Pattern.compile("ь$");
    private static final Pattern NN = Pattern.compile("нн$");

    public String stem(String word) {
        word = word.toLowerCase();
        word = word.replace('ё', 'е');
        Matcher m = RVRE.matcher(word);
        if (m.matches()) {
            String pre = m.group(1);
            String rv = m.group(2);
            String temp = PERFECTIVEGROUND.matcher(rv).replaceFirst("");
            if (temp.equals(rv)) {
                rv = REFLEXIVE.matcher(rv).replaceFirst("");
                temp = ADJECTIVE.matcher(rv).replaceFirst("");
                if (!temp.equals(rv)) {
                    rv = temp;
                    rv = PARTICIPLE.matcher(rv).replaceFirst("");
                } else {
                    temp = VERB.matcher(rv).replaceFirst("");
                    if (temp.equals(rv)) {
                        rv = NOUN.matcher(rv).replaceFirst("");
                    } else {
                        rv = temp;
                    }
                }

            } else {
                rv = temp;
            }

            rv = I.matcher(rv).replaceFirst("");

            if (DERIVATIONAL.matcher(rv).matches()) {
                rv = DER.matcher(rv).replaceFirst("");
            }

            temp = P.matcher(rv).replaceFirst("");
            if (temp.equals(rv)) {
                rv = SUPERLATIVE.matcher(rv).replaceFirst("");
                rv = NN.matcher(rv).replaceFirst("н");
            }else{
                rv = temp;
            }
            word = pre + rv;

        }

        return word;
    }

}


Для желающих протестировать, волшебная кнопка:



Tuesday, December 14, 2010

Стоп-символы русского языка

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


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


Помимо указанных слов имеет смысл еще фильтровать цифры, отдельные буквы и знаки препинания.

P.S. Cуществуют еще, так называемые, зависимые стоп-символы. Это, например, слово Владимир в фразе Владимир Путин. Такие слова нельзя выделить в отдельный список, однако их приходится учитывать при создании алгоритмов анализа текстов. Многие из них являются частью именованных элементов и представляют особый интерес. К ним мы еще обязательно вернемся.

Инвестирование, век живи - век учись.


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

Thursday, December 9, 2010

Японские свечи, автоматическое распознавание

Пока мое счастливое семейство отдыхает в дали от Московской суеты, в свободное от работы время, занимаюсь написанием программки, которая будет распознавать свечные модели на графиках акций. Изначально была мысль проверить статистику, а теперь подумалось, а вдруг оно кому-то еще пригодится. В связи с этим, написал маленький гаджет для blogspot, который показывает результаты распознавания свечных моделей на дневных графиках для акций компаний, входящих в ММВБ-Топ.

Результаты генерятся раз в день, в 9 вечера по Москве, и отображаются пока только последние, то есть, согласно теории технического анализа, должны предсказывать изменения котировок на следующий день. Дату генерации всегда можно посмотреть сверху.

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



Ах да, дисклаймер: Никакие данные с этого гаджета не являются публичной офертой, вы сами отвечаете за последствия принятых инвестиционных решений. Ни при каких обстоятельствах algorithmist.ru и его владелец не несут ответственности за ущерб, прямым или косвенным образом полученный в результате использования этих данных.

Monday, December 6, 2010

Вопросы с собеседований Google, часть 3

Доброго времени суток, уважаемый читатель.
Пришло время продолжить серию вопросов с собеседований. Следующие пять вопросов ниже. Начало этой серии тут и тут

Для желающих решать самостоятельно, сами вопросы:

11) Напишите функцию f(a,b) которая получает на вход две строки a и b и возвращает строку, содержащую символы содержащиеся в обеих строках, в том порядке, в котором они перечислены в строке a. Напишите версию с алгоритмической сложностью O(N2) и O(N)
12) Вам дана программа, которая падает во время работы. Вы запустили её 10 раз в дебаггере и обнаружили, что она никогда не падает в одном и том же месте. Известно что программа однопоточная и использует только стандартную библиотеку С. Что может вызывать подобное поведение? Как вы проверите свои гипотезы?
13) Объясните, как работает контроль насыщения (congestion control) в TCP?
14) В Java, в чем разница между final, finally и finalize?
15) Что такое многопоточное программирование и что такое взаимная блокировка (deadlock)?

Продолжение...

Thursday, December 2, 2010

Вопросы с собеседований в Google, часть 2

Продолжаю решать вопросы с собеседований в Google. Первый пост тут

Итак, сначала вопросы, для тех кто хочет решить самостоятельно:

6) Спроектируйте библиотеку классов для создания карточных игр
7) Вам нужно проверить, что у вашего друга есть ваш правильный телефонный номер, но вы не можете спросить его напрямую. Вы должны написать вопрос на открытке и дать её Еве, которая отнесет открытку Бобу и потом вернет ответ вам. Что следует написать на открытке помимо вопроса, чтобы Боб смог закодировать сообщение так, чтобы Ева не смогла расшифровать ваш телефонный номер? 
8) Как передаются Cookies в HTTP протоколе?
9) Спроектируйте таблицы SQL базы данных для системы проката автомобилей.
10) Напишите регулярное выражение которое матчит email-адрес.


Wednesday, December 1, 2010

Вопросы и ответы с собеседований в Google

Здесь опубликован список вопросов с собеседований Google на должность разработчика.

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

Вопросов много, посему это растянется на несколько постов. Итак, поехали:

1) Почему крышки для канализационных люков круглые?

Пожалуй, самый известный вопрос с собеседований гугл. Он уже столько раз обсуждался, что я даже не уверен, задавался ли он на самом деле в гугле. На самом деле, этот вопрос скорее проверяет способность рассуждать. Классический ответ на него можно найти в википедии.

2) Чем мутекс отличается от семафора? Кого из них вы будете использовать для того чтобы обезопасить операцию инкремент?

Прежде всего, мутекс бинарный, то есть либо занят – либо свободен. Либо открыт – либо закрыт. Семафор же может принимать множество значений от 0 до некоторого заданного максимального значения.

Но это еще не всё.  Мутекс всегда приналежит одному единственному потоку. Этот поток его получает и он же обязан его вернуть. Семафор же, напротив, никому не принадлежит и может получить сигнал из любого потока (процесса).

Что же касается второй части вопроса, я буду использовать мутекс.

3) Напишите программу на C которая измеряет скорость переключения контекста на UNIX/Linux.

В C я не силен, а вот написать программу измеряющую скорость переключения контекста на Java… давайте попробуем:
public class ContextSwitch implements Runnable{

    private Object lock = new Object();
    private volatile int counter = 0;
    public static final int MAX_CNT = 1000000;

    public void run() {
        for(;;){
           synchronized (lock){
               counter++;
               lock.notify();
               if (counter<MAX_CNT){
                   try { lock.wait(10000); } catch (InterruptedException e) {}
               }else{
                   break;
               }
           }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        ContextSwitch cts = new ContextSwitch();
        Thread t1 = new Thread(cts);
        Thread t2 = new Thread(cts);
        long startTime = System.currentTimeMillis();
        t1.start();
        t2.start();
        t1.join();
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }

}

На моем компьютере получается 100000 переключений в секунду.


4)Вам дана функция возвращающая случайное число в диапазоне от 1 до 5. Напишите функцию которая будет возвращать случайное число в диапазоне от 1 до 7.

Дополнение: обе функции возвращают целые числа.

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

int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i равномерно распределено между 1 и 25
} while(i &gt; 21);
// i равномерно распределено между 1 и  21
return i % 7 + 1; // результат равномерно распределен между 1 и 7

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


5)Опишите алгоритм обхода графа в глубину.

Для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Реализуется обычно либо с помощью стека либо с помощью рекурсии.