🖥 Задача. Подготовка экспедиции на Марс

N кандидатов готовятся к двум космическим экспедициям на Марс. Поскольку экспедиции будут продолжаться несколько лет, а их участники окажутся в замкнутом пространстве небольшого объёма, то важное значение приобретает психологическая совместимость членов экипажа.

Путём тестирования были установлены пары кандидатов, присутствие которых в одной и той же экспедиции было бы нежелательным. Результаты тестирования отражены в таблице размера NxN. Если на пересечении -той строки и $j$-го столбца таблицы находится знак «+», то участие -го и $j$-го кандидатов в одной экспедиции нежелательно.

Составьте программу, разделяющую кандидатов на две группы для участия в экспедициях. Если такое разделение невозможно, программа должна выводить сообщение «No solution». В противном случае, программа должна выводить номера кандидатов, принадлежащих первой группе. Первой группой мы будем считать группу, в которой меньше кандидатов.

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

Программа должна считывать со стандартного потока ввода количество кандидатов и матрицу размера NxN. Например, для входных данных

8
- - + - - - - -
- - - + - - - -
+ - - - - - - +
- + - - - + - -
- - - - - - - -
- - - + - - - -
- - - - - - - +
- - + - - - + -

программа должна выводить

1 2 6 8


👉 Пишите ваше решение в комментариях👇

@python_job_interview

🖥 Задача реализовать алгоритм интерполяционного поиска

Интерполяционный поиск — это еще один алгоритм «разделяй и властвуй», аналогичный бинарному поиску. В отличие от бинарного поиска, он не всегда начинает поиск с середины. Интерполяционный поиск вычисляет вероятную позицию искомого элемента по формуле:

index = low + [(val-lys[low])*(high-low) / (lys[high]-lys[low])]
В этой формуле используются следующие переменные:

lys — наш входной массив.
val — искомый элемент.
index — вероятный индекс искомого элемента. Он вычисляется как более высокое значение, когда значение val ближе по значению к элементу в конце массива (lys[high]), и более низкое, когда значение val ближе по значению к элементу в начале массива (lys[low]).
low — начальный индекс массива.
high — последний индекс массива.
Алгоритм осуществляет поиск путем вычисления значения индекса:

Если значение найдено (когда lys[index] == val), возвращается индекс.
Если значение val меньше lys[index], то значение индекса пересчитывается по формуле для левого подмассива.
Если значение val больше lys[index], то значение индекса пересчитывается по формуле для правого подмассива.


Решение:

def InterpolationSearch(lys, val):
low = 0
high = (len(lys) - 1)
while low <= high and val >= lys[low] and val <= lys[high]:
index = low + int(((float(high - low) / ( lys[high] - lys[low])) * ( val - lys[low])))
if lys[index] == val:
return index
if lys[index] < val:
low = index + 1;
else:
high = index - 1;
return -1
Если мы используем функцию для вычисления:

>>> print(InterpolationSearch([1,2,3,4,5,6,7,8], 6))
Наши начальные значения будут следующими:

val = 6,

low = 0,

high = 7,

lys[low] = 1,

lys[high] = 8,

index = 0 + [(6-1)*(7-0)/(8-1)] = 5

Поскольку lys[5] равно 6, что является искомым значением, мы прекращаем выполнение и возвращаем результат:

5

Если у нас большое количество элементов и наш индекс не может быть вычислен за одну итерацию, то мы продолжаем пересчитывать значение индекса после корректировки значений high и low.

Временная сложность интерполяционного поиска равна O(log log n), когда значения распределены равномерно. Если значения распределены неравномерно, временная сложность для наихудшего случая равна O(n) — так же, как и для линейного поиска.

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

👉 Пишите ваше решение в комментариях👇


@python_job_interview

🖥 Auto-resume-raising – программа для автоматического подъема резюме на HeadHunter каждые 4 часа

Альтернатива платной услуге Продвижение.LITE от HeadHunter

🖥 Github: https://github.com/sergo-code/hh-ru-auto-resume-raising

#github #python

@python_job_interview

🖥 Задача реализовать экспоненциального поиска.

Экспоненциальный поиск — это еще один алгоритм поиска, который может быть достаточно легко реализован на Python, по сравнению с jump search и поиском Фибоначчи, которые немного сложны. Он также известен под названиями galloping search, doubling search и Struzik search.

Экспоненциальный поиск зависит от бинарного поиска для выполнения окончательного сравнения значений. Алгоритм работает следующим образом:

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

Решение

Реализация алгоритма экспоненциального поиска на Python:

def ExponentialSearch(lys, val):
if lys[0] == val:
return 0
index = 1
while index < len(lys) and lys[index] <= val:
index = index * 2
return BinarySearch( lys[:min(index, len(lys))], val)

Используем функцию, чтобы найти значение:

>>> print(ExponentialSearch([1,2,3,4,5,6,7,8],3))

Рассмотрим работу алгоритма пошагово.

Проверяем, соответствует ли первый элемент списка искомому значению: поскольку lys[0] равен 1, а мы ищем 3, мы устанавливаем индекс равным 1 и двигаемся дальше.

Перебираем все элементы в списке, и пока элемент с текущим индексом меньше или равен нашему значению, умножаем значение индекса на 2:
index = 1, lys[1] равно 2, что меньше 3, поэтому значение index умножается на 2 и переменной index присваивается значение 2.
index = 2, lys[2] равно 3, что равно 3, поэтому значение index умножается на 2 и переменной index присваивается значение 4.
index = 4, lys[4] равно 5, что больше 3. Условие выполнения цикла больше не соблюдается и цикл завершает свою работу.
Затем выполняется двоичный поиск в полученном диапазоне (срезе) lys[:4]. В Python это означает, что подсписок будет содержать все элементы до 4-го элемента, поэтому мы фактически вызываем функцию следующим образом:

>>> BinarySearch([1,2,3,4], 3)
Функция вернет следующий результат:

2

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

Экспоненциальный поиск выполняется за время O(log i), где i — индекс искомого элемента. В худшем случае временная сложность равна O(log n), когда искомый элемент — это последний элемент в массиве (n — это длина массива).

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

👉 Пишите ваше решение в комментариях👇

@python_job_interview

🖥 Задача с собеседования | Уровень: #Easy

Условие:

Создать функцию которая принимает число и возвращает "Even" для чётных чисел и "Odd" для нечётных.

Пример:

2 → "Even"
1 → "Odd"
-46 → "Even"
71 → "Odd"
0 → "Even"
-123 → "Odd"


👉 Пишите ваше решение в комментариях👇


@python_job_interview

🖥 Задача реализовать алгоритм Jump Search

Jump Search похож на бинарный поиск тем, что он также работает с отсортированным массивом и использует аналогичный подход «разделяй и властвуй» для поиска по нему.

Его можно классифицировать как усовершенствованный алгоритм линейного поиска, поскольку он зависит от линейного поиска для выполнения фактического сравнения при поиске значения.

В заданном отсортированном массиве мы ищем не постепенно по элементам массива, а скачкообразно. Если у нас есть размер прыжка, то наш алгоритм будет рассматривать элементы входного списка lys в следующем порядке: lys[0], lys[0+jump], lys[0+2jump], lys[0+3jump] и так далее.

Решение
С каждым прыжком мы сохраняем предыдущее значение и его индекс. Когда мы находим множество значений (блок), где lys[i] < element < lys[i + jump], мы выполняем линейный поиск с lys[i] в качестве самого левого элемента и lys[i + jump] в качестве самого правого элемента в нашем множестве:

import math
def JumpSearch (lys, val):
length = len(lys)
jump = int(math.sqrt(length))
left, right = 0, 0
while left < length and lys[left] <= val:
right = min(length - 1, left + jump)
if lys[left] <= val and lys[right] >= val:
break
left += jump;
if left >= length or lys[left] > val:
return -1
right = min(length - 1, right)
i = left
while i <= right and lys[i] <= val:
if lys[i] == val:
return i
i += 1
return -1
Поскольку это сложный алгоритм, давайте рассмотрим пошаговое вычисление для следующего примера:

>>> print(JumpSearch([1,2,3,4,5,6,7,8,9], 5))

Jump search сначала определит размер прыжка путем вычисления math.sqrt(len(lys)). Поскольку у нас 9 элементов, размер прыжка будет √9 = 3.
Далее мы вычисляем значение переменной right.

Оно рассчитывается как минимум из двух значений: длины массива минус 1 и значения left + jump, которое в нашем случае будет 0 + 3 = 3. Поскольку 3 меньше 8, мы используем 3 в качестве значения переменной right.
Теперь проверим, находится ли наш искомый элемент 5 между lys[0] и lys[3]. Поскольку 5 не находится между 1 и 4, мы идем дальше.
Затем мы снова делаем расчеты и проверяем, находится ли наш искомый элемент между lys[3] и lys[6], где 6 — это 3 + jump. Поскольку 5 находится между 4 и 7, мы выполняем линейный поиск по элементам между lys[3] и lys[6] и возвращаем индекс нашего элемента:
4

Временная сложность jump search равна O(√n), где √n — размер прыжка, а n — длина списка. Таким образом, с точки зрения эффективности jump search находится между алгоритмами линейного и бинарного поиска.

Единственное наиболее важное преимущество jump search по сравнению с бинарным поиском заключается в том, что он не опирается на оператор деления (/).

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

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

Чтобы ускорить jump search, мы могли бы использовать бинарный поиск или какой-нибудь другой алгоритм для поиска в блоке вместо использования гораздо более медленного линейного поиска.

👉 Пишите ваше решение в комментариях👇


@python_job_interview

😎 Подборка сайтов для поиска работы по всему миру

🚀Франция
https://candidat.pole-emploi.fr/espacepersonnel/
https://www.indeed.fr
https://www.monster.fr
🚀Германия
https://stellenmarkt.sueddeutsche.de/
https://www.arbeitsagentur.de/
https://www.monster.de/
https://www.horizontjobs.de/
🚀Италия
https://www.careerjet.it/
http://www.monster.it/
https://it.indeed.com/
https://www.infojobs.it/
🚀Испания
https://www.infojobs.net/
https://www.monster.es/
https://www.infoempleo.com/
🚀США
www.indeed.com
https://www.careerbuilder.com/
http://craiglist.com/
www.monster.com
https://www.vacancyopen.com/
🚀Чехия
https://www.jobs.cz/
https://www.profesia.cz/
https://www.prace.cz/
https://www.dobraprace.cz/
www.dzob.cz
🚀Польша
https://www.pracuj.pl/
https://www.jobs.pl
https://gazetapraca.pl/
www.gowork.pl
🚀Великобритания
https://www.indeed.co.uk
https://www.monster.co.uk/advertise-a-job/
https://www.cv-library.co.uk/
🚀Швеция
https://www.monster.se/
https://www.jobbsafari.se/
https://www.metrojobb.se/
🚀Австралия
http://jobsearch.gov.au
www.seek.com.au
www.careerone.com.au
🚀Венгрия
https://nofluffjobs.com/hu/
🚀Канада
www.workopolis.com
http://www.canadajobs.com
http://ca.indeed.com
http://www.monster.ca/
🚀Латвия
https://www.cv.lv/lv/
🚀Турция
http://www.yenibiris.com/
http://www.kariyer.net/
https://turkey.xpatjobs.com/

#vacancy #job
@python_job_interview

🖥 Практическая задача. Разработать функции для работы с приоритетной очередью

Запрограммировать функции для работы с приоритетной очередью. Очередь запросов формируется согласно приоритету, снятие выполняется подряд, начиная с младших адресов ( то есть с начала очереди).

Очередь должна представлять из себя массив, в котором должен выполняться сдвиг после каждого чтения и сдвиг — после достижения границы памяти, которая выделена для очереди. Приоритет: минимальное значение числового параметра, при совпадении параметров — LIFO.

Пишите свое решение в комментариях👇

@python_job_interview

🖥 Практическая задача.

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

Рекомендую ограничить длину вводимого пароля до 4-х символов, больше не надо, иначе программа долго будет работать. Еще лучше, если на этапе разработки программы, длина пароля будет 2 — 3 символа. Кроме того, задайте в программе множество допустимых символов пароля. Например, в пароле могут использоваться только цифры и/или буквы, это заметно поможет ускорить процесс отладки программы-брутфорса.

Пишите свое решение в комментариях👇

@python_job_interview

🖥 Задача. Количество изолированных островов

Условие задачи: дан двумерный массив, содержащий 0 (острова) и 1(воду).

Остров - множество нулей, соединенных в четырех направлениях (справа, снизу, слева, сверху), изолированый остров - множество нулей, окруженных со всех сторон единицами.

Надо посчитать количество изолированных островов.

Пример:

Ввод:

grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]

Вывод: 2
Объяснение:

Ввод: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Вывод: 1

Решение

Пишите свое решение в комментариях👇

@python_job_interview

🖥 Задача. Как сделать поиск подстроки в строке через регулярные выражения python?

Проверить строки на шаблон можно с помощью модуля re

# re.findall() ищет все вхождения в строке
text = "He was carefully disguised but captured quickly by police."
re.findall(r"\w+ly\b", text) # ['carefully', 'quickly']

# re.match() позволяет объединять в групыы
m = re.match(r"(\d+)\.(\d+)", "24.1632")
m.groups() # ('24', '1632')

Пишите свое решение в комментариях👇

@python_job_interview