Toptal 라이브 인터뷰 질문 및 답변

Q1: Divide and Conquer 알고리즘이란 무엇입니까? 그들이 어떻게 작동하는지 설명하십시오. 이 접근 방식이 사용될 수 있는 문제 유형의 일반적인 예를 제시할 수 있습니까?

답변: 이름에서 알 수 있듯이 Divide & Conquer 알고리즘은 문제를 여러 하위 문제로 나누는 문제 해결 기술입니다. 더 이상 나눌 필요가 없고 직접 해결할 수 있는 상태에 도달할 때까지 그렇게 합니다. 그런 다음 포괄적인 솔루션을 얻기 위해 이들을 결합합니다.

재귀를 사용하여 이러한 솔루션을 구현할 수 있습니다.

이 기술은 이진 검색, 병합 정렬, 빠른 정렬 등과 ​​같은 유명한 알고리즘에서 사용됩니다.


Q2. k가 정수(양수/음수)인 p^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

정렬 알고리즘

보고 정렬

이것은 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
]

루비 구현

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]