Open Source & Linux Lab

It's better when it's simple

User Tools

Site Tools


etc:interview_tasks

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

etc:interview_tasks [2008/03/30 10:24] (current)
kkv создано
Line 1: Line 1:
 +Взято отсюда:​ http://​malaya-zemlya.livejournal.com/​356873.html
  
 +1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст),​ дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст - в начале. (Microsoft)
 +
 +
 +2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать,​ что игра не может продолжаться бесконечно. (J.H.Conway)
 +2b. Если у нас уже есть монеты достоинствами x[0]...x[n] (каждого типа - неограниченнок количество),​ то можно задать вопрос:​ как нам выплатить данную сумму денег S минимальным общим числом монет? Напишите соответвующую программу.
 +
 +3. Может ли цепная реакция в gridgame продолжаться бесконечно?​
 +(Mark James)
 +
 +4. Что делает следующий С++ код? (Matt Marcus)
 +
 +<code cpp>.
 +struct A {
 +   ​A(const volatile void*);
 +};
 +
 +char f(A);
 +int f(...);
 +
 +template <class T>
 +struct Test {
 +   ​static const int value = (sizeof(f(*(T*)0)) == sizeof(char));​
 +};
 +
 +</​code>​
 +
 +5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится?​ уменьшится?​ останется неизменным?​ (популярный вопрос,​ на многих фирмах задают,​ в том числе на и Микрософте)
 +5b. Кусок замороженного спирта в бочке с пивом. Что станет с уровнем жидкости,​ когда спирт весь растает?​ (не понмню откуда)
 +
 +6. Вы отправились в прошлое на машине времени и повстречали,​ ну скажем,​ Михайло Ломоносова (варианты:​ А.С. Пушкина,​ Томаса Эдисона,​ Николу Теслу итп). Объясните ему, что такое "​Интернет"​ (мое, по Микрософтовской идее). (Садистский вариант:​ объясните ему, что такое General Protection Failure :))
 +
 +7. У вас есть 8 с виду одинаковых монет, одна из которых,​ тем не менее, фальшивая. Фальшивая монета чуть тяжелее,​ но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками,​ как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку?​ (популярная задача)
 +
 +8. Придумайте структуру данных,​ которую бы мог на выходе создать парсер MAKE-файлов. Напишите (на псевдокоде) интерпретатор/​исполнитель для этой структуры (Microsoft)
 +
 +9. Протестируйте Save Dialog в Notepad'​e (задача для микософтовских тестеров)
 +
 +10. Есть три урны из тех, что содержат шары в задачках по теории вероятности. На первой написано "​ЧЕРНЫЕ",​ на второй - "​БЕЛЫЕ",​ на третьей - "​ЧЕРНЫЕ И БЕЛЫЕ"​. В одной лежат белые шары, в другой - черные,​ в оставшейся - и черные и белые. Все надписи заведомо ложны. Разрешается достать один шар из только одной урны. Как определить в какой урне что лежит? (Microsoft)
 +
 +11. Дано много картинок в формате RGB (т.е. цвет каждого пикселя представлен тремя числами:​ количеством красного цвета, зеленого цвета и синего цвета). Перевести картинки в 256-цветовой формат (а-ля Gif) с использованием заданной палитры (палитра одна на все картинки). Т.е. вместо каждого цвета подставить индекс ближайшего к нему цвета в палитре. Разумеется,​ хорошо бы это сделать как можно более эффективно. (Google)
 +
 +12. Обойти двоичное дерево,​ НЕ используя рекурсию. (Michael Abrash)
 +
 +13. На консоли Xbox адрес пикселя с координатами x, y записывается в двоичной форме как x7 y7 x6 y6 x5 y5 x5 y5 x4 y4 x3 y3 x2 y2 x1 y1 x0 y0 (где xn, yn - соответствующие биты чисел x и y). Дан пиксель с адресом a, найти адрес его соседа справа (Visual Concepts)
 +
 +14. Дана строчка текста,​ переставить в ней все слова в противоположном порядке,​ так чтобы, например,​ строчка "​Здесь был Вася"​ превратилась в "​Вася был Здесь"​. Дополнительную память выделять не разрешается (популярная задача)
 +
 +15. Дано число. Определить,​ является ли оно целой степенью 2. (Microsoft и другие)
 +
 +16а. Дан связный список. Проверить,​ нет ли в нем циклов. (популярная)
 +16b. Сделать то же самое с двоичным деревом.
 +
 +17. В вершинах равностороннего треугольника со стороной 200 метров сидит по собаке. По команде "​старт!"​ каждая из них начинает гнаться за своей соседкой слева со скоростью 200 метров в минуту. Каждая собака бежит точно в направлении текущего положения своей (тоже, разумеется,​ бегущей) цели. Поэтому их траектории представляют некие сходящиеся спирали. Через какое время все собаки сойдутся,​ (вернее,​ сбегутся) в центре?​ (вариант популярной задачи)
 +
 +18. Даны две строчки битов, длинная и короткая. Определить,​ как можно более эффективно,​ содержится ли короткая строчка в длинной (мое)
 +
 +19. Почему пивные банки скошены сверху и снизу? (Microsoft)
 +
 +20. Как провести электричество,​ чтобы свет на лестнице можно было включать/​выключать и с верхней площадки,​ и с нижней. Нарисуйте схему проводки.
 +
 +21. Даны указатели на два элемента в двоичном дереве,​ найти их общего родителя (Microsoft)
 +
 +22. Стандартный способ "​честного"​ деления пирога:​ первый участник делит, второй выбирает себе один из кусков,​ оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер,​ чтоли?​)
 +
 +23. Есть круглый бассейн. От его бортика в направлении точно на север отплыла рыба. Проплыв 6 метров,​ она опять столкнулась с бортиком. Тогда рыба повернула на восток,​ проплыла еще 8 метров и опять столкнулась с бортиком. Найти диаметр бассейна. (опять Мартин Гарднер)
 +
 +24. Дано число int x. Как наиболее эффективно подсчитать количество единичных битов в нем, если нельзя пользоваться дополнительной памятью. Соответствующей командой ассемблера тоже пользоваться нельзя. (впервые видел в Dr.Dobbs Journal)
 +
 +25. У вас есть зажигалка и веревка. Если веревку поджечь с конца, то она вся сгорит за полчаса. Как отмерить,​ при помощи этих двух предметов 15 минут? Важное обстоятельство:​ Веревка горит неравномерно,​ где-то быстрее,​ где-то медленнее. (очень популярная задача)
 +
 +26. Есть программа,​ которая рисует на экране шар (скажем,​ с картой Земли на поверхности). Хочется,​ чтобы можно было при помощи мыши управлять ориентацией шара, дабы рассмотреть его со всех сторон. Придумайте соответствующий пользовательский интерфейс. Напишите (на псевдокоде) основной алгоритм управления ориентацией. (мое)
 +
 +27. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)
 +
 +28.a (Для мэнеджеров,​ наверное) Вы - добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью,​ они пока далеко позади. К несчастью,​ через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы,​ которыми Вы можете разить орков наповал. К еще большему счастью,​ на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью,​ у Вас имеется только 5 стрел. К еще большему несчастью,​ орки об этом знают. Как Вам спастись?​ (D.Friedman)
 +Update28.b Какие у орков могут быть контр-приемы?​
 +
 +29. В какие времена суток положение всех трех стрелок часов (часовой,​ минутной и секундной) совпадает?​ (не помню откуда)Разъяснение Часы механические,​ и стрелки двигаются с равномерной скоростью.
 +
 +30. Почему в стандарте С++ не позволено по умолчанию преобразовывать %%char**%% в %%const char**%%? Напишите пример кода, где такое преобразование (если бы его разрешили) привело бы к ошибке. (С++ faq)
 +
 +31. У Вас с другом есть прямоугольный торт, из которого какой-то гад, к сожалению,​ уже вырезал (и съел) прямоугольный кусок. Ориентация и положение вырезанного куска могут быть совершенно произвольными. Как вам с другом разделить оставшийся торт на две равные части? (Microsoft)
 +
 +32. Как передвинуть гору Фудзи? (Microsoft)
etc/interview_tasks.txt · Last modified: 2008/03/30 10:24 by kkv