Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Thematic forums > Science and Education
Register

Reply
 
LinkBack Thread Tools
Old 20.01.2006, 23:31   #1
инсценирующи
 
[ Xelgen ]'s Avatar
 
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 31
Posts: 4,327
Downloads: 22
Uploads: 0
Reputation: 193 | 4
Default 31 задачек и вопросов для програмистов (и не только них)

Задачки часто задаются програмистам, во время приема на работу.
Взято с http://www.xakep.ru/post/29666/default.asp

=========

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. Почему пивные банки скошены сверху и снизу? (Microsoft)

19. Как провести электричество, чтобы свет на лестнице можно было включать/выключать и с верхней площадки, и с нижней. Нарисуйте схему проводки.

20. Даны указатели на два элемента в двоичном дереве, найти их общего родителя. (Microsoft)

21. Стандартный способ "честного" деления пирога: первый участник делит, второй выбирает себе один из кусков, оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер?)

22. Есть круглый бассейн. От его бортика в направлении точно на север отплыла рыба. Проплыв 6 метров, она опять столкнулась с бортиком. Тогда рыба повернула на восток, проплыла еще 8 метров и опять столкнулась с бортиком. Найти диаметр бассейна. (опять Мартин Гарднер)

23. Дано число int x. Как наиболее эффективно подсчитать количество единичных битов в нем, если нельзя пользоваться дополнительной памятью. Соответствующей командой ассемблера тоже пользоваться нельзя. (впервые видел в Dr.Dobbs Journal)

24. У вас есть зажигалка и веревка. Если веревку поджечь с конца, то она вся сгорит за полчаса. Как отмерить, при помощи этих двух предметов 15 минут? Важное обстоятельство: Веревка горит неравномерно, где-то быстрее, где-то медленнее. (очень популярная задача)

25. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)

26.a (Для мэнеджеров, наверное) Вы - добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman)
Update26.b Какие у орков могут быть контр-приемы?

27. В какие времена суток положение всех трех стрелок часов (часовой, минутной и секундной) совпадает? Разъяснение: Часы механические, и стрелки двигаются с равномерной скоростью.

28. Почему в стандарте С++ не позволено по умолчанию преобразовывать char** в const char**? Напишите пример кода, где такое преобразование (если бы его разрешили) привело бы к ошибке. (С++ faq)

29. У Вас с другом есть прямоугольный торт, из которого какой-то гад, к сожалению, уже вырезал (и съел) прямоугольный кусок. Ориентация и положение вырезанного куска могут быть совершенно произвольными. Как вам с другом разделить оставшийся торт на две равные части? (Microsoft)

30. Как передвинуть гору Фудзи? (Microsoft)

31. В Лондоне женщина вышла из автобуса около дома № 37 и спросила мужчину, в каком направлении идти к дому № 33 - по ходу автобуса или в обратную сторону? Что ей ответить?
__________________
...ибо...
Rgrdz. [ Кселджэн ]
Reply With Quote
Old 20.01.2006, 23:57   #2
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default Re: 31 задачек и вопросов для програмистов (и не только них)

И как все таки передвинуть гору Фудзи?
Reply With Quote
Old 21.01.2006, 18:44   #3
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: 31 задачек и вопросов для програмистов (и не только них)

5а. уровень останется неизменным
5b. уровень понизится
10. достаем шар из урны с ложной надписью "ЧЕРНЫЕ И БЕЛЫЕ", далее - элементарно
15. a == (a>>1)<<1
22. 10
23. наиболее эффективно - это в 5 "строк", используя только сам x и побитовые операции
25. дуть (+ вариации на тему)
29. касаясь вершин дыры, режем параллельно стороне, ближайшей к соответствующей вершине, далее - элементарно
30. относительно чего и, главное, зачем??
Reply With Quote
Old 21.01.2006, 18:56   #4
инсценирующи
 
[ Xelgen ]'s Avatar
 
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 31
Posts: 4,327
Downloads: 22
Uploads: 0
Reputation: 193 | 4
Default Re: 31 задачек и вопросов для програмистов (и не только них)

Насчет 5а и 5б случайно не наоборот?
25. Можно еще отшвыривать что нить от себя..
30. Зачем не знаю, но вот насчет относительно чего, сам думал.
10. Ага, помоему эту задачу тут уже решали.
29. Гм, да, даже если стороны вырезанного треугольника не паралельны сторонам торта, то получившиеся 4 треугольника, при твоем методе попарно равны.

Я если честно ожидал большей активности. Может спугнул народ, тем что адресовал это прораммистам?
Reply With Quote
Old 21.01.2006, 18:57   #5
инсценирующи
 
[ Xelgen ]'s Avatar
 
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 31
Posts: 4,327
Downloads: 22
Uploads: 0
Reputation: 193 | 4
Default Re: 31 задачек и вопросов для програмистов (и не только них)

Кста есть идеи насчет 17ой?
Reply With Quote
Old 21.01.2006, 18:59   #6
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: 31 задачек и вопросов для програмистов (и не только них)

нет, не наоборот...

так треугольник или четырехугольник?
Reply With Quote
Old 21.01.2006, 20:04   #7
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default Re: 31 задачек и вопросов для програмистов (и не только них)

5а Уровень воды скорее всего опуститься.. ибо тут дело в том что
тзавал погруженной лодки под тяжестю керпича больше чем тзавал самого керпича под его тяжестью...да и Хтутюн этой части лодки и Керпича разные...и ответ что уровень останеться тем же неправилен..имхо Правильный ответ : Смотря какая лодка, и какой Керпич
26..наш проджект менеджер пока думает ...
30. Копать ее сверху тоже вариант
31..маразм кто нить знет ответ? ей можно сказать только одно...мадам вы тормоз.
Reply With Quote
Old 21.01.2006, 21:02   #8
инсценирующи
 
[ Xelgen ]'s Avatar
 
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 31
Posts: 4,327
Downloads: 22
Uploads: 0
Reputation: 193 | 4
Default Re: 31 задачек и вопросов для програмистов (и не только них)

26. Интрересно можно каким то образом использовать стрелы во второй раз, типа достать и снова выстрелить?
30. Кстати оригинально
31. Я вообще не в кусре есть ли какое то общепринятый метод нумерации зданий, в зависимости от направления движений автомобилей.


Knightmare> нам нужен физик, но я думаю так же как и Сайбер Джо.
если вырезанный прямоуголник повернут относительно прямоугольника торта, то при твоем способе получаеться 4 треуголника.
Reply With Quote
Old 21.01.2006, 21:44   #9
Banned
 
Forever Child's Avatar
 
Join Date: 10 2001
Location: ...осень колибри
Age: 37
Posts: 7,487
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: 31 задачек и вопросов для програмистов (и не только них)

Quote:
Originally Posted by [ Xelgen ]
31. В Лондоне женщина вышла из автобуса около дома № 37 и спросила мужчину, в каком направлении идти к дому № 33 - по ходу автобуса или в обратную сторону? Что ей ответить?
Представьте, что вы в России. Ответ станет тривиальным.
Reply With Quote
Old 21.01.2006, 22:02   #10
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: 31 задачек и вопросов для програмистов (и не только них)

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

Xelgen: четыре треугольника = две пары равных треугольников, имхо, и тогда всё поделенно

для 17-ой нужен математик

24. по теореме о неподвижной точке - поджечь с двух сторон, и хрен с ней, с неравномерностью.
Reply With Quote
Old 21.01.2006, 22:03   #11
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: 31 задачек и вопросов для програмистов (и не только них)

хотя если плотность спирта ниже плотности пива.... ну и нах
Reply With Quote
Old 21.01.2006, 22:21   #12
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: 31 задачек и вопросов для програмистов (и не только них)

26a. Если цель орков (каждого по отдельности) именно съесть (а, значит, поддержать свою жизнь), то достаточно пригрозить им тем, что через некоторое время вы убъете того, кто ближе всего к вам. Но тогда, правда, достаточно и одной стрелы... Разумные орки должны решить (каждый по отдельности), что важнее: смерть и неосуществимая идея насыщения, или голодная жизнь. В результате, все отстают.

P.S. Всё верно, ведь эти твари эгоистичны!
Reply With Quote
Old 22.01.2006, 00:36   #13
инсценирующи
 
[ Xelgen ]'s Avatar
 
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 31
Posts: 4,327
Downloads: 22
Uploads: 0
Reputation: 193 | 4
Default Re: 31 задачек и вопросов для програмистов (и не только них)

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

А вот с лодкой. Как бы объяснить то, как я это понимаю на пальцах..
Предсавь что в бассейне плавает большой пенопластовый плот, и на нем лежит чугунная болванка. Чтоб компенсировать весь болванки, пенопласт должен опуститься настолько, чтоб вытеснить воду весом в болванку.
Теперь, если болванку скинуть на дно бассейна, то она вытеснит лишь равный своему объему объем воды. (Болванка как и кирпич тяжелее/плотнее воды.) Следовательно уровень опуститься..

Надеюсь понятно выразил свою полуночную мысль..

Кстати, неплохое решенеие насчет эльфа. Но так как орки эгоистичны, они будут стоять и ждать пока половина из их группы подойдет и ты их пристрелишь, а потом уже оставшиеся тебя безоружного съедят.
Как-то не очень надежно получается..
Reply With Quote
Old 22.01.2006, 01:05   #14
The splendid
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Pure thoughts
Age: 36
Posts: 3,408
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default Re: 31 задачек и вопросов для програмистов (и не только них)

15. а==(a>>1)<<1 вроде не верно: (a & -a) == a
23. (((x - ((x >> 1) & 033333333333) - ((x >> 2) & 011111111111)) + ((x -((x >> 1) & 033333333333) - ((x >> 2) & 011111111111)) >> 3)) & 030707070707) % 63 -> в MIT-е об этом додумались
Reply With Quote
Old 22.01.2006, 09:14   #15
скромный VIP
 
analyst's Avatar
 
Join Date: 06 2003
Location: Yerevan
Age: 30
Posts: 960
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: 31 задачек и вопросов для програмистов (и не только них)

Nu esli pomnit chto jidkosti pri zamerzanii rasshirayutsya w obyeme(butilka s wodoy w morozilneike), to sledowateno, kogda spirt w piwe rastaet, urown podnizetsya... I budet u was bolshaya bochka s Ershem.
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 01:59.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.