После 20–25 минут вопросов руководства мне задали этот вопрос в техническом раунде на должность инженера по машинному обучению. На этот вопрос у меня было около 30 минут.
Вопрос:
# Inputs example_products_input = [ "alpha beta gamma’, "delta alpha eta theta", "epsilon alpha eta zeta’, "epsilon', ] # Find the top x most frequently occurring words in a list of product descriptions. # Input: products=example_products_input, x=2 # Output: ['alpha', ‘eta'] def top_x_words(products: List[str], x: int) -> List[str]:
Подход:
Я знаю, что это выглядит как стандартная проблема с литкодом, которую можно решить с помощью кучи (точнее, минимальной кучи, чтобы получить O(n*lg(x)) TC). Но если вы внимательно посмотрите на вопрос, мы можем добиться большего успеха, используя инвертированный индекс.
Я начал разговор с нескольких уточняющих вопросов. Я спросил интервьюера: «Каковы возможные разделители для сбора токенов?». Он сказал: «Только космос». Я спросил его, должен ли я игнорировать специальные символы после сбора токенов (например, должен ли я относиться к ice и ice; одинаково). Он сузил ситуацию, сказав, что я могу предположить, что жетоны всегда разделены одним пробелом, а единственными возможными символами являются маленькие буквы английского алфавита и пробел. Я почувствовал облегчение.
Я объяснил ему идею, сначала создав словарь с токеном в качестве ключа и соответствующей ему частотой в качестве значения. Я сказал ему, что токены получаются путем разделения описания продукта пробелом. В этот момент я сказал, что словарь будет выглядеть примерно так:
d = {"alpha": 3, "beta": 1, "gamma": 1, "delta": 1, "eta": 2, "theta": 1, "epsilon": 2, "zeta": 1} TC for d = O(N), N -> number of tokens
скорее всего в другом порядке. Затем я обсудил с ним несколько идей,
Идея №1:
Соберите пары ключ-значение в форме (значение, ключ) и поместите их один за другим в максимальную кучу. Поскольку для помещения каждого элемента в максимальную кучу требуется O(lg(n)), я вычислил и показал ему, на что будет похожа общая TC,
TC = sum(O(log(i)), for i = 1 to n, n -> number of unique tokens = O(log(n!)) (using property log(a) + log(b) = log(ab)) ~ O(n*lg(n)), using Stirling's approximation (n! ~ n^(n + 0.5))
Я сказал ему, что асимптотическое время не так уж и хорошо. Я сказал ему, что я буду лучше этого.
Идея №2:
Вставьте пары (значение, ключ) (где значение = частота и ключ = токен) в мини-кучу вместо этого, пока размер кучи не станет x. А затем удалите min и сохраните его во временном файле и поместите в кучу максимальное значение следующей пары (значение, ключ) и temp. TC для этого подхода выглядит так:
TC = O(x*log(x)) + O((n - x)*lg(x)), n -> number of unique tokens, x -> number of elements wanted
Идея №3:
Я сказал, что мы можем уменьшить TC O(x*lg(x)) в приведенном выше подходе до O(x), сохранив первый x элементы в списке и используя heapify в этом списке.
TC = O(x) + O((n - x)*lg(x)), n -> number of unique tokens, x -> number of elements wanted
Идея №4:
Затем я объяснил, что идея heapify может быть распространена на весь список. Список будет содержать кортежи вида (значение, ключ) со значением = частота и ключ = токен. Применение max heapify к этому списку и сбор x элементов займет,
TC = O(n) (max heapify) + O(x) (collect x elements) (n -> number of unique tokens, x -> number of elements wanted = O(n + x)
Идея № 5:
На этом этапе я хотел поговорить о подходе с индексом и инвертированным индексом и объяснить, почему этот подход будет работать лучше на практике. После построения индекса, словаря с токеном в качестве ключа и соответствующей ему частотой в качестве значения, я теперь говорил об инвертированном индексе, который также является словарем, ключом которого является частота элементов, а значением является список элементов, имеющих эту частоту. Я сказал ему, что отсортирую индекс по обратному принципу. его ключ, т. е. частота элементов.
d2 = {3: ["alpha"], 2: ["eta", "epsilon"], 1: ["beta", "gamma", "delta", "theta", "zeta"]}
Чтобы собрать первые k элементов, мы должны выполнить итерацию инвертированного индекса. В этот момент я задал ему вопрос: «Как мы должны обрабатывать связи с частотой?». Например, в данном вопросе есть 2 слова («сливки» и «черника») с частотой = 2. Он сказал, что я могу вернуть любое из 2 слов в случае ничьей, но размер выходного списка должен содержать ровно x элементов. Я оценивал ТС за это,
TC = O(k) (for inverted index) + O(k*lg(k)) (reverse sorting the inverted index) + O(x); n -> number of unique tokens, k -> number of unique frequencies, x -> number of elements wanted = O(k + k*lg(k) + x) O(k*lg(k) + x)
Интервьюер спросил, чем этот подход лучше предыдущего. Я оценил максимальное значение k.
worst case for k comes when frequencies are 1, 2, 3, ... j, such that, sum(1 + 2 + ... j) = N => j ~ O(sqrt(N)) Therefore, max value for k = (sqrt(N)) Overall TC = O(sqrt(N) * lg(sqrt(N)) + x) = O(sqrt(N) * lg(N) + x)
Идея №6:
Поскольку значение k выше всегда ≤ N, я сказал, что мы можем использовать сортировку с подсчетом вместо библиотечной сортировки, чтобы снизить TC до,
TC = O(k + x), k -> number of unique frequencies, x -> number of elements wanted = O(sqrt(N) + x), as max value of k ~ sqrt(N)
Лично я предпочитаю подход с инвертированным индексом максимальной куче, потому что такие программы, как эластичный поиск, помогают создавать индекс и инвертированный индекс и масштабировать его из коробки в распределенной среде. Это важный аспект, потому что кодирование — это не просто выполнение данного упражнения. Это также о том, как мы воплощаем вещи в жизнь. Это очень и очень важно, особенно при подаче заявки на должности старшего уровня. На данный момент у меня осталось всего 15 минут. Поэтому я начал кодировать.
Код:
def get_top_x_words(products: List[str], x: int) -> List[str]: d = {} for description in products: words = description.split(" ") for word in words: d[word] = d.get(word, 0) + 1 d2 = {} for k, v in d.items(): v2 = d2.get(v, []) v2.append(k) d2[v] = v2 ans = [] count = 0 for k in reverse(sorted(d2.keys())): v = d2[k] ans.extend(v[:min(len(v), x - count)]) count += len(v) if count >= x: break return ans
Таким образом, конструкцию индекса (d в приведенном выше коде) и инвертированного индекса (d2 в приведенном выше коде) можно вынести наружу и хранить либо в памяти, либо в хранилище данных, как эластичный поиск, в зависимости от варианта использования. Остальная часть кода больше связана с получением первых слов x из инвертированного индекса.
Во время интервью я написал строчку:
count += len(v)
выше
ans.extend(v[:min(len(v), x - count)])
и интервьюер определил это. Он попросил меня исправить это. Я извинился и исправил. В целом обсуждение прошло гладко, и интервьюеру понравился мой разговор, в котором я рассказал о некоторых деталях подхода. Позже рекрутер сказал мне, что я получил Strong Hire в этом раунде.
Улучшения:
- Из-за нехватки времени во время интервью я не мог реализовать сортировку подсчетом для обратной сортировки инвертированного индекса.
- Кроме того, значение в инвертированном индексе, который я использовал выше, представляет собой список. На практике набор имеет больше смысла, так как мы можем обновлять элемент как в индексе (d), так и в инвертированном индексе (d2) за постоянное время. Однако в этом случае мы должны правильно пройти через d2, чтобы собрать x элементов.
Дайте мне знать, если у вас есть какие-либо комментарии/предложения.