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

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

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

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

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

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

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

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

Очень простые задачи
---
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(), и все что-то выдумывают сложное такое

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

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

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

Ну и там перед этим конечно вносим проверки на все исключения.

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 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

Этот плох вариант?

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

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

return sorted(s) == sorted(t)

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

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

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

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

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

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

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

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

На питоне, так как я не пишу на нем, то сделал бы сортировку строк, и по элементо сравнивал бы каждый элемент , и если бы нашел первое нк соответствие то вернул бы false.

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

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

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

print(anagram(s, t))

def anagram(s, t):
return sorted(s) == sorted(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

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

return t == t[::-1]

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

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

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

Я так решил, чтобы не создавать 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

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

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

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

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

Я тоже начинающий 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))

Кто может подсказать какие есть косяки в моём решении, что можно улучшить? Спасибо

Из минусов: такие задачки, обычно, "в уме" решаются.
И вообще странно, что человек, который активно затачивал алгосы, не решил эти задачи минуты за 3.
И еще страннее, что не сразу понял, почему ИДЕ подчёркивает переменные.

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

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

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

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

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

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)))

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
...:

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

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

ну версий много, перебор в расчёт не берём
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()

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