Здравствуйте, cppguard, Вы писали:
C>Дело не в синусе. Ряд Тейлора используется в математике как инструмент для разных доказательств, а для численных методов есть другие инструменты, более точные.
В ml используется для линеаризации, например. Чем не вариант?
Здравствуйте, Sharov, Вы писали:
S>Не скажите, про железо вопросы более-менее простые, если проходил какой-нибудь курс на курсере про S>процессоры или читал Хеннеси и Паттерсона. Чисто кругозорные вопросы обещго плана "что-то слышал".
если обо все поговорить так по верхам от железа до гауссианов, то тогда не понятно за что компания (тем более Яндекс) собираются платить (пусть и с премиями) 700к рублей на руки.
S>>Не скажите, про железо вопросы более-менее простые, если проходил какой-нибудь курс на курсере про S>>процессоры или читал Хеннеси и Паттерсона. Чисто кругозорные вопросы обещго плана "что-то слышал". JR>если обо все поговорить так по верхам от железа до гауссианов, то тогда не понятно за что компания (тем более Яндекс) собираются платить (пусть и с премиями) 700к рублей на руки.
Из того, что написано, кажется, что что-то по верхам, а что-то глубоко. Т.е. если человек хорошо разбирается в ml, но о кэшах процессора впервые услышал на собеседовании, то может быть это не очень здорово. Может нужен спец, который за месяц способен погрузиться в какую-нибудь область от ml до железа, при этом если человек до этого ничего о ней не знал, едва ли он это сделает быстро. Может что-то такое. Потому что если реально копать глубоко, и нужен прям профи, едва ли это один человек.
Как я понял, у человека неплохой алг. бэкграунд+ml (в Я работал), а знания железа -- курсы+кругозор+глубокие копания в цпп.
Здравствуйте, Sharov, Вы писали:
S>Кажется, что логично, если нам надо что-то считать, то посл-ть будет увеличиваться. Не понял подвох или суть вопроса. S>А вот что происходит с удаленными номерами -- . Ничего, наверное. Нету же там како-то пула страниц.
Здравствуйте, cppguard, Вы писали:
L>>В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы. L>>Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, если тоже 1, то ищем индекс K в этой последовательности на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.
C>Ага, и сложность вышеописанного алгоритма — O(N * log(M)) в худшем случае:
C>
Здравствуйте, landerhigh, Вы писали:
C>>Я задачу понял так: даны N последовательностей, каждая состоит из M значений. В каждый последовательности сперва идут нули, потом в какой-то момент начинают идти единицы. Нужно определить номер последовательности, в которой индекс первой единицы — наименьший. Если всё верно, то я бы очень хотел посмотреть на алгоритм O(N+log(M)) для этой задачи.
L>Дело в том, что нет никакой необходимости проводить N поисков по M: L>В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы. L>Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, если тоже 1, то ищем индекс K в этой последовательности на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.
Очень хочется надеяться, что это всего лишь бесполезная задачка с собеседования. И что в продакшене для выделенного выше все-таки используется нормальная реализация bitset с каким-нибудь clz
Здравствуйте, PM, Вы писали:
PM>Очень хочется надеяться, что это всего лишь бесполезная задачка с собеседования. И что в продакшене для выделенного выше все-таки используется нормальная реализация bitset с каким-нибудь clz
В продакшене, когда речь идет о датчиках, используется КА, который срабатывает, как только один датчик меняет состояние.
Если нужно анализировать данные в офлайне, уже когда-нибудь потом, то на сложность по большому счету пофиг.
Здравствуйте, so5team, Вы писали:
S>Ведь тогда на шагах со второго по последний нам придется делать одинаковые поиски со сложностью O(log(M-1)). Разве нет?
В этом случае, в шагах, начиная со второгшо по последний, поиски проводить вообще не требуется.
Здравствуйте, landerhigh, Вы писали:
S>>Ведь тогда на шагах со второго по последний нам придется делать одинаковые поиски со сложностью O(log(M-1)). Разве нет?
L>В этом случае, в шагах, начиная со второгшо по последний, поиски проводить вообще не требуется.
Э...
если тоже 1, то ищем индекс K в этой последовательности на отрезке [0, K]
На втором шаге вы обнаруживаете 1 по индексу K (при этом K==(M-1)). Вы знаете, что по индексу K единица, но не знаете, первая ли это единица в строке или нет. Чтобы это узнать, вам нужно сделать поиск единиц слева от K (т.е. в диапазоне [0, (K-1)]).
И, поскольку K у вас не меняется, на каждой следующей итерации вы должны будете проделывать тоже самое.
Здравствуйте, so5team, Вы писали:
S>На втором шаге у вас K==(M-1). Вы знаете, что по индексу K единица, но не знаете, первая ли это единица в строке или нет. Чтобы это узнать, вам нужно сделать поиск единиц слева от K (т.е. в диапазоне [0, (K-1)]). S>И, поскольку K у вас не меняется, на каждой следующей итерации вы должны будете проделывать тоже самое.
Мне просто лень было уже детали описывать.
Дело в том, что мы не ищем 1 или 0. Мы ищем позицию K, где sensor[0][K] != sensor[0][K-1].
И соответственно, когда мы ее нашли в первом датчике, мы проверяем значение sensor[1][K]. Если оно равно 1, то выполняем также и сравнение sensor[1][K] == sensor[1][K-1]. Если оно true, то этот датичк сработал раньше, чем датчик 0 и нужно вести поиск по sensor[1][0, K] (на самом деле sensor[1][0, K) )
Здравствуйте, landerhigh, Вы писали:
L>Дело в том, что мы не ищем 1 или 0. Мы ищем позицию K, где sensor[0][K] != sensor[0][K-1]. L>И соответственно, когда мы ее нашли в первом датчике, мы проверяем значение sensor[1][K]. Если оно равно 1, то выполняем также и сравнение sensor[1][K] == sensor[1][K-1]. Если оно true, то этот датичк сработал раньше, чем датчик 0 и нужно вести поиск по sensor[1][0, K] (на самом деле sensor[1][0, K) )
Соответственно, первоначальное описание, содержащие:
В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
Проверяем значение, находящемся по этому индексу K в следующей последовательности
следовало бы переформулировать так:
В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
Проверяем значение, находящемся по этому индексу (K-1) в следующей последовательности
.
ибо смысл проверять сперва sensor[i+1][K] и только затем, если там 1, делать сравнение c sensor[i+1][K-1], не видно. Можно же сразу сравнивать sensor[i][K] с sensor[i+1][K-1].
Здравствуйте, landerhigh, Вы писали:
L>Нет. Сумма асимптоматик (коей является О большое) — это max() (хотя бы тут.)
L>Тут сразу бросается в глаза, что
L>O(1)+O(2) = O(1)
Чувак, ты смешал в кучу коней и людей. Почитай КМП на тему того, как правильно считать сложность алгоритмов. По твоей логике insertion sort тоже должен иметь сложность O(N), потому что там O(N) + O(N-1) + ... + O(N-N+1).
L>Согласен, что это неинтуитивно, но можно хоть на питоне накорябать тест и проверить асимптоматику.
асимптоматика это то, что считается в голове или на бумаге. Нельзя запустить программу, увидеть там какие-то числа и сделать из этого вывод про сложность алгоритма.
. Ничего, наверное. Нету же там како-то пула страниц.
асимптоматика это то, что считается в голове или на бумаге. Нельзя запустить программу, увидеть там какие-то числа и сделать из этого вывод про сложность алгоритма.
