Skip to content

Instantly share code, notes, and snippets.

@sergei-mironov
Created December 22, 2014 09:10
Show Gist options
  • Save sergei-mironov/7413c23ea4a56483b5ab to your computer and use it in GitHub Desktop.
Save sergei-mironov/7413c23ea4a56483b5ab to your computer and use it in GitHub Desktop.
Валерий
тут на голландском и французском в целом разговаривают
20.12.14
но на работе на английском
я в University of Antwerp
типа phd-студент
Сергей
Ога! А что за тема?
20.12.14
Валерий
там есть один из белорусии еще, испанец есть)
20.12.14
какие-то арабы немного
tomographic reconstruction
Сергей
А, она и есть
20.12.14
Валерий
ага)
20.12.14
Сергей
Живешь в кампусе?
20.12.14
Валерий
квартиру снимаю
20.12.14
типа второй этаж какого-то домика недалеко от работы - 15 минут пешком
Сергей
А работа и учеба - это разные вещи?
20.12.14
Валерий
ну в целом одно и то же)
20.12.14
меня тут ресерчером взяли в лабораторию - и я чего-то делаю, и дожен над диссертацией работать
пытался на курсы голландского ходить, но как-то занятия пропустил по болезни и по дедлайнам - теперь до экзамена могут не пустить)
Сергей
Ну голландский - не самая страшная потеря :)
20.12.14
Валерий
он местами забавный
20.12.14
похоже петр I привез часть слов в россию)
Сергей
Круто! А тебя снаала взяли в лабораторию или ты сначала на phd поступил?
20.12.14
*сначала
Валерий
koop - купить, kantoor - офис)
20.12.14
это была phd-позиция
Сергей
ох, знакомо
20.12.14
Валерий
я на неё пособеседовался - и вот попал
20.12.14
я так понимаю, место в лабе - это способ платить студентам
Сергей
и она предполагала одновременно и работу и учебу?
20.12.14
Валерий
стандартный способ
20.12.14
ага
Сергей
мм, а какой конкурс надо было выдержать для поступления?
20.12.14
Валерий
https://www.uantwerpen.be/en/jobs/vacancies/ap/2014ba..
20.12.14
на вот эту позицию пособеседовался - и меня тут же позвали
про конкурс не знаю
я так понимаю, у них есть какие-то источники финансирования - и они более-менее постоянно хайрят
Сергей
просто собеседование?
20.12.14
Валерий
если кандидат нравится
20.12.14
по сути да
там было два собеседования
а перед этим у меня попросили cover letter и оценки из университета
Сергей
вот это да. Ну а какой уровень требовалось показать? И вот ещё: насколько они смотрели на английский?
20.12.14
Валерий
то есть, я сначала потратил сколько-то времени на cover letter, потом было общее собеседование. дальше они мне дали статью и попросили прокомментировать
20.12.14
Сергей
а, понятно
20.12.14
Валерий
ну если беседу поддерживаешь - то ок
20.12.14
Сергей
а в какой форме комментарий?
20.12.14
Валерий
еще одно скайп-собеседование
20.12.14
Сергей
Слушай, ещё вопрос: до какого возраста они по твоим ощущениям берут на phd?
20.12.14
Валерий
сначала я им рассказал, как я понял алгоритм, потом рассказал, как бы я его улучшил
20.12.14
Сергей
угу, понятно
20.12.14
Валерий
я так понимаю, можно и около 30 вполне
20.12.14
есть люди, которые в industry поработали, а потом решили получить степень
вроде у нас в лабе есть кто-то, кто уже за 30 и недавно получил степень
я про эту проблему тоже беспокоился весной, но решил попробовать
перед этим попробовал еще в швейцарский гугл попасть, но получил 3 отрицательных отзыва против 2 положительных - после 5 интервью подряд)
Сергей
Понятно. Ну спасибо, очень интересно!
20.12.14
Валерий
без практики собеседований они как-то плохо проходят
20.12.14
Сергей
а там именно на английском (в гугле)
20.12.14
Валерий
да
20.12.14
даже с русскими людьми - на английском
Сергей
и гугл это не phd
20.12.14
Валерий
ага
20.12.14
Сергей
а что там спрашивали?
20.12.14
дурацкие задачки решать просили как пугают?
Валерий
ну там было пять интервью
20.12.14
по 45-50 минут каждое - потом перерыв
Сергей
внушительно.. ого, и подряд?
20.12.14
Валерий
после третьего длинный перерыв с питанием
20.12.14
да
Сергей
а, они очные?
20.12.14
Валерий
щас по порядку расскажу
20.12.14
Сергей
давай
20.12.14
Валерий
началось все зимой, когда я решил немного жизнь поменять
20.12.14
написал в январе-феврале резюме
Сергей
:)
20.12.14
Валерий
подал через знакомого в гугл
20.12.14
Сергей
сразу в швейцарский?
20.12.14
Валерий
и для тренировки еще в Samsung Research подал
20.12.14
да
Сергей
так, ага
20.12.14
Валерий
сразу скажу, что про швейцарский гугл была похоже глупость - туда большая конкуренция, потому что там зарплаты повыше
20.12.14
гугл мне позвонил и сделал screen check
спросили что-то про O-нотацию и про сложность сортировки
заодно задали вопрос, не хочу ли я например в Лондон вместо Цюриха
наверное, стоило сказать, что хочу)
дальше было второе интервью по hangouts
велели какой-то простой код писать в google docs
и комментировать
Сергей
хм, странный вопрос, действительно. А что такое hangouts?
20.12.14
Валерий
это гуглочат
20.12.14
типа скайпа
Сергей
а, дада
20.12.14
Валерий
там была какая-то простая задача - надо было картинку покрасить в шахматный порядок
20.12.14
картинка - это массив
ну и по ходу дела спрашивали, сколько памяти нужно, на что она уходит
ну и я там рассказывал чего-то про стек, про стек-фреймы и всякую такую хрень
Сергей
хм, ну да, понятно
20.12.14
Валерий
задачу усложняли постепенно, из соображений экономии памяти
20.12.14
дошли до битовой картинки, где надо было 10 битов красить в один цвет, следующие в другой цвет и тд
геморно, но решаемо, конечно)
потом спрашивали про поиск дубликатов файлов
типа на хеш-таблицы
Сергей
рекурсивно по каталогам?
20.12.14
а, без привязки к файловой системе?
Валерий
ну скорее про стурктуры данных, в которых надо хранить данные про файл
20.12.14
Сергей
ага
20.12.14
Валерий
поговорили на эту тему
20.12.14
потом он решил видимо дать положительный отзыв и меня допустили до очных интервью
они в московском оффисе проходили
Сергей
угу
20.12.14
на английском?
Валерий
трое очно спрашивали, двое снова по конференц-связи из цюриха
20.12.14
все на английском
Сергей
ага
20.12.14
Валерий
перед очными интервью я пошел на интервью в самсунг ресерч
20.12.14
Валерий
там они оказались дурацкими
20.12.14
сначала меня два раза спрашивали более менее одно и то же по скайпу
Сергей
слышал я нелестные отзывы о самсунге
20.12.14
Валерий
общие вопросы
20.12.14
потом они дали мне статью и попросили сделать презентацию про неё
чтобы было про что на очном интервью поговорить
я презентацию не сделал, просто пришел )
стал рассказывать по порядку и точно
* у меня там были какие-то непонятки про разные моменты в статье, но я решил, что до них еще много чего можно рассказать
вместо того, чтобы дослушать, они предложили рукомахательно все рассказать
Сергей
хм
20.12.14
Валерий
ну я так и сделал, после чего они решили, что хватит))
20.12.14
рукомахательно = в общих чертах
Сергей
ага
20.12.14
Валерий
предложили переключиться на какие-то стандартные программерские вещи
20.12.14
Сергей
и тебя захотели брать в самсунг?
20.12.14
Валерий
а я в место этого стал сам им вопросы про статью задавать
20.12.14
ща)
Сергей
угу
20.12.14
Валерий
они короче на них ответить не смогли)
20.12.14
Сергей
хехе
20.12.14
Валерий
в итоге я почувствовал себя увереннее и расслабленней)
20.12.14
после этого собеседования меня захотели брать - типа команде понравился
поговорил с тимлидом по скайпу снова — он опять общие вопросы задава
потом было последнее собеседование с директором центра
Сергей
во как
20.12.14
Валерий
оно было совсем простым
20.12.14
помню вопрос про нейронную сеть
и я ему дал нормальный ответ, а он его переформулировал в какие-то идиотские блоксхемы)
но в общем они решили меня брать и спросили сколько я денег хочу
Сергей
хм
20.12.14
Валерий
я попросил 150k
20.12.14
и пошел ждать офер от них
Сергей
в рублях, а это московский офис?
20.12.14
Валерий
в рублях в москву, да
20.12.14
в итоге они мне предложили потом 108 и готовы были после переговоров до 130 поднять вроде, но я уже на тот момет имел оффер из Антверпена сюда, так что забил
после интервью в самсунге у меня были эти 5 в гугле
Сергей
хм, очень забавно!
20.12.14
Валерий
ну и они были совсем другими - так что я к ним был плохо готов
20.12.14
в первом интервью просили рассказать про самую интересную задачу, которую решал
Сергей
хм
20.12.14
Валерий
и потом предложили придумать алгоритм, как выбрать какие-то веса веса в решающем дереве, чтобы среднеквадратичный функционал минимизировать
20.12.14
ну и там более-менее стандартно сортировкой и все решилось за nlogn
на следующем интервью меня спросили про такую задачу
дана шахматная доска и на ней стоит конь
Сергей
ага
20.12.14
Валерий
он случайно прыгает
20.12.14
надо найти вероятность того, что конь в доске на n-том ходу
если он за доску прыгает - он пропадает
Сергей
ага
20.12.14
Валерий
ну я на этой задаче затупил
20.12.14
я знал, что ее традиционно решают динамическим программированием
но с ходу формулу не получилось записать, так что пришлось думать
Сергей
да, там подумать нужно. может, рассматривать 4 границы независимо и потом как-то суперпозицию получить?
20.12.14
Валерий
нее
20.12.14
там все проще)
короче, есть экспоненциальное решение - это просто промоделировать ходы до глубины n - и посчитать)
Сергей
а, это на алгоритм?
20.12.14
Валерий
не совсем
20.12.14
Сергей
я думал аналитически
20.12.14
Валерий
ща
20.12.14
да, на алгоритм
можно посчитать p(i, k) — вероятность того, что конь на k-ом ходу в позиции i
и рекурсивно выразить через p(j, k-1)
ну я эту формулу написал
она позволяет 64 * O(n) все считать тут
и после этого он мне предложил распараллелить это дело
Сергей
хм, ну ладно
20.12.14
Валерий
ну и у меня была проблема, потому что я не мог сделать 1 лок за итерацию, а дедал 2
20.12.14
делал
и с его подсказки вроде получилось за один
но реально с этой задачей все забавней
потому что вся эта хрень - это просто марковская цепь на 65 состояниях
и надо просто матрицу 65x65 возводить в n степерь за O(log n) операций перемножения матриц
ну то есть я на момент начала интвервью такое умел делать и не знаю, почему не сделал)
от волнения мб
Сергей
ага, понял
20.12.14
Валерий
ну и параллелить там уже по-другому можно
20.12.14
всякие scan, reduce, map
в следующем интервью меня просили сделать дизайн системы, которая бы рекламу по ключевым словосочетаниям в поисковом запросе выдавала бы
Сергей
ну конечно :)
20.12.14
Валерий
при условии, что у меня есть 8 компов, чтобы все работало, а на одном там ниче не помещается)
20.12.14
Сергей
рекламщики
20.12.14
Валерий
тут начала проявляться проблема, которую я себе организовал прямо перед интервью))
20.12.14
я за день до подумал — я никогда не писал сжатого бора))
и взял и написал
Сергей
это преобразование какое-то?
20.12.14
Валерий
это дерево слов
20.12.14
compressed trie
структура данных
Сергей
понял
20.12.14
Валерий
ну я начал эту штуку дизайнить в виде распределенного бора на компах)
20.12.14
но это вроде ничего, нормально
в конце меня попросили оценить, как быстро такое будет работать
вроде какую-то оценку дал, но она, вроде была слишком пессимистичной
но я думаю, это интервью было ок
Сергей
ага
20.12.14
Валерий
на следующем интервью была задача типа "дано слово X и список слов. какие слова из списка можно составить из букв слова X"
20.12.14
надо было код в гуглодоке написать
написал какой-то код, на сравнении гистограм
Сергей
хм, на первый взгляд задача понятна
20.12.14
Валерий
ага
20.12.14
после этого он начал спрашивать, а как можно делать, если слов много
в списке
как-то усложнять начал
и я с дуру снова начал все совать в бор :D
в итоге какое-то переусложненное решение получил
с непонятной асимптотикой
Сергей
запал ты на бор
20.12.14
Валерий
ага)
20.12.14
это не последний раз :D
Сергей
да, они же наверное в константной памяти хотели решение?
20.12.14
Валерий
не, вроде не такое
20.12.14
надо было все подмножества X перебрать, отсортировать и положить в хеш-таблицу
а дальше слово приходит - его можно снова превратить в сортированную последовательность букв, взять хеш и посмотреть в таблицу
Сергей
а, ну да, понятно
20.12.14
Валерий
короче, сейчас реально тема в хеш-таблицах)
20.12.14
их балансировать проще на много машин
Сергей
у нас тоже они - основа "базы данных" NATа
20.12.14
Валерий
здорово)
20.12.14
у меня как-то с ними практики пока не было
так вот, в последнем интервью мне дали задачу - надо про очень большой файл сказать, какой посделовательности из 4 символов в нем нет
и тут я снова решил строить что-то боро-подобное по файлу *facepalm*
Сергей
Да, уже понял что так и будет :)
20.12.14
Валерий
потом меня постепенно надоумили, что можно просто в памяти битовый массив огранизовать
20.12.14
по всем возможным подстрокам длины 4
Сергей
и там ксорить что-то?
20.12.14
Валерий
ну типа если строка есть, мы просто превращаем её в индекс int32 - и по этому индексу в таблице ставим 1
20.12.14
Сергей
а, дада
20.12.14
Валерий
а потом надо пройти по таблице, найти на какой позиции 0 — вот и ответ
20.12.14
ну и еще какие-то мелочи спрашивали
например, сколько бывает бинарных деревьев на занумерованных вершинах
я там выписал рекуррентную формулу — только была пробелема, я не сказал, что это числа Каталана — хотя знал )
Сергей
гм
20.12.14
:)
Валерий
ну просто известные числа)
20.12.14
в кормене про них пишут например, когда матрицы перемножают динамическим программированием
Сергей
ну ладно, в целом ясно
20.12.14
Валерий
в общем, оказался не подготовленным к 5 часам интервью на английском
20.12.14
если бы в форме подошел, то мб и прокатило бы
после этого я подался еще в facebook, в лондон
ну и на phd тоже
Сергей
Опыт вынести оказался в состоянии
20.12.14
Валерий
с фейсбуком было заочное skype интервью
20.12.14
да, про опыт хорошо) потом пригодится
Сергей
что там спрашивали?
20.12.14
Валерий
в фб дали сначала какую-то простую задачу
20.12.14
надо было что-то посортировать и что-то еще сделать
а потом дали задачу посложней
дана строка. нужно сказать, сколько в ней таких подстрок, что в них встречается ровно две различные буквы
Сергей
сначала условие бы понять. Буквы - любые?
21.12.14
тоесть отфильтровать строки, где все буквы - уникальные?
*подстроки
и где хоть одного повтроения буквы больше 2
Валерий
abbahaabba
21.12.14
дана такая строка
у неё подстроки всякие есть
Сергей
ну это да
21.12.14
Валерий
ab, abb, aab - хорошие
21.12.14
а вот baha и aa - плохие
в хороших есть две различные буквы
а в плохих одна или три или больше
Сергей
а ну да
21.12.14
Валерий
хочешь порешать или к решению переходить? :)
21.12.14
Сергей
и на что оптимизировать?
21.12.14
да переходит
*переходи
Валерий
ну у меня в итоге получилась какая-то линейная сложность
21.12.14
я как эту задачу увидел - сразу понял, что надо "два указателя использовать"
но такие задачи меня все время бесят, потому что надо переходы разные продумывать
в итоге из моих попыток чел понял, что идею я знаю, а вот до конца не довел решение
там идея такая
фиксируем левый указатель и идем правым дальше от левого
сначала у нас ситуация типа
aaaaa
потом
aaaaabbbbaaaabbbbaaaa....bbbbcccc
Сергей
ну да
21.12.14
Валерий
вот когда с появились, надо сделать какой-то апдейт
21.12.14
можем посчитать число всех подстрок на aaabbbaaabbb блоке
из него надо вычесть все подстроки, концы которых находятся в aaa и в bbbb
так что надо парсить такими участками постоянства и суммировать подстроки на них
а потом вычесть эту сумму из числа подстрок большого блока
и сдвинуть левый указатель на начало последнего участка постоянства перед cccc
ну и так перемещаться пока строка не кончится
Сергей
хм
21.12.14
Валерий
гемного неприятно кодить, но такое работает и особо злых структур данных по ходу дела не требует
21.12.14
это решение я придумал через 20 минут после конца интервью)
Сергей
у меня что-то с хэш таблицами теперь крутится в голове =)
21.12.14
Валерий
)))
21.12.14
я подумал, что и facebook меня зареджектил
но потом оказалось, что они зовут меня на очное в лондон
типа там оплата отеля и перелета и визы
Сергей
мм
21.12.14
и как?
Валерий
но на тот момент у меня было предложение из университета уже
21.12.14
и я точно знал что поеду я в бельгию, в антверпен
Сергей
а чем примерно в фб пришлось бы заниматься?
21.12.14
Валерий
они какие-то поисковые алгоритмы у себя делать хотят
21.12.14
там лингвистика какая-то
language processing, machine learning
Сергей
угу
21.12.14
логично
Валерий
я в итоге в мае забил на fb, потому что там какой-то гемор с визой был
21.12.14
надо было много анкет заполнять, в очереди ждать чего-то..
Сергей
а в Бельгии проще?
21.12.14
Валерий
не :)
21.12.14
сложнее даже
я сначала пачку документов делал для универа
месяц где-то
потом месяц ждал
потом еще месяц делал пачку на визу
и еще протупил - надо было жениться в начале лета
тогда бы совместно подались на визу и уехали бы вместе
Сергей
=)))
21.12.14
Валерий
а так я женился за дня три до отъезда — жена сейчас только на визу смогла податься
21.12.14
до этого надо было еще местные документы собирать типа residence permit
еще с посольством много геморроя
например, они просят справку про отсутсвие судимости
Сергей
по идее это не сложно
21.12.14
Валерий
правильные шаги такие
1. заказать справку и подождать месяц
2. заказать апостиль на справку и подождать неделю
3. перевести справку и апостиль, сделав нотариальное заверение перевода и копии
4. заказать апостиль на нотариальное заверение перевода и копии
5. сделать 2 копии с полученной пачки :)
21.12.14
Сергей
дыаааа
21.12.14
Валерий
и так со многими другими доками)
21.12.14
с дипломом
на апостилях и переводах можно на 50-100k потратиться легко
если бы с гуглом/фейсбуком переезжал - они бы это дело оплатили и еще с вещами релоцировали
а так у меня еще в москве 100кг книг лежит
не знаю, как их дешево и сердито перевезти...
Сергей
на яхте с каким-нибудь яхтсменом
21.12.14
Валерий
было бы неплохо :)
21.12.14
тут люди вместо домов/квартир иногда на баржах живут, кстати)
Сергей
хаха))
21.12.14
Валерий
в амстердаме на них вечеринки устраивают всякие)
21.12.14
Сергей
у нас я тоже про такое слышал, но это а нашем случае это исключает активную общественную жизнь
21.12.14
Валерий
ага
21.12.14
Сергей
слушай, какую поучительную ты историю рассказал! спасибо, буду осмыслять. индустрия наша мне приелась, я плаинрую вот-вот запускать процесс перевода себя на 3 дня работы в неделю
21.12.14
Валерий
неплохая тема)
21.12.14
можно какие-то другие индустрии попробовать
с phd есть минус некоторый - мне сейчас 2k euro примерно платят
Сергей
такчто желай удачи. в свободное время надеюсь заняться самообразованием, твой опыт воодушевляет. Можно я твой рассказ друзьям передам?
21.12.14
Валерий
я мог бы на большие деньги в австрийский стартап новый перейти - но пока тут нравится, потому что знания
21.12.14
можно)
Сергей
ок. а 2k как там на жизнь?
21.12.14
Валерий
я многое наобум делал, можно гораздо лучгше
21.12.14
вроде нормально
Сергей
сколько квартира стоит?
21.12.14
Валерий
по слухам обычные бельгийцы иногда меньше получают
21.12.14
или на налоги много уходит
квартиру снимаю за 630+электричество+газ+интернет
Сергей
вообще 2k по российским меркам теперь огого после этого кризиса нового
21.12.14
Валерий
так в 720 укладываюсь более-менее
21.12.14
можно дешевле
ага :)
и европа доступна для путешествий
тут всякие билеты выходного дня есть, которые раза в два дешевле
можно ездить по странам
Сергей
ну уж представляю
21.12.14
Валерий
в голландию очень просто ездить - за 40 евро туда-обратно
21.12.14
причем минут за 40 - час можно до амстердама комфортно в поезде проехать
Сергей
слушай, а как устроен механизм открытия phd-вакансий? их институты открывают и публикуют?
21.12.14
Валерий
обычно в институтах есть лабы, которые чем-то занимаются
21.12.14
в какой-то момент в лабе получают грант и хотят по нему проводить работу
Сергей
угу
21.12.14
Валерий
под это дело нанимают phd студентов
21.12.14
и в этот момент в лабе публикуют вакансию - на сайте университета
а еще в разные мейлинг-листы научных сообществ
я так понимаю, иногда даже если нет открытых вакансий, можно все равно напроситься
Сергей
ага, вот теперь сходится у меня инфа. видел же я подобные объявления
21.12.14
там просят часто высылать application или как-то так. Что это может быть?
Валерий
хм
21.12.14
я тут подумал, похоже есть два варианта
бывают вузы, в которые есть отдельный сезонный набор на phd
типа стенфорда, MIT...
Сергей
If you are interested in applying, please contact a potential
supervisor in the FP lab prior to submitting your application
21.12.14
Валерий
в америке всякой
21.12.14
Сергей
вот к примеру там
21.12.14
Валерий
ща
21.12.14
1. если школа имеет какой-то дедлайн по набору, то вроде туда надо прислать стандартный пакет документов, главное в котором —- cover letter, рекомендации, оценки — в таком порядке. Как я понял, можно послать много - часть из писем получает отклик — и тогда можно выбирать из тех, кто согласен, лучший вариант
2. есть отдельные позиции, как в моем случае. там надо примерно тот же пакет документов изготовить, но там надо прямо на емейл будущих руководителей что-то присылать
ну и во втором случае идут какие-то индивидуальные собеседования, и решается вопрос
есть какие-то промежуточные варианты)
http://www.inria.fr/en/institute/recruitment/offers/p..
я вот сюда еще смотрел, например
http://academicpositions.eu
Сергей
Понял, спасибо! Нужно хорошо подумать. Можно я потом тебя ещё помучаю?
21.12.14
Валерий
еще полезно этим заниматься в начале зимы
21.12.14
конечно
Сергей
а почему не осенью?
21.12.14
или точнее не перед началом учебного года?
Валерий
да, осенью еще лучше
21.12.14
так бы я еще попробовал в какие-то штуки типа mit, stanford, ... податься
но хотелось чего-то побыстрей поменять - ну и в течение пары недель все порешить :)
в целом не жалею - тут интересно и задачи сложные
но в целом по миру не самое престижное место
в голландии кстати вузы тоже веселые
Сергей
в каком смысле?
21.12.14
Валерий
веселые?
21.12.14
неплохие
в Lieden-е например разные Лоренцы учились, работали)
Дейкстра тоже из голландии
есть старые университеты с богатой историей
в бельгии тоже есть какие-то. а конктретно мой университет довольно молодой - его лет 15 назад начали организовывать на базе каких-то учебных заведений
в целом все зависит от твоих желаний/предпочтений)
Валерий
если хочется найти новую область и поработать в ней с пользой - не обязательно выбирать именитый вуз
21.12.14
в общем, смотри вакансии)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment