Bing Interview

[fantaseour]

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

Comments

[fantaseour]

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

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

[fantaseour]

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

[realurix]

Первая задача на знание и ПОНИМАНИЕ теоремы о кодировании Шеннона.
Вторая задача про автомат лексического анализа.

[fantaseour]

спасибо.