Алгоритмы - Собеседования, Олимпиады, ШАД

Задача с собеседования в Яндекс

Нужно написать функцию normalize, которая принимает на вход юниксовый путь и выдает его нормализованный вариант (схлопываются слеши, обрабатываются все возможные точки).
Каталоги разделяются слэшами (/). Подряд может идти несколько слэшей ( /// ). Если указан символ точка "." - это означает текущую папку. Если указано два символа точки подряд ".." - это означает ссылку на родительскую папку. Требуется получить нормализованное представление

Примеры:
In: /foo/bar//bax/asdf/quux/..
Out: /foo/bar/bax/asdf

In: a/../../b
Out: ../b

In: /a/../../b
Out: /b

Решение:
Изейшая задачка на стек
Если встречаем несколько слэшей, при этом до этого слэш был, то игнорим их. Если встречаем имя папки, пушаем её. Если встречаем две точки, то попаем последний элемент в стеке (и проверяем перед этим, что он не пуст, иначе пушаем две точки)

def normalize(path: str) -> str:
if not path:
return "."

is_absolute = path.startswith('/')
parts = []

for part in path.split('/'):
if part == '' or part == '.':
continue
elif part == '..':
if parts and parts[-1] != '..':
parts.pop()
else:
if not is_absolute:
parts.append(part)
else:
parts.append(part)

normalized_path = '/'.join(parts)

if is_absolute:
normalized_path = '/' + normalized_path

if not normalized_path:
return '/' if is_absolute else '.'

return normalized_path

Асимптотика O(N)

@algoses

www.tgoop.com/algoses/324

8.7K viewsApr 10 at 20:18

Задача с собеседования в Яндекс

Нужно написать функцию normalize, которая принимает на вход юниксовый путь и выдает его нормализованный вариант (схлопываются слеши, обрабатываются все возможные точки).
Каталоги разделяются слэшами (/). Подряд может идти несколько слэшей ( /// ). Если указан символ точка "." - это означает текущую папку. Если указано два символа точки подряд ".." - это означает ссылку на родительскую папку. Требуется получить нормализованное представление

Примеры:
In: /foo/bar//bax/asdf/quux/..
Out: /foo/bar/bax/asdf

In: a/../../b
Out: ../b

In: /a/../../b
Out: /b

Решение:
Изейшая задачка на стек
Если встречаем несколько слэшей, при этом до этого слэш был, то игнорим их. Если встречаем имя папки, пушаем её. Если встречаем две точки, то попаем последний элемент в стеке (и проверяем перед этим, что он не пуст, иначе пушаем две точки)

def normalize(path: str) -> str:
if not path:
return "."

is_absolute = path.startswith('/')
parts = []

for part in path.split('/'):
if part == '' or part == '.':
continue
elif part == '..':
if parts and parts[-1] != '..':
parts.pop()
else:
if not is_absolute:
parts.append(part)
else:
parts.append(part)

normalized_path = '/'.join(parts)

if is_absolute:
normalized_path = '/' + normalized_path

if not normalized_path:
return '/' if is_absolute else '.'

return normalized_path

Асимптотика O(N)

@algoses

BY Алгоритмы - Собеседования, Олимпиады, ШАД