Math test at InteractiveBrokers.com

[crypto5]

Мне конечно немного неловко обьяснять элементарные вещи, но все же, длинный шаг будет выглядеть следующим образом:
for(int i = 0; i < n; i ++) {
n2 = n2 -> next;
if(n2 == n1) loop!!!
}
где n - количество подшагов за длинный шаг.

[LKB]

Мне конечно немного неловко обьяснять элементарные вещи, но все же, длинный шаг будет выглядеть следующим образом:
for(int i = 0; i < n; i ++) {
n2 = n2 -> next;
if(n2 == n1) loop!!!
}
где n - количество подшагов за длинный шаг.

Вы что тут показываете? Я сказала, что если есть 2 указателя один с шагом 2 и один с шагом один то при попаданиии в луп они в какой-то момент пересекутся т.е. будут указывать на один и тот же элемент => это и будет означать луп.

Вы сказали, что нужны дополнительны проверки а то можно подобрать такую длину лопа, что они НЕ пересекутся. Какие дополнительные проверки вы имели ввиду и при какой длине лупа для шага 2 они никогда не пересекутся?

[crypto5]

Мне конечно немного неловко обьяснять элементарные вещи, но все же, длинный шаг будет выглядеть следующим образом:
for(int i = 0; i < n; i ++) {
n2 = n2 -> next;
if(n2 == n1) loop!!!
}
где n - количество подшагов за длинный шаг.

Вы что тут показываете? Я сказала, что если есть 2 указателя один с шагом 2 и один с шагом один то при попаданиии в луп они в какой-то момент пересекутся т.е. будут указывать на один и тот же элемент => это и будет означать луп.

Вы сказали, что нужны дополнительны проверки а то можно подобрать такую длину лопа, что они НЕ пересекутся. Какие дополнительные проверки вы имели ввиду и при какой длине лупа для шага 2 они никогда не пересекутся?

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

[vaduz]

7. A spider needs to eat three flies a day. Until he fills his quota, he has an even chance of catching any fly that attempts to pass his web. What are a fly's chances of survival, given that five flies have flown by today and no more will?

Как правильно отмчено, паук либо наловит 3х мух из пролетевших пяти, тогда 6-я муха - в шоколаде, либо не наловит и тогда 6-я муха рискует не по-деццки.

Обозначим вероятность поймать муху Pм, и вероятность наловить 3х мух из 5-и - P3/5

Вероятность мухи выжить

Pж = P3/5 + (1-Pм)*(1-P3/5) = 1-Pм*(1-P3/5)

Осталось посчитать P3/5
Общую формулу не знаю и лень искать, потому просто сложим вероятности возможных исходов, (х - поймал, 0 - просвистела мимо):

00ХХХ
0Х0ХХ
0ХХ0Х
Х00ХХ
Х0Х0Х
ХХ00Х

для каждого исхода из этих 6-ТИ вероятность p = Pм^3*(1-Pм)^2

0ХХХ
Х0ХХ
ХХ0Х

для каждого исхода из этих 3х вероятность p = Pм^3*(1-Pм)

ХХХ : p = Pм^3


итого
P3/5 = Pм^3 + 3*Pм^3*(1-Pм) + 6*Pм^3*(1-Pм)^2
P3/5 = Pм^3*(10-15*Pм+6*Pм^2)

[baton]

- Ты знаешь арамейский? - спросил раввин.
- Нет.
- А иврит?
- Нет.
- А Тору в детстве учил?
- Нет, ребе. Но вы не волнуйтесь. Я закончил философский факультет
Беркли и только что защитил диссертацию по логике в философии Сократа.
А теперь, чтобы восполнить белые пятна в моих познаниях, я хочу
немного поучить Талмуд.
- Ты не готов учить Талмуд, - сказал раввин. - Это глубочайшая книга из
всех, написанных людьми. Но раз ты настаиваешь, я устрою тебе тест на
логику: справишься - буду с тобой заниматься.
Молодой человек согласился, и раввин продолжил.
- Два человека спускаются по дымоходу. Один вылезает с чистым лицом,
другой - с грязным. Кто из них пойдёт умываться?
У молодого философа глаза на лоб полезли.
- Это тест на логику?!
Раввин кивнул.
- Ну, конечно, тот, у кого грязное лицо!
- Неправильно. Подумай логически: тот, у кого грязное лицо, посмотрит на
того, у кого лицо чистое, и решит, что его лицо тоже чистое. А тот, у
кого лицо чистое, посмотрит на того, у кого лицо грязное, решит, что сам
тоже испачкался, и пойдёт умываться.
- Хитро придумано! - восхитился гость. - А ну-ка, ребе, дайте мне ещё
один тест!
- Хорошо, юноша. Два человека спускаются по дымоходу. Один вылезает с
чистым лицом, другой - с грязным. Кто из них пойдёт умываться?
- Но мы уже выяснили - тот, у кого лицо чистое!
- Неправильно. Оба пойдут умываться. Подумай логически: тот, у кого
чистое лицо, посмотрит на того, у кого лицо грязное, и решит, что его
лицо тоже грязное. А тот, у кого лицо грязное, увидит, что второй пошёл
умываться, поймёт, что у него грязное лицо, и тоже пойдёт умываться.
- Я об этом не подумал! Поразительно - я допустил логическую ошибку!
Ребе, давайте ещё один тест!
- Ладно. Два человека спускаются по дымоходу. Один вылезает с чистым
лицом, другой - с грязным. Кто из них пойдёт умываться?
- Ну: Оба пойдут умываться.
- Неправильно. Умываться не пойдёт ни один из них. Подумай логически:
тот, у кого лицо грязное, посмотрит на того, у кого лицо чистое, и не
пойдёт умываться. А тот, у кого лицо чистое, увидит, что тот, у кого
лицо грязное, не идёт умываться, поймёт, что его лицо чистое, и тоже не
пойдёт умываться.
Молодой человек пришёл в отчаяние.
- Ну поверьте, я смогу учить Талмуд! Спросите что-нибудь другое!
- Ладно. Два человека спускаются по дымоходу:
- О Господи! Ни один из них не пойдёт умываться!!!
- Неправильно. Теперь ты убедился, что знания логики Сократа
недостаточно, чтобы учить Талмуд? Скажи мне, как может быть такое, чтобы
два человека спускались по одной и той же трубе, и один из них испачкал
лицо, а другой - нет?! Неужели ты не понимаешь? Весь этот вопрос -
бессмыслица, и если ты потратишь жизнь, отвечая на бессмысленные
вопросы, то все" твои ответы тоже будут лишены смысла!

[adda_]

Для Стемфорда - неплохая зарплата.. Тут как бы и не грех знать математику на уровне Бауманского училища.

Я учился в МАИ (что почти одно и тоже), но студентом был плохим поетому сеичас пасплачиваюсь за лень

Я защитил PhD в МАИ и ну их нах с их дурацкими задачками.
Никому не нужными на самом деле.
Пусть выеживаются дальше. В реальной работе все это нах не нужно...

[daemon_]

есче задачку от них вспомнил, уже на самом интервью задали -
написать класс для множества интервалов [a-b] & [c-d].. и так далее
а, b, c, d могут быть целыми или нецелыми

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

[mutabor2]

How many rectangles can be composed in a (n,m) grid?

Moe reshenije:

It's multiplication of number of continuous number sequences between 1 and n to number of the same between 1 to m.
1: 1
2: 2 + (2-1)
3: 3+ (3-1) + (3-2)
...
n: n+(n-1)+...+1

Same for m.

Answer: n**2*m**2/4

Все верно, только сумма арифметической прогресии равна n(n+1)/2
=>Решение n(n+1)m(m+1)/4.

Например, если n=1, а m=3 ответ 6, а не 9/4 и не 0 (как для ответа n(n-1)m(m-1)/4 ) .

[crypto5]

Нехорошо редактировать сообщения..

[crypto5]

Например, если n=1, а m=3 ответ 6, а не 9/4 и не 0 (как для ответа n(n-1)m(m-1)/4 ) .

В оригинальной постановке задачи(как там нарисовано), неочевидно грид (1,1) это точка или квадрат, поэтому у меня и ответ другой получился. Но идейно ты прав конечно.

[crypto5]

Например, если n=1, а m=3 ответ 6, а не 9/4 и не 0 (как для ответа n(n-1)m(m-1)/4 ) .

В оригинальной постановке задачи(как там нарисовано), неочевидно грид (1,1) это точка или квадрат, поэтому у меня и ответ другой получился. Но идейно ты прав конечно.

Присмотрелся, вроде все таки очевидно..

[crypto5]

Кстати, доказать что они действительно пересeкутся это вторая часть этого вопроса была обычно.

Кстати, а как доказать?

[fessa]

а третья часть вопроса - найти начало цикла

[baton]

На ету работу жалею что не попал: KDB Developer в Barclays Capital.

Если интересно писать напрямую манагеру: ramesh.regulapati@barclayscapital.com

Задачка на interview: есть интервал чисел от 0 до 100 и толпа народу. Каждому человеку задан один и тот же вопрос: Выбрать число из интервала которое будет равно 2/3 от average всеи выборки.

Я ответил что ето normal distribution поетому average будет 50, поетому ответ: 20.

ето, похоже неправильно, потому что он стал говорить о game theory и о том что опредленая чась людей будет думать также как я.

[baton]

Все верно, только сумма арифметической прогресии равна n(n+1)/2
=>Решение n(n+1)m(m+1)/4.

Например, если n=1, а m=3 ответ 6, а не 9/4 и не 0 (как для ответа n(n-1)m(m-1)/4 ) .

Спасибо! Вспомнил, Гаусс, в школе ету формулу придумал.

[nightmare2]

- Ты знаешь арамейский? - спросил раввин.
- Нет.
- А иврит?
- Нет.
- А Тору в детстве учил?
- Нет, ребе. Но вы не волнуйтесь. Я закончил философский факультет
Беркли и только что защитил диссертацию по логике в философии Сократа.
А теперь, чтобы восполнить белые пятна в моих познаниях, я хочу
немного поучить Талмуд.
- Ты не готов учить Талмуд, - сказал раввин. - Это глубочайшая книга из
всех, написанных людьми. Но раз ты настаиваешь, я устрою тебе тест на
логику: справишься - буду с тобой заниматься.
Молодой человек согласился, и раввин продолжил.
- Два человека спускаются по дымоходу. Один вылезает с чистым лицом,
другой - с грязным. Кто из них пойдёт умываться?
У молодого философа глаза на лоб полезли.
- Это тест на логику?!
Раввин кивнул.
- Ну, конечно, тот, у кого грязное лицо!
- Неправильно. Подумай логически: тот, у кого грязное лицо, посмотрит на
того, у кого лицо чистое, и решит, что его лицо тоже чистое. А тот, у
кого лицо чистое, посмотрит на того, у кого лицо грязное, решит, что сам
тоже испачкался, и пойдёт умываться.
- Хитро придумано! - восхитился гость. - А ну-ка, ребе, дайте мне ещё
один тест!
- Хорошо, юноша. Два человека спускаются по дымоходу. Один вылезает с
чистым лицом, другой - с грязным. Кто из них пойдёт умываться?
- Но мы уже выяснили - тот, у кого лицо чистое!
- Неправильно. Оба пойдут умываться. Подумай логически: тот, у кого
чистое лицо, посмотрит на того, у кого лицо грязное, и решит, что его
лицо тоже грязное. А тот, у кого лицо грязное, увидит, что второй пошёл
умываться, поймёт, что у него грязное лицо, и тоже пойдёт умываться.
- Я об этом не подумал! Поразительно - я допустил логическую ошибку!
Ребе, давайте ещё один тест!
- Ладно. Два человека спускаются по дымоходу. Один вылезает с чистым
лицом, другой - с грязным. Кто из них пойдёт умываться?
- Ну: Оба пойдут умываться.
- Неправильно. Умываться не пойдёт ни один из них. Подумай логически:
тот, у кого лицо грязное, посмотрит на того, у кого лицо чистое, и не
пойдёт умываться. А тот, у кого лицо чистое, увидит, что тот, у кого
лицо грязное, не идёт умываться, поймёт, что его лицо чистое, и тоже не
пойдёт умываться.
Молодой человек пришёл в отчаяние.
- Ну поверьте, я смогу учить Талмуд! Спросите что-нибудь другое!
- Ладно. Два человека спускаются по дымоходу:
- О Господи! Ни один из них не пойдёт умываться!!!
- Неправильно. Теперь ты убедился, что знания логики Сократа
недостаточно, чтобы учить Талмуд? Скажи мне, как может быть такое, чтобы
два человека спускались по одной и той же трубе, и один из них испачкал
лицо, а другой - нет?! Неужели ты не понимаешь? Весь этот вопрос -
бессмыслица, и если ты потратишь жизнь, отвечая на бессмысленные
вопросы, то все" твои ответы тоже будут лишены смысла!

[blak_box]

Задачка на interview: есть интервал чисел от 0 до 100 и толпа народу. Каждому человеку задан один и тот же вопрос: Выбрать число из интервала которое будет равно 2/3 от average всеи выборки.

Я ответил что ето normal distribution поетому average будет 50, поетому ответ: 20.

По-моему ответ 0. Так как 2/3 от 0 тоже 0.

[crypto5]

Задачка на interview: есть интервал чисел от 0 до 100 и толпа народу. Каждому человеку задан один и тот же вопрос: Выбрать число из интервала которое будет равно 2/3 от average всеи выборки.

Я ответил что ето normal distribution поетому average будет 50, поетому ответ: 20.

По-моему ответ 0. Так как 2/3 от 0 тоже 0.

Думаю что точного ответа тут быть не может. Нужно делать предположения о том какова удельная часть людей вообще не знакомы с математикой и могут произвести ответ от 0 до 100(пусть их удельная часть будет К1%), какова часть батонов(пусть их будет К2%), сколько людей на шаг умнее батона и которые считают что все думают как батон и соответственно выдадут ответ 50 * (2/3)^2, пусть их будет К3%. При такой простейшей апроксимации, оценка очевидно будет: 2/3 * (50 * К1/100 + 50 * 2/3 * К2/100 + 50 * (2/3)^2 * К3/100).

Возможно еще что интервьюер хотел услышать про Nash equilibrium.

Мне кажеться что не ожидался конкретный ответ, а хотелось увидеть цепь рассуждений и дополнительных вопросов.

[crypto5]

а третья часть вопроса - найти начало цикла

Програмка с квадратичным временем пишеться достаточо просто:
один указатель двигаеться с начала списка, и на каждый его шаг второй делает круг по цыклу. Когда оба указателя пересекуться это и будет начало цыкла.

А у вас какое решение?

Ну и понятно что все предыдущие размышления справедливы если есть требование не использовать дополнительную память(кроме пары указателей и переменных), иначе все решаеться намного проще.

[baton]

Возможно еще что интервьюер хотел услышать про Nash equilibrium.

Круто, спасибо!

[baton]

А у вас какое решение?

В изначалной постановке вторая метка двигалась сразу за первой и как только ее адрес становился больше ето был цикл.

[crypto5]

А у вас какое решение?

В изначалной постановке вторая метка двигалась сразу за первой и как только ее адрес становился больше ето был цикл.

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

Ну а про решение я спрашивал относительно подзадачи нахождения длины цикла.

[fessa]

есть/нет цикл - вы уже определили.
далее - длина цикла - тоже просто - один указатель стоит на месте, второй - инкрементируем, пока не встретятся, пусть длина = k.

нахождение начала цикла: 2 указателя, первый позиционируем на начало списка, 2-й - на k-й элемент.
инкрементируем оба указателя, пока они не встретятся, этот элемент и будет началом цикла. сложность - линейная.

[crypto5]

нахождение начала цикла: 2 указателя, первый позиционируем на начало списка, 2-й - на k-й элемент.
инкрементируем оба указателя, пока они не встретятся, этот элемент и будет началом цикла. сложность - линейная.

Отличное решение, только нужно 2-ой указатель на к+1-ый ставить(если с единицы начинать считать), или нужно обязательно 2-ой указатель в первую очередь инкрементировать.
Я бы до такого на собеседовании точно не додумался..

[Bobo]

7. A spider needs to eat three flies a day. Until he fills his quota, he has an even chance of catching any fly that attempts to pass his web. What are a fly's chances of survival, given that five flies have flown by today and no more will?

Здесь главная проблема - языковая. "Аn even chance" здесь переводится просто как "вероятность 1/2".
Вероятность поймать меньше 3 мух из 5 = 1/32 (0 мух) + 5/32 (1 муха) + 10/32 (2 мухи) = 1/2.
Ответ: 3/4.