Я люблю CodeForces не только за то, что тут можно порешать интересные контесты, но и потому, что есть возможность читать блоги.
К сожалению, большинство блогов унылы чуть более, чем полностью. Исключение составляют разборы задач и отчеты с поездок, а также почти все посты SkidanovAlex.
Недавно в посте RodionGork всплыло обсуждение того, кем работают олимпиадные программисты. Такие обсуждения были и раньше. Было бы интересно послушать рассказы тех, кому действительно есть что рассказать. В одном из комментов SkidanovAlex писал, что ушел из MicroSoft ради работы в стартапе. Я почитал также про это в его блоге (кстати, всем рекомендую) и, думаю, сообществу CodeForces также интересно было бы узнать эту историю. Ведь он уже писал об "истории одной браузерки", о своем путешествии в Лас-Вегас, а также смысле жизни после ICPC.
Так вот было бы здорово послушать о специфике работы в MicroSoft и стартапе, а также почитать советы начинающим, как стать таким крутым.
Почти в любой большой компании (кроме, однозначно, Facebook -- об этом ниже) очень много бюрократии. Программист может принимать какие-то решения на низком уровне, но все глобальные решения принимаются вверху, и они часто спорные. Приходится фигачить то, с чем не согласен.
Microsoft хорош, если нужна стабильность -- у тебя высокая зарплата, карьерный рост, пакет страховки -- все что надо. Можно писать аисту на тему детей, и оседать :о) Но в 25 такой вариант не заходит (всем привет, у кого первый мелкий появился раньше -- я не согласен с вашим решением :о)).
А в 25 хочется сделать что-то более безбашенное. Когда я ушел из Microsoft у меня оставалось несколько месяцев до грин-карты и очень много незавестенных акций -- но это не сильно остановило, потому что деньги вообще не важны при текущем уровне зарплат в америке для программиста -- 90К в год или 150К в год уже не так важно, потому что и то и то -- это до хрена. И акции не важны. Потому что деньги, которые есть сегодня, не важны, важно, как много ты сможешь делать завтра (сетевики в этом плане дело говорят -- работать, чтобы получать деньги -- это тупо, надо работать, чтобы в будущем получать больше денег). Хотя тоже зависит от количества акций. Если акций на 2 миллиона, то они важны :о) Ну у меня столько не было в любом случае.
Стартапов в калифорнии как овец не резанных. 30% -- новые революционные соцаильные сети, еще 30% -- новое убийственное приложение для iPhone, еще 30% -- новое революционное облачное решение, и 10% -- бесперспективные по мнению первых 90% стартапы :о) Ну мы в 10% -- мы пишем базу данных.
И у стартапов есть очень крутые свойства:
1. Ты получаешь такую же зарплату (если ты не founder -- я не founder).
2. Ты делаешь то, что тебе интересно!
3. Ты принимаешь решения
4. У тебя есть не нулевой шанс стать очень богатым.
Так как стартапов миллионы, то и процесс там уже поставлен на рельсы. Есть компании, которые знакомят стартапы с инвесторами. Нашей компанией была Y-Combinator. Нами интересовалась sequoia, Paul Buchheit (пацанчик, который начинал Gmail), и (о да!) Эштон Кучер :о) Короче там все круто. После стартапа я подумываю вернуться в Microsoft. В Калифорнии тоже есть варианты -- Facebook, Google. Но в Microsoft вы программируете в студии, а тут надо отправляться в одиночное эротическое путешествие в emacs или vim -- это, конечно, не вариант :о(
А, да, почему в Facebook нет бюрократии -- потому что там убийственно тупой режим ,когда сотрудники принимают все решения (я не знаю все ли это еще так, и не утрировал ли это все тот парнишка, который мне это рассказывал во время интервью туда). Из крутых примеров -- фейсбуковский чат написан на Эрланге, потому что два чувака, которые начинали его, решили, что Эрланг отлично для этого подходит. Ну теперь там миллиарды сообщений в день проходят через него -- а он на писан на (очевидно, не очень шустом) Эрланге :о И release cycle там, соответственно, очень крутой -- все что зачекинино за неделю дается всем сотрудникам в понедельник поиграться, найти косяки, а во вторник идет на live site.
Это, однозначно, очень круто для тех, кто работает там -- ваш код идет live меньше чем через неделю, вы принимаете решения -- это очень круто. Но я не уверен, что это хорошо для продукта.
Я просто немного утрировал :о) В любом случае, доминирующее количество С++ кода в Google пишется в emacs и vim.
Никто не говорит, что они не подходят. Весь мир в них пишет, и не жалуется.
Но мне большого удовольствия это не доставляет -- я предпочитаю Visual Studio. Я вообще не фанат Linux и всего, что с ним связано.
Визу-то сделали конечно.
Визу можно обновлять в течение шести лет, потом надо на год выехать из страны, и можно снова по H1B.
За шесть лет я надеюсь все-таки получить Green Card :о)
Пипец если наступит в Америке, в остальном мире тоже сладко не будет -- там не важно будет где ты заныкался :о) А тушенки у меня в холодильнике на этот случай и доширака на год.
Доширак = просто лапша :о).
Медалька помогает быть замеченным, интервью в Microsoft и Google, которые я проходил, были не серьезными. В Facebook были пожестче, причем значительно.
На последнем курсе надо поехать на стажировку -- заметно проще попасть, чем сразу на работу, получишь кучу денег, повыпендриваться перед одногруппниками, которые ехали в Work and Travel, и работали в Loriel или Cheesecake Factory, что вот ты такой крутой. Там главное не провтыкать пока ты там, и сделать так, чтобы на следующий год тебя пригласили на полный рабочий день.
Английский знать надо так, чтобы ты мог понимать людей, и мог выразить мысль. Посмотри серию теории большого взрыва на английском. Если ты можешь следить за мыслью -- половина пути уже пройдена. Но, понятно, пара месяцев репетитора лишними не будут. Я по английски до сих пор говорю на слабеньком уровне, меня это не сильно смущает :о)
К иностранцам здесь относятся как к своим -- это не Россия, где у людей комплексы на эту тему, и иностранцев чмырят. Паспорт никто не спрашивает -- он тут никому не нужен. Внутри страны даже на самолете можно летать по водительским правам. Паспорт я с пыльной полки достал только один раз, когда летал в Харбин.
Кстати, про Work and Travel -- я сам туда не ездил, но это потому что я был тупой. Даже если ты будешь работать барменом всю поездку, ты отобьешь стоимость с заметным запасом, посетишь кучу офигенных мест, посмотришь, как живут в "той стране". Конечно, альтернативно можно подумать, что это "не твой" уровень -- делать коктейли, и просидеть все лето играя в контру и решая задачки. Это выбор каждого отдельного человека :о)
Выведи дерево по слоям за константу памяти и линейное время. Дерево задано ссылками на детей, менять ссылки можно.
Это не совсем то, что мне задали (там NDA, я не могу говорить задачки), но это того же уровня.
С этой задачи начался мой провал, но вообще в конечном итоге я провалил не из-за алгоритмического интервью.
A
|\
CD
| \
B E
\
F
ACDBEF?
Хм, интересно было бы где-нибудь внизу темы услышать решение.
Забыл сказать, что дерево бинарное. Каждая вершина хранит два указаеля на детей, и их можно менять.
у каждой вершины ровно 2 указателя? (кроме детей)
менять указатели - это в том числе направлять их на какую попало вершину, разрушая структуру дерева?
upd. есть ли указатели у детей? можно ли их тоже тыкать куда попало?
Да, дерево можно разрушить. Восстанавливать в конце не надо.
У каждого из детей, очевидно, есть тоже ровно два указателя -- на его детей :о) Если ребенка нет, указатель все равно есть, просто он равен NULL.
Указатель на предка делаем указателем на следующую в этом слое вершину справа. Для первого слоя у нас есть только одна вершина, а для каждого i-го мы можем получить ее (следующую в этом слое вершину), пробежавшись по i-1-му слою. Таким образом, каждую вершину мы посетим максимум 3 раза - когда будем ее выводить, когда будем подцеплять ее первого потомка, и когда будем подцеплять ее второго потомка. Аналогично, потребуется только 2 указателя
Да, все, почему-то показалось, что есть еще ссылка на предкаВроде как-то так
-----------------------------------------------------------------------
Пробежавшись по i-1-ому слою и поменяв ссылки у i-ого, мы потеряли информацию о i+1-ом, нет?
nevermind
UPD. в прошлой редакции что то похожее на решение о ОЭто правильное (и задуманное) решение.
Петя живет в Москве, а не в России. Это две большие разницы.
У меня были причины уехать. И нет причин возвращаться :о) Я не считаю уровень жизни в Америке и России одинаковым.
Попытка переписать пост на общем языке в предыдущей правке оказалась не оценена :о(
Обазятельно будем искать общий язык на онсайте :о)