Вторая помена должна поменять местами M[2] и M[3].
Это действительно работает. Поддерживается инвариант, что первые j элементов массива M содержат элементы из начала запрещенного массива V[1..j]. А элементы больше максимального V[1..j] не тронуты (M[i] = i, i > max(V[k] | k <= j)).
На каждой следующей итерации, поскольку V упорядочен, то V[j] >= j и M[v[j]] = j (по инварианту с предыдущей итерации). Поменяв местами M[v[j]] и M[j] мы восстановим инвариант: На индексах < j стоят вычеркнутые числа еще с предыдущей итерации. Вот тут мы в j-ый индекс поместили v[j]. Так же, мы испортили лишь v[j]-ый элемент, а значит все более правые элементы в массиве М все еще равны индексам.
У вас уже есть массив M размера N, значит N не очень большое. Тогда можно в битовом массиве размера N пометить все числа из K, потом все числа из M выводить в ответ, если битовой пометки нет.
Это работает и для неупорядоченного массива K, в отличии от вашего алгоритма. Если вам медленно аллокации, то можно делать пометки прямо в массиве M в каких-нибудь старших битах (например, знак менять у чисел).
Если же и N и K очень большие, то можно использовать хеш-таблицу для пометок.
Если массив V упорядочен, то можно что-то вроде операции слияния из сортировки слияния делать: сравниваем текущее число из M с текущим из V. Если меньшее в V, просто выбрасываем его. Если меньшее в M - выводим его в ответ. Если они равны, выбрасываем оба.
В видео кодеках. Вот пример из vp9. Но тут не очень понятно, может тут немного другое. В браузерах. Вот пример из хрома. Точно применяется во всяких игровых движках. Скорее всего применяется в каких-нибудь базах данных (в географических индексах, например). Наверняка применяется в недрах операционных систем.
Может применятся вообще везде, где у вас что-то хоть немного сложнее перекладывания json-ов и формошлепства.
Главное отличие в том, что белковые нейросети обладают абстрактным мышлением и логикой. И способны за счет этого незнакомые ситуации разруливать. Поэтому ошибки они совершают на порядки реже. Компьютерные нейросети же вообще непонятно что будут делать в незнакомой ситуации.
Да, не совсем верно выразился, смысл хотел передать такой, что подходящих кандидатов в итоге совсем не остается.
Да не, остается. Просто если кандидаты будут заранее иметь представление о собеседовании, то они будут меньше тупить и паниковать. И общий уровень прошедших подрастет.
Вы опечатались? По контексту подходит, что вы считаете, что отсеивается слишком много. Если бы отсеивалось недостаточно много, то наоборот вводились бы какие-то дополнительные секретные практики и каверзные вопросы.
Предложения более хороших вариантов собеседований, которые оценивают профессионализм, применительно к яндексу, я так понимаю, от вас не будет?
Предлагайте! Только помните, что там сотни кандидатов сплошным потоком, надо сделать все более менее объективно, технологии внутри яндекса все проприетарные (так что по какому-нибудь условному реакту не погоняешь кандидата). А еще туда, несмотря на ненавистные всеми алго-собеседования, ломятся куча вайтишников и прочих самозванцев, ведь зарплаты там неплохие, да и строчка в резюме потом дает хороший буст к нанимаемости. И вам очень важно иметь низкое количетсов ложно-положительных результатов, ведь вы нанимаете и из других городов, и платите за переезд и большую зарплату.
Начните пустой абзац, слева будет знак +. Ткните в него и выберите "код". Появится поле для ввода кода. Или выделите текст, появятся кнопки над ним, выберите <>.
Ваш код, в общем-то правильный, но он немного неоптимален и немного не то, что надо в задаче. Вы создаете новый список, а надо переставить на месте. Ну это надо у интервьювера в начале спросить. Потом, использование "глобальной" переменной в функции - такое себе. Ваш код хоть и пропускает всю логику за счет использования стандартной библиотеки, но он плохо читаем и содержит плохие практики. Ясно, что без этого вам сложно сделать однострочник из стандартных функций, но можно было бы, например, отфильтровать список, а потом сравнить его длину с изначальной и добить нужным количеством нулей.
Я не питонист, т.ч. не уверен 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, то можно взять число в этой строке - ведь раз тут единицы начались, то они начались из-за перехода по этому числу, а столбец, куда вы попадете при вычитании этого числа, имел единицы на предыдущей строке, значит дальше вы будете брать только более ранние числа. Поэтому не надо даже перебирать какое число суда прикладывается, а просто взять одно известное.
Вторая помена должна поменять местами M[2] и M[3].
Это действительно работает. Поддерживается инвариант, что первые j элементов массива M содержат элементы из начала запрещенного массива V[1..j]. А элементы больше максимального V[1..j] не тронуты (M[i] = i, i > max(V[k] | k <= j)).
На каждой следующей итерации, поскольку V упорядочен, то V[j] >= j и M[v[j]] = j (по инварианту с предыдущей итерации). Поменяв местами M[v[j]] и M[j] мы восстановим инвариант: На индексах < j стоят вычеркнутые числа еще с предыдущей итерации. Вот тут мы в j-ый индекс поместили v[j]. Так же, мы испортили лишь v[j]-ый элемент, а значит все более правые элементы в массиве М все еще равны индексам.
У вас уже есть массив M размера N, значит N не очень большое. Тогда можно в битовом массиве размера N пометить все числа из K, потом все числа из M выводить в ответ, если битовой пометки нет.
Это работает и для неупорядоченного массива K, в отличии от вашего алгоритма. Если вам медленно аллокации, то можно делать пометки прямо в массиве M в каких-нибудь старших битах (например, знак менять у чисел).
Если же и N и K очень большие, то можно использовать хеш-таблицу для пометок.
Если массив V упорядочен, то можно что-то вроде операции слияния из сортировки слияния делать: сравниваем текущее число из M с текущим из V. Если меньшее в V, просто выбрасываем его. Если меньшее в M - выводим его в ответ. Если они равны, выбрасываем оба.
В видео кодеках. Вот пример из vp9. Но тут не очень понятно, может тут немного другое. В браузерах. Вот пример из хрома. Точно применяется во всяких игровых движках. Скорее всего применяется в каких-нибудь базах данных (в географических индексах, например). Наверняка применяется в недрах операционных систем.
Может применятся вообще везде, где у вас что-то хоть немного сложнее перекладывания json-ов и формошлепства.
В автопилотных такси нет водителя.
Главное отличие в том, что белковые нейросети обладают абстрактным мышлением и логикой. И способны за счет этого незнакомые ситуации разруливать. Поэтому ошибки они совершают на порядки реже. Компьютерные нейросети же вообще непонятно что будут делать в незнакомой ситуации.
Да не, остается. Просто если кандидаты будут заранее иметь представление о собеседовании, то они будут меньше тупить и паниковать. И общий уровень прошедших подрастет.
Чтобы снижать ложное-отрицательные результаты.
Вы опечатались? По контексту подходит, что вы считаете, что отсеивается слишком много. Если бы отсеивалось недостаточно много, то наоборот вводились бы какие-то дополнительные секретные практики и каверзные вопросы.
Предложения более хороших вариантов собеседований, которые оценивают профессионализм, применительно к яндексу, я так понимаю, от вас не будет?
Предлагайте! Только помните, что там сотни кандидатов сплошным потоком, надо сделать все более менее объективно, технологии внутри яндекса все проприетарные (так что по какому-нибудь условному реакту не погоняешь кандидата). А еще туда, несмотря на ненавистные всеми алго-собеседования, ломятся куча вайтишников и прочих самозванцев, ведь зарплаты там неплохие, да и строчка в резюме потом дает хороший буст к нанимаемости. И вам очень важно иметь низкое количетсов ложно-положительных результатов, ведь вы нанимаете и из других городов, и платите за переезд и большую зарплату.
Начните пустой абзац, слева будет знак +. Ткните в него и выберите "код". Появится поле для ввода кода. Или выделите текст, появятся кнопки над ним, выберите <>.
Ваш код, в общем-то правильный, но он немного неоптимален и немного не то, что надо в задаче. Вы создаете новый список, а надо переставить на месте. Ну это надо у интервьювера в начале спросить. Потом, использование "глобальной" переменной в функции - такое себе. Ваш код хоть и пропускает всю логику за счет использования стандартной библиотеки, но он плохо читаем и содержит плохие практики. Ясно, что без этого вам сложно сделать однострочник из стандартных функций, но можно было бы, например, отфильтровать список, а потом сравнить его длину с изначальной и добить нужным количеством нулей.
Я не питонист, т.ч. не уверен 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 была операция для всех вычислений, то да. Но все, что вы из встроенного используете - это np.roll. А дальше там пересылка индексов через питон. Всякие максимумы, которые не факт что векторизованы.
Ну так это же и есть количество единиц. Индекс в перевернутом виде - номер строки с конца. Вот это взятое число - это та строка, с которой начинаются единицы. Вот и получается, что номер числа с конца это и есть количество единиц. Ну, может там +1 откуда-то получается везде, но это не принципиально.
Попозже сравню у себя питоновскую реализацию с си++.
Ну вот вы и пришли почти к тому же, что и в статье. Автор остановился на arccos, но в комментах выше уже несколько раз предлагали использовать арктангенс, векторное и скалярные произведения - последнюю формулу.
Да. Это, похоже, лучшее по памяти решение. И если вы будете его сравнивать с линейным решателем, то надо делить время на 10. Ведь решатель-то написан на каком-нибудь с++, а из питона вы лишь вызваете библиотеку. А циклы в питоне, да и вот это перекладывание из одного numpy массива в другой - это медленно. Там еще массив temp будет выделятся на каждй итерации, да и всякие конструкции вроде temp[temp>0] похоже выделяют память под список индексов. А решение на С++ будет вообще без лишних выделений памяти и сильно быстрее.
Я придумал, кажется, весьма интуитивное его объяснение этому решению. Очевидно, что можно хранить прямоугольный битовый dp[][] - не одну строчку, а всю матрицу. По ней восстановление ответа легко сделать - можно взять число j, если dp[i-j][j-1]. Потом можно заметить, что каждый столбец там начинается с нулей, но где-то станет равен 1 и дальше будут только 1. поэтому можно вместо прямоугольной матрицы хранить строку чисел, где помечать, где именно начинаются 1 в каждом столбце. У вас в решении примерно это и хранится, только перевернутое - вы храните, сколько там единиц в столбце. Мой код на С++ где-то в комментах тут хранит само число с номером равным этой строке.
Восстановление ответа работает так: если в каком-то столбце где-то начались 1, то можно взять число в этой строке - ведь раз тут единицы начались, то они начались из-за перехода по этому числу, а столбец, куда вы попадете при вычитании этого числа, имел единицы на предыдущей строке, значит дальше вы будете брать только более ранние числа. Поэтому не надо даже перебирать какое число суда прикладывается, а просто взять одно известное.