Разбор задачи с собеседования Google: поиск соотношения

Автор оригинала: Alex Golec
  • Перевод


Добро пожаловать в очередную из серии статей с разбором задачек, которые я задавал на собеседованиях в Google, прежде чем их запретили после утечки. С тех пор я оставил работу инженера-программиста в Google и перешёл на должность менеджера по разработке в Reddit, но у меня всё ещё осталось несколько замечательных тем. К настоящему моменту мы разобрали динамическое программирование, возведение матриц в степень и синонимичность запросов. На этот раз совершенно новый вопрос.

Но сначала два замечания. Во-первых, работа в Reddit была потрясающей. Последние восемь месяцев я строил и возглавлял новую команду Ads Relevance и занимался организацией нового офиса разработки в Нью-Йорке. Как бы это ни было весело, к сожалению, я обнаружил, что до недавнего времени у меня не оставалось времени или энергии на блог. Боюсь, что я немного забросил эту серию. Извините за задержку.

Во-вторых, если вы следили за статьями, то после последнего выпуска могли подумать, что я начну копаться в вариантах синонимичности запросов. Хотя я хотел бы когда-то вернуться к этому, но должен признаться, что из-за смены работы потерял должный интерес к этой проблеме и пока решил отложить её. Впрочем, оставайтесь на связи! За мной должок, и я намерен его вернуть. Просто, ну знаете, чуть позже…

Быстрый отказ от ответственности: хотя собеседование кандидатов является одной из моих профессиональных обязанностей, этот блог представляет мои личные наблюдения, личные истории и личное мнение. Пожалуйста, не принимайте это за какое-либо официальное заявление от Google, Alphabet, Reddit или любого другого лица или организации.

Поиск нового вопроса


В предыдущей статье я описал один из своих любимых вопросов, который использовал в течение длительного времени, до неизбежной утечки. Предыдущие вопросы были увлекательными с теоретической точки зрения, но я хотел выбрать проблему, чуть более актуальную для Google как компании. Когда этот вопрос запретили, то я хотел найти замену с учётом нового ограничения: чтобы вопрос был проще.

Теперь это может показаться немного удивительным, учитывая печально известный процесс собеседований в Google. Но в то время более простая проблема имела смысл. Мои рассуждения состояли из двух частей. Первая прагматичная: кандидаты обычно не очень хорошо справлялись с предыдущими вопросами, несмотря на многочисленные намёки и упрощения, и я не всегда был полностью уверен, почему. Вторая теоретическая: процесс собеседования должен разделять кандидатов на категории «стоит нанимать» и «не стоит нанимать», и мне было любопытно, можно ли сделать это с вопросом немного попроще.

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

Хорошие интервью дают широкую картину сильных и слабых сторон кандидата. Для комитета по найму недостаточно просто сказать, что «он провалился»: комитет определяет, есть ли у кандидата специфические для компании качества, которые они ищут. Точно так же слова «он крут» не помогают комитету принять решение по кандидату, который силён в некоторых областях, но сомнителен в других. Я обнаружил, что более сложные вопросы слишком часто разделяют кандидатов по этим двум категориям. В этом свете «я не всегда уверен, почему у человека возникают проблемы» означает «неспособность продвинуться в этом вопросе сама по себе не рисует картину способностей этого кандидата».

Классификация кандидатов как «стоит нанимать» и «не стоит нанимать» не означает, что процесс собеседования должен отделять глупых кандидатов от умных. Я не могу вспомнить ни одного кандидата, который не был бы умным, талантливым и мотивированным. Многие пришли из отличных университетов, а остальные явно были исключительно мотивированы. Проход через телефонные собеседования — уже хорошее сито, и даже отказ на этом этапе не является признаком отсутствия способностей.

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

Я прочитал много комментариев reddit с жалобами на излишне сложные вопросы собеседования. Мне стало любопытно, можно ли по-прежнему сделать рекомендацию «достоин/не достоин» на более простой задаче. Я подозревал, что это даст полезный сигнал без лишней трепли нервов кандидата. Расскажу о своих выводах в конце статьи…

С этими мыслями я искал новый вопрос. В идеальном мире это достаточно простой вопрос, чтобы решить его за 45 минут, но с дополнительными вопросами, чтобы более сильные кандидаты проявили свои навыки. Он также должен быть компактным в реализации, потому что многие кандидаты по-прежнему пишут на доске. Большой плюс, если тема будет как-то связана с продуктами Google.

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

Вопрос


Поговорим об измерении расстояний. Хэнд — это единица измерения в четыре дюйма, которая обычно используется в англоязычных странах для измерения высоты лошадей. Световой год — ещё одна единица измерения, равная расстоянию, которое частица (или волна?) света пройдёт за определённое количество секунд, примерно равное одному земному году. На первый взгляд, у них мало общего друг с другом, кроме того, что они используются для измерения расстояния. Но оказывается, что Google может довольно легко их конвертировать:



Это может показаться очевидным: в конце концов, они обе измеряют расстояние, поэтому ясное дело, что есть преобразование. Но если подумать, немного странно: как они вычислили этот коэффициент конверсии? Ясно, что никто на самом деле не считал количество хэндов в световом году. На самом деле не нужно считать это напрямую. Вы можете просто использовать общеизвестные преобразования:

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



Рёбра помечены коэффициентом конверсии, на который вы должны умножить A, чтобы получить B.

Я почти всегда ожидал, что кандидат придумает такой фрейминг, и редко давал серьёзные подсказки для него. Я могу простить кандидата, который не замечает решения проблемы с использованием непересекающихся множеств или не слишком глубоко знаком с линейной алгеброй, чтобы реализовать решение, сводящееся к повторному возведению в степень матрицы смежности, но на любой учебной программе или курсе по программированию преподаются графы. Если у кандидата нет соответствующих знаний, это сигнал «не стоит нанимать».

В любом случае

Представление в виде графа сводит решение к классической проблеме поиска графа. В частности, здесь полезны два алгоритма: поиск в ширину (BFS) и поиск в глубину (DFS). При поиске в ширину мы исследуем узлы в соответствии с их расстоянием от начала координат:


Более тёмные синие цвета означают более поздние поколения

А при поиске в глубину мы исследуем узлы в том порядке, в каком они встречаются:



Более тёмные синие цвета также означают более поздние поколения. Обратите внимание, что мы на самом деле не посещаем все узлы

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

Но подождите, чего-то не хватает. Мы не хотим искать, существует ли путь, мы хотим найти коэффициент конверсии! Именно здесь кандидат должен совершить скачок: оказывается, вы можете модифицировать любой алгоритм поиска для вычисления коэффициента конверсии, просто сохранив дополнительное состояние по мере прохождения. Вот где иллюстрации перестают иметь смысл, так что давайте погрузимся прямо в код.

Во-первых, нужно определить структуру данных графа, поэтому используем это:

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просят о несуществующем узле?
    • Что делать, если коэффициент преобразования не существует?
  • Осознать, что обратные преобразования возможны и, вероятно, необходимы

Этот вопрос легче предыдущих, но при этом так же труден. Как и во всех предыдущих вопросах, кандидат должен совершить мысленный прыжок от абстрактно сформулированного вопроса к алгоритму или структуре данных, которая открывает путь к решению. Единственное, что здесь итоговый алгоритм менее продвинутый, чем в других вопросах. Вне этого алгоритмического материала действуют те же требования, особенно в отношении крайних случаев и корректности.

«Но подождите!, — вы можете спросить. — Разве 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, и всё готово! Визуально это выглядит так:


Обратите внимание, что между любыми двумя узлами не больше двух рёбер

Оказывается, для вычисления этой таблицы нам почти не нужно изменять решение 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(V+E), потому что должен хранить все рёбра и вершины, а эта структура требует только O(V), потому что нам больше не нужны рёбра.

Результаты


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

Если разбить решение этой задачи на четыре препятствия (обсуждение фрейминга, выбор алгоритма, реализация, обсуждение выполнения за постоянное время), то к концу собеседования почти все кандидаты дошли до «выбора алгоритма». Как я и подозревал, обсуждение фрейминга стало хорошим фильтром: кандидаты либо сразу выводили граф, либо никак не могли к нему прийти, несмотря на существенные подсказки.

Это уже сразу полезный сигнал. Я могу понять, когда человек не знает продвинутых или неясных структур данных, потому что будем честными, вам нечасто придётся реализовывать непересекающиеся множества. Но графы — фундаментальная структура данных и преподаётся в рамках практически любого вводного курса по этой теме. Если кандидат изо всех сил пытается понять их или не может их легко применить, вероятно, ему будет трудно добиться успеха в Google (по крайней мере, в моё время там, не знаю как сегодня).

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

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

В моём представлении любой, кто прошёл этап реализации, уже заслужил от меня рекомендацию «Нанимать», а этап обсуждения постоянного времени выполнения просто бонусный. Хотя в статье мы подробно рассмотрели решение, на практике обычно более продуктивным является устное обсуждение, а не написание кода. Очень немногие кандидаты сразу могли высказать решение. Мне часто приходилось давать существенные подсказки, и даже тогда многие люди не могли его найти. Это нормально: как и предполагалось, рейтинг «настоятельно рекомендую» трудно заслужить.

Но подождите, это ещё не всё!


В основном, мы рассмотрели проблему целиком, но если вы заинтересованы в её дальнейшем изучении, то есть целый ряд расширений, в которые я не буду погружаться. Оставляю следующие упражнения для читателя:

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

Во-вторых, во всех рассуждениях предполагалось, что все равные пути через граф равны изначально, что не всегда так. Один из интересных вариантов этой проблемы — конвертация валют: узлы — это валюты, а рёбра от A до B и наоборот — это цены на предложение/спрос каждой валютной пары. Мы можем перефразировать вопрос о конверсии единиц как вопрос о валютном арбитраже: реализовать алгоритм, который, учитывая граф конвертации валюты, вычисляет через граф цикл, который даст трейдеру больше денег, чем начальная сумма. Не учитывайте никаких комиссий за транзакции.

Наконец, настоящая жемчужина: некоторые единицы выражаются в виде комбинации различных базовых единиц. Например, ватт определяется в системе СИ как кг•м²/с³. Последняя задача заключается в расширении этой системы для поддержки преобразования между этими единицами, учитывая только определения основных единиц СИ.

Если у вас есть вопросы, не стесняйтесь обращаться ко мне на reddit.

Заключение


Когда я начал задавать эту задачу на собеседованиях, то надеялся, что она будет немного легче предыдущих. Эксперимент был в значительной степени успешным: если кандидат сразу видел решение, то обычно быстро справлялся с задачей, так что у нас оставалось много времени, чтобы поговорить о продвинутом решении с постоянным временем. Люди, которые испытывали затруднения, как правило, спотыкались в местах, отличных от алгоритмического концептуального скачка: кандидат не мог подходящим способом полностью сформулировать проблему или набросал хорошее решение, но не смог перевести его в рабочий код. Независимо от того, где и когда они испытывали затруднения, я обнаружил, что могу получить значимую информацию о сильных и слабых сторонах кандидатов.

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

Подробнее
Реклама

Комментарии 73

    +43
    Спасибо за перевод!
    Эта статья подводит нас к очень интересной проблеме: американцы привыкли работать с несистемными размерами, поэтому для них естественно использовать цепочку преобразований для перевода попугаев в футы. Первое же, что приходит в голову человеку, знакомому с СИ — перевести все единицы в СИ и назад. Никакого графа, поиска в глубину и т.д. — все «общеизвестные преобразования» должны быть заранее вбиты в таблицу с коэффициентами вроде «1 фут = 0.3048 метра» и все вычисления должны происходить через метры. Если у нас нет таблицы таких «общеизвестные преобразований» в метры и программа стартует с пустой таблицей, то первым делом ее надо «обучить», наполнив эту таблицу. Если данные для обучения выданы в произвольном порядке, то их надо отсортировать так, чтобы они всегда опирались на уже существующие преобразования.
    В любом случае, финальное вычисление после этого будет делаться в два умножения. Я просто не могу себе представить как у автора получился «интуитивный подход», это для нас совершенно неестественно.
      0

      Таблица преобразований — это один из входных параметров задачи и она фиксирована. То есть оперировать можно только с этими коэффициентами и там далеко не для всех пар величин есть коэффициент.


      Для примера с метрами, представьте что есть преобразование светового года как в метра, так и в футы, а вот из хендов есть преобразование только в футы и никакого в метры. Вот тогда и приходится искать путь среди связей величин, чтобы получить ответ.

        +16
        Но задача отлично решается при наличии полной таблицы преобразований в метры. Значит перед работой надо неполную таблицу сделать полной, это подготовительная операция. А само преобразование уже потом делается в два умножения. Конечно, мы можем где-то потерять точность из-за количества операций с плавающей запятой, но это тоже решаемо, н-р, рациональными дробями.
          0
          Хотел бы я посмотреть, как ваша реализация рациональных дробей будет работать со значениями навроде 1.0737e−17
            +6

            Кстати, нормально будет работать. Потому что в double максимальные и минимальные степени могут быть очень большими и за этот предел будет проблематично вылезти.
            В умножении "очень большого числа на очень маленькое" потерь точности практически нет, в отличие от сложения.

              0
              При чём тут double? Nomad1 предложил вместо плавающей запятой использовать рациональные дроби.

              Пример потери точности при умножении double есть прямо в тексте статьи.
                +2
                Во-первых, кустарной реализации на собеседовании (да и в коммерческой разработке) быть не должно, потому что рациональные дроби не делал только ленивый. Если говорить о .Net, то разумно использовать, н-р, Rationals.Net, где числитель и знаменатель задаются BigInteger — оберткой вокруг массива чисел, без ограничений по размеру и порядку. Для C++ берем cpp_rational с такими же свойствами.
                Во-вторых, дробь с e-17 это совсем не много, задается 64-битными числами, пусть и близко к пределу.
                В-третьих, при некотором желании (и желании сделать пару велосипедов) можно использовать представление с мантиссой и экспонентой (даже тот же double) и в рациональных дробях. Ошибка будет накапливаться только при очень большой разнице между исходной и результирующей величиной (ангстремы в парсеки).
                  0
                  Вот как раз на собеседовании в гугл от вас ожидают реализовать то, что в коммерческой разработке принято брать готовым, не разбираясь, что внутри.

                  А то я тоже у них на какой-то вопрос по поводу потери точности ляпнул «тогда возьмём длинную арифметику», после чего до конца часа писал на доске реализацию умножения десятичных дробей произвольной длины, да так и потонул в обработке разных граничных случаев.
                    +1
                    Ну тут я вам не отвечу, я у гугла не был на собеседовании :)
                    Здравый смысл говорит о том, что рациональные числа в boost появились в 1999году. Через 20 лет реализовывать их заново это, кхм, странно. Ну может только чтобы впечатлить собеседника.
                  +2

                  Откуда берётся эта потеря точности? 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.

                    0
                    Вы заметили, как Google показывает коэффициент конверсии 1.0739e-17, но мой расчёт вручную даёт 1.0737e-17?
                      +5

                      Ну и какой вывод? Считая вручную мы обычно не записываем на бумгае 15 знаков после запятой, а лишь 5-6 как в примере. 4 преобразвания с такой потерей точности и вот у нас ошибка в 5 знаке.

          +1
          Я просто не могу себе представить как у автора получился «интуитивный подход», это для нас совершенно неестественно.

          У континентальной Европы, Англии/США и Японии разные инженерные школы.

          Вопрос культурных различий в этом контексте ничуть не хуже, чем умение применять алгоритмы на графах. Люди просто думают одни и те же мысли совершенно по-разному.
            0

            Это решение автор предложил в 4-ой части. Да, я тоже сразу подумал, что надо таблицу перобразований задавать с какой-то фиксированной велечиной, к которой все и приводить. Но это усложняет требования к таблице и алгоритм уже не применить, например, к намайненным с интернета данным.

              +2
              Алгоритм все так же применяется, просто на другой стадии — на подготовке данных. Т.е. наша инженерная школа подразумевает очень простое и точное решение этой задачи — «видишь не-СИ значение, приведи его к СИ». В данной формулировке задача решается в два умножения. То, чего хочет автор — решение с помощью графа — нам кажется нелогичным, но при этом нормально такой подход использовать для разворчивания намайненных данных в таблицу, т.е. на подготовительном этапе. Тут уже можно проявить фантазию в поиске наименьшего количества конверсий, проставлении коэффициентов достоверности и т.д. Но конкретно представители нашей школы на этом собеседовании будут ошеломлены и обескуражены, ведь это уровень средней школы.
                +2

                Это и есть финальный ответ, на 5+ (в части 4). Обходим граф один раз, строим таблицу с эталонной величиной и потом переводим туда-обратно все что надо.


                Да, многие из Европы сразу бы спросили, а почему таблица такая кривая дана? Получили бы ответ, ну вот так вот. Других данных нет.


                Это решение, да, очевиднее тем, кто работает с единицами си. Но тем, кто футы в мили переводит, гораздо инуитивнее делать переводы в несколько этапов, потому что 1231760 запомнить проще, чем 12, 36, 63360 и другие кривые числа. Именно поэтому входные данные такие.

            –4
            Отсюда вытекает свойство «кратчайший путь / наименьшее число умножений»

            BFS это метод перебора узлов графа, как и DFS у него нет свойства находить кратчайший путь.

              +4

              Оказывается у BFS есть такое свойство.

                0

                Тут надо сделать важную оговорку, что у всех рёбер/вершин одинаковый вес, а это не классическая постановка проблемы поиска кратчайшего пути.

                0

                Отчасти, вы правы. Но только если рассматривать значение узла как путь. Автор имел ввиду минимальное количество узлов = умножений. То-есть в данной задаче длина всех узлов равна.

                  0

                  В невзвешенном графе (веса всех рёбер равны единица), BFS — это алгоритм поиска кратчайшего пути.

                    +1

                    BFS всегда находит кратчайший путь в невзвешеном графе(либо если все веса равны). Это просто из определения BFS следует.

                    0
                    Кажется это решается с помошью dimensional table. Надо только граф ориентировать в таблицу с расстояниями.
                      +5
                      Я подозреваю, что на собеседовании валились люди, получившие образование в метрической системе. У них когнитивный диссонанс от неоптимального решения. А товарищ явно пушил в сторону деревьев.
                        +3
                        Имхо на собеседовании валились люди с инженерным подходом к решению задачи. Irl обычно не создаётся конвертор всего во все. Первый вопрос, который должен задать грамотный специалист — вопрос о применимости данной системы. То что приведено в качестве примера — неприменимо от слова совсем именно по причине быстрой деградации точности. Второй вопрос: оптимальный путь для каждого значения нужно найти только один раз, причем это путь не до искомой системы измерения, а до промежуточной общей (например СИ или любой другой). Полученное значение зафиксировать в таблице и поставить отметку о необходимости повышения точности. При таком подходе время первичного поиска пути конвертации и как следствие оптимальность алгоритма не будет иметь решающего значения, т.к. все остальные конвертации по данному направлению будут иметь фиксированное время (согласен с Nomad1).
                          +5
                          Я про то, что товарищ, ИМХО демонстрировал то на что его натаскали в американском ВУЗе — питон + деревья. При этом он демонстрировал знания без понимания. Это заученный материал, не переваренный. При этом он ожидал именно этого и от собеседуемых.
                          Я думаю отвалились на его собеседованиях слабые и сильные программисты, а средние прошли.
                            +1
                            Ты демонстрируешь мне питон + деревья, но ты делаешь это без понимания
                        +11
                        Прочитал задачку, скроллю дальше, вижу графы. Понимаю, почему у гугла не получился гуглплюс и овер 9000 других проектов. Е...., на всю голову.
                          0
                          И наверное, я бы эту задачу начал с построения множества возможных элементов преобразования для каждого элемента конвертации. Тогда задача решается просто: берём множества возможных преобразований запрошенных элементов конвертации и находим их пересечение (поиск промежуточного общего). Если не пересекаются — не судьба. Если пересекаются — сразу имеем кратчайший путь конвертации. Добавление нового элемента конвертации сводится к формированию его собственного множества с элементами конвертации, в которые он умеет конвертировать, и к добавлению этого элемента конвертации в те множества элементов конвертации, которые входят в сформированное собственное множество данного элемента.
                            +2
                            А насколько рационально тратить ресурсы при поиске ответа на каждый запрос в поисковике? Не будет ли проще принять одну из единиц как «стандартную» (например, тот же метр из СИ), и просто при добавлении в базу любой новой единицы пересчитывать ее в метры, и хранить в БД один коэффициент? Тогда задача из топика сведется к двум банальным арифметическим действиям для любой из пар единиц измерения. Да и проверка возможности/невозможности решения сведется к запросу «для обеих ли заданных единиц измерения существуют записи в БД».
                              +2
                              Проще, но проблема в том, что отношения к «стандартной» единице в общем случае для конвертируемых единиц в анализируемом наборе данных может не существовать. Короче, и вы тоже мыслите как инженер и собеседование не прошли :)
                                +2
                                В моем мире инженер — это похвала. :)

                                Кстати, многих запутал перевод.
                                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:

                                превратилось в
                                Приведите список коэффициентов пересчёта (отформатированный на выбранном вами языке) в виде набора начальных единиц измерения, конечных единиц и множителей, например:


                                Т.е. если строго говорить, то решение гуглера верно, если принять за аксиому, что постановка задачи верна. Но обычно так не бывает на собеседованиях — обычно тебе разрешают задавать вопросы. И вот тут первым делом нужно спросить у него, осознает ли он, что текущая постановка задачи ведет к не оптимальному решению.

                                  0
                                  Плохо, когда инженеры не проходят собеседование.
                                    +1
                                    На самом деле мой косяк тут тоже есть — должен был перед началом реализации уточнить «а не будет ли возможным в условии задачи двух разных систем измерения длины, не имеющих способа пересчета из одной в другую». За то, что не подумал об этом меня и назвали инженером. )))
                                      +2
                                      Назвали не за то, что не подумали, а за подход к решению. Автор пляшет от общего, сферического, и как следствие, неоптимального решения. Причем задачу решает в лоб. «Инженерный» подход (в моем понимании :) ) предполагает использование частного решения, с учётом известных проектировщику ограничений. Это ограничивает область применимости, но повышает эффективность. Т.е. для забивания гвоздя используется не синхрофазатрон, а другой, более удобный для этого инструмент.
                                      То, что делает автор, допустимо и даже приветствуется в исследовательской работе, но недопустимо для решения, которое реализуется в железе.
                                      Нижe предлагают для решения задачи использовать непересекающиеся множества (DSU). Судя по описанию, это то, к чему я пришел после непродолжительного анализа возможных путей решения задачи ( знал, что велосипед изобретаю :)). Исходя из этого могу предположить, что этап аналитической работы по изучению существующих алгоритмов и решений был пропущен в пользу инструмента, для которого уже есть наработки, что не есть хорошо при проектировании систем.
                                      Печаль заключается в том, что автор, участвуя в подборе специалистов, во-первых, определяет технические подходы компании к решению задач; во-вторых, влияет на развитие тех специалистов, которыми руководит.
                                        0
                                        Лихо вы так кастрировали инженерный подход до частного.
                                +2
                                Хорошая статья. Но отмечу, что не все единицы измерения конвертируются через умножение/деление на число, порой преобразования бывают посложнее, например логарифмическое или полиномиальное. Хотя решение не сильно поменяется, просто ребрам будут приписываться не числа, а функции. А путь тогда будет, по сути, соответствовать композиции функций.
                                  0
                                  Не знаю ни одного логарифмического преобразования, а из полиномиальных — только линейные с константой (между температурными шкалами).

                                  Я бы отметил другое — что есть «сложные единицы», чей набор практически не ограничен. Например, редко используемые единицы плотности «хандредвейт на акр» (сwt/ac) и «хандредвейт на тысячу квадратных футов» (cwt/MSF) гугловскому калькулятору неизвестны — хотя по отдельности он понимает и хандредвейты, и акры, и футы. А ведь сложные единицы могут быть и ещё экзотичнее, вроде «пудов на квадратный аршин».
                                    +1
                                    Там со звуком вроде логарифмы: децибелл это логарифм чего то.
                                      0
                                      Таки да, но ни в какую другую единицу децибел не переводится.
                                        0

                                        Тем не менее это прецедент и серьёзный. Раньше у нас были пары преобразований типа "1 метр = 3 фута" и неявное допущение, что вот это "=" означает умножение. Теперь же мы добавляем пару "1 децибел = 10 аудиоджоулей", но "=" здесь означает логарифм. И вся эта хитрая конструкция с графом рушится: как бы будем сранивать какое преобразование короче если слева и справа трехэтажная формула с логарифмами?

                                          +1
                                          Как я описывал, ребрам приписываем не числа, а функции. А путь тогда будет, по сути, соответствовать композиции функций.
                                            +2

                                            Цель поиска — найти кратчайший путь. Как мы будем сравнивать эти композиции функций?

                                              0
                                              Кратчайший путь это, очевидно, тот, в котором меньше ребер. И тогда в композиции будет меньше функций.
                                                0
                                                В контексте данной статьи, кратчайший путь — это тот, который вносит наименьшую погрешность при вычислениях.
                                                  0

                                                  Нет, это именно количество преобразований, если в контексте статьи. BFS ничего про погрешность не знает.

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

                                                      А если учитывать, что точность сильнее теряется подальше от 1, то становится ещё интереснее. Что лучше, умножить 2 числа 10 порядков или 10 раз но 2 но 0.5 (пример грубый).

                                            0
                                            Не знаю, что такое «аудиоджоуль». И гугл тоже не знает.
                                            Если это единица энергии, то децибел в неё не переводится.
                                            0
                                            она переводится в безразмерные «разы» — т.е. усиление интенсивности звука в 10 раз — 10 децибел, в 100 раз — 20 децибел, а в 10000 раз — 40 децибел.
                                            Посмотрите еще в сторону площадей и объемов — там квадратные и кубические см к км нелинейные.
                                              0
                                              Что не так с площадями и объёмами?
                                              1 км3 = 1015 см3, соотношение вполне линейное.
                                                0

                                                Скажем перевести 1 акр в метры.

                                                  +1
                                                  С тем же успехом можно вольты переводить в килограммы.
                                                    +2
                                                    Физики любят измерять массу частиц в электронвольтах )). В СГС, кажется
                                                0
                                                Абсолютная шкала тоже существует, за ноль децибел принимается порог слышимости.
                                                +1
                                                Это же безразмерная величина, по сути. (деци) Бел — строго говоря, когда-то и кому-то в меру удобное название психофизиологического приближения к логарифму.
                                          +9

                                          Интересно, куда потом в пучинах Гугла пропадают все эти умнейшие люди, которые на собеседованиях решают подобные задачи

                                            0
                                            Во-первых, работа в Reddit была потрясающей.

                                            Почему была?
                                              +1

                                              Можно ещё быстрее за 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)

                                                0

                                                Можно. А чем это будет лучше сразу системы непересекающихся множеств, которая за 2 умножения/деления всегда даёт ответ? Добавление в систему в среднем O(1). Построение всей системы строго O(N) (1 BFS или подобное из корневой).


                                                А вообще задача мне показалась как-то ну очень простой. Граф пришёл в голову сразу, отсчёт от центра тоже.

                                                  0
                                                  А вообще задача мне показалась как-то ну очень простой.

                                                  Всё верно.
                                                  Принцип собеседования в гугле — начать с очень простой задачи, и на протяжении часа добавлять усложнения.
                                                    +1

                                                    Тогда непонятно, почему автор всю статью разбирал такое простое решение, если у неё существуют гораздо более эффективные, но не сильно более сложные.

                                                    0

                                                    Хмм, действительно отличное решение. И ошибка будет меньше. Как-то я просто при виде задачи сразу подумал над быстрым поиском пути в дереве, а до DSU не догадался.

                                                    0
                                                    Спасибо! Пришел практически к этому путем размышлений. Теперь буду знать как это называется — DSU!!! :)
                                                    +1
                                                    Любой американец, который путешествовал за пределами США, знает, что большая часть мира для измерения расстояний использует таинственную единицу «километр»

                                                    Вспомнилось: "There is a world outside US, yes!"

                                                    Что касается перевода единиц, то, интуитивно (но с условием, что единицы одного типа: скажем, длину в длину переводим, а не площадь в объем) же, кажется, что достаточно выделить одну единицу как основную, эталонную, от которой остальные зависят, так сразу получаем возможность выразить преобразуемое число в тих эталонных единицах, а потом число эталонных единиц в целевых единицах. Да, есть вопрос точности, но граф как таковой оценку точности преобразования также дает опосредованную, а точность, по сути, будет зависеть от округления каждой операции. Но это, кажется, слишком простое объяснение для собеседования девелопера — тут даже код красиво не напишешь на доске.
                                                      0
                                                      Пересчет единиц измерения — вполне себе рядовая задача для консультанта по ERP не важно какой: SAP, 1C или Axapta.
                                                      У сварщика техкарта — в метрах/сантиметрах сварного шва
                                                      Кладовщица выдает электроды: в штуках, но может и в коробках.
                                                      Закупер закупает: в килограммах, но может и в ящиках.
                                                      Итого измеряемые величины — единицы измерения
                                                      а) длина — метры и сантиметры
                                                      б) количество — штуки, коробки, ящики
                                                      в) масса — килограммы
                                                      … и в рамках всего одного техпроцесса — электросварка
                                                        +1

                                                        К своему стыду (после прочтения комментариев) первой мыслью таки было "кратчайший путь на графе". Второй мыслю было "привести к СИ".

                                                          –1
                                                          Да, статья познавательная. Но какое это имеет отношение к реальному программированию?
                                                          Если кто-то скажет, что имеет — он бы не прошел у меня собеседование.
                                                            +1
                                                            Когда-то мой знакомый ПМ в шутку сформулировал термин превентивное планирование — обработка и переформулирование задачи таким образом, чтобы ее можно было решить без написания программы :)
                                                              +1
                                                              Не поверите, прямо сейчас решаю точно эту задачу. Имея набор пар валют нужно рассчитать средний курс одной валюты в другой, желательно быстро, желательно не потратив на это кучу памяти. На работу к вам не пойду, у вас похоже задачи тухлые очень, вида «вставить данные из формочки в БД».
                                                              0
                                                              Как посредственный программист я бы решил этот вопрос без графов.
                                                              Выделил бы базовые типы величин (размер, вес, температура, площадь).
                                                              Каждый тип дополнил бы некоей «идеальной величиной», в которую удобно конвертировать остальные.
                                                              В итоге любое преобразование занимает ровно 2 операции (из одной в абсолютную, из абсолютной в нужную).
                                                              Проблему невозможных преобразований (из литра в метры) решал бы за меня полиморфизм — если единицы от разных абстрактных классов, то они одна из них просто не залезет в метод конвентера.
                                                                +1

                                                                У вас нет классов, методов и прочего. Есть, условно говоря, текстовый файлик на вход. И там может быть


                                                                увррик деннон 3.124
                                                                деннок зазак 484.005
                                                                ...

                                                                И пока вы не прочитаете файл, вы даже не знаете, какие там есть единицы: относящиеся к одной величине (один граф) или к нескольким (два и более несвязанных подграфа). Данный формат входных значений и данное решение не покрывает случай производных единиц (например, Н/м -> Па), но автор об этом говорит в конце.

                                                                0

                                                                — Алекс, это ведь будет LPG-граф. Так давайте и будем хранить его в графовой СУБД, а коэффициенты преобразований вычислять запросами. Что у вас там есть развернутого? Neo4, говорите… Ну тогда так:


                                                                MATCH (foot:Unit {name:'foot'}), (meter:Unit {name:'meter'})
                                                                WITH shortestPath ((foot)-[:RATIO*]-(meter)) AS p
                                                                WITH nodes(p) AS ns, relationships(p) AS rs
                                                                WITH [i IN range(0, length(rs)-1) |
                                                                      CASE
                                                                      WHEN ns[i] = startNode(rs[i])
                                                                           THEN rs[i].ratio
                                                                           ELSE 1/rs[i].ratio
                                                                      END
                                                                     ] AS ratios
                                                                RETURN reduce (acc = 1, r IN ratios | acc * r) 

                                                                Да, согласен… Думаю, графовая СУБД с поддержкой правил вывода позволила бы последовательно вычислить наилучшие с точки зрения точности попарные коэффициенты. Конечно, по соображениям производительности лучше не выводить их при каждом запросе, а единожды материализовать.


                                                                — Добро пожаловать в Google Knowledge Graph, сынок.

                                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                Самое читаемое