1

Тема: [Задачі] Співбесіди в ІТ гігантах і не тільки

Наштовхнувся на задачі зі співбесід ІТ гігантів.

Так привернула увагу задача, правильну відповідь на яку не розкрив екзаменатор.

Qualcomm

Что спрашивают в Qualcomm
7. Эту задачку описал пользователь, которого собеседовали на позицию senior systems engineer. Он отметил в описании задачи, что у него был свой ответ, по поводу которого он долго спорил с человеком, проводившим собеседование.

Предположим, у нас происходит 10 пакетных передач данных по беспроводной сети. Канал не очень качественный, так что есть вероятность 1/10, что пакет данных не будет передан. Трансмиттер всегда знает, удачно или неудачно был передан пакет данных. Когда передача неудачная, трансмиттер будет передавать пакет до тех пор, пока не преуспеет.

Вопрос: Какую пропускную способность канала получаем?

Ответ: По версии пользователя, ответ должен был быть 9 пакетов в секунду. Но человек, проводивший интервью, с ним не согласился, правда, ответа не назвал, но повторял, что «из-за ретрансмиссии пропускная способность должна быть уменьшена больше, чем на 1/10″.

Трохи поворушив мізками щось підказало що відповідь десь 81 зі 100, тож трохи по шаманив та отримав 81.9 зі 100. А хто ще які відповіді отримав на цю задачу?

2

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Та це не программерська задача, а із теорії ймовірностей, 1 чи 2 курс математичного факультету в більшості ВНЗ...

0.1 - ймовірність невдачі, відповідно, кожна спроба переслати пакет, що не відіслався - теж має імовірність 0.1 невдачі. Отже, шлях ваших думок вірний - 0.9 * 0.9 = 0.81 успіху... але іще з умови незрозуміло чи в цей же час пересилаються інші пакети, а не тільки той, шо не вдалося. У яких знову ж таки може ймовірність невдачі... І як тут поступити - важко сказати, тим більше, шо вже мало що памятаю з предмету теорії ймовірностей

3

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

В задачі ніде не сказано, що пакети передаються за 1 секунду. Якщо додати цю умову, то один пакет буде передаватися в середньому 1*0.9+2*0.1*0.9+3*0.1*0.1*0.9+...+0.9*n*(0.1)^(n-1)+...= S секунд. Тоді
S = 0.9(1+2*0.1+3*0.1^2+n*(0.1)^(n-1)+...) =
(виділяємо суму геометричної прогресії)
  = 0.9( (1+0.1+0.1^2+...+0.1^n+...) + (0.1+2*0.1^2 + 3*0.1^3 + ... + n *0.1^n+...) ) =
  = 0.9( 10/9 + 0.1(1+2*0.1+3*0.1^2+n*(0.1)^(n-1)+...) ) =
в других дужках лишилося щось знайоме, підставимо S/0.9
  = 0.9( 10/9 + 0.1*S/0.9 )
Маємо
S = 1 + 0.1*S
S = 10/9
Отже, один пакет буде йти 10/9 секунд, а пропускна здатність, відповідно, 9 п/с. Як не дивно, все правильно.

4

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

В мене вийшло (8.88...) із десяти.

При ретрансмісії ми втрачаємо 1/10 пакетів, при реретрансмісії ще 1/10, і так далі. Це зводиться до
https://latex.codecogs.com/gif.latex?%5Csum_%7Bn%3D1%7D%5E%7B%5Cinfty%7D%5Cfrac%7B1%7D%7B10%5En%7D

Подякували: HetmanNet1

5

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

quez написав:

В мене вийшло (8.88...) із десяти.

При ретрансмісії ми втрачаємо 1/10 пакетів, при реретрансмісії ще 1/10, і так далі. Це зводиться до
https://latex.codecogs.com/gif.latex?%5Csum_%7Bn%3D1%7D%5E%7B%5Cinfty%7D%5Cfrac%7B1%7D%7B10%5En%7D

Саме це хотів порахувати... але не знаю чому вийшло 81.9% :( Схоже мозок десь пішов каву попити, а мене не попередив про свою тимчасову відсутність  *PARDON*

Подякували: quez, leofun012

6

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Можна ще сказати так: кожну секунду ми відправляємо 9 нових пакетів і 1 старий. Приходить з них завжди 9, неважливо, нових чи старих. Наступної секунди знову буде відправлено 9 нових і 1 старий і прийнято 9. Пропускна здатність - 9.

Подякували: quez1

7

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

koala написав:

Можна ще сказати так: кожну секунду ми відправляємо 9 нових пакетів і 1 старий. Приходить з них завжди 9, неважливо, нових чи старих. Наступної секунди знову буде відправлено 9 нових і 1 старий і прийнято 9. Пропускна здатність - 9.

Практично.

Я, як і інтерв'юєр, виходив з припущення, що про недоставлений пакет можна дізнатись за час, яким можна знехтувати і трансміттер може повторити передачу практично в ту ж мить. Це справджується як мінімум не завжди. З іншої сторони, я й не синьйор.

8 Востаннє редагувалося koala (09.12.2015 17:07:17)

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Глянув, що там питают в Adobe - це, панове, ппц, 100 кілометрів загубили ж. Щонайменше.

Прихований текст

Что спрашивают в Adobe

3. У вас 50 мотоциклов, с заполненным топливом баком, которого хватает на 100 км езды.

Вопрос: Используя эти 50 мотоциклов, как далеко вы сможете заехать (учитывая, что изначально они находятся в условно одной точке пространства)?

Ответ:

Самый простой ответ: завести их все одновременно и проехать 100 км. Но есть и другое решение. Сначала переместите все мотоциклы на 50 км. Затем, перелейте топливо из половины мотоциклов в другую половину. У вас таким образом — 25 мотоциклов с полным баком. Проедьте еще 50 км и повторите процедуру. Так можно забраться на 350 км (не учитывая того топлива, которое останется от «лишнего» мотоцикла при разделе 25 надвое).

Правильна відповідь:

Їдемо 100/50=2 кілометри. Розливаємо бензобак одного з мотоциклів, де лишився запас на 98 км, по решті - у всіх, крім одного, повні баки, його лишаємо. Їдемо 100/49=2,041км, розливаємо бак одного по решті 48 і т.д. В результаті проїдемо 100(1/50+1/49+...+1/2+1)=449.92км

Подякували: HetmanNet1

9

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Для того щоб відправити 100 пакетів потрібно відправити 111.(1).
Відповідно швидкість виходить як 100/111.(1) = 0,9 * Реальна_швидкість.

Подякували: koala1

10

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

[code=python]# -*- coding: utf-8 -*-
#
import random


def need_packet(packets_to_send):
    sent_packets = 0
    while packets_to_send > 0:
        sent_packets += 1
        if random.randrange(10) > 0:
            packets_to_send -= 1
    return sent_packets


packets = 1000000
total_packets = need_packet(packets)
print('Необхідно надіслати пакетів: ', packets)
print('Надіслано пакетів:           ', total_packets)
print('Коефіцієнт ефективності:     ', packets/total_packets)[/code]

Необхідно надіслати пакетів:  1000000
Надіслано пакетів:            1111168
Коефіцієнт ефективності:      0.8999539223591753
Подякували: koala, HetmanNet, Sensetivity3

11

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

koala написав:

Глянув, що там питают в Adobe - це, панове, ппц, 100 кілометрів загубили ж. Щонайменше.

Прихований текст

Что спрашивают в Adobe

3. У вас 50 мотоциклов, с заполненным топливом баком, которого хватает на 100 км езды.

Вопрос: Используя эти 50 мотоциклов, как далеко вы сможете заехать (учитывая, что изначально они находятся в условно одной точке пространства)?

Ответ:

Самый простой ответ: завести их все одновременно и проехать 100 км. Но есть и другое решение. Сначала переместите все мотоциклы на 50 км. Затем, перелейте топливо из половины мотоциклов в другую половину. У вас таким образом — 25 мотоциклов с полным баком. Проедьте еще 50 км и повторите процедуру. Так можно забраться на 350 км (не учитывая того топлива, которое останется от «лишнего» мотоцикла при разделе 25 надвое).

Правильна відповідь:

Їдемо 100/50=2 кілометри. Розливаємо бензобак одного з мотоциклів, де лишився запас на 98 км, по решті - у всіх, крім одного, повні баки, його лишаємо. Їдемо 100/49=2,041км, розливаємо бак одного по решті 48 і т.д. В результаті проїдемо 100(1/50+1/49+...+1/2+1)=449.92км

Якось забагато у них помилок як на мене.

формула

http://replace.org.ua/misc.php?action=pun_attachment&item=1096&download=0&secure_str=430t5891

Post's attachments

Зняток екрану з 2015-12-09 20:03:59.png 3.93 kb, 187 downloads since 2015-12-09 

12

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Мені цікаво, як вони збираються їхати на 100 мотоциклах одночасно?

13

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

А з практики реальна швидкість десь буде половина від заявленої. Бо постійно хтось з чимось своїм кривим підключитья, чи якісь робочі поставлять металічний екран посередині.

14

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Vo_Vik написав:

Мені цікаво, як вони збираються їхати на 100 мотоциклах одночасно?

Теж цікаво. За новим мотоциклом вони повертаються пішки? Я б сказав що проїхати можна 100 км, бо я манав повертатись пішки за новим мотоциклом. А на кількох одночасно поїхати не вдасться.

Ще варіант.

Прихований текст

1. Їду за своєю подругою і приводжу її до мотоциклів.
2. Сідаємо з нею на два інших мотоцикли і проїзжаємо 50 км.
3. Зливаємо бензин з одного мотоцикла в інший.
4. Один мотоцикл кидаємо, а на іншому їдемо ще 100 км.

Відповідь 150 км ))

15

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Vo_Vik написав:

Мені цікаво, як вони збираються їхати на 100 мотоциклах одночасно?

Беремо N-водіїв і жертвуємо ними по мірі закінчення бензину)

16

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

З’їдаємо? За одно вирішуємо проблему не тільки з бензином, а і з харчуванням.

Подякували: HetmanNet1

17

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Плюс не враховано. що мотоцикл з повним і порожнім баком має різний розхід.

18

Re: [Задачі] Співбесіди в ІТ гігантах і не тільки

Vo_Vik написав:

Плюс не враховано. що мотоцикл з повним і порожнім баком має різний розхід.

Тому що це ідеальний мотоцикл довжину в один метр і вагою в один кілограм.