Алгоритм интервью с Google

Я долгое время скрывался, и просто имел интервью с Google, где они задали мне этот вопрос:

Различные артисты хотят выступать в Королевском Альберт-Холле, и вы несете ответственность за планирование их концерты. Запросы на участие в холле размещаются по первому политика. Только одно исполнение возможно в день и, кроме того, не может быть никаких концертов происходят в течение 5 дней друг с другом.

Учитывая заданное время d, что невозможно (т.е. в течение 5 дней с уже запланированного времени, uled), дать алгоритм O (log n) -time, чтобы найти следующий доступный день d2 (d2 > d).

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

Ответ 1

Вам нужно обычное двоичное дерево поиска интервалов доступных дат. Просто найдите интервал, содержащий d. Если он не существует, перейдите к следующему (по порядку) интервалу до точки остановки поиска.

Примечание: смежные интервалы должны быть объединены в один node. Например: интервалы доступных дат {2 - 15} и {16 - 23} должны стать {2 - 23}. Это может произойти, если бронирование концерта было отменено.

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

Ответ 2

Храните запланированные концерты в двоичном дереве поиска и найдите возможное решение, выполнив двоичный поиск.

Что-то вроде этого:

FindDateAfter(tree, x):
  n = tree.root
  if n.date < x 
    n = FindDateAfter(n.right, x)
  else if n.date > x and n.left.date < x
    return n
  return FindDateAfter(n.left, x)

FindGoodDay(tree, x):
  n = FindDateAfter(tree, x)
  while (n.date + 10 < n.right.date)
    n = FindDateAfter(n, n.date + 5)
  return n.date + 5

Ответ 3

Я использовал двоичное дерево поиска (BST), которое содержит диапазоны для допустимых свободных дней, которые могут быть запланированы для выступлений. Один из диапазонов должен заканчиваться int.MaxValue, потому что у нас есть бесконечное количество дней, поэтому оно не может быть связано.

Следующий код выполняет поиск ближайшего дня к запрашиваемому дню и возвращает его.

Временная сложность O (H), когда H - высота дерева (обычно H = log (N), но в некоторых случаях может стать H = N). Сложность пространства такая же, как и временная сложность.

public static int FindConcertTime(TreeNode<Tuple<int, int>> node, int reqDay)
{
    // Not found!
    if (node == null)
    {
        return -1;
    }
    Tuple<int, int> currRange = node.Value;
    // Found range.
    if (currRange.Item1 <= reqDay &&
        currRange.Item2 >= reqDay)
    {
        // Return requested day.
        return reqDay;
    }
    // Go left.
    else if (currRange.Item1 > reqDay)
    {
        int suggestedDay = FindConcertTime(node.Left, reqDay);
        // Didn't find appropriate range in left nodes, or found day
        // is further than current option.
        if (suggestedDay == -1 || suggestedDay > currRange.Item1)
        {
            // Return current option.
            return currRange.Item1;
        }
        else
        {
            // Return suggested day.
            return suggestedDay;
        }
    }
    // Go right.
    // Will always find because the right-most node has "int.MaxValue" as Item2.
    else //if (currRange.Item2 < reqDay)
    {
        return FindConcertTime(node.Right, reqDay);
    }
}

Ответ 4

Я думаю, что все, что он задает, это двоичная реализация search. Найдите элемент, который является следующим более высоким. Это может следовать тому же механизму, что и стандартный бинарный поиск, но если вам нужно реализовать сохранение отсортированного массива, вы можете использовать дерево в соответствии с perreal. Для текущего вопроса в интервью было бы достаточно bsearch.

Ответ 5

Храните количество использованных ночей в год, квартал и месяц. Чтобы найти бесплатную ночь, найдите первый год, который не полностью забронирован, затем квартал в течение этого года, затем месяца. Затем проверьте каждую ночь в этом месяце.

Неисправности в календарной системе делают это немного сложнее, поэтому вместо использования лет и месяцев вы можете применить идею для единиц из 4 ночей как "месяц", 16 ночей как "четверть" и т.д.

Ответ 6

Почему бы не попробовать использовать Union-Find? Вы можете сгруппировать каждый день концерта + следующие 5 дней как часть одного набора, а затем выполнить НАЙТИ в указанный день, который вернет следующий установленный идентификатор, который будет вашей следующей датой концерта.

Если реализовано с использованием дерева, это дает сложность времени O (log n).

Ответ 7

Предположим, что на уровне 1 доступны все данные графика. Групповой график 16-дневного расписания на уровне 2. Статус группы 16 уровня 2 на уровне 3. Статус группы 16 уровня 3 на уровне 4. В зависимости от количества дней, которые вы хотите расширить, увеличьте уровень.

Теперь выполните поиск с более высокого уровня и выполните двоичный поиск в конце.

Ответ 8

Асимптотическая сложность: - Это означает, что время выполнения меняется по мере увеличения ввода. предположим, что у нас есть входная строка "abcd". Здесь мы проходим через каждый символ, чтобы найти его длину, поэтому затраченное время пропорционально no символов в строке, например n no из char. Таким образом, O (n). но если мы поместим длину строки "abcd" в переменную, то независимо от того, как долго длина строки будет, мы все равно можем найти длину строки, посмотрев на переменную len. (Len = 4). ex: return 23. Независимо от того, что вы вводите, мы все равно имеем результат 23. поэтому сложность O (1). Таким образом, программа будет работать в постоянном времени по размеру ввода. для O (log n) - операции выполняются с логарифмическими шагами.

https://drive.google.com/file/d/0B7eUOnXKVyeERzdPUE8wYWFQZlk/view?usp=sharing

Соблюдайте изображение в приведенной выше ссылке. Здесь мы видим линию сгиба (логарифмическая линия). Здесь мы можем сказать, что для небольших входов нотация O (log n) работает хорошо, так как время меньше, чем мы можем видеть в изгибе, но когда вход растет, линейная нотация i.e O (n) считается лучшим способом. Есть также лучшие и худшие сценарии, которые можно увидеть. Как и вышеприведенный пример.

Вы также можете обратиться к этому обману для алгоритмов: http://bigocheatsheet.com/

Ответ 9

Это уже упоминалось выше, но в основном сохраняйте его простым двоичным деревом. Вы знаете, что двоичное дерево имеет сложность log N. Итак, вы уже знаете, какой алгоритм вам нужно использовать. Все, что вам нужно сделать, это создать структуру дерева node и использовать алгоритм вставки двоичного дерева, чтобы найти следующую доступную дату: Возможный вариант: Дерево node имеет два атрибута: d (дата концерта) и d + 5 (дата окончания для периода блокировки 5 дней). Снова, чтобы это было просто, используйте временную метку для двух атрибутов даты. Теперь тривиально найти следующую доступную дату, используя алгоритм вставки двоичного дерева inder с начальным условием root = null.