Сборник задач от Microsoft?

Token · Post by **Token** » 28 Jan 2002 05:25

Где можно найти сборник задач от Microsoft, т.е. логических и технических задач встреченных на интервью с Microsoft, телефонном и очном?
Если у кого то уже есть опыт не могли бы также поделиться здесь или по email?

adb · Post by **adb** » 28 Jan 2002 06:23

Мне вот посоветовали сайт:
http://www.acetheinterview.com

8K · Post by 8K » 28 Jan 2002 23:19

Я недавно постил вот такую ссылку http://halcyon.usc.edu/~kiran/msqs.html

Token · Post by **Token** » 29 Jan 2002 05:27

<blockquote>quote:<hr>Originally posted by adb:
Мне вот посоветовали сайт:
http://www.acetheinterview.com<hr></blockquote>

Хороший сайт, только что-то он постоянно надоедает боксом. Можно его убрать?

Token · Post by **Token** » 29 Jan 2002 05:28

<blockquote>quote:<hr>Originally posted by 8K:
Я недавно постил вот такую ссылку http://halcyon.usc.edu/~kiran/msqs.html<hr></blockquote>

8K, спасибо за ссылку. Сами, небось, пользовались, судя по адресу?

listen_me_now · Post by **listen_me_now** » 29 Jan 2002 08:34

Там есть задачка про 8 шаров , один из которых отличается по весу от
остальных . Как за 2 взвешивания можно его найти ?
Нужно положить на чашку по 3 шара , если равновесие не нарушено ,
то шар в оставшихся 2-х .

Возник вот такой вопрос : имеется n шаров , один из которых отличается
от остальных весом , и дается всего 3 взвешивания .
Каково максимально возможное n , при котором задача разрешима ?
А если дается 4,5,..,n взвешиваний - каково максимально допустимое
число шаров ?

gekkarp · Post by **gekkarp** » 29 Jan 2002 16:41

[QUOTE]Originally posted by listen_me_now:
[QB]Там есть задачка про 8 шаров , один из которых отличается по весу от
остальных . Как за 2 взвешивания можно его найти ?
Нужно положить на чашку по 3 шара , если равновесие не нарушено ,
то шар в оставшихся 2-х .

Возник вот такой вопрос : имеется n шаров , один из которых отличается
от остальных весом , и дается всего 3 взвешивания .
[QUOTE][QB]
Вроде 27
Рассуждение такое - максимальное кол-во шаров, которое можно исследовать за 2 взвешивания - 9.
Максимальное число шаров, которое можно привести к предыдущей задаче - 27 (3*9) за одно взвешивание получим 9 с нужным шаром. Соотв.
4 взвешивания 3^4.
n - 3^n
Так?

gekkarp · Post by **gekkarp** » 29 Jan 2002 16:48

Кто-нибудь может мне тупому объяснить в чем тут штука?
5. How many cars are there in the USA?
Тут какая-то язковая хитрость или ответить надо что-то типа ask DMV?
Или are there имеется ввиду конкретно "здесь, в месте разговора"?

Vovka · Post by **Vovka** » 29 Jan 2002 18:09

<blockquote>quote:<hr>Originally posted by gekkarp:
Кто-нибудь может мне тупому объяснить в чем тут штука?
5. How many cars are there in the USA?
Тут какая-то язковая хитрость или ответить надо что-то типа ask DMV?
Или are there имеется ввиду конкретно "здесь, в месте разговора"?<hr></blockquote>

Может, это на умение давать грубую оценку какой-нить величине по неполным данным? Наверное, требуется сказать что-нить более-менее правдоподобное - с точностью до порядка?

listen_me_now · Post by **listen_me_now** » 30 Jan 2002 08:12

<blockquote>quote:<hr>Originally posted by gekkarp:
к предыдущей задаче - 27 (3*9) за одно взвешивание получим 9 с нужным шаром. Соотв.
4 взвешивания 3^4.
n - 3^n
Так?[/QB]<hr></blockquote>

Похоже , так оно и есть .
Пусть имеем 27 шаров - за 3 взвешивания :
1. берем из них 18 шаров и раскладываем поровну ,
2. затем берем те 9 , и приходим к вышеуказанному решению

Пусть имеем 81 шар - за 4 взвешивания :
1. берем из них 27 , и приходим к вышеуказанному решению

И т.д.

listen_me_now · Post by **listen_me_now** » 30 Jan 2002 08:26

Мне там понравилась еще одна задача - чем-то она напоминает классику
про черепаху .

Первый поезд отправляется из лос-анжелеса в нью-йорк со скоростью 15 км.
одновременно с ним вылетает птица в том же направлении со скоростью 25 км .
Второй поезд идет из нью-йорка навстречу со скоростью 20 км.
Когда птица долетит до встречного поезда , она разворачивается и летит
с радостной вестью обратно , потом опять разворачивается и т.д.
Скоко раз она сможет это сделать ?
s - расстояние между городами
v1 - скорость первого поезда
v2 - скорость второго поезда
v3 - скорость птицы
t1 = s/(v1+v2) - время , через которое поезда встретятся
t2 = s/(v2+v3) - время , через которое птица первый раз долетит
до второго поезда
Ваше решение ?

gekkarp · Post by **gekkarp** » 30 Jan 2002 09:20

<blockquote>quote:<hr>Originally posted by Vovka:


Может, это на умение давать грубую оценку какой-нить величине по неполным данным? Наверное, требуется сказать что-нить более-менее правдоподобное - с точностью до порядка?<hr></blockquote>
Тогда я знаю правильный ответ - ДОФИГА. [img:0319f198e9]images/smiles/icon_smile.gif[/img:0319f198e9]

gekkarp · Post by **gekkarp** » 30 Jan 2002 14:37

<blockquote>quote:<hr>Originally posted by listen_me_now:
Мне там понравилась еще одна задача - чем-то она напоминает классику
про черепаху .

Первый поезд отправляется из лос-анжелеса в нью-йорк со скоростью 15 км.
одновременно с ним вылетает птица в том же направлении со скоростью 25 км .
Второй поезд идет из нью-йорка навстречу со скоростью 20 км.
Когда птица долетит до встречного поезда , она разворачивается и летит
с радостной вестью обратно , потом опять разворачивается и т.д.
Скоко раз она сможет это сделать ?
s - расстояние между городами
v1 - скорость первого поезда
v2 - скорость второго поезда
v3 - скорость птицы
t1 = s/(v1+v2) - время , через которое поезда встретятся
t2 = s/(v2+v3) - время , через которое птица первый раз долетит
до второго поезда
Ваше решение ?<hr></blockquote>
Вопрос был сколько она пролетит а не сколько раз.
Подобная задачка уже кстати здесь рассказывалась IMHO. Про собаку и велосипедистов

clinger · Post by **clinger** » 30 Jan 2002 16:38

<blockquote>quote:<hr>Originally posted by gekkarp:
[QUOTE]Originally posted by listen_me_now:
[QB]Там есть задачка про 8 шаров , один из которых отличается по весу от
остальных . Как за 2 взвешивания можно его найти ?
Нужно положить на чашку по 3 шара , если равновесие не нарушено ,
то шар в оставшихся 2-х .

Возник вот такой вопрос : имеется n шаров , один из которых отличается
от остальных весом , и дается всего 3 взвешивания .
[QUOTE][QB]
Вроде 27
Рассуждение такое - максимальное кол-во шаров, которое можно исследовать за 2 взвешивания - 9.
Максимальное число шаров, которое можно привести к предыдущей задаче - 27 (3*9) за одно взвешивание получим 9 с нужным шаром. Соотв.
4 взвешивания 3^4.
n - 3^n
Так?<hr></blockquote>

Видимо не так. 27 за 3 не получается если не известно тяжелее или легче шар. Если он просто ОТЛИЧАЕТСЯ по весу, то только 12 за 3 взвешивания, эта задачка подробно разбиралась здесь же несколько месяцев назад.

Интересно получается. Из двух шаров неправильный вообще не определить, из трех за одно взвешивание тоже не определить.

.pl

Andy77 · Post by **Andy77** » 30 Jan 2002 17:07

<blockquote>quote:<hr>Originally posted by listen_me_now:
Мне там понравилась еще одна задача - чем-то она напоминает классику
про черепаху .

Первый поезд отправляется из лос-анжелеса в нью-йорк со скоростью 15 км.
одновременно с ним вылетает птица в том же направлении со скоростью 25 км .
Второй поезд идет из нью-йорка навстречу со скоростью 20 км.
Когда птица долетит до встречного поезда , она разворачивается и летит
с радостной вестью обратно , потом опять разворачивается и т.д.
Скоко раз она сможет это сделать ?
s - расстояние между городами
v1 - скорость первого поезда
v2 - скорость второго поезда
v3 - скорость птицы
t1 = s/(v1+v2) - время , через которое поезда встретятся
t2 = s/(v2+v3) - время , через которое птица первый раз долетит
до второго поезда
Ваше решение ?<hr></blockquote>

ДОФИГА, очевидно.

gekkarp · Post by **gekkarp** » 30 Jan 2002 17:08

<blockquote>quote:<hr>Originally posted by clinger:


Видимо не так. 27 за 3 не получается если не известно тяжелее или легче шар. Если он просто ОТЛИЧАЕТСЯ по весу, то только 12 за 3 взвешивания, эта задачка подробно разбиралась здесь же несколько месяцев назад.

Интересно получается. Из двух шаров неправильный вообще не определить, из трех за одно взвешивание тоже не определить.

.pl<hr></blockquote>
Надо найти отличающийся.
Нда. а ведь действительно. если из 3 шаров 2 одинаковых мы взвесили - то все ок. А если нет - то надо еще одно взвешивание.
т.е. при n взвешиваниях можно исследовать
3 ^(n-1) шар

[ 30-01-2002: Message edited by: gekkarp ]

8K · Post by 8K » 30 Jan 2002 19:36

<blockquote>quote:<hr>Originally posted by Token:


8K, спасибо за ссылку. Сами, небось, пользовались, судя по адресу?<hr></blockquote>

Да не, я и так крут [img:effa52d217]images/smiles/icon_smile.gif[/img:effa52d217] . Хотя иногда оттуда пацану даю задачки.

8K · Post by 8K » 30 Jan 2002 22:19

<blockquote>quote:<hr>Originally posted by Token:


Ну-ка расскажите как из 9 шаров определить какой отличается по весу за 2 взвешивания...<hr></blockquote>

Да и за одно взвешивание можно, вообще говоря. От весов зависит.

CTAC_P · Post by **CTAC_P** » 31 Jan 2002 03:49

<blockquote>quote:<hr>Originally posted by listen_me_now:
Там есть задачка про 8 шаров , один из которых отличается по весу от
остальных . Как за 2 взвешивания можно его найти ?
Нужно положить на чашку по 3 шара , если равновесие не нарушено ,
то шар в оставшихся 2-х .
<hr></blockquote>
А если нарушено? В задаче же сказано про ОТЛИЧАЮЩИЙСЯ, а не больший/меньший. Если у Вас одна из чаш перевесила, то Вы не можете сказать, на какой из чаш ОТЛИЧАЮЩИЙСЯ. Он может быть и легче и тяжелее.

Token · Post by **Token** » 31 Jan 2002 09:17

<blockquote>quote:<hr>Originally posted by gekkarp:

Вроде 27
Рассуждение такое - максимальное кол-во шаров, которое можно исследовать за 2 взвешивания - 9.
Максимальное число шаров, которое можно привести к предыдущей задаче - 27 (3*9) за одно взвешивание получим 9 с нужным шаром. Соотв.
4 взвешивания 3^4.
n - 3^n
Так?<hr></blockquote>

Ну-ка расскажите как из 9 шаров определить какой отличается по весу за 2 взвешивания...

gekkarp · Post by **gekkarp** » 01 Feb 2002 13:52

<blockquote>quote:<hr>Originally posted by Token:


Ну-ка расскажите как из 9 шаров определить какой отличается по весу за 2 взвешивания...<hr></blockquote>
Уже ж поправился.
За 3. Потому как если из оставшейся тройки мы взвесим разные то придется делать еще одно

Token · Post by **Token** » 07 Feb 2002 20:47

никто не знает, как решить задачу №8?

8. You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then a marble will be picked from the jar. Placing all of the marbles in the jars, how can you maximize the chances of a red marble being picked? What are the exact odds of getting a red marble using your scheme?

Melkor · Post by **Melkor** » 07 Feb 2002 22:11

<blockquote>quote:<hr>Originally posted by Token:
никто не знает, как решить задачу №8?

8. You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then a marble will be picked from the jar. Placing all of the marbles in the jars, how can you maximize the chances of a red marble being picked? What are the exact odds of getting a red marble using your scheme?<hr></blockquote>

Я думаю, нужно в один графин положить красный шар, а во второй 50 синих и 49 красных. При случайном и равномерно распределенном выборе шара из графина (это почему-то явно не указано в условии) лучше, по-моему, нельзя.