1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)
2b. Если у нас уже есть монеты достоинствами x[0]...x[n] (каждого типа — неограниченнок количество), то можно задать вопрос: как нам выплатить данную сумму денег S минимальным общим числом монет? Напишите соответвующую программу.
3. Может ли цепная реакция в gridgame продолжаться бесконечно?
(Mark James)
4. Что делает следующий С++ код? (Matt Marcus)
struct A {
A(const volatile void*);
};
char f(A);
int f(...);
template
struct Test {
static const int value = (sizeof(f(*(T*)0)) == sizeof(char));
};
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)
Кто что решит пишите
(с) voffka
18.01.06 13:40: Перенесено из 'Коллеги, улыбнитесь'
Здравствуйте, Grammer, Вы писали: G>22. Стандартный способ "честного" деления пирога: первый участник делит, второй выбирает себе один из кусков, оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер, чтоли?)
Кстати, если не пирог, а сыпучее вещество, то можно "честно" делить на любое количество участников
Здравствуйте, Grammer, Вы писали:
G>1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
Тупая задача вроже бы. Или я совсем тупой. Или нужно запретить использование буферных переменных и ассемблера, чтобы обязательно использовать некоторый(-е) из нулей, как буфер.
Думаю, примерно так: на входе
DS:[ESI] и DS:[EDI] — буферы (первый эл-т)
inv1 proc near
CLD
PUSH EDI ; Кажетcя именно он в SCAS, а не ESI, но могу ошибаться
POP EBX
MOV AL, 0
REPNZ SCASB
PUSH EDI
DEC EDI
STD
@@sw: MOV AL, [EDI]
XCHG AL, [EBX]
STOSB
INC EBX
CMB EDI, EBX
JA @@sw
POP ECX
POP EDI
SUB ECX, EDI
RET
inv1 endp
bufswap proc
PUSH EDI
CALL inv1
MOV EDI, ESI
MOV EDX, ECX
CALL inv1
POP EDI
CMP EDX, ECX ; тут можно бы наверное CMPXCHG - но я остановился на i386 :)
JBE @@1
MOV ECX, EDX
@@1: CLD
@@2: MOV AL, [EDI]
XCHG AL, [ESI]
STOSB
INC ESI
LOOP ECX
RET
bufswap endp
Здравствуйте, Grammer, Вы писали:
G>17. В вершинах равностороннего треугольника со стороной 200 метров сидит по собаке. По команде "старт!" каждая из них начинает гнаться за своей соседкой слева со скоростью 200 метров в минуту. Каждая собака бежит точно в направлении текущего положения своей (тоже, разумеется, бегущей) цели. Поэтому их траектории представляют некие сходящиеся спирали. Через какое время все собаки сойдутся, (вернее, сбегутся) в центре? (вариант популярной задачи)
Забавная задача. Как правило ее легко решают школьники и студенты старших курсов. Первые, правда, предоставляют более красивое и изящное решение. А вот для студентов первых курсов эта задача оказывается не по зубам
Здравствуйте, Grammer, Вы писали:
G>2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)
Здравствуйте, MaximVK, Вы писали:
MVK>Забавная задача. Как правило ее легко решают школьники и студенты старших курсов. Первые, правда, предоставляют более красивое и изящное решение. А вот для студентов первых курсов эта задача оказывается не по зубам
А разве у нее есть какое-нибудь нормальное решение кроме перехода в неинерциальную систему координат, связанную с бегущей собакой?
Здравствуйте, VsevolodC, Вы писали:
VC>Очевидно, выигрывает первый игрок, назвав 0
И как с помощью 0 чего-нибудь кроме 0 выплачивать? Решение следует, очевидно, из того, что для взаимнопростых a,b любое с > 2*a*b можно представить в виде c = ax+by, где x и y >= 0.
Здравствуйте, Grammer, Вы писали:
G>1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
Тупое решение состоит в том, чтобы сперва реверсировать каждую строчку, а затем обменять их (или наоборот: сперва обменять, а потом реверсировать).
Думаю, что оно будет и наиболее быстрым.
Хитрое решение отрабатывает цепочки обменов для каждой буквы по отдельности. Причём цепочки могут быть довольно длинными (предположительно, максимум достигается, если длины строк — соседние числа Фибоначчи; впрочем, это только догадка).
G>3. Может ли цепная реакция в gridgame продолжаться бесконечно? G>(Mark James)
G>struct A {
G>A(const volatile void*);
G>};
G>char f(A);
G>int f(...);
G>template// во-первых, даёт ошибку компиляции
G>struct Test {
G>static const int value = (sizeof(f(*(T*)0)) == sizeof(char)); // во-вторых, проверяет дизъюнкцию условий
// sizeof(int)==sizeof(char)
// T==A
// T - класс и существует T::operator A()
// T==U* (cv-квалификация типа U не имеет значения)
G>};
G>5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится? уменьшится? останется неизменным? (популярный вопрос, на многих фирмах задают, в том числе на и Микрософте)
Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма.
Хотя, если кирпич пористый или из замороженного спирта, то возможны варианты.
G>5b. Кусок замороженного спирта в бочке с пивом. Что станет с уровнем жидкости, когда спирт весь растает? (не понмню откуда)
Объём тающего спирта увеличивается, а объём охлаждаемой воды — уменьшается (до 4°С), затем снова увеличивается.
Объём водно-спиртовой смеси — меньше объёмов каждого из компонентов.
При растворении спирта выделяется тепло.
Бочка может быть термостабилизированной или термоизолированной. Колебания объёма могут быть изобарическими или сопровождаться колебаниями давления. При этом может затрачиваться разное количество энергии (одно дело пробулькать водяной затвор, другое — деформировать бочку, третье — сатурация или десатурация пива углекислым газом).
В общем, идёт довольно затейливый процесс, суммарный эффект варьируется и от количества веществ, и от начальной температуры, и от других условий.
G>6. Вы отправились в прошлое на машине времени и повстречали, ну скажем, Михайло Ломоносова (варианты: А.С. Пушкина, Томаса Эдисона, Николу Теслу итп). Объясните ему, что такое "Интернет" (мое, по Микрософтовской идее). (Садистский вариант: объясните ему, что такое General Protection Failure
Ну про GPF всё просто. Напился, ошибся дверью, хозяин набил морду.
G>12. Обойти двоичное дерево, НЕ используя рекурсию. (Michael Abrash)
А какой порядок обхода имеется в виду?
Если в глубину, то семейство обходов PLR, LPR, LRP (Parent, Left, Right) основываются на одном и том же алгоритме обхода. http://www.rsdn.ru/File/4783/traverse-bin-trees.gif
Если в ширину, то можно без рекурсии, но со счётчиком (и с квадратичным временем работы).
Здравствуйте, andyJB, Вы писали:
JB>Здравствуйте, VsevolodC, Вы писали:
VC>>Очевидно, выигрывает первый игрок, назвав 0 JB>И как с помощью 0 чего-нибудь кроме 0 выплачивать? Решение следует, очевидно, из того, что для взаимнопростых a,b любое с > 2*a*b можно представить в виде c = ax+by, где x и y >= 0.
Условие было только одно:
При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет.
и оно выполняется, потому что ранее названных нет.
К>Тупое решение состоит в том, чтобы сперва реверсировать каждую строчку, а затем обменять их (или наоборот: сперва обменять, а потом реверсировать). К>Думаю, что оно будет и наиболее быстрым.
К>Хитрое решение отрабатывает цепочки обменов для каждой буквы по отдельности. Причём цепочки могут быть довольно длинными (предположительно, максимум достигается, если длины строк — соседние числа Фибоначчи; впрочем, это только догадка).
Что значит для каждой буквы по отдельности ?
Хитрое так примерно: (я пасквилятник, но надеюсь все же тут ошибиться негде почти).
void Reverse (char * const seq1, char * const seq2)
{ int len1, len2; char * ptr1, * ptr2; char buffer;
char * shorter_src, * shorter_dest, * longer; int len;
for( len1=0, ptr1 = seq1; *ptr1; ptr1++, len1++);
for( len2=0, ptr2 = seq2; *ptr2; ptr2++, len2++);
if ( len1 > len2)
{ len = len1; longer = ptr1; shorter_src = ptr2;
shorter_dest = seq2 + len1;
assert( shorter_src == seq2 + len2); } else
{ len = len2; longer = ptr2; shorter_src = ptr1;
shorter_dest = seq1 + len2;
assert( shorter_src == seq1 + len1); }
//Тонкость, если len1==len2, то shorter_src == shorter_dest и нужен промеж. буфер
// если нет, то и пофигу, буффер будет в регистре.while (len--) {
buffer = * (--shorter_src);
* (--shorter_dest) = * (--longer);
* longer = buffer;
}
}
Здравствуйте, Кодт, Вы писали:
G>>5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится? уменьшится? останется неизменным? (популярный вопрос, на многих фирмах задают, в том числе на и Микрософте)
К>Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма.
Уменьшится. Все-таки плотность кирпича больше плотности воды, поэтому будучи в лодке, он вытеснит больше воды, чем сам, пойдя ко дну. Исключения типа водоплавающих кирпичей пока не рассматриваем
Здравствуйте, Grammer, Вы писали:
G>7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)
2 достаточно. можно и с 9ю монетами справиться.
G>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)
P — точка.
сосед справа (( P | 1010101010101010 ) + 2) & ( P | 0101010101010101 )
G>Кто что решит пишите
G>(с) voffka
Здравствуйте, Аноним, Вы писали:
К>>Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма.
А>Уменьшится. Все-таки плотность кирпича больше плотности воды, поэтому будучи в лодке, он вытеснит больше воды, чем сам, пойдя ко дну. Исключения типа водоплавающих кирпичей пока не рассматриваем
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Grammer, Вы писали:
G>>1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
К>Тупое решение состоит в том, чтобы сперва реверсировать каждую строчку, а затем обменять их (или наоборот: сперва обменять, а потом реверсировать). К>Думаю, что оно будет и наиболее быстрым.
Обмен с реверсом одновременно, но с получением нулей вначале.
a[N1], b[N2] — длины буферов, пусть N=min(N1,N2). Начинаем менять пары местами a[0]<->b[N-1], a[1]<->b[N-2] и т.д. Получаем строки с нулями вначале — циклически сдвигаем их в начало.
G>>4. Что делает следующий С++ код? (Matt Marcus) К>
К> // T==U* (cv-квалификация типа U не имеет значения)Это что такое?
К>
G>>5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится? уменьшится? останется неизменным? (популярный вопрос, на многих фирмах задают, в том числе на и Микрософте)
К>Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма. К>Хотя, если кирпич пористый или из замороженного спирта, то возможны варианты.
Уменьшится. Пока кирпич в лодке он вытесняет воду объемом, равному своему весу. Когда кирпич падает в воду, он вытесняет воду объемом, равному своему объему. Посколько плотность кирпича явно больше плотности воды, во втором случае вытесняемой воды будет меньше.
К>Ну про GPF всё просто. Напился, ошибся дверью, хозяин набил морду.
Вы сидите за старинным столом, и пишете на листках, которую я даю, и по моей команде. Рядом стоит страж, который следит, чтобы стол не испачкали, и в случае чего бьет по голове дубиной. В какой-то момент я забываю дать листок, но даю команду что-то написать...
Здравствуйте, VsevolodC, Вы писали:
VC>и оно выполняется, потому что ранее названных нет.
И что? Второй назовет произвольное число, отличное от 1, и игра продолжится.
Здравствуйте, Grammer, Вы писали:
G>10. Есть три урны из тех, что содержат шары в задачках по теории вероятности. На первой написано "ЧЕРНЫЕ", на второй — "БЕЛЫЕ", на третьей — "ЧЕРНЫЕ И БЕЛЫЕ". В одной лежат белые шары, в другой — черные, в оставшейся — и черные и белые. Все надписи заведомо ложны. Разрешается достать один шар из только одной урны. Как определить в какой урне что лежит? (Microsoft)
Поскольку все три надписи ложные, надо их все поменять.
Есть только два варианта смены надписей
ЧБ
/ \
Ч----Б
по часовой стрелке и против.
Вытаскиваем из ЧБ один шар. Посколько надпись ложная, то в этой урне должны быть или все белые, или все черные. Смотрим на вытащенный шар, и двигаем надписи в соответствующем направлении.
Стопудово выпил! Значит ответ — уровень уменьшится.
Перекуём баги на фичи!
