Собеседование python разработчик. Алгоритмическая секция | Рабадан Ибрагимов 

t.me/RU-vidPronin Чат для общения pyhton разработчиков и им сочуствующих. Свободное общение, тестовые и вопросы с собесов и прочее. Заходите, там вам рады. Поддержать канал: www.tinkoff.ru/rm/pronin.andrey156/3QNa723323 Обычно денежка идёт на книжки про питончик. Но иногда на светлое и тёмное.

def anagram(s, t): return sorted(s) == sorted(t)

Обе задачи в первой десятке уровня Easy на LeetCode

Из минусов: такие задачки, обычно, "в уме" решаются. И вообще странно, что человек, который активно затачивал алгосы, не решил эти задачи минуты за 3. И еще страннее, что не сразу понял, почему ИДЕ подчёркивает переменные. В целом - норм. Корнеркейсы рассматривает, в голове код прогоняет. Идеи нормальные пришли, примерно понимает цену базовых операций, действия обдуманные и тд. Как для человека, который не планирует идти в Яндексы и тд. - точно норм. Но тут надо сделать учёт, что задачи - элементарные. Типа мелтайс. Поэтому делать какие-то выводы на основании этих 2 задач - это преждевременно. И, мне кажется, что Руслан слегка лукавит насчёт того, что это частые задачи в ФААНГе - если только в качестве разогрева.

народ, подписываемся, на 20к Андрей обещал начинать собес с подтягиваний))

Руслан краш

Может что-то поинтереснее, например на графы/деревья/структуры?

А почему isalnum(), а не isalpha()? Если в исходной строке будет цифра, то ничего не выйдет ведь.

def anogram(s, t): set_s = set(s) count = 0 for i in set_s: if i in t and t.count(i) == s.count(i): count += 1 return count == len(set_s)

def anagram(s, t): s = sorted(s) t = sorted(t) if s == t: return True else: return False print(anagram(s, t))

обычно задачи решают через хешмап, отличное решение было от Рабадана "по классике" def isAnagram(s, t) : if len(s) != len(t): return False countS, countT = {}, {} for i in range(len(s)): countS[s[i]] = 1 + countS.get(s[i], 0) countT[t[i]] = 1 + countT.get(t[i], 0) return countS == countT

В задаче на лайфкодинге можно было проверить сперва, одинаковая ли длина, а потом выводить фолс, если количество буквы из первого слова не равно второму, а самом конце вывести тру. Почему сразу в голову пришло. Смотрел видос с Данилой из Г компании, там задачу решил за 20 сек, подобрав идеальнейший алгоритм. Либо я гений, либо, когда тебя интервьюируют, затуп начинается.

А если, идти по одной строке и символ искать в другой строке (если не пробел) и удалять этот символ во второй. в конце должна получится пустая строка или с пробелами

Когда он сказал что перебирать будет у меня челюсть отвалилась. Вот и все , какие софт-скилс ... Один вопрос про алгоритм и все понятно.

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

А задачу на анаграммы можно же решить так?) return sorted(a) == sorted(t)?)

огонь! лайк от СЕООНЛИ! я еще не надоел?)

ну версий много, перебор в расчёт не берём 1. создать два Counter и сравнить их(но часто на собесах просят не использовать готовые штуки из либ, в связи с чем идёт к следующему варианту 2. при условии, что длины слов равны, в одном цикле пройтись по обеим строкам сразу (хотя можно и отдельно это все ещё O(n) будет) и накопить два отдельных словаря, где ключ это буква, а значение количество этой буквы в слове (тот же Counter только ручками) и потом их сравнить 3. пройтись по строке s в цикле и создать словарь (ключ это буква, значение количество буквы в слове), затем в отдельном цикле пройтись по строке t и уменьшать значения( ну например в строке s у нас две буква «а», соотвественно в словаре будет «а»: 2, затем, когда проходимся по строке t мы встретили букву «а», делаем поиск через in в словаре [операция поиска в словаре за О(1) работает] вычитываем единичку из значения, получаем «а»: 1, когда снова встретили в строке t букву «а», снова поиск и снова уменьшаем, получаем «а»: 0, в каждой итерации цикла работает условие, если значение равно 0, значит этот ключ можно дропнуть) после завершения обработки строки t просто останется проверить пустой ли словарь, если да, то True, иначе False ps. не забываем, что в строке t может быть буквы, которой нет в строке s, соотвественно, метод get вам в помощь как минимум три варианта решения ps. решение с сортировкой в комменте ниже выполняется за O(nlogn), не круто вторая задача: метод двух указателей, идём слева и справа, и не забываем чекать, что символ str.isalpha()

Сортирнуть и в цикле сравнить посимвольно. Оно?

Андрей, а не думали ли вы как нибудь собрать больше людей и побатлится в написании алгоритмов ,на том же codingbattle ? Думаю будет фаново ...

Если в слове пробелы есть, то можно добавить строчку на эту проверку. def is_palindrome(string: str) -> bool: left = 0 right = len(string) - 1 while left < right: if string[left] != string[right]: return False left += 1 right -= 1 return True

def foo(a, b): return dict(map(lambda x: (x, a.count(x)) , set(a))) == dict(map(lambda x: (x, b.count(x)) , set(b)))

во второй задаче метод isalnum() проверяет состоит ли строка из цифр или букв и если в строке будет цифра выдаст True. нужен метод isalpha().

А если отсортировать два аргумента и сравнить? на 2 строки

def is_anagramma(s1, s2): if len(s1) != len(s2): return False a1 = list(s1.lower()) a2 = list(s2.lower()) length = len(a1) i = 0 while i < length: if a1[i] not in a2: return False if a2[i] not in a1: return False i+=1 return True Этот плох вариант?

Забавно, скорее всего человек эти задачки уже решал, это easy с leetcode. Стоит ли предупреждать интервьюера об этом, если задачи знакомы?

def poly_check(str): return str.lower() == str.lower()[::-1] Такой вариант решения на поллиандром нельзя? Это без проверки символов на буквенность, но допилить ее же не проблема

Интерсная задача, правда я на Си пишу, и сделал просто сложил бы все символы строк используя XOR, если получил ноль, то строки анограммы, в другом варианте нет. Ну а первым действием проверил бы длинну строк. На питоне, так как я не пишу на нем, то сделал бы сортировку строк, и по элементо сравнивал бы каждый элемент , и если бы нашел первое нк соответствие то вернул бы false.

Нельзя ли задание на амбиграмму сделать через sorted? Если sorted (str_1)==sorted(str_2) : True Иначе false. Ещё можно регистр не учитывать ,прописав в key лямбду определеную

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

def anagr(str1 = s, str2 = t): s = sorted(list(str1)) t = sorted(list(str2)) return s == t кто в определении сложности шарит, какой вариант первой задачи лучше - этот или из видео? def poly(str1 = s, str2 = t): s = ''.join(list(str1)[::-1]) return s == t и этот для второй задачки сравните плиз, если не трудно. не проходил еще алгоритмы и их сложность :(

драбадан)

В питоне не строгая типизация или она не такая строгая? Думаю собес можно продолжать на лайте, с шутками и прикольчиками :)

Я так решил, чтобы не создавать 2 словаря: def anagram(s: str, t: str): count_dict = {} if len(s) == len (t): for i in range(len(s)): count_dict[s[i]] = count_dict.get(s[i], 0) + 1 count_dict[t[i]] = count_dict.get(t[i], 0) - 1 else: return False return not all(count_dict.values()) or not count_dict

def fn(x, y) : L_x=list(x) L_y=list(y) If sorted(L_x) ==sorted(L_y) : print True else: print False fn("robot", "rbtoo") =>> # True

return sorted(s) == sorted(t)

from collections import Counter def anagram(s, t): return Counter(s) == Counter(t)

def isanogram(s ,t): if set(s) == set(t): return True return False a = "listen" b = "silent" print(isanogram(a,b)) output: True может это быть как ответ на первую задачу или нужно через хешмап?

Очень простые задачи --- def is_anagram(s, t): return sorted(s) == sorted(t) assert is_anagram('silent', 'listen') == True assert is_anagram('silentt', 'listen') == False --- --- def is_palindrome(a): return a.lower() == a[::-1].lower() assert is_palindrome('abba') == True assert is_palindrome('abbA') == True assert is_palindrome('bbea') == False --- Мало того, я вижу что ребята в других собесах с вами же. Вообще не хотят использовать set(), и все что-то выдумывают сложное такое

Я тоже начинающий python-разработчик и решил задачу на анаграмму так: def anagramm(s, t): if len(s) != len(t): return False d1 = {i: s.count(i) for i in s} return all(map(lambda sign: sign in d1 and t.count(sign) == d1[sign], t)) Кто может подсказать какие есть косяки в моём решении, что можно улучшить? Спасибо

если разрешают встроенные функции - можно легко все решить, и почему ребята начитают писать так много кода? я начинаю терять мысль в таких случаях( def isPalindrome(s) : t ='' for i in s.lower(): if i.isalnum(): t += i return t == t[::-1]

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

Ля, ладно. Может херню скажу. А чё нельзя просто инвертировать список? Ну строка это список, инвертируем список и сравниваем. Палиндром читается одинаково с обоих сторон, следовательно инвертация даст точно такой же список. Ну и там перед этим конечно вносим проверки на все исключения.

Дизлайк за то что интервьюер не дал условие задачи текстом, не опсиал что такое анаграмма не дал ограничений по условию.

def get_anagrams(string_1, string_2): set_string = set(string_1) for i in set_string: if string_1.count(i) != string_2.count(i): return False return True

анаграма это по сути проверка на одинаков ли наш массив. отсортировали, сравнили. все! надо пробелы, ну чуть дописали... строка, преобразовали.)) анаграма - is_anagram = lambda x1, x2: sorted(x1) == sorted(x2) полидром - is_palindrome = lambda phrase: phrase == phrase[::-1] норм джун, прошел?😂 проверку пробела можете дописать.))

def anogram(s, t): lst = len(list(filter(lambda x: x if x in s else False, set(t)))) return lst == len(s)

По задаче на анограммы: - сджойнить обе строки и выполнить xor поэлементно🙈 По палиндрому: - метод двух указателей

В конце конечно ерунда про вовлечённость и прочее. В первую очередь люди идут в компанию чтобы зарабатывать деньги и опыт, а так же запись в своём резюме, не будем это скрывать и наигранно потом выдавать на собеседовании, это будет выглядеть откровенно глупо. Если человек подал на вакансию и его устраивает стек, то скорее всего задачи это ассорти (если не указано иное). На первых порах плевать чем заниматься, потому что человек даже предметную область скорее всего не знает

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

Задача на палиндром: def palindrom(string): ref = [x.lower() for x in string if x.isalpha()] s = ''''.join(ref) return s == s[::-1]

А дать формализованное условие задачи текстом религия не позволяет? Или банальная лень?

def palin(inp: str): str_len = len(inp) if str_len == 1: return True elif str_len % 2 == 0: border = int(str_len / 2) left = border - 1 right = border if left == 0: if inp[left] == inp[right]: return True else: return False while left != 0: if inp[left] == inp[right]: left -= 1 right += 1 continue else: return False return True else: mid = int(str_len / 2) left = mid - 1 right = mid + 1 if left == 0: if inp[left] == inp[right]: return True else: return False else: while left != 0: if inp[left] == inp[right]: left -= 1 right += 1 continue else: return False

Решение на анаграммы сводится к return set(a) == set(b) and len(b) == len(a)

def is_palindrome(string: str, ) -> bool: """ >>> is_palindrome('aaaaaaaaaaaaaaaaaaaaa') True """ for i in range(len(string) // 2): if string[i] != string[~i]: return False return True

На фразе: - Сгенерировать все перестановки... Нужно было заканчивать интервью и гнать кандидата ссаными тряпками

1. def check(s1: str, s2: str) -> bool: """меньше памяти, меньше времени""" ...: storage = {} ...: for letter in s1: ...: storage[letter] = storage.get(letter, 0) + 1 ...: for letter in s2: ...: temp = storage.get(letter, -1) - 1 ...: if temp == -1: ...: return False ...: if temp == 0: ...: storage.pop(letter) ...: else: ...: storage[letter] = temp ...: return len(storage) == 0 2. : def check(pal: str) -> bool: """менее громоздко""" ...: left = 0 ...: right = len(pal) - 1 ...: while left < right: ...: if not pal[left].isalpha(): ...: left += 1 ...: continue ...: if not pal[right].isalpha(): ...: right -= 1 ...: continue ...: if pal[left].lower() != pal[right].lower(): ...: return False ...: left += 1 ...: right -= 1 ...: return True ...:

def polindrom(s): return s[::-1] == s

def palindrom(s): s = s.split() s = ''.join(s) return s[:len(s)+1] == s[::-1]

задачи на стажировку в детский садик

def anagram(s, t): return sorted(s) == sorted(t)