После 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 в этом раунде.

Улучшения:

  1. Из-за нехватки времени во время интервью я не мог реализовать сортировку подсчетом для обратной сортировки инвертированного индекса.
  2. Кроме того, значение в инвертированном индексе, который я использовал выше, представляет собой список. На практике набор имеет больше смысла, так как мы можем обновлять элемент как в индексе (d), так и в инвертированном индексе (d2) за постоянное время. Однако в этом случае мы должны правильно пройти через d2, чтобы собрать x элементов.

Дайте мне знать, если у вас есть какие-либо комментарии/предложения.