Юбилейный десятый выпуск, и у нас снова Python ❤️
Задачка несложная, но мне она очень нравится по двум причинам:
• Можно решать тремя подходами, все правильные, но какие-то красивее
• В ней есть робот
Задачка с интервью в Магнит 🛒 Условие:
Робот стоит в точке (0, 0). Ему подаются команды: U (вверх), D (вниз), L (влево), R (вправо). Определить, вернется ли робот в исходную точку после выполнения всех команд.
Примеры:
"UD" → True
"RRDD" → False
💡 ИДЕЯ
Робот вернется в (0, 0) тогда и только тогда, когда:
➡️ число шагов вверх = числу шагов вниз (U == D)
➡️ число шагов влево = числу шагов вправо (L == R)
Причем порядок команд не имеет значения. "UDLR" и "ULDR" дадут один результат.
❗️ Это подсказка, что нам не нужно симулировать путь по шагам - достаточно посчитать буквы!
Но начнем мы именно с наивной симуляции, так как на моей памяти у студентов это самое частое решение 😎
➡️ Решение 1: наивная симуляция
Буквально делаем то, что написано: заводим координаты и проходим по командам, двигая робота:
def robot_return(s: str) -> bool:
x, y = 0, 0
for c in s:
if c == 'U':
y += 1
elif c == 'D':
y -= 1
elif c == 'L':
x -= 1
elif c == 'R':
x += 1
return x == 0 and y == 0
➕ Плюс: максимально прозрачно, читается как условие задачи.
➖ Минус: многословно, четыре ветки if/elif.
➡️ Решение 2: считаем буквы
Раз порядок не важен, а важны только количества - давайте не гонять робота, а сразу сравним счётчики. В лоб через .count():
def robot_return(s: str) -> bool:
return s.count('U') == s.count('D') and s.count('L') == s.count('R')
Одна строка, читается как наша математическая формулировка. Красыво ❤️
А еще это повод узнать .count(), если вы вдруг пока не видели этого метода!
❗️Нюанс (для любителей алгоритмов):
Каждый .count() проходит по всей строке заново. Асимптотика все равно O(n), но с константой 4 (4 использования функции .count()). Если придираются к эффективности - см. решение 3.
➡️ Решение 3: один проход + словарь
Компромисс между читаемостью и эффективностью - пройти строку ОДИН раз и накопить счетчики в словаре:
def robot_return(s: str) -> bool:
count = {'U': 0, 'D': 0, 'L': 0, 'R': 0}
for c in s:
if c in count:
count[c] += 1
return count['U'] == count['D'] and count['L'] == count['R']
А если можно пользоваться библиотеками, то этот же способ схлопывается в две строчки через Counter:
from collections import Counter
def robot_return(s: str) -> bool:
c = Counter(s)
return c['U'] == c['D'] and c['L'] == c['R']
➡️ Так какой способ "правильный"?
А это прелесть этой задачи, на собесе все три решения - правильные. Но показывают разное:
1️⃣ [Симуляция] → "Я перевожу условие в код дословно, без ошибок"
2️⃣ [.count()] → "Я упростил задачу"
3️⃣ [Словарь] → "Я упростил задачу + уменьшил число проходов"
Насколько будут придираться - зависит от собеседующего. Главное тут - уловить фишку про равное количество букв и озвучить ее.
Еще лучше - учесть ее и написать решение 2 или 3)
————
Какое решение написали бы вы? 🙃
По классике - жду ваших 🔥🔥🔥
Предыдущие разборы:
Можете тыкнуть случайный в честь юбилея 🥰
vol. 1 | vol. 2 | vol. 3 | vol. 4 | vol. 5
vol. 6 | vol. 7 | vol. 8 | vol. 9