Q1: What are Divide and Conquer algorithms? Describe how they work. Can you give any common examples of the types of problems where this approach might be used?

Ans: As the name suggests, Divide & Conquer algorithms are a problem solving technique in which we divide the problem into multiple sub-problems. We do so until we reach to a state where no need to further divide and can be solved directly. Then we combine them to get the comprehensive solution.

We can use recursion to implement these solutions.

This technique is used in famous algorithms like binary search, merge sort, quick sort, etc.

Q2. How would you optimally calculate p^k, where k is an integer(positive/negative)? What is the complexity of the solution?

One of the simplest solution would be, multiplying the result with p k times. The time complexity of the solution would be O(k). But there is also a more efficient solution.

For P^k, if k = a * b, then P^k = (P^a)^b; similarly

P^k = (P^2)^(k/2). In this way, we can reduce the number of iteration by half every time. which results O(log(n)) time complexity.

so, looks like the problem can be divided into two sub-problems. This can be solved recursively.

# @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

Sorting Algorithms

Bogo Sort

This is the most inefficient algorithm which has the best case performance of O(n) and average performance of O((n+1)!).
In this algorithm we shuffle the given array and every-time check if the array is magically sorted or not.

Selection Sort

In this algorithm, if there is a given array a=[2,5,1,3,1,7,3,4], we take another empty array b. Then, we iteratively fill data in array b in ascending order.

The best case, worst case and average complexity is O(n^2).

Insertion Sort

Quick Sort

In this algorithm, we use divide & conquer technique. We partition the given array from a pivot into two arrays in which first array will contain elements that are smaller than the pivot and the other array will contain elements larger than pivot.
We will repeat the process for these two arrays and recursively sort the given array in-place.

JS Implementation

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)

Output

$ node sort.js                                     1 ↵
a [
  4, 3, 2, -4,
  5, 3, 0,  0
]
output: [
  -4, 0, 0, 2,
   3, 3, 4, 5
]

Ruby Implementation

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}"

Output

$ ruby sort.rb                                   130 ↵
a: [4, 3, 2, -4, 5, 3, 0, 0]
output: [-4, 0, 0, 2, 3, 3, 4, 5]