![](https://habrastorage.org/getpro/habr/post_images/915/39d/3b3/91539d3b3be71056861dc65e18921c88.png)
Добро пожаловать в очередную из серии статей с разбором задачек, которые я задавал на собеседованиях в Google, прежде чем их запретили после утечки. С тех пор я оставил работу инженера-программиста в Google и перешёл на должность менеджера по разработке в Reddit, но у меня всё ещё осталось несколько замечательных тем. К настоящему моменту мы разобрали динамическое программирование, возведение матриц в степень и синонимичность запросов. На этот раз совершенно новый вопрос.
Но сначала два замечания. Во-первых, работа в Reddit была потрясающей. Последние восемь месяцев я строил и возглавлял новую команду Ads Relevance и занимался организацией нового офиса разработки в Нью-Йорке. Как бы это ни было весело, к сожалению, я обнаружил, что до недавнего времени у меня не оставалось времени или энергии на блог. Боюсь, что я немного забросил эту серию. Извините за задержку.
Во-вторых, если вы следили за статьями, то после последнего выпуска могли подумать, что я начну копаться в вариантах синонимичности запросов. Хотя я хотел бы когда-то вернуться к этому, но должен признаться, что из-за смены работы потерял должный интерес к этой проблеме и пока решил отложить её. Впрочем, оставайтесь на связи! За мной должок, и я намерен его вернуть. Просто, ну знаете, чуть позже…
Быстрый отказ от ответственности: хотя собеседование кандидатов является одной из моих профессиональных обязанностей, этот блог представляет мои личные наблюдения, личные истории и личное мнение. Пожалуйста, не принимайте это за какое-либо официальное заявление от Google, Alphabet, Reddit или любого другого лица или организации.
Поиск нового вопроса
В предыдущей статье я описал один из своих любимых вопросов, который использовал в течение длительного времени, до неизбежной утечки. Предыдущие вопросы были увлекательными с теоретической точки зрения, но я хотел выбрать проблему, чуть более актуальную для Google как компании. Когда этот вопрос запретили, то я хотел найти замену с учётом нового ограничения: чтобы вопрос был проще.
Теперь это может показаться немного удивительным, учитывая печально известный процесс собеседований в Google. Но в то время более простая проблема имела смысл. Мои рассуждения состояли из двух частей. Первая прагматичная: кандидаты обычно не очень хорошо справлялись с предыдущими вопросами, несмотря на многочисленные намёки и упрощения, и я не всегда был полностью уверен, почему. Вторая теоретическая: процесс собеседования должен разделять кандидатов на категории «стоит нанимать» и «не стоит нанимать», и мне было любопытно, можно ли сделать это с вопросом немного попроще.
Прежде чем разъяснить эти два пункта, хочу указать на то, что они не означают. «Я не всегда уверен, почему у человека возникают проблемы» не означает бесполезность вопросов и что я хотел упростить собеседование по этой причине. Даже с самым сложным вопросом многие хорошо справлялись. Я имею в виду то, что когда у кандидатов возникали проблемы, мне бывало трудно понять, чего им не хватает.
Хорошие интервью дают широкую картину сильных и слабых сторон кандидата. Для комитета по найму недостаточно просто сказать, что «он провалился»: комитет определяет, есть ли у кандидата специфические для компании качества, которые они ищут. Точно так же слова «он крут» не помогают комитету принять решение по кандидату, который силён в некоторых областях, но сомнителен в других. Я обнаружил, что более сложные вопросы слишком часто разделяют кандидатов по этим двум категориям. В этом свете «я не всегда уверен, почему у человека возникают проблемы» означает «неспособность продвинуться в этом вопросе сама по себе не рисует картину способностей этого кандидата».
Классификация кандидатов как «стоит нанимать» и «не стоит нанимать» не означает, что процесс собеседования должен отделять глупых кандидатов от умных. Я не могу вспомнить ни одного кандидата, который не был бы умным, талантливым и мотивированным. Многие пришли из отличных университетов, а остальные явно были исключительно мотивированы. Проход через телефонные собеседования — уже хорошее сито, и даже отказ на этом этапе не является признаком отсутствия способностей.
Однако я могу вспомнить многих, кто не был достаточно подготовлен к интервью или работал слишком медленно, или требовал слишком большого надзора для решения проблемы, или общался неясным образом, или не смог перевести свои идеи в код, или придерживался позиции, которая просто не привела бы его к успеху в долгосрочной перспективе и т. д. Определение «стоит нанять» размытое и варьируется в зависимости от компании, а процесс собеседования и заключается в том, чтобы определить соответствие каждого кандидата требованиям конкретной компании.
Я прочитал много комментариев reddit с жалобами на излишне сложные вопросы собеседования. Мне стало любопытно, можно ли по-прежнему сделать рекомендацию «достоин/не достоин» на более простой задаче. Я подозревал, что это даст полезный сигнал без лишней трепли нервов кандидата. Расскажу о своих выводах в конце статьи…
С этими мыслями я искал новый вопрос. В идеальном мире это достаточно простой вопрос, чтобы решить его за 45 минут, но с дополнительными вопросами, чтобы более сильные кандидаты проявили свои навыки. Он также должен быть компактным в реализации, потому что многие кандидаты по-прежнему пишут на доске. Большой плюс, если тема будет как-то связана с продуктами Google.
Наконец, я остановился на вопросе, который какой-то замечательный гуглер тщательно описал и вставил в нашу базу данных вопросов. Сейчас я проконсультировался с бывшими коллегами и убедился, что вопрос по-прежнему запрещён, поэтому вам его точно не зададут на собеседовании. Представляю его в таком виде, в каком он кажется мне наиболее эффективным, с извинениями перед оригинальным автором.
Вопрос
Поговорим об измерении расстояний. Хэнд — это единица измерения в четыре дюйма, которая обычно используется в англоязычных странах для измерения высоты лошадей. Световой год — ещё одна единица измерения, равная расстоянию, которое частица (или волна?) света пройдёт за определённое количество секунд, примерно равное одному земному году. На первый взгляд, у них мало общего друг с другом, кроме того, что они используются для измерения расстояния. Но оказывается, что Google может довольно легко их конвертировать:
![](https://habrastorage.org/webt/uu/8z/y-/uu8zy-po4rpuvr61dtewmyhjns0.png)
Это может показаться очевидным: в конце концов, они обе измеряют расстояние, поэтому ясное дело, что есть преобразование. Но если подумать, немного странно: как они вычислили этот коэффициент конверсии? Ясно, что никто на самом деле не считал количество хэндов в световом году. На самом деле не нужно считать это напрямую. Вы можете просто использовать общеизвестные преобразования:
- 1 хэнд = 4 дюйма
- 4 дюйма = 0,33333 фута
- 0,33333 фута = 6,3125e?5 миль
- 6,3125e?5 миль = 1,0737e?17 световых лет
Цель задачи — разработать систему, которая выполнит это преобразование. В частности:
На входе у вас список коэффициентов пересчёта (отформатированный на выбранном вами языке) в виде набора начальных единиц измерения, конечных единиц и множителей, например:
фут дюйм 12 фут ярд 0,3333333 и т. д.
Таким образом, что ORIGIN * MULTIPLIER = DESTINATION. Разработайте алгоритм, который принимает два произвольных значения единиц измерения и возвращает коэффициент преобразования между ними.
Обсуждение
Мне нравится эта проблема, потому что у неё интуитивно понятный и очевидный ответ: просто конвертировать из одного единицы в другую, потом в следующую, пока не найдёте цель! Не могу вспомнить ни одного кандидата, который столкнулся с этой проблемой и был полностью озадачен, как её решить. Это хорошо соответствует требованию «более простой» проблемы, поскольку предыдущие обычно требовали длительного изучения и размышлений, прежде чем находился хотя бы базовый подход к решению.
И всё же многие кандидаты не смогли реализовать интуицию в виде рабочего решения без явных намёков. Одно из достоинств этого вопроса в том, что он проверяет способность кандидата сформулировать проблему (сделать фрейминг) таким образом, чтобы она поддавалась анализу и кодированию. Как мы увидим, здесь есть одно очень интересное расширение, которое требует нового концептуального скачка.
Для контекста, фрейминг — это акт перевода проблемы с неочевидным решением в эквивалентную проблему, где решение выводится естественным путём. Если это звучит совершенно абстрактно и неприступно, простите, но так и есть. Я объясню, что имею в виду, когда представлю начальное решение этой проблемы. Первая часть решения будет упражнением в разработке и применении алгоритмических знаний. Вторая часть будет упражнением в манипулировании этим знанием, чтобы прийти к новой и неочевидной оптимизации.
Часть 0. Интуиция
Прежде чем копнуть глубже, давайте полностью исследуем «очевидное» решение. Большинство требуемых преобразований просты и понятны. Любой американец, который путешествовал за пределами США, знает, что большая часть мира для измерения расстояний использует таинственную единицу «километр». Для преобразования нужно всего лишь умножить количество миль примерно на 1,6.
С такими вещами мы сталкиваемся на протяжении большей части жизни. Для большинства единиц измерения уже есть предварительно вычисленное преобразование, так что нужно лишь посмотреть его в соответствующей таблице. Но если нет прямого преобразования (например, из хэндов в световые годы), есть смысл построить путь преобразования, как указано выше:
- 1 хэнд = 4 дюйма
- 4 дюйма = 0,33333 фута
- 0,33333 фута = 6,3125e?5 миль
- 6,3125e?5 миль = 1,0737e?17 световых лет
Это было совсем просто, я просто придумал такое преобразование, используя своё воображение и стандартную таблицу преобразований! Однако остаются некоторые вопросы. Есть ли более короткий путь? Насколько точен коэффициент? Всегда ли возможно преобразование? Можно ли его автоматизировать? К сожалению, здесь наивный подход ломается.
Часть 1. Наивное решение
Приятно, что проблема имеет интуитивное решение, но на самом деле эта простота является препятствием для решения проблемы. Нет ничего труднее попыток понять по-новому то, что вы уже понимаете — не в последнюю очередь потому, что вы часто знаете меньше, чем думаете. Для иллюстрации, представьте, что вы пришли на интервью — и у вас в голове этот интуитивный метод. Но он не позволяет решить ряд важных проблем.
Например, что делать, если нет преобразования? Очевидный подход ничего не говорит, действительно ли возможно преобразование из одной единицы в другую. Если мне дадут тысячу коэффициентов конверсии, мне будет очень трудно определить, возможно ли оно в принципе. Если меня просят сделать преобразование между незнакомыми (или выдуманными) единицами укачки и уколки, то я без понятия, с чего начать. Как здесь поможет интуитивный подход?
Должен признать, что это своего рода надуманный сценарий, но есть и более реалистичный. Видите, что моя постановка задачи включает только единицы расстояния. Это сделано специально. Что, если я попрошу систему перевести из дюймов в килограммы? И вы, и я знаем, что это невозможно, потому что они измеряют разные типы, но входные данные ничего не говорят о «типе», который измеряет каждая единица.
Именно здесь тщательная постановка вопроса позволяет проявить себя сильным кандидатам. Перед разработкой алгоритма они продумывают крайние случаи системы. И такая постановка проблемы целенаправленно даёт им возможность спросить меня, будем ли мы переводить разные единицы. Это не такая огромная проблема, если она встретится на ранней стадии, но всегда хороший знак, когда кто-то заранее спрашивает меня: «Что должна вернуть программа, если преобразование невозможно?» Постановка вопроса таким образом даёт мне представление о способностях кандидата, прежде чем он напишет хотя бы одну строку кода.
Представление в виде графа
Очевидно, что наивный подход не подходит, поэтому мы должны подумать, как можно произвести такую конверсию? Ответ — рассмотреть единицы как граф. Это первый скачок понимания, необходимый для решения этой задачи.
В частности, представьте, что каждая единица является узлом в графе, и существует ребро от узла
A
до узла B
, если A
можно преобразовать в B
:![](https://habrastorage.org/getpro/habr/post_images/fc6/d25/89f/fc6d2589f8a9a411cec0d704e2ad644e.png)
Рёбра помечены коэффициентом конверсии, на который вы должны умножить
A
, чтобы получить B
.Я почти всегда ожидал, что кандидат придумает такой фрейминг, и редко давал серьёзные подсказки для него. Я могу простить кандидата, который не замечает решения проблемы с использованием непересекающихся множеств или не слишком глубоко знаком с линейной алгеброй, чтобы реализовать решение, сводящееся к повторному возведению в степень матрицы смежности, но на любой учебной программе или курсе по программированию преподаются графы. Если у кандидата нет соответствующих знаний, это сигнал «не стоит нанимать».
В любом случае
Представление в виде графа сводит решение к классической проблеме поиска графа. В частности, здесь полезны два алгоритма: поиск в ширину (BFS) и поиск в глубину (DFS). При поиске в ширину мы исследуем узлы в соответствии с их расстоянием от начала координат:
![](https://habrastorage.org/getpro/habr/post_images/d45/4cb/15b/d454cb15b85c4ea9ce32e87623ed4115.png)
Более тёмные синие цвета означают более поздние поколения
А при поиске в глубину мы исследуем узлы в том порядке, в каком они встречаются:
![](https://habrastorage.org/getpro/habr/post_images/40b/f4c/f1a/40bf4cf1ae3d89554505c031c4529559.png)
Более тёмные синие цвета также означают более поздние поколения. Обратите внимание, что мы на самом деле не посещаем все узлы
Любой из алгоритмов легко определяет, существует ли преобразование из одной единицы в другую, достаточно просто выполнить поиск по графу. Начинаем с исходной единицы и ищем, пока не найдём единицу назначения. Если не удаётся найти пункт назначения (как при попытке преобразовать дюймы в килограммы), мы знаем, что пути нет.
Но подождите, чего-то не хватает. Мы не хотим искать, существует ли путь, мы хотим найти коэффициент конверсии! Именно здесь кандидат должен совершить скачок: оказывается, вы можете модифицировать любой алгоритм поиска для вычисления коэффициента конверсии, просто сохранив дополнительное состояние по мере прохождения. Вот где иллюстрации перестают иметь смысл, так что давайте погрузимся прямо в код.
Во-первых, нужно определить структуру данных графа, поэтому используем это:
class RateGraph(object):
def __init__(self, rates):
'Initialize the graph from an iterable of (start, end, rate) tuples.'
self.graph = {}
for orig, dest, rate in rates:
self.add_conversion(orig, dest, rate)
def add_conversion(self, orig, dest, rate):
'Insert a conversion into the graph.'
if orig not in self.graph:
self.graph[orig] = {}
self.graph[orig][dest] = rate
def get_neighbors(self, node):
'Returns an iterable of the nodes neighboring the given node.'
if node not in self.graph:
return None
return self.graph[node].items()
def get_nodes(self):
'Returns an iterable of all the nodes in the graph.'
return self.graph.keys()
Затем приступим к работе над DFS. Существует много способов реализации, но на сегодняшний день наиболее распространённым является рекурсивное решение. Начнём с такого:
from collections import deque
def __dfs_helper(rate_graph, node, end, rate_from_origin, visited):
if node == end:
return rate_from_origin
visited.add(node)
for unit, rate in rate_graph.get_neighbors(node):
if unit not in visited:
rate = __dfs_helper(rate_graph, unit, end, rate_from_origin * rate, visited)
if rate is not None:
return rate
return None
def dfs(rate_graph, node, end):
return __dfs_helper(rate_graph, node, end, 1.0, set())
В двух словах, этот алгоритм начинается с одного узла, перебирает его соседей и немедленно посещает каждого, выполняя рекурсивный вызов функции. Каждый вызов функции в стеке сохраняет состояние своей собственной итерации, поэтому, когда возвращается одно рекурсивное посещение, его родитель немедленно продолжает итерацию. Мы избегаем повторного посещения одного и того же узла, поддерживая набор посещённых узлов во всех вызовах. Мы также вычисляем коэффициент, назначая каждому узлу коэффициент преобразования между ним и источником. Таким образом, когда мы сталкиваемся с целевым узлом/блоком, мы уже создали коэффициент преобразования от исходного узла, и можем просто вернуть его.
Это прекрасная реализация, но она страдает от двух основных недостатков. Во-первых, она рекурсивная. Если окажется, что нужный путь состоит из более тысячи прыжков, мы вылетим со сбоем. Конечно, это маловероятно, но если и есть что-то неприемлемое для долговременного сервиса, так это сбой. Во-вторых, даже если успешно закончим, у ответа некоторые нежелательные свойства.
Я на самом деле уже дал подсказку в начале поста. Вы заметили, как Google показывает коэффициент конверсии
1.0739e-17
, но мой расчёт вручную даёт 1.0737e-17
? Оказывается, все эти перемножения с плавающей запятой заставляют уже думать о распространении ошибки. Здесь слишком много нюансов для этой статьи, но суть в том, что нужно свести к минимуму умножения с плавающей запятой, чтобы избежать ошибок, которые накапливаются и вызывают проблемы.DFS — прекрасный алгоритм поиска. Если решение существует, оно его найдёт. Но ему не хватает ключевого свойства: он не обязательно находит самый короткий путь. Для нас это важно, потому что более короткий путь означает меньше прыжков и меньшую ошибку из-за умножений с плавающей запятой. Чтобы решить проблему, мы обращаемся к BFS.
Часть 2. Решение BFS
На этом этапе, если кандидат успешно реализовал рекурсивное решение DFS и остановился на нём, я обычно даю хотя бы слабую рекомендацию по найму этого кандидата. Он понял проблему, выбрал подходящий фрейминг и реализовал рабочее решение. Это наивное решение, поэтому я не настаиваю на его найме, но если он хорошо справился с другими собеседованиями, то не буду рекомендовать отказ.
Это стоит повторить: если сомневаетесь, то напишите наивное решение! Даже если оно не совсем оптимально, наличие кода на доске — уже достижение, и часто на его основе можно найти правильное решение. Скажу иначе: никогда не работайте впустую. Скорее всего, вы подумали о наивном решении, но не хотели его предлагать, потому что знаете, что оно не оптимально. Если вы прямо сейчас готовы выложить лучшее решение, это прекрасно, но если нет, то зафиксируйте достигнутый прогресс, прежде чем переходить к более сложным вещам.
С этого момента поговорим об улучшениях алгоритма. Основные недостатки рекурсивного решения DFS заключаются в том, что оно рекурсивно и не минимизирует количество умножений. Как мы скоро увидим, BFS минимизирует количество умножений, и его тоже очень сложно реализовать рекурсивно. К сожалению, нам придётся отказаться от рекурсивного решения DFA, поскольку для его улучшения потребуется полностью переписать код.
Без дальнейших церемоний, представляю итеративный подход на основе BFS:
from collections import deque
def bfs(rate_graph, start, end):
to_visit = deque()
to_visit.appendleft( (start, 1.0) )
visited = set()
while to_visit:
node, rate_from_origin = to_visit.pop()
if node == end:
return rate_from_origin
visited.add(node)
for unit, rate in rate_graph.get_neighbors(node):
if unit not in visited:
to_visit.appendleft((unit, rate_from_origin * rate))
return None
Эта реализация функционально сильно отличается от предыдущей, но если внимательно посмотреть, она делает примерно то же самое, с одним существенным изменением: в то время как рекурсивный DFS сохраняет состояние дальнейшего маршрута в стеке вызовов, эффективно реализуя стек LIFO, итеративное решение сохраняет его в очереди FIFO.
Отсюда вытекает свойство «кратчайший путь / наименьшее число умножений». Мы посещаем узлы в том порядке, в котором они встречаются, и таким образом получаем поколения узлов. Первый узел вставляет своих соседей, а затем мы посещаем этих соседей по порядку, всё время прикрепляя их соседей и так далее. Свойство кратчайшего пути вытекает из того, что узлы посещаются в порядке их расстояния от источника. Поэтому, когда мы сталкиваемся с местом назначения, мы знаем, что нет более раннего поколения, которое могло бы к нему привести.
В этот момент мы почти закончили. Сначала нужно ответить на несколько вопросов, и они заставляются вернуться к первоначальной постановке проблемы.
Во-первых, самое тривиальное, что делать, если исходная единица измерения не существует? То есть мы не можем найти узел с заданным именем. На практике нужно выполнить некоторую нормализацию строк, чтобы Фунт, ФУНТ и lb указывали на один узел «фунт» (или какое-то другое каноническое представление), но это выходит за рамки нашего вопроса.
Во-вторых, что делать, если между двумя единицами нет преобразования? Напомним, что в исходных данных только преобразования между единицами, и оно не даёт никаких указаний на то, можно ли получить из одной конкретной единицы другую. Это сводится к тому, что преобразования и пути прямо эквивалентны, поэтому если между двумя узлами нет пути, то нет преобразования. На практике вы в конечном итоге получаете несвязанные острова единиц измерения: один для расстояний, один для весов, один для валют и т. д.
Наконец, если внимательно посмотреть на граф выше, оказывается, что вы не можете произвести конверсию между хэндами и световыми годами с таким решением. Направление связей между узлами означает, что от хэнда к световым годам нет пути. Впрочем, это довольно легко исправить, потому что преобразования можно обратить в другую сторону. Мы можем изменить наш код инициализации графа следующим образом:
def add_conversion(self, orig, dest, rate):
'Insert a conversion into the graph. Note we insert its inverse also.'
if orig not in self.graph:
self.graph[orig] = {}
self.graph[orig][dest] = rate
if dest not in self.graph:
self.graph[dest] = {}
self.graph[dest][orig] = 1.0 / rate
Часть 3. Оценка
Готово! Если кандидат дошёл до этого момента, то я с большой вероятностью буду рекомендовать его к найму. Если вы изучали информатику или прошли курс алгоритмов, то можете спросить: «И этого действительно достаточно, чтобы пройти собеседование у этого парня?», на что я отвечу: «По сути, да».
Прежде чем вы решите, что вопрос слишком простой, давайте рассмотрим, что должен сделать кандидат, чтобы достичь этой точки:
- Понять вопрос
- Построить сеть преобразований в виде графа
- Понять, что коэффициенты можно сопоставить с рёбрами графа
- Увидеть возможность использования алгоритмы поиска для достижения этой цели
- Выбрать свой любимый алгоритм и изменить его, чтобы отслеживать коэффициенты
- Если он реализовал DFS как наивное решение, осознать его слабые стороны
- Реализовать BFS
- Отступить назад и изучить крайние случаи:
- Что, если нас cпросят о несуществующем узле?
- Что делать, если коэффициент преобразования не существует?
- Что, если нас cпросят о несуществующем узле?
- Осознать, что обратные преобразования возможны и, вероятно, необходимы
Этот вопрос легче предыдущих, но при этом так же труден. Как и во всех предыдущих вопросах, кандидат должен совершить мысленный прыжок от абстрактно сформулированного вопроса к алгоритму или структуре данных, которая открывает путь к решению. Единственное, что здесь итоговый алгоритм менее продвинутый, чем в других вопросах. Вне этого алгоритмического материала действуют те же требования, особенно в отношении крайних случаев и корректности.
«Но подождите!, — вы можете спросить. — Разве Google не одержима сложностью рантайма? Вы даже не спросили о временной или пространственной сложности этой проблемы. Да ну!» Вы также можете спросить: «Погодите, вы же давали оценку "настоятельно рекомендую к найму"? Как её получить?» Очень хорошие вопросы, оба. Это приводит нас к нашему заключительному дополнительному бонусному раунду…
Часть 4. Можно ли сделать лучше?
В этот момент я хотел бы поздравить кандидата с хорошим ответом и дать понять, что всё дальнейшее — просто бонус. Когда давление исчезнет, мы сможем начать творить.
Итак, какова сложность выполнения BFS? В худшем случае мы должны рассмотреть каждый отдельный узел и ребро, что даёт линейную сложность
O(N+E)
. Это поверх такой же сложности O(N+E)
построения графа. Для поисковой системы это, вероятно, хорошо: тысячи единиц измерения достаточно для большинства разумных приложений, а выполнение поиска в памяти по каждому запросу не является чрезмерной нагрузкой.Тем не менее, можно сделать лучше. Для мотивации рассмотрим, как этот код вставляется в поисковую строку. Преобразования некоторых нестандартных единиц встречаются чуть чаще, поэтому мы будем вычислять их снова и снова. Каждый раз выполняется поиск, вычисляются промежуточные значения и т. д.
Часто предлагают просто кэшировать результаты вычисления. Всякий раз, когда вычисляется преобразование единиц, мы всегда можем просто добавить ребро между двумя преобразованиями. В качестве бонуса, мы получим обратное преобразование, причём бесплатно! Готово?
Действительно, это даст нам асимптотически постоянное время поиска, но будет стоить хранения дополнительных рёбер. Это на самом деле становится довольно дорогим: со временем мы будем стремиться к полному графу, поскольку все пары преобразований постепенно вычисляются и сохраняются. Число возможных рёбер в графе составляет половину квадрата числа узлов, поэтому для тысячи узлов нам понадобится полмиллиона рёбер. Для десяти тысяч узлов — около пятидесяти миллионов и т. д.
Выходя за рамки поисковой системы, для графа из миллиона узлов мы стремимся к половине триллиона рёбер. Такое количество просто неразумно хранить, плюс мы тратим время на вставку рёбер в граф. Мы должны сделать лучше.
К счастью, есть способ добиться постоянного времени для поиска коэффициентов, без квадратичного роста пространства. На самом деле, почти всё необходимое уже у нас прямо под носом.
Часть 4. Постоянное время
Итак, тотальное кэширование на самом деле близко к оптимальному решению. В этом подходе мы (в конечном итоге) получаем рёбра между всеми узлами, то есть наше преобразование сводится к поиску одного ребра. Но действительно ли нужно хранить преобразования из каждого узла в каждый узел? Что, если мы просто сохраним коэффициенты преобразования от одного узла ко всем остальным?
Взглянем ещё раз на решение BFS:
from collections import deque
def bfs(rate_graph, start, end):
to_visit = deque()
to_visit.appendleft( (start, 1.0) )
visited = set()
while to_visit:
node, rate_from_origin = to_visit.pop()
if node == end:
return rate_from_origin
visited.add(node)
for unit, rate in rate_graph.get_neighbors(node):
if unit not in visited:
to_visit.appendleft((unit, rate_from_origin * rate))
return None
Посмотрим, что здесь происходит: мы начинаем с исходного узла, и для каждого узла, с которым сталкиваемся, вычисляем коэффициент преобразования от источника к этому узлу. Затем, как только прибываем в пункт назначения, мы возвращаем коэффициент между исходным и конечным пунктами и отбрасываем промежуточные коэффициенты.
Эти промежуточные коэффициенты являются ключевыми. А что, если мы их не выбросим? А что, если вместо этого мы их запишем? Все самые сложные и непонятные поиски становятся простыми: чтобы найти отношение A к B, сначала найдём отношение X к B, затем разделим его на отношение X к A, и всё готово! Визуально это выглядит так:
![](https://habrastorage.org/getpro/habr/post_images/284/a08/b6c/284a08b6cb6ef95af556422fa3c604f3.png)
Обратите внимание, что между любыми двумя узлами не больше двух рёбер
Оказывается, для вычисления этой таблицы нам почти не нужно изменять решение BFS:
from collections import deque
def make_conversions(graph):
def conversions_bfs(rate_graph, start, conversions):
to_visit = deque()
to_visit.appendleft( (start, 1.0) )
while to_visit:
node, rate_from_origin = to_visit.pop()
conversions[node] = (start, rate_from_origin)
for unit, rate in rate_graph.get_neighbors(node):
if unit not in conversions:
to_visit.append((unit, rate_from_origin * rate))
return conversions
conversions = {}
for node in graph.get_nodes():
if node not in conversions:
conversions_bfs(graph, node, conversions)
return conversions
Структура преобразований представлена словарём единицы A в двух значениях: корень для связанного компонента единицы A и коэффициент преобразования между корневой единицей и единицей A. Поскольку мы вставляем единицу в этот словарь при каждом посещении, то можем использовать пространство ключей этого словаря в качестве набора посещений вместо использования выделенного набора посещений. Обратите внимание, что у нас нет конечного узла, и вместо этого мы перебираем узлы, пока не закончим.
За пределами этого BFS есть вспомогательная функция, которая перебирает узлы в графе. Всякий раз, когда она сталкивается с узлом вне словаря преобразования, то запускает BFS, начиная с этого узла. Таким образом, мы гарантированно свернём все узлы в их связанные компоненты.
Когда нужно найти соотношение между единицами, мы просто используем структуру преобразований, которую только что вычислили:
def convert(conversions, start, end):
'Given a conversion structure, performs a constant-time conversion'
try:
start_root, start_rate = conversions[start]
end_root, end_rate = conversions[end]
except KeyError:
return None
if start_root != end_root:
return None
return end_rate / start_rate
Ситуация «нет такой единицы» обрабатывается прослушиванием исключения при доступе к структуре преобразований. Ситуация «нет таких преобразований» обрабатывается сравнением корней двух величин: если у них разные корни, значит, они обнаружены через два разных вызова BFS, то есть находятся в двух разных связанных компонентах, и поэтому никакого пути между ними не существует. Наконец, мы выполняем преобразование.
Вот так! У нынешнего решения при предварительной обработке сложность
O(V+E)
(не хуже, чем у предыдущих решений), но она также ищет с постоянным временем. Теоретически, мы удваиваем требования к пространству, но бoльшую часть времени нам больше не нужен исходный граф, поэтому мы можем просто удалить его и использовать только этот. При этом пространственная сложность на самом деле меньше, чем исходный граф: тот требует O(V+E)
, потому что должен хранить все рёбра и вершины, а эта структура требует только O(V)
, потому что нам больше не нужны рёбра.Результаты
Если вы продвинулись так далеко, то можете вспомнить, что изначально один из вопросов был в том, чтобы проверить, сможет ли более простая проблема по-прежнему оставаться полезной в выборе достойных кандидатов и может ли она дать лучшую картину способностей. Я хотел бы дать какой-то окончательный научный ответ, но у меня есть только истории из личного опыта. Тем не менее, я заметил некоторые положительные результаты.
Если разбить решение этой задачи на четыре препятствия (обсуждение фрейминга, выбор алгоритма, реализация, обсуждение выполнения за постоянное время), то к концу собеседования почти все кандидаты дошли до «выбора алгоритма». Как я и подозревал, обсуждение фрейминга стало хорошим фильтром: кандидаты либо сразу выводили граф, либо никак не могли к нему прийти, несмотря на существенные подсказки.
Это уже сразу полезный сигнал. Я могу понять, когда человек не знает продвинутых или неясных структур данных, потому что будем честными, вам нечасто придётся реализовывать непересекающиеся множества. Но графы — фундаментальная структура данных и преподаётся в рамках практически любого вводного курса по этой теме. Если кандидат изо всех сил пытается понять их или не может их легко применить, вероятно, ему будет трудно добиться успеха в Google (по крайней мере, в моё время там, не знаю как сегодня).
С другой стороны, выбор алгоритма оказался не особенно полезным источником сигнала. Люди, которые прошли стадию фрейминга, обычно без особых проблем добирались до алгоритма. Подозреваю, это связано с тем, что алгоритмы поиска почти всегда преподаются вместе с самими графами, поэтому, если кто-то знаком с одним, то знает и другое.
Реализация оказалась непростой. У многих людей не было проблем с рекурсивной реализацией DFS, но, как я уже упоминал выше, эта реализация не подходит для продакшна. К моему удивлению, итеративные реализации BFS и DFS, похоже, не очень знакомы людям, и даже после явных подсказок они часто плавали в теме.
В моём представлении любой, кто прошёл этап реализации, уже заслужил от меня рекомендацию «Нанимать», а этап обсуждения постоянного времени выполнения просто бонусный. Хотя в статье мы подробно рассмотрели решение, на практике обычно более продуктивным является устное обсуждение, а не написание кода. Очень немногие кандидаты сразу могли высказать решение. Мне часто приходилось давать существенные подсказки, и даже тогда многие люди не могли его найти. Это нормально: как и предполагалось, рейтинг «настоятельно рекомендую» трудно заслужить.
Но подождите, это ещё не всё!
В основном, мы рассмотрели проблему целиком, но если вы заинтересованы в её дальнейшем изучении, то есть целый ряд расширений, в которые я не буду погружаться. Оставляю следующие упражнения для читателя:
Во-первых, разминка: в решении для постоянного времени, которое я выложил, я произвольно выбрал корневой узел каждого подключённого компонента. В частности, я использую первый узел компонента, с которым мы сталкиваемся. Это не оптимально, потому что для всех известных значений мы выбрали какой-то узел, хотя какой-то другой узел может быть ближе к центру с более короткими путями ко всем другим узлам. Ваша задача состоит в том, чтобы заменить этот произвольный выбор на тот, который минимизирует количество требуемых умножений и минимизирует распространение ошибки с плавающей запятой.
Во-вторых, во всех рассуждениях предполагалось, что все равные пути через граф равны изначально, что не всегда так. Один из интересных вариантов этой проблемы — конвертация валют: узлы — это валюты, а рёбра от A до B и наоборот — это цены на предложение/спрос каждой валютной пары. Мы можем перефразировать вопрос о конверсии единиц как вопрос о валютном арбитраже: реализовать алгоритм, который, учитывая граф конвертации валюты, вычисляет через граф цикл, который даст трейдеру больше денег, чем начальная сумма. Не учитывайте никаких комиссий за транзакции.
Наконец, настоящая жемчужина: некоторые единицы выражаются в виде комбинации различных базовых единиц. Например, ватт определяется в системе СИ как кг•м?/с?. Последняя задача заключается в расширении этой системы для поддержки преобразования между этими единицами, учитывая только определения основных единиц СИ.
Если у вас есть вопросы, не стесняйтесь обращаться ко мне на reddit.
Заключение
Когда я начал задавать эту задачу на собеседованиях, то надеялся, что она будет немного легче предыдущих. Эксперимент был в значительной степени успешным: если кандидат сразу видел решение, то обычно быстро справлялся с задачей, так что у нас оставалось много времени, чтобы поговорить о продвинутом решении с постоянным временем. Люди, которые испытывали затруднения, как правило, спотыкались в местах, отличных от алгоритмического концептуального скачка: кандидат не мог подходящим способом полностью сформулировать проблему или набросал хорошее решение, но не смог перевести его в рабочий код. Независимо от того, где и когда они испытывали затруднения, я обнаружил, что могу получить значимую информацию о сильных и слабых сторонах кандидатов.
Надеюсь, вы нашли полезной эту статью. Понимаю, что здесь может быть не так много приключений с алгоритмами, как в некоторых предыдущих статьях. На собеседованиях разработчиков принято обильно обсуждать алгоритмы. Но правда в том, что значительные сложности возникают при использовании даже простого, хорошо известного метода. Весь код — в репозитории этого цикла статей.
Комментарии (72)
andreyverbin
15.09.2019 12:42Отсюда вытекает свойство «кратчайший путь / наименьшее число умножений»
BFS это метод перебора узлов графа, как и DFS у него нет свойства находить кратчайший путь.
andreyverbin
15.09.2019 12:57Оказывается у BFS есть такое свойство.
h1pp0
16.09.2019 07:43Тут надо сделать важную оговорку, что у всех рёбер/вершин одинаковый вес, а это не классическая постановка проблемы поиска кратчайшего пути.
Tarik02
15.09.2019 20:55Отчасти, вы правы. Но только если рассматривать значение узла как путь. Автор имел ввиду минимальное количество узлов = умножений. То-есть в данной задаче длина всех узлов равна.
marsermd
15.09.2019 22:44В невзвешенном графе (веса всех рёбер равны единица), BFS — это алгоритм поиска кратчайшего пути.
kdmitrii
16.09.2019 07:43BFS всегда находит кратчайший путь в невзвешеном графе(либо если все веса равны). Это просто из определения BFS следует.
kabuto
15.09.2019 15:39Кажется это решается с помошью dimensional table. Надо только граф ориентировать в таблицу с расстояниями.
grinCo
15.09.2019 20:32+1Я подозреваю, что на собеседовании валились люди, получившие образование в метрической системе. У них когнитивный диссонанс от неоптимального решения. А товарищ явно пушил в сторону деревьев.
beerchaser
15.09.2019 22:27+1Имхо на собеседовании валились люди с инженерным подходом к решению задачи. Irl обычно не создаётся конвертор всего во все. Первый вопрос, который должен задать грамотный специалист — вопрос о применимости данной системы. То что приведено в качестве примера — неприменимо от слова совсем именно по причине быстрой деградации точности. Второй вопрос: оптимальный путь для каждого значения нужно найти только один раз, причем это путь не до искомой системы измерения, а до промежуточной общей (например СИ или любой другой). Полученное значение зафиксировать в таблице и поставить отметку о необходимости повышения точности. При таком подходе время первичного поиска пути конвертации и как следствие оптимальность алгоритма не будет иметь решающего значения, т.к. все остальные конвертации по данному направлению будут иметь фиксированное время (согласен с Nomad1).
grinCo
16.09.2019 00:46+1Я про то, что товарищ, ИМХО демонстрировал то на что его натаскали в американском ВУЗе — питон + деревья. При этом он демонстрировал знания без понимания. Это заученный материал, не переваренный. При этом он ожидал именно этого и от собеседуемых.
Я думаю отвалились на его собеседованиях слабые и сильные программисты, а средние прошли.
NoRegrets
15.09.2019 23:17+2Прочитал задачку, скроллю дальше, вижу графы. Понимаю, почему у гугла не получился гуглплюс и овер 9000 других проектов. Е...., на всю голову.
beerchaser
16.09.2019 00:37И наверное, я бы эту задачу начал с построения множества возможных элементов преобразования для каждого элемента конвертации. Тогда задача решается просто: берём множества возможных преобразований запрошенных элементов конвертации и находим их пересечение (поиск промежуточного общего). Если не пересекаются — не судьба. Если пересекаются — сразу имеем кратчайший путь конвертации. Добавление нового элемента конвертации сводится к формированию его собственного множества с элементами конвертации, в которые он умеет конвертировать, и к добавлению этого элемента конвертации в те множества элементов конвертации, которые входят в сформированное собственное множество данного элемента.
harlong
16.09.2019 03:32А насколько рационально тратить ресурсы при поиске ответа на каждый запрос в поисковике? Не будет ли проще принять одну из единиц как «стандартную» (например, тот же метр из СИ), и просто при добавлении в базу любой новой единицы пересчитывать ее в метры, и хранить в БД один коэффициент? Тогда задача из топика сведется к двум банальным арифметическим действиям для любой из пар единиц измерения. Да и проверка возможности/невозможности решения сведется к запросу «для обеих ли заданных единиц измерения существуют записи в БД».
beerchaser
16.09.2019 06:39Проще, но проблема в том, что отношения к «стандартной» единице в общем случае для конвертируемых единиц в анализируемом наборе данных может не существовать. Короче, и вы тоже мыслите как инженер и собеседование не прошли :)
grinCo
16.09.2019 07:24В моем мире инженер — это похвала. :)
Кстати, многих запутал перевод.
Given a list of conversion rates (formatted in the language of your choice) as a collection of origin unit, destination unit, and multiplier, for example:
превратилось в
Приведите список коэффициентов пересчёта (отформатированный на выбранном вами языке) в виде набора начальных единиц измерения, конечных единиц и множителей, например:
Т.е. если строго говорить, то решение гуглера верно, если принять за аксиому, что постановка задачи верна. Но обычно так не бывает на собеседованиях — обычно тебе разрешают задавать вопросы. И вот тут первым делом нужно спросить у него, осознает ли он, что текущая постановка задачи ведет к не оптимальному решению.
katzen
16.09.2019 11:36Плохо, когда инженеры не проходят собеседование.
harlong
17.09.2019 01:25На самом деле мой косяк тут тоже есть — должен был перед началом реализации уточнить «а не будет ли возможным в условии задачи двух разных систем измерения длины, не имеющих способа пересчета из одной в другую». За то, что не подумал об этом меня и назвали инженером. )))
beerchaser
17.09.2019 05:00Назвали не за то, что не подумали, а за подход к решению. Автор пляшет от общего, сферического, и как следствие, неоптимального решения. Причем задачу решает в лоб. «Инженерный» подход (в моем понимании :) ) предполагает использование частного решения, с учётом известных проектировщику ограничений. Это ограничивает область применимости, но повышает эффективность. Т.е. для забивания гвоздя используется не синхрофазатрон, а другой, более удобный для этого инструмент.
То, что делает автор, допустимо и даже приветствуется в исследовательской работе, но недопустимо для решения, которое реализуется в железе.
Нижe предлагают для решения задачи использовать непересекающиеся множества (DSU). Судя по описанию, это то, к чему я пришел после непродолжительного анализа возможных путей решения задачи ( знал, что велосипед изобретаю :)). Исходя из этого могу предположить, что этап аналитической работы по изучению существующих алгоритмов и решений был пропущен в пользу инструмента, для которого уже есть наработки, что не есть хорошо при проектировании систем.
Печаль заключается в том, что автор, участвуя в подборе специалистов, во-первых, определяет технические подходы компании к решению задач; во-вторых, влияет на развитие тех специалистов, которыми руководит.
Janycz
16.09.2019 07:43Хорошая статья. Но отмечу, что не все единицы измерения конвертируются через умножение/деление на число, порой преобразования бывают посложнее, например логарифмическое или полиномиальное. Хотя решение не сильно поменяется, просто ребрам будут приписываться не числа, а функции. А путь тогда будет, по сути, соответствовать композиции функций.
tyomitch
16.09.2019 09:38Не знаю ни одного логарифмического преобразования, а из полиномиальных — только линейные с константой (между температурными шкалами).
Я бы отметил другое — что есть «сложные единицы», чей набор практически не ограничен. Например, редко используемые единицы плотности «хандредвейт на акр» (сwt/ac) и «хандредвейт на тысячу квадратных футов» (cwt/MSF) гугловскому калькулятору неизвестны — хотя по отдельности он понимает и хандредвейты, и акры, и футы. А ведь сложные единицы могут быть и ещё экзотичнее, вроде «пудов на квадратный аршин».ankh1989
16.09.2019 11:06Там со звуком вроде логарифмы: децибелл это логарифм чего то.
tyomitch
16.09.2019 11:14Таки да, но ни в какую другую единицу децибел не переводится.
ankh1989
16.09.2019 11:30-1Тем не менее это прецедент и серьёзный. Раньше у нас были пары преобразований типа "1 метр = 3 фута" и неявное допущение, что вот это "=" означает умножение. Теперь же мы добавляем пару "1 децибел = 10 аудиоджоулей", но "=" здесь означает логарифм. И вся эта хитрая конструкция с графом рушится: как бы будем сранивать какое преобразование короче если слева и справа трехэтажная формула с логарифмами?
Janycz
16.09.2019 11:43Как я описывал, ребрам приписываем не числа, а функции. А путь тогда будет, по сути, соответствовать композиции функций.
ankh1989
16.09.2019 11:45+1Цель поиска — найти кратчайший путь. Как мы будем сравнивать эти композиции функций?
Janycz
16.09.2019 11:50Кратчайший путь это, очевидно, тот, в котором меньше ребер. И тогда в композиции будет меньше функций.
tyomitch
16.09.2019 11:52В контексте данной статьи, кратчайший путь — это тот, который вносит наименьшую погрешность при вычислениях.
Dolios
16.09.2019 15:38Нет, это именно количество преобразований, если в контексте статьи. BFS ничего про погрешность не знает.
tyomitch
16.09.2019 15:49Если все преобразования — это умножения (как в статье), то важно только их количество. Если используются разные функции, тогда важно не только количество.
ptyrss
16.09.2019 16:52А если учитывать, что точность сильнее теряется подальше от 1, то становится ещё интереснее. Что лучше, умножить 2 числа 10 порядков или 10 раз но 2 но 0.5 (пример грубый).
tyomitch
16.09.2019 11:48Не знаю, что такое «аудиоджоуль». И гугл тоже не знает.
Если это единица энергии, то децибел в неё не переводится.
vassabi
16.09.2019 11:33она переводится в безразмерные «разы» — т.е. усиление интенсивности звука в 10 раз — 10 децибел, в 100 раз — 20 децибел, а в 10000 раз — 40 децибел.
Посмотрите еще в сторону площадей и объемов — там квадратные и кубические см к км нелинейные.tyomitch
16.09.2019 11:45Что не так с площадями и объёмами?
1 км3 = 1015 см3, соотношение вполне линейное.
Fedorkov
16.09.2019 13:01Абсолютная шкала тоже существует, за ноль децибел принимается порог слышимости.
katzen
16.09.2019 11:46+1Это же безразмерная величина, по сути. (деци) Бел — строго говоря, когда-то и кому-то в меру удобное название психофизиологического приближения к логарифму.
vitalijs
16.09.2019 07:43Интересно, куда потом в пучинах Гугла пропадают все эти умнейшие люди, которые на собеседованиях решают подобные задачи
SmnTin
16.09.2019 10:59Можно ещё быстрее за O(log n) с помощью Heavy-Light Decomposition.
Представим всё в виде дерева (леса). По факту между каждой парой вершин есть два ориентированных ребра. В одну сторону мы делим, а в другую сторону умножаем на одну и ту же величину. Поэтому можно мысленно представить неориентированный граф и найти в нём любое остовное дерево. Выберем в качестве корня центроид для лучшей константы. И снова мысленно направим рёбра в сторону от корня к листам. Назначим, каждому ребру коэффициент так, чтобы в сторону от корня к листу умножать, а в обратную делить. Теперь можно сделать HLD — разбить дерево на log путей. Затем на каждом пути сделать структуру, позволяющую быстро считать произведение. Мы можно использовать ту же идею, что и в частичных суммах: посчитаем произведения на префиксах. Ответ: pref[r] / pref[l — 1]. Всё построение выполняется за O(V + E), т. к. используются только обходы в глубину.
Теперь как искать ответ. Коэффициент между двумя единицами измерения — произведение/отношение коэффициентов на пути. Простой путь в дереве между любой парой вершин единственнен; — это путь a -> lca(a, b) -> b. Ответ: f(lca(a, b) -> b) / f(a -> lca(a, b)). Он ищется за O(log n) — не более log путей на запрос, в каждом из которых операция за O(1)ptyrss
16.09.2019 13:04Можно. А чем это будет лучше сразу системы непересекающихся множеств, которая за 2 умножения/деления всегда даёт ответ? Добавление в систему в среднем O(1). Построение всей системы строго O(N) (1 BFS или подобное из корневой).
А вообще задача мне показалась как-то ну очень простой. Граф пришёл в голову сразу, отсчёт от центра тоже.
tyomitch
16.09.2019 15:00А вообще задача мне показалась как-то ну очень простой.
Всё верно.
Принцип собеседования в гугле — начать с очень простой задачи, и на протяжении часа добавлять усложнения.SmnTin
16.09.2019 16:52Тогда непонятно, почему автор всю статью разбирал такое простое решение, если у неё существуют гораздо более эффективные, но не сильно более сложные.
SmnTin
16.09.2019 16:49Хмм, действительно отличное решение. И ошибка будет меньше. Как-то я просто при виде задачи сразу подумал над быстрым поиском пути в дереве, а до DSU не догадался.
beerchaser
17.09.2019 05:03Спасибо! Пришел практически к этому путем размышлений. Теперь буду знать как это называется — DSU!!! :)
achekalin
16.09.2019 12:22Любой американец, который путешествовал за пределами США, знает, что большая часть мира для измерения расстояний использует таинственную единицу «километр»
Вспомнилось: "There is a world outside US, yes!"
Что касается перевода единиц, то, интуитивно (но с условием, что единицы одного типа: скажем, длину в длину переводим, а не площадь в объем) же, кажется, что достаточно выделить одну единицу как основную, эталонную, от которой остальные зависят, так сразу получаем возможность выразить преобразуемое число в тих эталонных единицах, а потом число эталонных единиц в целевых единицах. Да, есть вопрос точности, но граф как таковой оценку точности преобразования также дает опосредованную, а точность, по сути, будет зависеть от округления каждой операции. Но это, кажется, слишком простое объяснение для собеседования девелопера — тут даже код красиво не напишешь на доске.
Sedlo
16.09.2019 13:50Пересчет единиц измерения — вполне себе рядовая задача для консультанта по ERP не важно какой: SAP, 1C или Axapta.
У сварщика техкарта — в метрах/сантиметрах сварного шва
Кладовщица выдает электроды: в штуках, но может и в коробках.
Закупер закупает: в килограммах, но может и в ящиках.
Итого измеряемые величины — единицы измерения
а) длина — метры и сантиметры
б) количество — штуки, коробки, ящики
в) масса — килограммы
… и в рамках всего одного техпроцесса — электросварка
Alex_ME
16.09.2019 14:19К своему стыду (после прочтения комментариев) первой мыслью таки было "кратчайший путь на графе". Второй мыслю было "привести к СИ".
ovsv
16.09.2019 15:55Да, статья познавательная. Но какое это имеет отношение к реальному программированию?
Если кто-то скажет, что имеет — он бы не прошел у меня собеседование.Nomad1
16.09.2019 16:42Когда-то мой знакомый ПМ в шутку сформулировал термин превентивное планирование — обработка и переформулирование задачи таким образом, чтобы ее можно было решить без написания программы :)
andreyverbin
16.09.2019 17:39Не поверите, прямо сейчас решаю точно эту задачу. Имея набор пар валют нужно рассчитать средний курс одной валюты в другой, желательно быстро, желательно не потратив на это кучу памяти. На работу к вам не пойду, у вас похоже задачи тухлые очень, вида «вставить данные из формочки в БД».
FODD
16.09.2019 18:04Как посредственный программист я бы решил этот вопрос без графов.
Выделил бы базовые типы величин (размер, вес, температура, площадь).
Каждый тип дополнил бы некоей «идеальной величиной», в которую удобно конвертировать остальные.
В итоге любое преобразование занимает ровно 2 операции (из одной в абсолютную, из абсолютной в нужную).
Проблему невозможных преобразований (из литра в метры) решал бы за меня полиморфизм — если единицы от разных абстрактных классов, то они одна из них просто не залезет в метод конвентера.Alex_ME
16.09.2019 21:50У вас нет классов, методов и прочего. Есть, условно говоря, текстовый файлик на вход. И там может быть
увррик деннон 3.124 деннок зазак 484.005 ...
И пока вы не прочитаете файл, вы даже не знаете, какие там есть единицы: относящиеся к одной величине (один граф) или к нескольким (два и более несвязанных подграфа). Данный формат входных значений и данное решение не покрывает случай производных единиц (например, Н/м -> Па), но автор об этом говорит в конце.
Nomad1
Спасибо за перевод!
Эта статья подводит нас к очень интересной проблеме: американцы привыкли работать с несистемными размерами, поэтому для них естественно использовать цепочку преобразований для перевода попугаев в футы. Первое же, что приходит в голову человеку, знакомому с СИ — перевести все единицы в СИ и назад. Никакого графа, поиска в глубину и т.д. — все «общеизвестные преобразования» должны быть заранее вбиты в таблицу с коэффициентами вроде «1 фут = 0.3048 метра» и все вычисления должны происходить через метры. Если у нас нет таблицы таких «общеизвестные преобразований» в метры и программа стартует с пустой таблицей, то первым делом ее надо «обучить», наполнив эту таблицу. Если данные для обучения выданы в произвольном порядке, то их надо отсортировать так, чтобы они всегда опирались на уже существующие преобразования.
В любом случае, финальное вычисление после этого будет делаться в два умножения. Я просто не могу себе представить как у автора получился «интуитивный подход», это для нас совершенно неестественно.
AlexanderplUs
Таблица преобразований — это один из входных параметров задачи и она фиксирована. То есть оперировать можно только с этими коэффициентами и там далеко не для всех пар величин есть коэффициент.
Для примера с метрами, представьте что есть преобразование светового года как в метра, так и в футы, а вот из хендов есть преобразование только в футы и никакого в метры. Вот тогда и приходится искать путь среди связей величин, чтобы получить ответ.
Nomad1
Но задача отлично решается при наличии полной таблицы преобразований в метры. Значит перед работой надо неполную таблицу сделать полной, это подготовительная операция. А само преобразование уже потом делается в два умножения. Конечно, мы можем где-то потерять точность из-за количества операций с плавающей запятой, но это тоже решаемо, н-р, рациональными дробями.
tyomitch
Хотел бы я посмотреть, как ваша реализация рациональных дробей будет работать со значениями навроде 1.0737e?17
lgorSL
Кстати, нормально будет работать. Потому что в double максимальные и минимальные степени могут быть очень большими и за этот предел будет проблематично вылезти.
В умножении "очень большого числа на очень маленькое" потерь точности практически нет, в отличие от сложения.
tyomitch
При чём тут double? Nomad1 предложил вместо плавающей запятой использовать рациональные дроби.
Пример потери точности при умножении double есть прямо в тексте статьи.
Nomad1
Во-первых, кустарной реализации на собеседовании (да и в коммерческой разработке) быть не должно, потому что рациональные дроби не делал только ленивый. Если говорить о .Net, то разумно использовать, н-р, Rationals.Net, где числитель и знаменатель задаются BigInteger — оберткой вокруг массива чисел, без ограничений по размеру и порядку. Для C++ берем cpp_rational с такими же свойствами.
Во-вторых, дробь с e-17 это совсем не много, задается 64-битными числами, пусть и близко к пределу.
В-третьих, при некотором желании (и желании сделать пару велосипедов) можно использовать представление с мантиссой и экспонентой (даже тот же double) и в рациональных дробях. Ошибка будет накапливаться только при очень большой разнице между исходной и результирующей величиной (ангстремы в парсеки).
tyomitch
Вот как раз на собеседовании в гугл от вас ожидают реализовать то, что в коммерческой разработке принято брать готовым, не разбираясь, что внутри.
А то я тоже у них на какой-то вопрос по поводу потери точности ляпнул «тогда возьмём длинную арифметику», после чего до конца часа писал на доске реализацию умножения десятичных дробей произвольной длины, да так и потонул в обработке разных граничных случаев.
Nomad1
Ну тут я вам не отвечу, я у гугла не был на собеседовании :)
Здравый смысл говорит о том, что рациональные числа в boost появились в 1999году. Через 20 лет реализовывать их заново это, кхм, странно. Ну может только чтобы впечатлить собеседника.
ankh1989
Откуда берётся эта потеря точности? double это пара
(m, e) = m*2**e
, гдеm
— 10 бит мантиссы, иe
— 52 бита экспоненты. У мантиссы есть погрешностьd(m) >= 2**-52
. У экспоненты погрешности нет, за исключением случая когда 10 бит не хватает (но это бы означало, что мы оперируем с числами порядка2**1024
). Когда мы умножаем два числа, то получаемm1*m2*2*(e1+e2)
. Погрешность произведения здесьd(m1)+d(m2)
. Тоже самое при делении. Короче говоря, каждое умножение снижает точность на один бит, а всего битов 52. Допустим нам нужно 6 десятичных знаков точности как в этом примере. Это 20 бит. Значит мы можем спокойно потерять 32 бита точности. Чтобы потреять 32 бита точности нам нужен граф в котором кратчайшее расстояние между двумя вершинами равно 32. Нехилый такой граф. При желании конечно можно выдумать нереальный пример вроде "первести валюту WLP в индекс RKP" и единственная цепочка преобразований идёт через мутные офшорные акции коих 35.tyomitch
ankh1989
Ну и какой вывод? Считая вручную мы обычно не записываем на бумгае 15 знаков после запятой, а лишь 5-6 как в примере. 4 преобразвания с такой потерей точности и вот у нас ошибка в 5 знаке.
RomanArzumanyan
У континентальной Европы, Англии/США и Японии разные инженерные школы.
Вопрос культурных различий в этом контексте ничуть не хуже, чем умение применять алгоритмы на графах. Люди просто думают одни и те же мысли совершенно по-разному.
wataru
Это решение автор предложил в 4-ой части. Да, я тоже сразу подумал, что надо таблицу перобразований задавать с какой-то фиксированной велечиной, к которой все и приводить. Но это усложняет требования к таблице и алгоритм уже не применить, например, к намайненным с интернета данным.
Nomad1
Алгоритм все так же применяется, просто на другой стадии — на подготовке данных. Т.е. наша инженерная школа подразумевает очень простое и точное решение этой задачи — «видишь не-СИ значение, приведи его к СИ». В данной формулировке задача решается в два умножения. То, чего хочет автор — решение с помощью графа — нам кажется нелогичным, но при этом нормально такой подход использовать для разворчивания намайненных данных в таблицу, т.е. на подготовительном этапе. Тут уже можно проявить фантазию в поиске наименьшего количества конверсий, проставлении коэффициентов достоверности и т.д. Но конкретно представители нашей школы на этом собеседовании будут ошеломлены и обескуражены, ведь это уровень средней школы.
wataru
Это и есть финальный ответ, на 5+ (в части 4). Обходим граф один раз, строим таблицу с эталонной величиной и потом переводим туда-обратно все что надо.
Да, многие из Европы сразу бы спросили, а почему таблица такая кривая дана? Получили бы ответ, ну вот так вот. Других данных нет.
Это решение, да, очевиднее тем, кто работает с единицами си. Но тем, кто футы в мили переводит, гораздо инуитивнее делать переводы в несколько этапов, потому что 1231760 запомнить проще, чем 12, 36, 63360 и другие кривые числа. Именно поэтому входные данные такие.