dmshar

Непонятно, откуда у вас MemoryError. Если исходная выборка размещена в памяти, и ей хватило там места, то на что у вас расходуется память? Вам ведь не надо запоминать все полученные простые числа. Вы берете их по одному и просто выясняете - простое оно или нет.
Вот со временем - да, если у вас действительно большие числа и их к тому-же много - ну тогда переборный алгоритм быстрый не будет. Поэтому ограничение в 1 сек. - это просто какая-то мягко говоря странность, если не указывать, а какие именно числа в вашей последовательности. Для 1000 чисел, всех лежащих в диапазоне от 0 до 1001 - это одно, а для лежащих в диапазоне от 10**12-1000 до 10**12 - это совсем разное время работы.

Если вы не можете САМИ решить тестовую задачу с собеседования - эта позиция вам ЕЩЕ не по зубам. Успокойтесь и начинайте не ответ искать, а разбираться, как решить ПОДОБНЫЕ задачи на следующих собеседованиях. Именно подобные а не конкретно "эту" - потому что на следующих собеседования вероятность попасть на ту-же задачу - почти нулевая.
Недавно отвечал на очень подобный вопрос на этом форуме. Там был вопрос/ответ про алгоритмы, но суть от этого не меняется:
https://qna.habr.com/answer?answer_id=1985526#answ...

Никогда не понимал, что значит "подготовиться к собеседованию". К экзамену понимаю - выучили "от сих до сих", ответили на вопрос, удовлетворили преподавателя, получили свою оценку и гуд бай.
А к собеседованию? Что толку, если вы "нахватаетесь" за 4 дня каких-то отрывочных знаний, даже на что-то правильно (почти случайно) ответите на собеседовании без глубокого понимания. Вы ведь тут не препода обманываете, вы завтра должны решать будете не игрушечно-собеседную, а реальную производственную задачу. Работодатель думает, что вы спец по алгоритмам, а вы просто чего-то там "нахватались" перед собеседованием. Можно догадаться, как закончиться ваш испытательный период. Так зачем тратить время? Лучше его потратить на ИЗУЧЕНИЕ алгоритмов, и на следующем собеседовании не трястись что тебя спросят чего-то, что не успел прочитать. Тогда и работодатель поймет с кем дело имеет, и вам польза будет на будущее.
В общем, собеседование - это не экзамен! К нему специально готовиться - себе во вред. Но на собеседовании надо показывать именно то, что вы собой на самом деле представляете. А если это не устраивает работодателя, то благодарить Бога, что на эту работу вас не взяли.
Впрочем, вменяемый работодатель и не будет заставлять на собеседовании до запятой рассказывать конкретный алгоритм. А вот попросить сравнить, объяснить почему один из них лучше, быстрее, экономичнее и пр. другого очень даже может. Или например попросить вас для конкретной задачи и конкретных данных подобрать наиболее подходящий алгоритм. Вот к пониманию именно таких вещей и надо посвящать время подготовки.

Если нет - легко написать самому. Рекурсия и элементарная теория графов.
Но надо иметь ввиду, что эта задача имеет экспоненциальную сложность. Поэтому даже если напишете - не факт, что при более-менее серьезном графе решите вашу задачу за вразумительное время. (Ну, если ваш граф не на пять-десять вершин). А если граф еще и не ориентированный - то решений вообще по определению бесконечное число.
Поэтому для практических нужд обычно формулируют ограничения, которые позволяют сократить круг рассматриваемых вариантов и решать реальные практические задачи.
Вот тут - элементарное объяснение:
kuimova.ucoz.ru/modul_10-grafy-bazovye_algoritmy.pdf
Вот тут - некий драфт скрипта
https://ru.stackoverflow.com/questions/1046271/алг...
Вот тут - если начнете писать - некоторые полезные обсуждения и идеи
https://coderoad.ru/2723438/Алгоритм-Графа-Для-Пои...
www.fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rul...
www.delphikingdom.com/asp/answer.asp?IDAnswer=56734

Вы не сообщили главного - в сколько параметров описывают ваши данные?
При двух-трех параметрах время вряд-ли будет катастрофически долгим.

Тем не менее.
Попробуйте DBSCAN например. Он не требует обработки всех данных на каждом шаге. Его вычислительная сложность O(NlogN), в худшем случае - O(N**2). Вот тут https://habr.com/ru/post/322034/
его рекомендуют для случая, когда у вас данных порядка 10**6 и даже больше, если можете распараллелить реализацию.

Не очень все понятно, но тем не менее.
Во-первых, функции могут пересечься и тогда, когда обе они растут или обе падают. Просто с разной скоростью. Вы этот случай отбросили намерено?
В-вторых, непонятно, у вас все точки измерений заранее накоплены или вы решаете задачу по мере поступления точек? Если последнее - то тут и думать нечего, просто меряете расстояние между значениями и принимаете решение.
Кстати, не ясно, у вас данные приходят в один момент, или в разные. Во втором случае просто расстоянием не обойдешься - надо искать возможные пересечения функций между точками замера. Это не сложно но тем не менее.
Далее. Если данные все-таки имеются "пакетно накопленные" - то проще всего используя, к примеру ту-же Pandas построить соответствующий ДатаФрейм, в котором точка пересечения (или точкИ пересечения) находятся с помощью одной строчки логического условия. Да и упорядочение точек, если они не одномоментно измерены, в Pandas - тоже стандартная процедура.

В данном контексте выражение log 64 не имеет особого смысла. Сложность алгоритма - это не про то, сколько времени (или памяти) он будет точно занимать, та то, каким образом растет зависимость при n. (См. понятие Асимптотическая сложность алгоритма). Как сказано в других ответах - это весьма примерная оценка, и каково основание логарифма - особой роли не играет. Главное - что она не линейна, не квадратична и пр. а именно "формы графика логарифма". Не больше и не меньше.

Проверка корректности вложенности скобок - классическая задача, которая используется при объяснении на простейшем примере работы. стека. Таким образом - на ваш вопрос "Как решать подобного рода задачи?" - отвечаю, используя стек. Открывающая скобка соответствует операции занесения нового элемента в стек. Закрывающая скобка - извлечение из стека. Если в конце прохода по данным стек пуст - выражение корректно. В противном случае - нет.

Ответил на другом ресурсе. Смотрите.

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

Это самый тривиальный алгоритм. Разберетесь с ним - потом можно будет переходить к всякого рода оптимизациям - начиная с того, что бы объекты для размещения брать от самого большого к самому малому.

Для поиска пропущенных чисел вовсе не обязательно делать последний цикл да еще и в цикле.
Достаточно один раз линейно пройти отсортированный массив от начала и да конца проверяя на каждом шаге выполняется или нет условие arr[i]==arr[i]+1, и если не выполняется - то arr[i] = это ваше число.

Можно и по другому. Если вам известна numpy, то сначала создаете нулевой массив на n позиций, потом каждое число х записываете так, что-бы arr[x]=х. А потом за один проход массива ищите те позиции, которые остались нулевыми.

Можно и еще придумать алгоритмы, которые будут работать точно быстрее, чем брутальный цикл в цикле.