Они скоро опять приезжают (говорят, что с 30 марта). Хочется поготовиться к собеседованию.
Насколько я понимаю, на очном интервью могут быть три типа задач.
1. На рассуждение. Типа "сколько шариков от пинг-понга поместится внутрь самолета" и т.д.
Тут, как я понимаю, готовиться особо нечего, надо просто уметь рассуждать, предлагать варианты, рассматривать проблему с разных сторон и т.д.
2. На сообразительность, на умение решать головоломки. Та самая любимая задача про гномов и тому подобные.
Тут пока у меня план только такой — прорешать подобные задачки из "Фудзи", сравнить с ответами. Подскажите, пожалуйста, еще сборники подобных задач, желательно, с ответами.
3. На программирование. Не менее любимая задачка о развороте списка и т. д.
Вот тут самое сложное — не очень понятно в какие области смотреть, что вспоминать, насколько глубоко. Структуры данных — списки, деревья, хеш-таблицы, графы — что про них надо знать, насколько глубоко в детали имеет смысл влезать?
Алгоритмы — сортировка, поиск, динамическое программирование, жадные алгоритмы, оценки быстродействия, что-то еще? Что тут надо уметь?
Здравствуйте, Ilias, Вы писали:
I>3. На программирование. Не менее любимая задачка о развороте списка и т. д. I>Вот тут самое сложное — не очень понятно в какие области смотреть, что вспоминать, насколько глубоко. I>Структуры данных — списки, деревья, хеш-таблицы, графы — что про них надо знать, насколько глубоко в детали имеет смысл влезать? I>Алгоритмы — сортировка, поиск, динамическое программирование, жадные алгоритмы, оценки быстродействия, что-то еще? Что тут надо уметь? I> I>Очень нравится эта
тема с похожими вопросами, но про "mathematical questions" — уж очень четко там темы накидали в ответах.
Вот что меня спрашивали — для примера:
1. Напишите код для организации Стека. Интересуют функции Push & Pop.
2. Сделайте их thread-safe с помощью http://msdn.microsoft.com/en-us/library/windows/desktop/ms683609%28v=vs.85%29.aspx.
У вас есть не более 10 минут — нужно прочитать страничку msdn (есть ноут.), посмотреть на свой код на бумажке и применить.
Здравствуйте, SemiCoder, Вы писали:
SC>Здравствуйте, Ilias, Вы писали:
SC>Вот что меня спрашивали — для примера: SC>1. Напишите код для организации Стека. Интересуют функции Push & Pop. SC>2. Сделайте их thread-safe с помощью http://msdn.microsoft.com/en-us/library/windows/desktop/ms683609%28v=vs.85%29.aspx. SC> У вас есть не более 10 минут — нужно прочитать страничку msdn (есть ноут.), посмотреть на свой код на бумажке и применить.
И это всё что там было? На 3-5 интервью всего две задачи? Просто эти ну совсем простые. Как-то ожидал гораздо более сложных.
Здравствуйте, Ilias, Вы писали: I>Они скоро опять приезжают (говорят, что с 30 марта). Хочется поготовиться к собеседованию. I>Насколько я понимаю, на очном интервью могут быть три типа задач.
вообще типов задач может быть бесконечно много , все зависит от интервьевера
I>1. На рассуждение. Типа "сколько шариков от пинг-понга поместится внутрь самолета" и т.д. I>Тут, как я понимаю, готовиться особо нечего, надо просто уметь рассуждать, предлагать варианты, рассматривать проблему с разных сторон и т.д.
первые две трата времени в долгосрочном плане, но помогают сильно для интервью. третья хорошо написанная книжка по алгоритмам, которая помогает в жизни (мне понравилась больше книжки "с ослом")
Вот задача объяснить почему этого делать нельзя (т.е. технически возможно, но лучше не надо) — куда более интересный вопрос для обсуждения на интервью, чем написание стека. Это как с наследованием эллипса от круга: если вы сумели, то показали свое знание основ языка программирования, а если не сумели — то показали глубокое понимание ООП и реальный опыт.
Здравствуйте, Ilias, Вы писали:
SC>>Вот что меня спрашивали — для примера: SC>>1. Напишите код для организации Стека. Интересуют функции Push & Pop. SC>>2. Сделайте их thread-safe с помощью http://msdn.microsoft.com/en-us/library/windows/desktop/ms683609%28v=vs.85%29.aspx. SC>> У вас есть не более 10 минут — нужно прочитать страничку msdn (есть ноут.), посмотреть на свой код на бумажке и применить.
I>И это всё что там было? На 3-5 интервью всего две задачи? Просто эти ну совсем простые. Как-то ожидал гораздо более сложных.
Самое интересное, что в соседних ветках от Паблика Морозова, сертифицированный MVP от MS с пеной у рта доказывает, что задача с переворотом списка слишком сложна для собеседований В то время, как в соседних ветках, обсуждают, что для поступления в этот же MS нужно написать thread-safe Stack.
Несколько лет назад слышал, что кому-то попалась задачка, где нужно было применить RB-tree.
Computer science is no more about computers than astronomy is about telescopes (c) Edsger Dijkstra
Здравствуйте, Ilias, Вы писали:
I>Они скоро опять приезжают (говорят, что с 30 марта). Хочется поготовиться к собеседованию.
I>1. На рассуждение. Типа "сколько шариков от пинг-понга поместится внутрь самолета" и т.д. I>Тут, как я понимаю, готовиться особо нечего, надо просто уметь рассуждать, предлагать варианты, рассматривать проблему с разных сторон и т.д.
Cracking the Coding Interview: 150 Programming Questions and Solutions
книга очень хорошая. т.к. у меня есть богатый опыт собеседований чуть ли не по всему миру, то могу подтвердить, что примеры в книге даны вполне релевантные. так же в ней объясняется как интевьер будет направлять ваши мысли в поток создания, падающий дампом стремительного домкрата. в ms устроится относительно просто. у них самые базовые требования. никаких изысков.
I> 2. На сообразительность, на умение решать головоломки. Та самая любимая задача про гномов и тому подобные.
это не гномы, а коды коррекции ошибок. базовая матчать.
I> 3. На программирование. Не менее любимая задачка о развороте списка и т. д.
в общем случае задача не имеет решение (мы как раз это на rsdn обсуждали). все зависит от языковых средств. если в языке нет ни swap, ни указателей, ни нормальной сборки мусора, то приходится решать задачу в лоб -- брать по одному элементу с конца и дописывать в конец нового списка. если есть swap, то все упрощается и можно обойтись перестановкой элементов, но -- черт возьми -- а если элементы списка это строки? и реализация swap такая, что все тормозит? таким образом, мы приходим к тому, что указатели -- очень полезная весчь. а двунаправленные списки -- еще более полезная штука.
I> Вот тут самое сложное — не очень понятно в какие области смотреть, что вспоминать, насколько глубоко.
совсем недавно обсуждалась dos атака на разные языки программирования путем генерации post'а. вом вам и разница между "в среднем" и "в худшем" случае. вот такая подлость на ровном месте, да. а вы еще спрашиваете зачем нужно знать как устроен HashMap и насколько глубоко копать.
I> Структуры данных — списки, деревья, хеш-таблицы, графы — что про них надо знать, насколько глубоко в детали имеет смысл влезать? I> Алгоритмы — сортировка, поиск, динамическое программирование, жадные алгоритмы, оценки быстродействия, что-то еще? Что тут надо уметь?
иметь общее представление. обход дерева могут спросить -- очень популярный вопрос. иногда в нем есть подвох -- где гарантия, что в дереве нет циклических ссылок? мы же зависнем тогда или отвалимся по исключению. с другой стороны на каждую хитрую жопу найдется свой мыщъх. и на этот вопрос я ответил -- не буду я обходить дерево. у меня на подлежащем уровне есть карта памяти. и пока вы будете ходить зиг-загами, я линейно пробегусь по списку, т.к. на самом фундаментальном урове дерево -- это список блоков памяти (правда это не дает ответа на вопрос как обойти поддерево).
I> Спасибо
да вы не волнуйтесь. ms компания большая и потому нужно плясать не от гномов, а от ваших сильных сторон, которые и будут искать на интерьвю. перед тем как пытать вас спросят куда наносить удар. так что нет смысла распыляться по всему периметру.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
М>иметь общее представление. обход дерева могут спросить -- очень популярный вопрос. иногда в нем есть подвох -- где гарантия, что в дереве нет циклических ссылок?
Если они есть, то это уже не дерево.
Здравствуйте, anomander, Вы писали:
A>Здравствуйте, мыщъх, Вы писали:
М>>иметь общее представление. обход дерева могут спросить -- очень популярный вопрос. иногда в нем есть подвох -- где гарантия, что в дереве нет циклических ссылок? A>Если они есть, то это уже не дерево.
у нас есть дерево. в нем нет циклических ссылок. потому что дерево. но дерево не может существовать в виде математической абстракции и потому оно хранится в памяти или на диске и в результате тех или иных обстоятельств в нем могут появится циклические ссылки (особенно, если это дерево хранится внутри файла, на который может воздействовать хакер).
обходить дерево без учета наличия циклических ссылок можно только если мы гарантируем целостность дерева, а это нереально. даже если API не дает прямого доступа к дереву и отлавливает попытки создания циклических ссылок -- ошибки типа "удара по памяти" разрушат это дерево из соседнего модуля.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
М>обход дерева могут спросить -- очень популярный вопрос. иногда в нем есть подвох -- где гарантия, что в дереве нет циклических ссылок?
По определению дерево — это ациклический граф.
"For every complex problem, there is a solution that is simple, neat,
and wrong."
Здравствуйте, AndrewJD, Вы писали:
AJD>По определению дерево — это ациклический граф.
Комменты не читай — комменты пиши
A>Здравствуйте, мыщъх, Вы писали:
М>у нас есть дерево. в нем нет циклических ссылок. потому что дерево. но дерево не может существовать в виде математической абстракции и потому оно М>хранится в памяти или на диске и в результате тех или иных обстоятельств в нем могут появится циклические ссылки (особенно, если это дерево хранится М>внутри файла, на который может воздействовать хакер). М> М>обходить дерево без учета наличия циклических ссылок можно только если мы гарантируем целостность дерева, а это нереально. даже если API не дает М>прямого доступа к дереву и отлавливает попытки создания циклических ссылок -- ошибки типа "удара по памяти" разрушат это дерево из соседнего модуля.
Это все конечно здорово, но, думаю, что не ошибусь, если скажу, что в большинстве мест, где зададут этот вопрос, захотят сначала услышать ответ, а потом уже, возможно, обсудить возможные проблемы (в зависимости от используемых языков, технологий и других факторов). Где-то, возможно, пройдет ваш подход, но я бы посчитал его увиливанием от ответа и сначала вывел бы на прямой ответ, а затем уже обсуждал особенности.
Здравствуйте, мыщъх, Вы писали:
М>обходить дерево без учета наличия циклических ссылок можно только если мы гарантируем целостность дерева, а это нереально. даже если API не дает прямого доступа к дереву и отлавливает попытки создания циклических ссылок -- ошибки типа "удара по памяти" разрушат это дерево из соседнего модуля.
А не лучше ли будет на этапе загрузки проверить целостность дерева, а потом использовать простой обход дерева?
"For every complex problem, there is a solution that is simple, neat,
and wrong."
Здравствуйте, AndrewJD, Вы писали:
AJD>Здравствуйте, мыщъх, Вы писали:
М>>обход дерева могут спросить -- очень популярный вопрос. иногда в нем есть подвох -- где гарантия, что в дереве нет циклических ссылок?
AJD>По определению дерево — это ациклический граф.
уже ответил, что определения идут лесом. из-за таких как вы фирмам приходится выпускать секьюрные патчи. потому что есть дерево, которое хранится в файле. на файл может воздействовать хакер. хакер создает циклические ссылки и в зависимости от алгоритма обхода мы имеем отказ в обслуживании или удаленное выполнение кода.
короче, вам передали дерево как аргумент функции. аргументы мы не проверяем, да? тогда объясните мне тупому, почему команда деления таки выполняет такие проверки, ведь на ноль делить нельзя -- это вам любой математик скажет.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, AndrewJD, Вы писали:
AJD>Здравствуйте, мыщъх, Вы писали:
М>>обходить дерево без учета наличия циклических ссылок можно только если мы гарантируем целостность дерева, а это нереально. даже если API не дает прямого доступа к дереву и отлавливает попытки создания циклических ссылок -- ошибки типа "удара по памяти" разрушат это дерево из соседнего модуля. AJD>А не лучше ли будет на этапе загрузки проверить целостность дерева, а потом использовать простой обход дерева?
ошибки удара по памяти могут разрушить дерево в любой момент, если дерево в памяти. если дерево на диске, то и подавно. кстати, обход (под)дерева каталогов fs вполне себе задача. циклические ссылки там могут быть, т.к. популярные fs это не отслеживают.
даю вводную.
винда (проверял хрюшу, что под рукой), NTFS. FAR.
F7, "demo_1", cd demo_1, Alt-F6, "demo_1\demo_2".
работает! можно бесконечно входить в demo, спускаясь все глубже и глубже (в FAR'e). а теперь посмотрите сколько программ развалится, если их попросить обработать директорию с под-директориями.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
М>короче, вам передали дерево как аргумент функции. аргументы мы не проверяем, да? тогда объясните мне тупому, почему команда деления таки выполняет такие проверки, ведь на ноль делить нельзя -- это вам любой математик скажет.
какие проверки выполняет команда деления? в каком языке?
Здравствуйте, мыщъх, Вы писали:
М>короче, вам передали дерево как аргумент функции. аргументы мы не проверяем, да? тогда объясните мне тупому, почему команда деления таки выполняет такие проверки, ведь на ноль делить нельзя -- это вам любой математик скажет.
Строго говоря, иногда на ноль делить-таки можно. И это скажет любой математик. Другое дело в наших с вами программках — да, там лучше этого не делать.
Я помню лет десять назад в одном моем графическом движке, в линуксе, gcc при делении на ноль помещал специально значение NaN в переменную. Отлаживать в динамике я тогда не умел и найти источник было очень трудно, а сдавать проект надо было сегодня. Выход нашелся удивительный:
if (foo — foo == 0.0)
// good value — draw!
else
// NaN — skip drawing element
И ведь работало. Любой математик наверное сразу бы застрелился. Проект был сдан, и только много позже я-таки разобрался как все это делается по-человечески.
Здравствуйте, blackhearted, Вы писали:
B>Здравствуйте, мыщъх, Вы писали:
М>>короче, вам передали дерево как аргумент функции. аргументы мы не проверяем, да? тогда объясните мне тупому, почему команда деления таки выполняет такие проверки, ведь на ноль делить нельзя -- это вам любой математик скажет.
B>какие проверки выполняет команда деления? в каком языке?
main(){ return 1/0;}
$cl 1.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86
Copyright (C) Microsoft Corp 1984-1998. All rights reserved.
1.c
1.c(1) : error C2124: divide or mod by zero
учите мат чать матъ вашу.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
, все зависит от интервьевера
В то время, как в соседних ветках, обсуждают, что для поступления в этот же MS нужно написать thread-safe Stack.
