Здравствуйте, cppguard, Вы писали:
S>>В ml используется для линеаризации, например. Чем не вариант? C>Речь шла о том, как расчитать косинус без доступа к math.h. Для этих целей TE не подходит.
А почему, мы же можем аппроксимировать для любой точки?
Здравствуйте, Ip Man, Вы писали:
IM>Это отличная задачка с собеседования.
Это неплохая задачка для кандидата в сортировщики гномиков, но нелепая задача для инженера, потому что реализация алгоритма предполагает, что данные целиком находятся в памяти, а чтобы их туда положить, нужно... сюрприз-сюрприз! — N*M операций. То есть уже на стадии формирования структуры мы можем посчитать нужную нам информацию. Но даже если мы этого не делаем, то даже простой перебор N*M никак не отразится на работе всей программы, так как подготовка данных + вычисления всё равно будут иметь общую сложность O(N*M). А вот если двоичный поиск будет реализовывать совсем юный сортировщик гномиков, который не знает, как правильно вычислять границу, чтобы не было переполнения, или как правильно формировать условие выхода из цикла (типичная ошибка в реализации BS), то программа будет весьма падучая.
Здравствуйте, Sharov, Вы писали:
S>А почему, мы же можем аппроксимировать для любой точки?
Потому что у нас не аппроксимация, а разложение в бесконечный ряд. Это первая проблема — мы не можем бесконечно вычислять члены этого ряда. Для аппроксимирующей функции мы всегда знаем погрешность. Для ряда Тейлора мы ограничиваем последовательность первыми N членами и можем посчитать погрешность как сумму оставшихся членов. Но не факт, что этот ряд будет сходиться, а значит суммы вообще может не существовать. Вторая проблема — нужно знать значение самой функции в точке разложения. Допустим, что для sin/cos это будет чередующиеся нули и единицы, но тогда чем дальше мы от точки разложения вычисляем значение исходной функции, тем больше растёт ошибка. Третья проблема — ограничивая члены ряда, мы получаем полином k-ой степени, а значит у нас может быть не более k-1 экстремумов, но изначальная функция может быть гораздо сложнее, а значит мы не только получаем непонятную прогрешность и но и вообще рискуем получить не то, что планировали при вычислениях. Например, тот же sin/cos имеют бесконечное число локальных экстремумов, а значит для использования ряда Тейлора нужно учитывать цикличность и приводить аргумент к виду [0; pi/2] (если sin) или [-pi/2; pi/2] (если cos). Четвёртая проблема — ручные аппроксимации функций нам нужны в системах на кристалле, которые не умеют конвееризацию и out-of-order execution, поэтому часто аппроксимации не только расчитываются исходя из погрешности, но и исходя из того, какие операции выполняются быстрее на целевой системе.
Здравствуйте, cppguard, Вы писали:
S>>Ведь тогда на шагах со второго по последний нам придется делать одинаковые поиски со сложностью O(log(M-1)). Разве нет?
C>Можно и так. В любом случае, N+logM не получить.
Тут как раз получается один log(M) и дополнительно N сравнений.
Здравствуйте, landerhigh, Вы писали:
L>Тут как раз получается один log(M) и дополнительно N сравнений.
Мы уже начинаем говорить о тонкостях реализации. Если на очередном шаге искать K в промежутке [0; K), то будет одно количество шагов, если в [0; K], то другое, но тогда граничные условия будут разными. Сложность алгоритма из-за этого не меняется.
Здравствуйте, cppguard, Вы писали:
L>>Тут сразу бросается в глаза, что L>>O(1)+O(2) = O(1) C>Чувак, ты смешал в кучу коней и людей. Почитай КМП на тему того, как правильно считать сложность алгоритмов.
Я читал Кнута. Правда, все забыл
C>По твоей логике insertion sort тоже должен иметь сложность O(N), потому что там O(N) + O(N-1) + ... + O(N-N+1).
Не надо за меня додумывать.
В принципе, очевидно думаю, что можно показать, что в "хорошем" случае мы получим сложность, близкую к O(M+log(N)).
"Плохой" случай вынуждает нас для каждого датчика вести бинарный поиск.
Но вообще, даже в худшем случае получается не совсем M(log N). Из-за того, что на каждом шаге N уменшьается на 1, там появляется некий множитель в районе 0.8 (посчитал на коленке в экселе), что наводит на мысли, что можно что-то хитрое придумать, чтобы "плохой" случай оптимизировать.
L>>Согласен, что это неинтуитивно, но можно хоть на питоне накорябать тест и проверить асимптоматику. C> асимптоматика это то, что считается в голове или на бумаге. Нельзя запустить программу, увидеть там какие-то числа и сделать из этого вывод про сложность алгоритма.
Здравствуйте, Sharov, Вы писали:
S>По этой логике вкалывать вообще не надо-- работай вполсилы, без особого погружения, прыгай через 2 года на другую работу и так по кругу.
Так многие и делают, чтобы максимизировать доход. По крайней мере, пока не запрыгнут в топовую компанию.
А зачем, собственно, работать в полную силу в компании, которая недоплачивает и с которой не планируешь растить детей долгую карьеру?
Здравствуйте, landerhigh, Вы писали:
L>В продакшене, когда речь идет о датчиках, используется КА, который срабатывает, как только один датчик меняет состояние. L>Если нужно анализировать данные в офлайне, уже когда-нибудь потом, то на сложность по большому счету пофиг.
я собеседовался в одну уважаему секюрети компанию
у них у клиента за сутки несколько тыс терабайт логов
и они на Python их парсят и ищут всяике события
я спросил может ищут на C а потом генерируют отчет на Python
нет говорят мы в облака загружаем логи а там мощи до дури так что на Python все
Здравствуйте, Ip Man, Вы писали:
IM>Ну вот это и скажешь на интервью в каком-нибудь гугле, когда такую задачу зададут
Зачем? В Риме поступай по-римски. Но если заниматься наймом в небольшой компании, где вклад каждого сотрудника важен, то точно уж не стоит просить сортировать гномиков.
Здравствуйте, sergey2b, Вы писали:
S>я спросил может ищут на C а потом генерируют отчет на Python S>нет говорят мы в облака загружаем логи а там мощи до дури так что на Python все
Это пока облака не начнут заряжать за перерасход электричества в датацентрах.
То есть, примерно до послезавтра.
Здравствуйте, cppguard, Вы писали:
C>Я задачу понял так: даны N последовательностей, каждая состоит из M значений. В каждый последовательности сперва идут нули, потом в какой-то момент начинают идти единицы. Нужно определить номер последовательности, в которой индекс первой единицы — наименьший. Если всё верно, то я бы очень хотел посмотреть на алгоритм O(N+log(M)) для этой задачи.
В общем, я не математик, такие вещи сразу не вижу.
Там есть очевидный, как мне кажется, O(M+N) алгоритм, и O(N*log(M))
Фишка в том, что при определенных значениях M и N первый алгоритм выгоднее. Можно даже посчитать границы, когда какой лучше использовать.
Но, если есть предположения, что "плохие" случаи вроде "ступеньки" маловероятны, то можно, наверное, совместить первый и второй подходы, получив нечто, что может быть не совсем O(N+log(M)), но что-то между O(N+log(M)) и O(N*log(M))
Здравствуйте, Pzz, Вы писали:
Pzz>Надо сказать, получается это у Яндекса весьма паршиво. Яндекс любит потоки по магистралям "ускорять", заманивая часть водителей на дублер. А потом, в том месте, где дублер назад вливается в основную дорогу, образуется пробка. Которую Яндекс и организовал — все же по евонному навигатору едут.
А ещё любит находить маршруты, которые на 1 минуту короче при поездке более 5 часов.
Либо вообще предлагать маршрут, который короче на 7 минут, но если его выбираешь, то время увеличивается на 10 минут. Если попросить построить назад, то вернётся прежнее время.
Здравствуйте, alzt, Вы писали:
A>А ещё любит находить маршруты, которые на 1 минуту короче при поездке более 5 часов. A>Либо вообще предлагать маршрут, который короче на 7 минут, но если его выбираешь, то время увеличивается на 10 минут. Если попросить построить назад, то вернётся прежнее время.
Я никогда не ведусь на его предложения сократить маршрут на две минуты путем заезда в задний двор местного сельского туалета. Но это в тех местах, где я и без него, в принципе, ориентируюсь. А вот в совсем незнакомое место ехать — приходится доверять бездушной железяке.
Здравствуйте, T4r4sB, Вы писали:
TB>>>прыгнул с парашюта CC>>... в результате чего на данный момент существует только в виде записей в DB
TB>И никто не может доказать, что он есть. Есть только стариковские байки, которым никто не верит.
Здравствуйте, mtnl, Вы писали:
M>Вполне серийный человек, обычно у таких образование — радиофизика или мехмат нормального вуза — дальше как опция пару лет в оборонном НИИ близко к железу — дальше работа в ЦРТ, конторах, делающих DPI или ныне ушедних Нокиа или Интеле, Хуавей их тоже активно зарплатами из регионов к себе перетаскивает. Я прямо несколько таких знаю.
Работал и в ЦРТ, и в НИИ, и на многие упомянутые вопросы ответил бы так себе просто за давностью лет
У условных "радиофизиков" и "мехматовцев" очень часто свои слабые стороны есть.
Здравствуйте, Qt-Coder, Вы писали:
QC>Перепост с пикабу.
Типичный заказной пост. Что вполне ожидаемо от этой помойки, пропагандирующей нацизм и феминизм.
В реале есть статистика, согласно которой в России лидируют Java, .NET и Go разработчики, а C++-ники плетутся в хвосте, наряду с PHP'шниками и 1C'никами.
А Яндекс давно печально известен своими зарплатами ниже рынка.
Может, мы обидели кого-то зря, cбросив пару сотен мегатонн.
А теперь горит и плавится земля — там, где был когда-то Пентагон.
JR>Либо это какая-то хитрая реклама Яндекс школы, либо человек невероятно уникальный, фактически единственный в стране, а может и мире. Поскольку большой стек практических знаний С/С++, знание архитектур x86/ARM, GPU. FPGA, по мимо этого глубокое знание работы виртуальной памяти, менеджера памяти, многопоточки и пр. Потом отдельно математика, мат.анализ университетского курса, следом машинное обучение, диплернинг и автору всего 33 года (согласно его комментариям на пикабу).
Ну, на конкретный момент времени этого в памяти всего одновременно нет.
Но опыт жеж не пропьешь.
Если специально готовиться к такого рода интервью, то вполне можно все освежить и проблем-то не будет.
Я вот еще в кодах восьмеричных писал, операционную систему писал, на ассемблере писал для нескольких архитектур — так мне пофиг, какая архитекутура.
Вы мне дайте документацию, я через пару дней вам нужную программу наваяю.
При том, что я уже более 30 лет не занимался специально писанием подобных программ.
Собственно, и с другими вопросами аналогично.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
асимптоматика это то, что считается в голове или на бумаге. Нельзя запустить программу, увидеть там какие-то числа и сделать из этого вывод про сложность алгоритма.
