Comments 73
Эта статья подводит нас к очень интересной проблеме: американцы привыкли работать с несистемными размерами, поэтому для них естественно использовать цепочку преобразований для перевода попугаев в футы. Первое же, что приходит в голову человеку, знакомому с СИ — перевести все единицы в СИ и назад. Никакого графа, поиска в глубину и т.д. — все «общеизвестные преобразования» должны быть заранее вбиты в таблицу с коэффициентами вроде «1 фут = 0.3048 метра» и все вычисления должны происходить через метры. Если у нас нет таблицы таких «общеизвестные преобразований» в метры и программа стартует с пустой таблицей, то первым делом ее надо «обучить», наполнив эту таблицу. Если данные для обучения выданы в произвольном порядке, то их надо отсортировать так, чтобы они всегда опирались на уже существующие преобразования.
В любом случае, финальное вычисление после этого будет делаться в два умножения. Я просто не могу себе представить как у автора получился «интуитивный подход», это для нас совершенно неестественно.
Таблица преобразований — это один из входных параметров задачи и она фиксирована. То есть оперировать можно только с этими коэффициентами и там далеко не для всех пар величин есть коэффициент.
Для примера с метрами, представьте что есть преобразование светового года как в метра, так и в футы, а вот из хендов есть преобразование только в футы и никакого в метры. Вот тогда и приходится искать путь среди связей величин, чтобы получить ответ.
Кстати, нормально будет работать. Потому что в double максимальные и минимальные степени могут быть очень большими и за этот предел будет проблематично вылезти.
В умножении "очень большого числа на очень маленькое" потерь точности практически нет, в отличие от сложения.
Пример потери точности при умножении double есть прямо в тексте статьи.
Во-вторых, дробь с e-17 это совсем не много, задается 64-битными числами, пусть и близко к пределу.
В-третьих, при некотором желании (и желании сделать пару велосипедов) можно использовать представление с мантиссой и экспонентой (даже тот же double) и в рациональных дробях. Ошибка будет накапливаться только при очень большой разнице между исходной и результирующей величиной (ангстремы в парсеки).
А то я тоже у них на какой-то вопрос по поводу потери точности ляпнул «тогда возьмём длинную арифметику», после чего до конца часа писал на доске реализацию умножения десятичных дробей произвольной длины, да так и потонул в обработке разных граничных случаев.
Откуда берётся эта потеря точности? 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.
Я просто не могу себе представить как у автора получился «интуитивный подход», это для нас совершенно неестественно.
У континентальной Европы, Англии/США и Японии разные инженерные школы.
Вопрос культурных различий в этом контексте ничуть не хуже, чем умение применять алгоритмы на графах. Люди просто думают одни и те же мысли совершенно по-разному.
Это решение автор предложил в 4-ой части. Да, я тоже сразу подумал, что надо таблицу перобразований задавать с какой-то фиксированной велечиной, к которой все и приводить. Но это усложняет требования к таблице и алгоритм уже не применить, например, к намайненным с интернета данным.
Это и есть финальный ответ, на 5+ (в части 4). Обходим граф один раз, строим таблицу с эталонной величиной и потом переводим туда-обратно все что надо.
Да, многие из Европы сразу бы спросили, а почему таблица такая кривая дана? Получили бы ответ, ну вот так вот. Других данных нет.
Это решение, да, очевиднее тем, кто работает с единицами си. Но тем, кто футы в мили переводит, гораздо инуитивнее делать переводы в несколько этапов, потому что 1231760 запомнить проще, чем 12, 36, 63360 и другие кривые числа. Именно поэтому входные данные такие.
Отсюда вытекает свойство «кратчайший путь / наименьшее число умножений»
BFS это метод перебора узлов графа, как и DFS у него нет свойства находить кратчайший путь.
Оказывается у BFS есть такое свойство.
Отчасти, вы правы. Но только если рассматривать значение узла как путь. Автор имел ввиду минимальное количество узлов = умножений. То-есть в данной задаче длина всех узлов равна.
В невзвешенном графе (веса всех рёбер равны единица), BFS — это алгоритм поиска кратчайшего пути.
Я думаю отвалились на его собеседованиях слабые и сильные программисты, а средние прошли.
Кстати, многих запутал перевод.
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:
превратилось в
Приведите список коэффициентов пересчёта (отформатированный на выбранном вами языке) в виде набора начальных единиц измерения, конечных единиц и множителей, например:
Т.е. если строго говорить, то решение гуглера верно, если принять за аксиому, что постановка задачи верна. Но обычно так не бывает на собеседованиях — обычно тебе разрешают задавать вопросы. И вот тут первым делом нужно спросить у него, осознает ли он, что текущая постановка задачи ведет к не оптимальному решению.
То, что делает автор, допустимо и даже приветствуется в исследовательской работе, но недопустимо для решения, которое реализуется в железе.
Нижe предлагают для решения задачи использовать непересекающиеся множества (DSU). Судя по описанию, это то, к чему я пришел после непродолжительного анализа возможных путей решения задачи ( знал, что велосипед изобретаю :)). Исходя из этого могу предположить, что этап аналитической работы по изучению существующих алгоритмов и решений был пропущен в пользу инструмента, для которого уже есть наработки, что не есть хорошо при проектировании систем.
Печаль заключается в том, что автор, участвуя в подборе специалистов, во-первых, определяет технические подходы компании к решению задач; во-вторых, влияет на развитие тех специалистов, которыми руководит.
Я бы отметил другое — что есть «сложные единицы», чей набор практически не ограничен. Например, редко используемые единицы плотности «хандредвейт на акр» (сwt/ac) и «хандредвейт на тысячу квадратных футов» (cwt/MSF) гугловскому калькулятору неизвестны — хотя по отдельности он понимает и хандредвейты, и акры, и футы. А ведь сложные единицы могут быть и ещё экзотичнее, вроде «пудов на квадратный аршин».
Тем не менее это прецедент и серьёзный. Раньше у нас были пары преобразований типа "1 метр = 3 фута" и неявное допущение, что вот это "=" означает умножение. Теперь же мы добавляем пару "1 децибел = 10 аудиоджоулей", но "=" здесь означает логарифм. И вся эта хитрая конструкция с графом рушится: как бы будем сранивать какое преобразование короче если слева и справа трехэтажная формула с логарифмами?
Цель поиска — найти кратчайший путь. Как мы будем сравнивать эти композиции функций?
Если это единица энергии, то децибел в неё не переводится.
Посмотрите еще в сторону площадей и объемов — там квадратные и кубические см к км нелинейные.
Интересно, куда потом в пучинах Гугла пропадают все эти умнейшие люди, которые на собеседованиях решают подобные задачи
Во-первых, работа в Reddit была потрясающей.
Почему была?
Можно ещё быстрее за 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)
Можно. А чем это будет лучше сразу системы непересекающихся множеств, которая за 2 умножения/деления всегда даёт ответ? Добавление в систему в среднем O(1). Построение всей системы строго O(N) (1 BFS или подобное из корневой).
А вообще задача мне показалась как-то ну очень простой. Граф пришёл в голову сразу, отсчёт от центра тоже.
А вообще задача мне показалась как-то ну очень простой.
Всё верно.
Принцип собеседования в гугле — начать с очень простой задачи, и на протяжении часа добавлять усложнения.
Хмм, действительно отличное решение. И ошибка будет меньше. Как-то я просто при виде задачи сразу подумал над быстрым поиском пути в дереве, а до DSU не догадался.
Любой американец, который путешествовал за пределами США, знает, что большая часть мира для измерения расстояний использует таинственную единицу «километр»
Вспомнилось: "There is a world outside US, yes!"
Что касается перевода единиц, то, интуитивно (но с условием, что единицы одного типа: скажем, длину в длину переводим, а не площадь в объем) же, кажется, что достаточно выделить одну единицу как основную, эталонную, от которой остальные зависят, так сразу получаем возможность выразить преобразуемое число в тих эталонных единицах, а потом число эталонных единиц в целевых единицах. Да, есть вопрос точности, но граф как таковой оценку точности преобразования также дает опосредованную, а точность, по сути, будет зависеть от округления каждой операции. Но это, кажется, слишком простое объяснение для собеседования девелопера — тут даже код красиво не напишешь на доске.
К своему стыду (после прочтения комментариев) первой мыслью таки было "кратчайший путь на графе". Второй мыслю было "привести к СИ".
Если кто-то скажет, что имеет — он бы не прошел у меня собеседование.
Выделил бы базовые типы величин (размер, вес, температура, площадь).
Каждый тип дополнил бы некоей «идеальной величиной», в которую удобно конвертировать остальные.
В итоге любое преобразование занимает ровно 2 операции (из одной в абсолютную, из абсолютной в нужную).
Проблему невозможных преобразований (из литра в метры) решал бы за меня полиморфизм — если единицы от разных абстрактных классов, то они одна из них просто не залезет в метод конвентера.
У вас нет классов, методов и прочего. Есть, условно говоря, текстовый файлик на вход. И там может быть
увррик деннон 3.124
деннок зазак 484.005
...И пока вы не прочитаете файл, вы даже не знаете, какие там есть единицы: относящиеся к одной величине (один граф) или к нескольким (два и более несвязанных подграфа). Данный формат входных значений и данное решение не покрывает случай производных единиц (например, Н/м -> Па), но автор об этом говорит в конце.
— Алекс, это ведь будет 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, сынок.
Разбор задачи с собеседования Google: поиск соотношения