August 23rd, 2011

Main

Все еще больница

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

Сходить домой официально не дают, но если я "ушел погулять" и меня 3-4 часа нет, то пока никто не придирался. Сделал за свой счет МРТ и КТ, прямо как в сериале про Хауса.

Есть возможность подучиться, -- продираюсь сквозь Crash monad tutorials juan_gandhi, вернее через перевод, где, несмотря на трололо, есть весьма полезные объяснительные комментарии. Как-то та математическая монада не до конца сцепилась с монадой Хаскельной в моей голове, это скорее от того, что я и хаскель еще не вкурил до понятного состояния. Ну буду медитировать и ковырять хаскель маленькими порциями.

Поскольку я тут единственный ходячий, вполне сойду скоро и за санитара :)
Нэцкэ

MS. Разбор полетов-1

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

Итак задачка про паттерн-матчинг:
Write a function which determines whether provided string matches specified pattern. Signature:
bool is_match(char* text, char* pattern)

Pattern can contain any characters + '*' character which means zero or more characters. For example: is_match("hello", "h*o") returns true; is_match("hello", "hel*lo") also returns true.

Чтобы понять механику решения необходимо понимать работу с конечными автоматами, в чем я имел пробел в знаниях. Наиболее лаконичная теоретическая часть приведена в статье:
Недетерминированные конечные автоматы,

решение конкретно этой задачи через НКА (вширь и в глубь), а также через ДКА есть на форуме RSDN:
http://rsdn.ru/forum/job/4374248.1.aspx

Там же приведено лаконичное решение через рекурсию (по сути это НКА вширь):
match (re,str)
  switch (*re)
    '*': return match(re+1,str) || match(re,str+1)
    '?': return match(re+1,str+1)
    0:   return *str==0
    default: return *re==*str && match(re+1,str+1)
Нэцкэ

MS. Разбор полетов-2

Задачка 2 с вариацией:
There is a file that contains 10G(1000000000) number of integers, please find the Median of these integers. you are given 2G memory to do this.

Вариация: у нас есть большой, но не огромный массив с целыми числами вместо файла.

Собственно по ссылке в моем исходном посте и было указано два решения.

Если у нас поток символов очень большой длины, то удобнее всего сделать массив для гистограммы, который покроет 16 битные целые. И два раза пробежаться по потоку (для старших 16 бит и для младших 16 бит), рассчитав гистограмму частоты вхождения каждого числа и взяв медиану по гистограмме. Места займет всего 8*2^16 байт, т.е. меньше мегабайта.

http://stackoverflow.com/questions/3572640/interview-question-find-median-from-mega-number-of-integers/3576479#3576479

Если у нас массив с числами и он уже помещается в памяти, то можно применить метод Медиан Медианов:
http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Он линеен по времени и использует сортировку "на месте", т.е. в исходном массиве.

Пример воплощения алгоритма:
http://books.google.ru/books?id=qhaOxkQANEgC&lpg=PA75&ots=dC9cXH7rQw&dq=BFPRT%20implementation&pg=PA75#v=onepage&q&f=false


realurix сказал подсказал, что эта задачка на знание и понимание теоремы кодирования Шеннона. Этого я не очень понял, поскольку теорема Шеннона она про сжатие и передачу сигнала по каналу с шумом. Единственный похожий на эту задачу подход я обнаружил в Алгоритме сжатия Шеннона — Фано, там строится частотная таблица точь-в-точь, как наша гистограмма.