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

Да, не совсем верно выразился, смысл хотел передать такой, что подходящих кандидатов в итоге совсем не остается.

Да не, остается. Просто если кандидаты будут заранее иметь представление о собеседовании, то они будут меньше тупить и паниковать. И общий уровень прошедших подрастет.

Начните пустой абзац, слева будет знак +. Ткните в него и выберите "код". Появится поле для ввода кода. Или выделите текст, появятся кнопки над ним, выберите <>.

Ваш код, в общем-то правильный, но он немного неоптимален и немного не то, что надо в задаче. Вы создаете новый список, а надо переставить на месте. Ну это надо у интервьювера в начале спросить. Потом, использование "глобальной" переменной в функции - такое себе. Ваш код хоть и пропускает всю логику за счет использования стандартной библиотеки, но он плохо читаем и содержит плохие практики. Ясно, что без этого вам сложно сделать однострочник из стандартных функций, но можно было бы, например, отфильтровать список, а потом сравнить его длину с изначальной и добить нужным количеством нулей.

Я не питонист, т.ч. не уверен 100%, но я бы такое решение принял на "leaning no hire". Естественно, если у вас и остальные решения такого же уровня были бы. По одной этой простой задачке судить рано.

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

Этой функцией массив можно отсортировать за O(N), независимо от размеров чисел. Заполним сначала n вызовами массив исходными числами, а потом за n-1 раз последний минимальный индекс уводим в бесконечность, прибавляя большое число. Так получим индексы всех чисел в порядке возрастания.

Чисто за O(N) работающей сортировки без какого-то ограничения на числа, по-моему, не существует.

Так что оно возможно только для небольших суммарных значений v (пусть сумма всех значений v для любого индекса не превосходит MaxV = O(N) где N - количество операций).

Тогда можно завести MaxV списков. Каждый элемент массива будет в одном двусвязном списке, соответствующим его значению. Сначала все индексы виртуально-лениво сложим в список для начального значения. При выполнении операции удаляем индекс из текущего его списка и кладем в список на +v позиций. Для этого надо для каждого элемента хранить указатель на него в каком-то двусвязном списке. Если список с минимальным значением опустел, переходим к следующему не пустому. Это обработает N операций за O(N + MaxV).

Имеет место предложение, от которого (вскоре) нельзя будет отказаться.

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

Хреновый перевод. Nagging - это "уговаривать", а не "тербовать". Гугл переводчик иногда не совсем точен. Например "Windows 10 will soon start nagging you to do it" переводит правильно в "Windows 10 скоро начнет вас уговаривать это сделать". И на скриншоте никаких требований нет, только назойливое предложение.

12.5 секунд. На 25% медленнее, чем изначальное решение. Выделение этого k все портит. Ну и я не очень понимаю, где вы тут один проход убрали. Раньше у вас было temp[temp > 0] = len(numbers) - i , вместо него стало temp.astype(bool)*k

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

Вообще-то, это лишь уведомление, о том, что есть такая возможность. Мерзкая реклама, но пока никакого принуждения.

Да, не, там не в памяти дело. Вообще, 1000 раз пройтись по массиву размером 80м, это 80 миллиардов операций. В секунду влезает 2-5 миллиардов. Ну вот и получается. что где-то 16-40 секунд оно и должно работать. Операции очень непросытые, ибо там условие, несколько проверок и присваение. Так что ближе к 40с. С векторизацией в 8 раз быстрее из-за векторизации, но в пару раз медленнее из-за дополнительных проходов (надо там отдельно roll сделать, отдельно занулить что-то и отдельно максимумы взять). Так что все более менее сходится.

Я был не прав. Мое изначальное решение на C++, которое шло по массиву задом-наперед, было гораздо медленнее. 50с вместо 10с у numpy. Развернув цикл, оно стало работать чуть быстрее - за 35с.

Действительно, векторизация внутри numpy перевешивает накладные расходы из-за питона.

Ну это такой аргумент, numpy если я не ошибаюсь написан на том же си и так же использует SIMD векторизацию.

Ну если бы в numpy была операция для всех вычислений, то да. Но все, что вы из встроенного используете - это np.roll. А дальше там пересылка индексов через питон. Всякие максимумы, которые не факт что векторизованы.

Не совсем так, я храню индекс числа в оригинальном массиве, в перевёрнутом виде.

Ну так это же и есть количество единиц. Индекс в перевернутом виде - номер строки с конца. Вот это взятое число - это та строка, с которой начинаются единицы. Вот и получается, что номер числа с конца это и есть количество единиц. Ну, может там +1 откуда-то получается везде, но это не принципиально.

Хотелось бы сравнить алгоритм с вашей реализацией по скорости.

Попозже сравню у себя питоновскую реализацию с си++.

Ну вот вы и пришли почти к тому же, что и в статье. Автор остановился на arccos, но в комментах выше уже несколько раз предлагали использовать арктангенс, векторное и скалярные произведения - последнюю формулу.

Да. Это, похоже, лучшее по памяти решение. И если вы будете его сравнивать с линейным решателем, то надо делить время на 10. Ведь решатель-то написан на каком-нибудь с++, а из питона вы лишь вызваете библиотеку. А циклы в питоне, да и вот это перекладывание из одного numpy массива в другой - это медленно. Там еще массив temp будет выделятся на каждй итерации, да и всякие конструкции вроде temp[temp>0] похоже выделяют память под список индексов. А решение на С++ будет вообще без лишних выделений памяти и сильно быстрее.

Я придумал, кажется, весьма интуитивное его объяснение этому решению. Очевидно, что можно хранить прямоугольный битовый dp[][] - не одну строчку, а всю матрицу. По ней восстановление ответа легко сделать - можно взять число j, если dp[i-j][j-1]. Потом можно заметить, что каждый столбец там начинается с нулей, но где-то станет равен 1 и дальше будут только 1. поэтому можно вместо прямоугольной матрицы хранить строку чисел, где помечать, где именно начинаются 1 в каждом столбце. У вас в решении примерно это и хранится, только перевернутое - вы храните, сколько там единиц в столбце. Мой код на С++ где-то в комментах тут хранит само число с номером равным этой строке.

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

И как же этот аргумент, собственно, вычислить?

Где же сломалась? Работает, проверьте исходные данные.

Вы сумму до 1108 исправили? В этом случае ваш код набирает 1106.

И сортировка тут вообще никак не поможет. В [2,3,3,4]->8 вы можете случайно взять 4, что делать нельзя. В [2,1,1] -> 3 вы можете взять 1 и потом опять 1. Тут все еще хуже, ибо тут надо использовать не ту 1, которую вы берете сейчас, а что-то, что вы рассмотрели еще раньше. При этом сами числа могут быть как больше, так и меньше текущего.

Ну вот новый контрпример: [2, 3, 3, 4, 52, 52, 100, 1000, 1000]

Вы опять придумали заплатку, которая никак логически не может влиять на основную проблему. Еще раз, проблема в том, что можно получить ситуацию, что вам надо набрать 8, а у вас остались числа [2, 3, 3, 4]. И тут вы никак не можете понять, что 4 брать нельзя. Или что-то подобное. Вы сделали так, что нельзя брать 100 в этом конкретном примере, чтобы попасть в 108-100=8? Ну вот я добавил пару 1000 в массив и ваша эвристика сломалась.

Пока вы логически не покажете, почему вы исключаете ситуацию, что dp[i-j] требует использовать j в сумме - вы не правы. В общем случае, а не затыкая конкретные контр-примеры.

И я не вижу никакого способа по лишь одной строке dp в конце этого избежать.

Если вам только понять, в какую сторону вращать, то вам достаточно знака угла. И тут даже тригонометрических функций не надо - просто смотрите на знак векторного произведения на плоскости (забейте на нулевые x компоненты векторов). Ведь на плоскости векторное произведение будет равно синусу угла, помноженному на длины векторов.