?

Log in

No account? Create an account
Main

Bing Interview

Сходил на интервью в Microsoft. Получил известную долю удовольствия.

5 интервью одно за другим. 4 технических, одно -- HR. Интервьюверы умны, приятны и обходительны, -- американцы, индусы и китайцы :). Началось 8 утра, закончилось в 14. Задачи-задачки-задачки -- как будете решать, напишите код, как будете тестировать? Ваше решение никогда не даст ответа! Почему?

Вы пишите на php? Пишите решения на php, раз Вам так привычно (use any language you like).

Впечатления очень положительные, однако я не решил две задачи. Вот эти:

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

т.е. "в лоб" я конечно написал, но не этого от меня хотели

2. http://www.careercup.com/question?id=7243930
паттерн-матчинг с одной * я написал, а вот с несколькими наступает жадность и я ее не решил.

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

Comments

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

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

слушай, а в первой задачке от тебя хотели, чтобы ты решил за один проход, или, чтобы ты оптимизировал число проходов?

вообще, конечно, противно, что набирают людей как будто бы надо выигрывать международные олимпиады по математике, а заниматься надо потом такими задачами, что хочется повеситься от скуки.
число сравнений скорее, потому, что я решил за один проход, но сложность n^2. Можно просто отсортировать быстрой сортировкой и взять середину. Но от меня хотели еще лучше. И по ссылке есть решение с гистограммой O(n) с фиксированной памятью, только я еще им не проникся до конца.
то есть числа в памяти лежат?
насколько я понял там строится побитовая гистограмма, сами числа не хранятся, домой приду вкурю до конца. а так я на работе еще....
насчет соответствия собеседования и реальных задачек, это да. про это есть много грустноватых шуток.

дадададад!

в стартапах обычные люди делают уникальные вещи.
в больших конторах уникальные люди делают обычные вещи.

Re: дадададад!

Do you like to work on the hardest problems in computing with the biggest user impact? Is Search your vision of computing’s future, but it isn’t nearly there yet? Want to be the one to make it happen?

We work on the cutting edge of computer science, where a petabyte of data is “small”, ten thousand machines is a “little cluster”, and one second is an “eternity”. Our tools include machine learning models and the world's largest distributed system. We are a high powered startup inside of Microsoft, working on technology and products that are critical to our company’s success and at the heart of the customer experience of the internet.
Hopefully you’ve had a chance to experience Microsoft’s new search engine Bing and seen how we're changing the game in Search. Bing is receiving amazing reviews and generating lots of great buzz. Bing has had a fantastic year so far. After the successful brand launch earlier this year, the team has been working hard, both on closing the gap with our competitors in key areas like relevance, as well as driving thought leadership with new paradigms for search and user experience. This is probably one of most exciting times to be on the team, and you have an opportunity to help shape its future.

Re: дадададад!

ребятам, которые такие бумаги пишут, платят хорошее бабло. Есть за что :).

Но я бы имел в виду, что реально интересные краерезки все больше делают в гараже/на кухне двое-трое лохматых голодных отморозка. Или на казенное бабло - государево, или у тех же мелкомягких в их лабах (бинг к ним вроде не относится). Банду умеющих решать стандартные задачи набирают позже, чтобы суппортить.

Re: дадададад!

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

Re: дадададад!

тут не поспоришь.

Re: дадададад!

отморозки в гороже рожают что-то гениальное, никем невиданное причем безо всяких CS понятий вообще.

А толпу олимпиадников зовут потом :) бороться с нагрузкой.

Re: дадададад!

В стартапах, в основном, занимаются всякой чухней.

Re: дадададад!

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

Re: дадададад!

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

Do you like to work on the hardest problems in computing with the biggest user impact? Is Search your vision of computing’s future, but it isn’t nearly there yet? Want to be the one to make it happen?

We work on the cutting edge of computer science, where a petabyte of data is “small”, ten thousand machines is a “little cluster”, and one second is an “eternity”. Our tools include machine learning models and the world's largest distributed system. We are a high powered startup inside of Microsoft, working on technology and products that are critical to our company’s success and at the heart of the customer experience of the internet.
Hopefully you’ve had a chance to experience Microsoft’s new search engine Bing and seen how we're changing the game in Search. Bing is receiving amazing reviews and generating lots of great buzz. Bing has had a fantastic year so far. After the successful brand launch earlier this year, the team has been working hard, both on closing the gap with our competitors in key areas like relevance, as well as driving thought leadership with new paradigms for search and user experience. This is probably one of most exciting times to be on the team, and you have an opportunity to help shape its future.
Это все верно. Только заниматься машинным обучением посадят, скорее всего, не просто программиста, а человека со степенью из хорошего универа.

Вообще, как показывает опыт (не только мой), нужно аккуратно отделять понты от реалии. Чтобы не было потом разочарований.

По поводу гистограммы: может там хотели что-то вроде подсчета медианы медиан (как подсказывают на стэкоферфлоу)? Тогда без единой перестановки можно найти медиану за логарифмическое число проходов. С гистограммой ведь бывают всякие нехорошие частные случаи.

Отмазка: сам не особо знаю, потому как алгоритмами выбора катого элемента никогда особо не интересовался.
я отделяю, не переживай :) я даже с тобой согласился там выше. А потом вспомнил про эту преамбулу.
Первая задача на знание и ПОНИМАНИЕ теоремы о кодировании Шеннона.
Вторая задача про автомат лексического анализа.
спасибо.