Однопроходные алгоритмы на python. Часто нужны на собеседованиях
ฝัง
- เผยแพร่เมื่อ 12 ก.ย. 2024
- Разбираем задачи:
Поиск второго максимума
Удаление дубликатов
Всем спасибо за просмотр! Ставьте 👍 если Вам понравилось видео!
Нажимайте 🔔 чтобы видеть наши новые выпуски. Благодарность за подписку
🔔ПОДПИСЫВАЙТЕСЬ:🔔
🔗Вконтакте: CaptPronin
🔗Facebook: / proninc
#ДжунНаПрокачку
в первом задании в цикле while нужен or вместо and
while max1==max2 or index < len(array) :
Добавлю пожалуй и свой вариант первой задачи, раз уже написала.
find_second_max_value.py
from typing import List, Optional
def find_second_max(array: List[int]) -> Optional[int]:
if(len(array) < 2):
return None
max_1 = array[0]
max_2 = None
for item in array[1:]:
if(item == max_1):
continue
if(item > max_1):
max_2 = max_1
max_1 = item
elif((max_2 is None) or
(item > max_2)):
max_2 = item
return max_2
----------------------------------------------------------------------------------------------------
test_secondmax.py
import pytest
from find_second_max_value import find_second_max
@pytest.mark.parametrize('value, expected', [
( [], None),
( [22], None),
( [0, 2], 0),
( [-10, 2], -10),
( [2, 2, 2], None),
( [2, 2, 2, 1], 1)
])
def test_second_max(value, expected):
assert find_second_max(value) == expected
Насчет равенства двух первых элементов.
Я бы добавил следующее условие в начале: if len(set(arr)) < 2: return None
Или уже в основном цикле проверял бы равенство максимумов (Если они равны, то нам неважно какой мы элемент встретили, меньший или больший, мы в любом случае должны заменить 2 максимум): if max_1 == max_2: max_2 = arr[i].
Ну а вообще, в крайнем случае, так как асимптотика однопроходного алгоритма O(n), то можно считерить и 2 раза пройти массив, потому что O(2*n) = O(n)
Вторую программу можно через хэш-таблицу сделать со счётчиками вхождений и в итоге вывести те, которые равны 1
P.S. Получилось как-то так, но здесь в 2 прохода массива, ещё не придумал как в один проход сделать (если это возможно)
def uniq_numbers(array):
numbers_count = {}
# собираем хэш-таблицу элементов и количества вхождений каждого элемента
for num in array:
if num
Думаю самое простое решение первой задачи
def max2a(arr):
if len(arr) < 2:
return None
max1, max2 = arr[0], None
for el in arr[1:]:
if el > max1:
max2, max1 = max1, el
elif el < max1:
max2 = el
return max2
👍 спасибо за крупный шрифт 😉
Учитываю пожелания)
@@AndyPronin а в чем прикол, я оставил три комментария, а тут только одно?
@@vadimvadim1662 ютуб фильтр. Я не знаю, как он работает. Но некоторые комментарии просто исчезают. Может быть слова использованы неподходящие с точки зрения ютуба. Или ссылка была.
Начал просмотр и сразу вопрос от ленивого меня . Вроде должно работать max1, max2 = array[:2].
PS. Досмотрел. Первый алгоритм у вас имеет два цикла. Достаточно одного. Выделить два первых элемента, потом пройтись по всему списку. В конце, max_2 if max_1>max_2 else None.
Второй, возможно, стоит решить через словарь, где ключи - элементы списка больше 5, значения - количество, посчитанное первым циклом. Вторым циклом выбираем ключи со значением == 1.
По задачке поиска второго максимума можно было все проще сделать: ввести динамический индекс с нуля и сдвигать его, пока элементы равны, а потом вся та же остальная логика:
try:
index = 0
while array[index] == array[index + 1]:
index += 1
if array[index] > array[index + 1]:
max_1, max_2 = array[index], array[index + 1]
else:
max_1, max_2 = array[index + 1], array[index]
except IndexError:
return None
а далее продолжаем поиск с index+2
def get_unique(numbers):
unique_numbers= {}
for key in numbers:
unique_numbers[key] = unique_numbers.get(key, 0) + 1
return list(filter(lambda x: ((unique_numbers[x] < 2) and (x > 5)), unique_numbers))
По второй задаче:
def some_function(array):
return [num for num in array if num > 5 and array.count(num) == 1]
работает, но по сути каждый вызов .count(num) будет отрабатывать O(n), т.е. проходиться по всему массиву. Т.е. алгоритм уже не однопроходной
Не знаю куда делись два других комментария, попробую снова)
Идея классная, но реализация немного не поехала. Джуну нужно подучить синтаксис, чтобы быть с вами на одной волне.
И лично мне нравится формат, если бы Ян видел задачу впервые. Это позволит посмотреть, как человек имеющий опыт думает и поставив на паузу порешать самому, если решил, то можно себя похвалить)
Отличная мысль
34:05 на 12 строке `elif max_2 < num != max_1 or num < max_1 == max_2`, 8-16 строки убираем, в for движемся от array[2:]
Логически то всё конечно правильно, но решение очень усложнённое и запутанное.
Я решил по другому, все ваши краевые случаи проходит.
Если кому интересно,
def second_max(a: list[int]) -> typing.Optional[int]:
max1 = max2 = -math.inf
for x in a:
if x == max1:
continue
elif x > max1:
max2 = max1
max1 = x
elif x > max2:
max2 = x
return max2 if max2 > -math.inf else None
Либо, еще до того как они совсем усложнили логику с if-ами, можно было просто привести массив к set(чтобы убрать дубликаты и проблему с [100, 100, 99]), сложность осталась бы O(n). Но ваше решение намного красивее в любом случае.
@@bfdhtfyjhjj, set это тоже цикл.
А что ваш код вернёт на [100,100] ? По идее тоже должно None вернуть, а у вас 100 вернёт….
@@alexeyzamesov2581 почему? Вернёт None, так как до проверки x > max2 даже не дойдем
@@nda861 согласен, отработает Проверка где continue
первое
def second_largest(array):
first = second = -inf
for num in array:
if num > first:
first, second = num, first
elif num == first:
continue
elif num > second:
second = num
return second if second != -inf else None
второе
def get_unique(array):
counter = Counter(array)
return [num for num in counter if counter[num] == 1 and num > 5]
Насчет второй, то можно и без класса Counter и в одну строчку.
return [x for x in array if array.count(x) == 1 and x > 5]
@@FyftyTony Counter вызывается один раз, поэтому сложность такого алгоритма составляет O(n), а вот array.count будет каждую итерацию проходить весь лист, и сложность возрастёт до O(n**2)
Здравствуйте!
А сколько времени даётся на решение однопроходных алгоритмов(понятное дело, вопрос максимально некорректный). Нужно сходу решить или может минут 30 каких))))))
Обычно 40-60 минут на 2 задачки.
@@AndyPronin, спасибо большое!
def secondmax(array):
max1 = None
max2 = None
for value in array:
if not max1:
max1 = value
elif value > max1:
max2 = max1
max1 = value
elif not max2 and value < max1:
max2 = value
elif max1 > value > max2:
max2 = value
return max2
result = [i for i in array if i > 5 and array.count(i) == 1]
По мне, легчайший вариант
С виду, здесь квадратичная сложность. Функция array.count(i) работает за O(n), и эта процедура выполняется в цикле, который работает также за O(n). Итоговая сложность O(n * n)
Хотя я ещё не досмотрел решение, предложенное на видео, мб там тоже квадрат
Думаю, здесь имеет смысл воспользоваться словарём. Создать из списка словарик, где ключи - сами числа, а значения - количество повторов. А ещё лучше сразу заюзать Counter из collections. Сейчас пролистал - ниже есть комментарий с таким решением. Однако, если нам нужно сохранить порядок, то не уверен, что под капотом Counter сохраняет его. Если не сохраняет, то через обычный словарь по-прежнему решается
Changed in version 3.7: As a dict subclass, Counter inherited the capability to remember insertion order. Math operations on Counter objects also preserve order. Results are ordered according to when an element is first encountered in the left operand and then by the order encountered in the right operand.
Сохраняет порядок. Можно юзать :)
2я задачка, стоимость операций со словарём O(1), кроме прохода O(n)... поэтому вроде как подходит
def get_unique(array: list[int]) -> list[int]:
dublicate = {}
unique_lst = []
for num in array:
dublicate[num] = dublicate.get(num, 0) + 1
if num > 5 and dublicate.get(num) < 2:
unique_lst.append(num)
return unique_lst
Неверно, если входной массив будет типа [8, 8, 10], то ваш код даст ответ [8, 10]. А нам надо просто [10]
Поставил на паузу в самом в начале и написал так: mx1 = mx2 = -inf; for i in sequence: if i > mx1: mx2, mx1 = mx1, i elif i> mx2: mx2 = i; return mx2
И главное переживал, что написал не красиво и есть более элегантное решение
Представьте мою кровь из глаз, когда я продолжил смотреть видео
Наверное я себя недооцениваю
По задаче с дублями, заведите еще один массив для хранения уже удаленных , этим вы обиграете случай с 3 и более нечетными повторами и если встречаете повтор в цикле надо дропнуть число из результируещего и добавить в массив уже удалённых и при следующем повторении просто уже не добавлять.
мое решение:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
def cleaner(numbers: list[int]) -> list[int]:
range_item = 5
result_list:list[int] = []
list_of_doubles:list[int] = []
for item in numbers:
if item in list_of_doubles or item
вторая вообще какая-то фигня. почему оно "однопроходное"? потому что там один цикл for? а ничего, что там при этом еще два цикла проверки по массиву и общая сложность O(n^3) ? тут надо counter использовать, чтобы O(n) получилось.
def find_max2(a):
try:
if a[0]>=a[1]:
max1,max2 = a[0],a[1]
else:
max1,max2 = a[1],a[0]
except IndexError:
return None
for v in a[2:]:
if v>max1:
max2=max1
max1=v
if v>max2 and v
Мое решение первой задачи, мне кажется оно легче для восприятия:
max_value = arr[0]
second = float[“-inf”]
for i in arr[1:]:
if i > max_value:
max_value = i
second = max_value
elif max_value > i > second:
second = i
if second == float(“-inf”):
return None
return second
Опустил создание функции и блок try - except, там ничего нового
Лайк!
Всем привет, по поводу первой задачи, я для себя ее немного усложнил и предположил что в параметрах к функции помимо списка передается так же порядковый максимального числа из списка.```from typing import Optional, Callable
def get_max(array: list[int], n: int) -> Optional[int]:
n_max: dict = {i: None for i in range(1, n + 1)}
for number in array:
for key, value in n_max.copy().items():
if value is None:
n_max[key] = number
break
elif number > value and n_max[key - 1] != value:
n_max[key], number = number, n_max[key]
elif value == number:
break
return n_max[n]```
На get_max([1,2,3,4,5,6], 1) выкидывает KeyError: 0
Зачем вам Callable?
Касаемо второй задачки, может я не прав, но она не тянет на однопроходник. Как сказал Ян оператор in это линейный поиск, а так как вы осуществляете на каждой итерации линейный поиск в (n - 1) элементах, то о каком однопроходнике идет речь?! O(n-1) == O(n). Если бы создали отдельный список (память компьютера сегодня дешевле временнОй)), то еще окей, так как в таком случае n может быть сильно больше длины нового списка и поиск по новому списку можно считать за константу, а лучше в качестве такого буффера создать множество, тогда поиск там будет осуществляться за константное время.
ps. специально пишу отдельными комментариями, я так понимаю, что это толкает видео в рекомендашки=)
Соглашусь, но частично. Задача однопроходник из класского собеседовнаия в яндекс 5ти летней давности. Вот только первоначально там был только один уникальный элемент- она решалась как однопроходник. Если уникальных элементов более двух- однопроходник меняем на что-то типа вашего предложения- вот только не множество,а dict. set и diсt работают через hash имеют линейное время поика. после dict просто фильтрануть. почему dict - потому что после решения с 1м уникальынм элементом, обычнно спрашивают, а 2, а если 3 и тд :) У Андрея, увы, "Смешались в кучу кони, люди, И залпы тысячи орудий"...
def greater_unique(array, min_value):
# убираем дубликаты, проходя по списку 1 раз
values = dict()
result_list = []
for value in array:
if value > min_value:
if value not in values:
values[value] = 1
result_list.append(value)
elif values[value]:
values[value] = 0
result_list.remove(value)
return result_list
remove делает сложность О n²
Собеседуемому совет: во время интервью не нужно накручивать полноценные тесты, промежуточные функции и переменные, достаточно такого:
assert get_unique([1,2,1,3]) == [1,2,3]
Пишется буквально за 3 секунды и можно приступать к задаче.
Если немножко усложнить до n-того максимума, то вот вариант:
def n_th_max(n,array):
max_seq = [float('-inf')]*n
for num in array:
for ind, m in enumerate(max_seq):
if num > m:
max_seq[ind+1:] = max_seq[ind:-1]
max_seq[ind] = num
break
elif num == m:
break
return max_seq[-1] if max_seq[-1] > float('-inf') else None
И тесты:
from numpy.random import randint
def test_n_th_max():
def tester(n, array):
seq = sorted(set(array),reverse = True)
return seq[n-1] if len(seq)>=n else None
tests = [[3,2,-10,2,100,45],
[100,100,99],
[1],
[],
[100,100,100],
[100,100,101],
[1,2,100,100],
randint(-100,100,20),
randint(1,3,20)]
ns = [1,2,3,10]
for n in ns:
for test in tests:
result = n_th_max(n,test)
assert result == tester(n,test), f'Wrong answer: {result} of {n}-max in {test}'
print('All tests complited succesfull')
if __name__=="__main__":
test_n_th_max()
Кстати, при n равном размеру уникальных элементов выходит что-то типа сортировки вставкой, если вернуть всю max_seq, только ещё и дубли выкидываются по пути. А если убрать elif num==m: break, взять n = len(array) и возвращать max_seq, то получим ту самую сортировку вставкой.
И алгоритм именно однопроходный, т.к. n фиксировано и скорость выполнения под циклом от размера массива не зависит. Другое дело, если привязать n к размеру массива, то выходит та самая сортировка и сложность растёт с размером массива на какую-то степень быстрее.
Что касается улучшения, то для больших n можно было бы использовать двоичный поиск по seq, например, чтобы быстрее находить место для вставки.
Максимально усложнили алгоритм, думаю это из-за нервов
"Я не люблю Ctrl+S"
Слова не мальчика, но вимера
Что-то у вас путаница случилась. Строгое неравенство - больше/меньше, нестрогое - больше или равно/меньше или равно
Можно решить последнюю задачку решетом Эратосфена :D
Не.. ну так не честно. :) Если уж озвучили, что решаем в одну строчку- так давайте в одну строчку:
foo = lambda x: [i[0] for i in Counter(x).items() if i[1]==1 and i[0]>5]
вот, собственно, так и ищем не дублирующие значения больше 5 если их несколько ....
А вот если одно- там так не получится в одну строчку. :)
xor в list comprehension не заработает
Как-то так написал
def second_max(arr):
if len(arr) < 2:
return None
if arr[0] == arr[1]:
max_1, max_2 = arr[0], None
elif arr[0] > arr[1]:
max_1, max_2 = arr[0], arr[1]
else:
max_1, max_2 = arr[1], arr[0]
for el in arr[2:]:
if el > max_1:
max_2 = max_1
max_1 = el
elif (max_2 == None and el != max_1) or \
(max_2 != None and el > max_2 and el != max_1):
max_2 = el
return max_2
А нельзя было сделать сорт, ремув макс, а потом вывести оставшийся максимум. Или это не алгоритм?
Мне кажется, в итоге сложность алгоритма для второй задачки получилась O(n^2). Так как на каждой итерации мы итерируемся по всему входящему массиву. Другими словами, цикл в цикле.
Думаю, что данную задачу невозможно решить за линейную сложность. Загвоздка именно в том, что нужно элементы, у которых есть дубли полностью убрать, а не просто убрать повторы и оставить только уникальные.
Я решил со сложностью O(n+n), как мне кажется.
def filter_duplicates(arr):
temp_filtered_arr = []
temp_dict = {}
for num in arr:
if num
О(n+n) есть О(n)
d = {}
[d.update({i:d.get(i,0)+1}) for i in l if i>5]
d = [i[0] for i in d.items() if i[1]==1]
print(d)
def unik(numbers):
dict = {}
for num in numbers:
dict[num] = num in dict or num
Если делать проверку Больше 5 сразу, сложность уменьшится, но код вырастет на строчку, но тогда можно словарь в параметры вынести, и код опять уменьшится.
import math
def second_max(array):
max1 = max2 = -math.inf
for x in array:
if x >= max1:
max1 = x
elif x > max2:
max2 = x
return None if max2 == -math.inf else max2
либо так еще можно, не знаю в чем разница между -math.inf и -float('inf'), sys.getsizeof() возвращает 24 байта и для первого и для второго случая
def second_max(array):
max1 = max2 = -float('inf')
for x in array:
if x >= max1:
max1 = x
elif x > max2:
max2 = x
return None if max2 == -float('inf') else max2
Ребят, подскажите можно ли при поиске двух максимумов задействовать библиотеку пандас? Или она много времени съест и памяти?
Я попробовал написать, но будет справедливо если только серия будет состоять из чисел, если символы то не будет работать
import pandas as pd
s = pd.Series([3, 4, 34, 100, 5, 5,32,34,3,100,99,90,90])
a=pd.unique(s)
print(sorted(a)[-2:]) #[99,100]
А зачем? Сортировка O(n) не бывает, насколько я помню.
В первой программе не пройдёт тест 100, 100, 101
Можно ещё изначально max_2 не присваивать и начинать цикл со 2го элемента
Решение:
def find_second_max(array):
max_1, max_2 = None, None
if len(array) < 2:
return None
max_1 = array[0]
for num in array:
if num > max_1:
max_2 = max_1
max_1 = num
continue
if num != max_1 and (max_2 is None or max_2 < num):
max_2 = num
return max_2
А если так:
x = [int(i) for i in input().split()]
a = max(a)
b = x.count(a)
d = len(a)
If d != 1 and b == 1:
x.pop(a)
c = max(a)
print(c)
if b > 1:
For i in x:
if x[i] == a:
x.pop(x[i])
x.pop(a)
c = max(a)
print(c
Else:
Print('none')
P.s Не бросайтесь помидорами я только начал учть))
@@user-ru2gn4uw4z у вас не однопроходный алгоритм - каждый раз при вызове max() он пройдёт по всему массиву, потом ещё нужно по всему массиву пройтись, чтобы удалить дубликаты максимума, плюс алгоритм на первый взгляд не рабочий (судя по второй строчке a = max(a) - ошибка, и синтаксических ошибок много).
@@bitowner спасибо, буду учиться))
У меня такое решение для поиска второго максимума получилось
def second_min(arr):
if len(arr) curr_max - arr[i] != 0:
curr_min_diff = abs(curr_max - arr[i])
curr_max = max(arr[i], curr_max)
return curr_max - curr_min_diff
а если на вход придет [1,1,1]?
Try/except для проверки длины массива - это жесть.
ко второй задаче - если уж мы допускаем проверкуin arr... то не проще сделать так?:
def get_uniques(arr):
return [i for i in arr if i > 5 and arr.count(i) < 2]
count тоже работает за O(N) но кода в разы меньше и лучше читается.
не проще ли тогда сделать count и потом пройтись по нему 1 раз и найти все числа удовлетворяющие условия?
Конечно там скорее всего вылезут проблемы с порядком, но можно в таком случае сделать 1 проход по массиву и смотреть на значение dict[arr[i]]] и проверять делимость. В таком случае надо сделать 1 проход Counter и 1 проход для формирования ans_list.
То, что ты написал выше может и красиво, но ты для каждого элемента массива делаешь проход в counter и тем самым у тебя O(N^2) вообще вылазит.
Можно так сделать return [i for i in set(arr) if i > 5 ]
Так можно?
random_list = [12, 7, 5, 5, 2, 6, 9, 13]
if len(random_list) > 2:
max1 = random_list[0]
max2 = random_list[len(random_list)-1]
for i in random_list:
if i > max1:
max2 = max1
max1 = i
print (f'Max 1: {max1} Max 2: {max2}')
else:
print('Please enter mininal 2 elements list')
если работает - то чеж нет.
Попробуй на таких данных
random_list = [14, 12, 7, 5, 5, 2, 6, 9, 13, 14]
Должно быть 14, 13 же?
@@AndyPronin Я был не прав, вот так работает:
random_list = [14, 12, 7, 5, 5, 2, 6, 9, 13, 14]
if len(random_list) > 1:
max1 = random_list[0]
max2 = 0
for i in random_list:
if i > max1:
max2 = max1
max1 = i
if i > max2 and i != max1:
max2 = i
print (f'Max 1: {max1} | Max 2: {max2}')
else:
print('Please enter a list of 2 elements and more')
Надо тест сделать, что бы он генерировал лист с рандомными числами, за 2 прохода "плохим" алгоритмом находил Min1 и Mix2 и готовил много тестов, с заведомо верными данными?
@Vladimir Dorofeyev Live генерировать в тестах не обязательно. Можно ручками сделать несоклько последовательностей и ассерты прописать. Что нибудь типа пустого массива, с дублами, с нулём и отрицательными. Тут особо не придумаешь граничных случаев. Задачка простая достаточно.
def uniq_num(numbers):
if len(numbers) >= 1 :
result = [i for i in numbers if numbers.count(i) == 1 and i > 5]
return result if result else None
return None
на 1, 2, 100, 100 оно не работает просто (второй максимум)
def find_dublicates(numbers):
unique_numbers = []
duplicate_numbers = []
for number in numbers:
if number > 5:
if number not in unique_numbers:
unique_numbers.append(number)
else:
if number not in duplicate_numbers:
duplicate_numbers.append(number)
return duplicate_numbers
Первое решение, что пришло в голову. Но создал два списка правда.
Должно быть такое условие:
if number > 5:
if number in uniques:
uniques.remove(number)
duplicates.append(number)
elif number not in duplicates:
uniques.append(number)
@@ivanpavlov6701 и правда, пасиб!
Жесть, есть же просто -float('inf')
Вторая задача никак не решается за один проход, ни на каком языке программирования и никаким способом. Если вы спрятали дополнительные проходы под капот, это не делает алгоритм однопроходным, я вас разочарую.
Зато хайпанули)
@@AndyPronin Есть мнение, что такой подход к изучению алгоритмов очень плох.
Человек, которого вдвоём начинают путать два человека при попытке написания кода, просто не способен его написать. В моём понимании лучше было бы проговорить/прописать то же самое на листочке в простейшем виде. Без кода, просто чтобы человек сам подумал как работает алгоритм, что делать и в каких случаях и лишь потом переносить в код. Когда ты сразу начинаешь писать код получается костыль на костыле и костылем погоняет, а когда ты ещё и не очень много кода писал, то становится ещё хуже. Тоже самое можно сказать и про Яна, который вместо придумывания нормального полного алгоритма просто путаясь сам писал очень костыльно.
Парень нашёл работу?
Да. Сейчас девопсом работает в Питере
Не соглашусь, сначало нужно выявить первый макс, затем его исключить и выявить второй, затем сравнить первый макс со вторым и если он меньше первого принять во внимание, если же второй макс равен первому то его тоже исключить и так далее.
Какое-то издевательство синьоров над интерном
Почему чувак тупит, а стыдно мне?🤔
Enumerate тут лишний, решение простое(само собой плохо что использую “in”, но с телефона печатать лень а думать под вечер так тем более, сам любитель в питоне:)
def make_unique(numbers):
unique_numbers = []
for number in numbers:
if number
def two_max(arr):
try:
m1 = m2 = arr[0]
except IndexError:
return None
for num in arr:
if num > m1:
m1, m2 = num, m1
elif num > m2 or m2==m1:
m2 = num
return m2 if m2
def second_max(a: list):
sm = fm = None
for num in a:
fm = num if not fm or num >= fm else fm
sm = num if fm and num < fm and (not sm or num > sm) else sm
return sm
Добрый день, Ваш алгоритм не переваривает массив из нулей, как минимум. Они тоже как None будут в условиях восприниматься.
@@alexanderkolesnik9357 для листа всех нулей он вернет None, что есть корректный результат. Проверьте..
@@denispatrakhin Извиняюсь, неточно выразился. Пусть будет [0,1], например. Главное, что я имел ввиду, это неразличимость нуля и None в условной конструкции.
@@alexanderkolesnik9357 да, понял, ну это просто надо условия подправить