Я не знаю правильных ответов на них, да и не на все из них есть правильные ответы, тем не менее, решить их будет интересной зарядкой для мозга. Буду рад любым комментариям.
Вопросов много, посему это растянется на несколько постов. Итак, поехали:
1) Почему крышки для канализационных люков круглые?
Пожалуй, самый известный вопрос с собеседований гугл. Он уже столько раз обсуждался, что я даже не уверен, задавался ли он на самом деле в гугле. На самом деле, этот вопрос скорее проверяет способность рассуждать. Классический ответ на него можно найти в википедии.
2) Чем мутекс отличается от семафора? Кого из них вы будете использовать для того чтобы обезопасить операцию инкремент?
Прежде всего, мутекс бинарный, то есть либо занят – либо свободен. Либо открыт – либо закрыт. Семафор же может принимать множество значений от 0 до некоторого заданного максимального значения.
Но это еще не всё. Мутекс всегда приналежит одному единственному потоку. Этот поток его получает и он же обязан его вернуть. Семафор же, напротив, никому не принадлежит и может получить сигнал из любого потока (процесса).
Что же касается второй части вопроса, я буду использовать мутекс.
3) Напишите программу на C которая измеряет скорость переключения контекста на UNIX/Linux.
В C я не силен, а вот написать программу измеряющую скорость переключения контекста на Java… давайте попробуем:
public class ContextSwitch implements Runnable{ private Object lock = new Object(); private volatile int counter = 0; public static final int MAX_CNT = 1000000; public void run() { for(;;){ synchronized (lock){ counter++; lock.notify(); if (counter<MAX_CNT){ try { lock.wait(10000); } catch (InterruptedException e) {} }else{ break; } } } } public static void main(String[] args) throws InterruptedException { ContextSwitch cts = new ContextSwitch(); Thread t1 = new Thread(cts); Thread t2 = new Thread(cts); long startTime = System.currentTimeMillis(); t1.start(); t2.start(); t1.join(); long endTime = System.currentTimeMillis(); System.out.println(endTime - startTime); } }
На моем компьютере получается 100000 переключений в секунду.
4)Вам дана функция возвращающая случайное число в диапазоне от 1 до 5. Напишите функцию которая будет возвращать случайное число в диапазоне от 1 до 7.
Дополнение: обе функции возвращают целые числа.
Т.к. вообще говоря, про распределение ничего не говорится, то можно написать всяческий бред. Я бы первым делом уточнил у собеседующего, какое распределение имеется в виду. Предположим, что равномерное, тогда ответ на эту задачу
int i; do { i = 5 * (rand5() - 1) + rand5(); // i равномерно распределено между 1 и 25 } while(i > 21); // i равномерно распределено между 1 и 21 return i % 7 + 1; // результат равномерно распределен между 1 и 7
Недостаток этого решения в том, что время его выполнения непредсказуемо и, пусть и с бесконечно малой вероятностью, может быть неограничено большим.
5)Опишите алгоритм обхода графа в глубину.
Для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Реализуется обычно либо с помощью стека либо с помощью рекурсии.
Равномерно распределенное в интервале 1..7 можно и по другому получить.
ReplyDelete3/2*(rand5()-1)+1
В скобках случайно распределенное в интервале 0..4. После умножения распределение меняется на равномерное в интервале 0..6. После прибавления единицы на 1..7.
Упс, спасибо, я забыл уточнить, что имеются в виду целые числа. В случае рациональных чисел задача действительно существенно упрощается.
ReplyDelete3/2*(rand5()-1)+1 - ответ неправильный.
ReplyDeleteВозьмем возможные результаты rand5()-1:
(каждый такой результат случается в одном из 5 случаев)
1)0 * 1.5 = 0
2)1 * 1.5 = 1.5
3)2 * 1.5 = 3
4)3 * 1.5 = 4.5
5)4 * 1.5 = 7
Здесь равным распределением даже не пахнет, не так ли?
3/2*(rand5()-1)+1 - любой коэффициент, на который вы умножите результат Rand5() просто раздвинет или сдвинет 5 равновероятных модальных значений.
ReplyDeleteИ не важно будут ли они находиться в отрезке с 1 до 7 или с 1 до 5. В этом отрезке всегда будут лишь 5 равновероятных значений, а все остальные значения будут выпадать с вероятностью 0.
Такой путь не ведет к решению задачи.
Насколько я понял, Anonymous имел в виду случай, когда rand5 возвращает не целые, а рациональные числа в диапазоне от 1..5
ReplyDeleteМутекс принадлежит всегда одному едиственному потоку?
ReplyDeleteЭто высказывние неверно! Мютекс, как и Семафор принадлежит ядру или операционной системе.
А вообще, проще будет сказать, что семафор, где count=1 - это и есть mutex.
Mutex - регулирует эксклюзивный допуск к одному объекту, а семафор - к пулу объектов.
В задаче с инкрементом - объект один.
mutex гарантирует, что только тот, кто его взял может его отпустить. Но он может быть также и полностью свободным, то есть не принадлежать никакому потоку.
ReplyDeletecount=1 это не единственное отличие. Мутекс может отпустить только тот поток, который его захватил. Семафор может освободить любой поток. Именно это я подразумевал под принадлежностью.
ReplyDeletehttp://en.wikipedia.org/wiki/Semaphore_%28programming%29#Semaphore_vs._mutex
"In many cases a mutex has a concept of an "owner": the process which locked the mutex is the only process allowed to unlock it. In contrast, semaphores generally do not have this restriction, something the producer-consumer example above depends upon."
>>>>Насколько я понял, Anonymous имел в виду >>>случай, когда rand5 возвращает не целые, а >>>рациональные числа в диапазоне от 1..5
ReplyDeleteВо-первых в условии задачи указаны целые числа... :-)
А во-вторых, если он имел ввиду вещественные числа, то задам вопрос:
Между 1 и 5 бесконечное количество вещественных чисел, не так ли?
То есть вероятность выпадания каждого числа = 1/бесконечность -> 0.
Представим, что число 2 у нас в этом случае выпадает в 2 раза чаще, чем число 3.
Значит вероятность выпадания 2-х = 2/бесконечность, а 3-х = 1/бесконечность. То есть и в том и в другом случае она стремится к нулю.
Вопрос: тогда как вообще написать функцию, которая дает не unified distribution на бесконечном пространстве значений?
Может ли такая задача вообще иметь смысл?
Или иными словами - почувствуйте разницу между 1/бесконечность и 0/бесконечность.
:-)
>>>Мутекс может отпустить только тот поток, который его захватил. Семафор может освободить любой поток. Именно это я подразумевал под принадлежностью.
ReplyDeleteЭто верное замечание, но если вставить слова "всегда принадлежит", то и оно немного режет слух.
Впрочем, наверное не стоит комментировать по мелочам, это правда.
>>> Вопрос: тогда как вообще написать функцию, которая дает не unified distribution на бесконечном пространстве значений?
ReplyDelete>>> Может ли такая задача вообще иметь смысл?
Может, и имеет.
Есть такое понятие как плотность вероятности: http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8
которое, собственно и описывает случайные распределения в множестве R.
И, пожалуй, самый известный пример неравномерного распределения на бесконечном пространстве: это нормальное распределение, оно же Гаусово
http://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5
сумма двух равномерно распределённых случайных величин не будет равномерно распределённой!!!
ReplyDeleteСмотрите пример 2 на http://sernam.ru/book_tp.php?id=60
Я в потоках и не особо разбираюсь. Но, в гугле работают или слышком умные или слишком амбциозные , прочитала в новостном портале, https://progamblingnews.com/istoriya-razvitiya-industrii-onlajn-razvlechenij/ . Да, там не только про казино пишут . Гугл, не работа, а мечта.
ReplyDelete