Вопросы и ответы Toptal Live Interview

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

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

Для реализации этих решений мы можем использовать рекурсию.

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


Q2. Как оптимально вычислить p^k, где k — целое число (положительное/отрицательное)? Какова сложность решения?

Одним из самых простых решений было бы умножение результата на p k раз. Временная сложность решения будет равна O(k). Но есть и более эффективное решение.

Для P^k, если k = a * b, то P^k = (P^a)^b; аналогично

P^k = (P^2)^(k/2). Таким образом, мы можем каждый раз уменьшать количество итераций вдвое, что приводит к временной сложности O(log(n)).

Итак, похоже, что проблема может быть разделена на две подпроблемы. Это можно решить рекурсивно.

# @param {Float} x
# @param {Integer} n
# @return {Float}

def my_pow(x, n)
  if n == 0
    return 1
  elsif n > 0
    if n.even?
      return my_pow(x*x, n/2)
    else
      return x*my_pow(x*x, (n-1)/2)
    end
  elsif n < 0
    1/my_pow(x,n.abs)
  end
end
Вход в полноэкранный режим Выход из полноэкранного режима

Алгоритмы сортировки

Bogo Sort

Это самый неэффективный алгоритм, который в лучшем случае имеет производительность O(n) и среднюю производительность O((n+1)!).
В этом алгоритме мы перемешиваем заданный массив и каждый раз проверяем, отсортирован ли массив магическим образом или нет.

Сортировка по выбору

В этом алгоритме, если есть заданный массив a=[2,5,1,3,1,7,3,4], мы берем другой пустой массив b. Затем итеративно заполняем данные в массиве b в порядке возрастания.

Наилучший случай, наихудший случай и средняя сложность составляют O(n^2).

Сортировка вставкой

Быстрая сортировка

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

JS-реализация

a = [4, 3, 2, -4, 5, 3, 0, 0]

function qs(a, l = 0, r = a.length - 1) {
  if (l > r) return
  const pivot = partition(a, l, r)

  qs(a, l, pivot - 1)
  qs(a, pivot + 1, r)
}

function partition(a, l, r) {
  const pi = a[r]
  let i = l - 1
  for (let j = l; j < r; j++) {
    if (a[j] <= pi) {
      i++;
      swap(a, i, j)
    }
  }
  swap(a, i + 1, r)
  return i + 1
}

function swap(a, i, j) {
  b = a[i];
  a[i] = a[j];
  a[j] = b;
}


console.log("a", a)
qs(a)
console.log("output:", a)
Вход в полноэкранный режим Выход из полноэкранного режима
Вывести
$ node sort.js                                     1 ↵
a [
  4, 3, 2, -4,
  5, 3, 0,  0
]
output: [
  -4, 0, 0, 2,
   3, 3, 4, 5
]

Вход в полноэкранный режим Выход из полноэкранного режима

Реализация Ruby

def qs(a, l = 0, r = a.length - 1)
  return if l > r

  pivot = partition(a, l, r)
  qs(a, l, pivot - 1)
  qs(a, pivot + 1, r)
end

def partition(a, l, r)
  pivot = a[r]

  i = l - 1
  j = l
  while j < r
    if a[j] < pivot
      i          += 1
      a[i], a[j] = a[j], a[i]
    end
    j += 1
  end
  a[i + 1], a[r] = a[r], a[i + 1]
  i + 1
end

a = [4, 3, 2, -4, 5, 3, 0, 0]
puts "a: #{a}"
qs(a)
puts "output: #{a}"


Вход в полноэкранный режим Выход из полноэкранного режима
Вывод
$ ruby sort.rb                                   130 ↵
a: [4, 3, 2, -4, 5, 3, 0, 0]
output: [-4, 0, 0, 2, 3, 3, 4, 5]

Ввести полноэкранный режим Выход из полноэкранного режима

Оцените статью
devanswers.ru
Добавить комментарий