DP: Longest Common Subsequence (LCS)

06 Oct 2011 | By Mihai Roman | Comments | Tags dynamic programming algorithms google C/C++
Given two sequences X = (x1, x2, … , xmi) and Y= (y1, y2, …, yni) we wish to find a maximum-length common subsequence of X and Y.

Given a sequences X = (x1, x2, … , xmi), Z= (z1, z2, …, zk) is a subsequence of X if there exists a strictly increasing sequence i1, i2, … , ik of indices of X such that for all j= 1, 2, … , k, we have xij = zj.

Given two sequences X and Y , we say that a sequence Z is a common subsequence of X and Y if Z is a subsequence of both X and Y .

int** init_matrix(int n, int m, int d) {
  int ** A = new int*[n];
  for (int i = 0; i < n; i++) {
    A[i] = new int[m];
    for (int j = 0; j < m; j++) {
     A[i][j] = d;
    }
  }
  return A;
}

void delete_matrix(int** A, int n) {
  for (int i = 0; i < n; i++) delete[] A[i];
  delete[] A;
}

#define UP  1
#define LEFT 2
#define DIAG 3

void get_path(int* a, int** B, int n, int m, int* c, int &k) {
  if (n > 0 && m > 0) {
    if (B[n][m] == DIAG) {
      get_path(a, B, n - 1, m - 1, c, k);
      c[k++] = a[n];
    } else if (B[n][m] == UP) {
       get_path(a, B, n - 1, m, c, k);
    } else 
       get_path(a, B, n, m - 1, c, k);
  } 
}

void lcs(int* a, int n, int* b, int m, int* c, int &k) {
  int** A = init_matrix(n + 1, m + 1, 0);
  int** B = init_matrix(n + 1, m + 1, 0);
  
  for (int i = 1; i < n + 1; i++) {
    for (int j = 1; j < m; j++) {
      if (a[i] == b[j]) {
        A[i][j] = A[i - 1][j - 1] + 1;
        B[i][j] = DIAG;
      } else {
        if (A[i][j - 1] < A[i - 1][j]) {
          A[i][j] = A[i - 1][j];
          B[i][j] = UP;
        } else {
          A[i][j] = A[i][j - 1];
          B[i][j] = LEFT;
        }
      }
    }
  }
  get_path(a, B, n, m, c, k);
  delete_matrix(A, n + 1);
  delete_matrix(B, n + 1); 
}

Sorting Algorithms in C/C++ - Part 3

05 Oct 2011 | By Mihai Roman | Comments | Tags sorting basics algorithms C/C++

Today we’re going through non-comparative sorting algorithms that also sort in O(n) time!

Counting Sort

The counting sort is fast algorithm for sorting small integers.

Worst case performance О(n)
Best case performance O(n)
Average case performance О(n)
Worst case space complexity O(maxn)
const int k = 1000;
int* count_sort(int n, int* v) {
  int c[k];
  int b[k];
  for (int i = 0; i < k; i++) {
    c[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    c[v[i]]++;
  }
  for (int i = 1; i < k; i++) {
    c[i] = c[i] + c[i-1];
  }
  for (int i = n-1; i >= 0; i--) {      
    b[c[v[i]] - 1] = v[i];
    c[v[i]]--;
  }
  for (int i = 0; i < n; i++) {
    v[i] = b[i];
  }
  return v;
}

Radix Sort

The following implementation of Radix sort uses counting sort to in O(lg(n)) a vector of integers.

Worst case performance О(n)
Best case performance O(n)
Average case performance О(n)
Worst case space complexity O(n)
const int k = 10;
const int ndigits = 5;

int by_digit(int n, int d) {
  return n / d % 10;
}

int * csort(int n, int* v, int d) {
  int c[k];
  int b[k];
  for (int i = 0; i < k; i++) {
    c[i] = 0;
  }
  for (int i = 0; i < n; i++) {
   c[by_digit(v[i], d)]++;
  }
  for (int i = 1; i < k; i++) {
    c[i] += c[i - 1];
  }
  for (int i = n-1; i >= 0; i--) {
    b[c[by_digit(v[i], d)]-1] = v[i];
    c[by_digit(v[i], d)]--;
  }
  for (int i = 0; i < n; i++) {
    v[i] = b[i];
  }
  return v;
}

int * radix_sort(int n, int* v) {
  //UPDATE: Thanks Alex.
  int d = 1;
  for (int i = 0; i < ndigits; i++) {
    csort(n, v, d);
    d *= 10;
  }
  return v;
}

Sorting Algorithms in C/C++ - Part 2

04 Oct 2011 | By Mihai Roman | Comments | Tags sorting basics algorithms C/C++ divide and conquer

Today we’re going through O(n*log(n)) algorithms: QuickSort, MergeSort and HeapSort.

Quick Sort

Worst case performance О(n^2)
Best case performance O(n*log(n))
Average case performance О(n*log(n))
Worst case space complexity O(1) auxiliary
int partition(int* v, int p, int q) {
  int x = v[q];
  int i = p - 1;
  for (int j = p; j < q; j++) {
    if (v[j] >= x) {
      i++;
      swap(v + j, v + i);
    }
  }
  swap(v + q, v + i + 1);
  return i + 1;
}

int* quick_sort(int* v, int p, int q) {
  if (p < q) {
    int r = partition(v, p, q);
    quick_sort(v, p, r - 1);
    quick_sort(v, r + 1, q); 
  }
  return v;
}

Merge Sort

Worst case performance О(n*log(n))
Best case performance O(n*log(n))
Average case performance О(n*log(n))
Worst case space complexity O(n)
void merge(int * c, int* v, int p, int q, int r) {
  int i = p;
  int j = r + 1;
  int k = p;
  while (i <= r && j <= q) {
    if (v[i] < v[j]) c[k++] = v[i++];
    else c[k++] = v[j++];
  }
  for (int a = i; a <= r; a++) c[k++] = v[a];
  for (int a = j; a <= q; a++) c[k++] = v[a];
  for (int a = p; a < k; a++) v[a] = c[a]; 
}

void merge_sort(int* c, int* v, int p, int q) {
  if (p < q){
    int r = (q + p) / 2;
    merge_sort(c, v, p, r);
    merge_sort(c, v, r + 1, q);
    merge(c, v, p, q, r);
  }
}
int*  merge_sort_in_place(int n, int* v) {
  if (n < 1) return v;
  int* c = new int[n];
  merge_sort(c, v, 0, n - 1);
  delete[] c;
  return v;
}

void swap(int * const &a, int * const &b) {
  int c = *a;
  *a = *b;
  *b = c;
}

Heap Sort

void swap(int* a, int* b) {
  int c = *a;
  *a = *b;
  *b = c;
}

int left(int n, int node) {
   int c = node * 2;
   return c > n ? n : c;
}

int right(int n, int node) {
  int c = node * 2 + 1;
  return c > n ? n : c;
}

void heapify(int* heap,int n, int node) {
   int l = left(n, node);
   int r = right(n, node);
   int max = node;
   if (heap[max] < heap[l]) max = l;
   if (heap[max] < heap[r]) max = r;
   if (max != node) {
    swap(heap + node, heap + max);
    heapify(heap, n, max);
   }
}

void heapsort(int* v, int n) {
  for (int i = n / 2; i >= 0; i--) {
    heapify(v, n, i);
  }
}

Sorting Algorithms in C/C++ - Part 1

03 Oct 2011 | By Mihai Roman | Comments | Tags sorting basics algorithms C/C++

Bubble Sort

Worst case performance О(n^2)
Best case performance O(n)
Average case performance О(n^2)
Worst case space complexity O(1) auxiliary
int* bubble_sort(const int &n, int * const &v) {
  bool s = true;
  int k = n;
  while (s) {
    s = false;
    k--;
    for (int i = 0; i < k; i++) {
      if (v[i] < v[i + 1]) {
         swap(v + i, v + i + 1);
         s = true;
      }
    } 
  }
  return v;
}

Insertion Sort

Worst case performance О(n^2)
Best case performance O(n)
Average case performance О(n^2)
Worst case space complexity O(1) auxiliary
int* insertion_sort(int n, int* v) {
  for (int i = 1; i < n; i++) {
    int value = v[i];
    int j = i;
    while (j > 0 && v[i] > value) {
      v[j] = v[j - 1];
      j--;    
    }
    v[j] = value;
  }
  return v;
}

Selection Sort

Worst case performance О(n^2)
Best case performance O(n^2)
Average case performance О(n^2)
Worst case space complexity O(1) auxiliary
int* selection_sort(int n, int* v) {
  for (int i = 0; i < n; i++) {
    int max = i;
    for (int j = i+1; j < n; j++) {
      if (v[j] > v[max]) max = j; 
    }
    swap(v + i, v + max);
  }
  return v;
}

void swap(int * const &a, int * const &b) {
  int c = *a;
  *a = *b;
  *b = c;
}

Dynamic Programming Algorithms List

02 Oct 2011 | By Mihai Roman | Comments | Tags SWE dynamic programming google algorithms

The following is a list of dynamic programming problems that you should be able to implement during an algorithmic phone interview screening.

Shortest Path in Dags

A dag is a directed acyclic graph. A dag can be linearized, such as the nodes can be arranged on a line so that all edges go from left to right (topological sort). Finding the shortest path in dags has a classic dynamic programming solution.

Longest Increasing Subsequence (LIS)

Given a sequence of numbers a1, a2, … , an find the longest increasing subsequence. A sequence is any subset of these numbers, taken in order: a_i1, a_i2, …, a_ik where -1 < i1 < i2…<ik.

Longest Common Subsequence (LCS)

Given two sequences X = (x1, x2, … , xmi) and Y= (y1, y2, …, yni) we wish to find a maximum-length common subsequence of X and Y.

Given a sequences X = (x1, x2, … , xmi), Z= (z1, z2, …, zk) is a subsequence of X if there exists a strictly increasing sequence i1, i2, … , ik of indices of X such that for all j= 1, 2, … , k, we have xij = zj.

Given two sequences X and Y , we say that a sequence Z is a common subsequence of X and Y if Z is a subsequence of both X and Y .

Edit Distance

Given a dictionary of N words and another word W, find the word in the dictionary that is closest to W. The measure of closeness if given by the number of operations applied on input word to match a dictionary word. Possible operations: insert, delete and replace a letter.

Knapsack

During a robbery, a burglar finds much more loot than he had expected and has to decide what to take. His bag (or “knapsack”) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1, . . . , wn and dollar value v1, . . . , vn. What’s the most valuable combination of items he can fit into his bag?

There are two versions of this problem: 1) unlimited quantities of each item available or 2) there is one of each item.

Chain Matrix Multiplication

How do we determine the optimal order, if we want to compute A1 × A2 × · · · × An, where the Ai’s are matrices with dimensions m0 × m1, m1 × m2, . . . , mn−1 × mn, respectively?

Floyd-Warshall Algorithm

Find the all pairs shortest paths in a graph.

The Traveling Salesman Problem

Minimize the overall distance traveled by a salesman that wants to visit each town exactly once, starting from his hometown. Given the pairwise distances between cities, what is the best order in which to visit them?

Independent Sets of Trees

Find the largest independent set of a tree.

Stairs Problem

A man climbs n stairs. In one step, he can only climb one or two stairs. How many ways can the man climb the n stairs?

Rocks Problem

A child has n rocks. He can arrange the rocks in multiple layers, each layer having less rocks than its base layer. How many ways can the child arrange his n rocks?

Maximum Subsequence

Given a sequence of numbers A = (a1, a2, …, an), find the subsequence with the maximum sum. A subsequence is a sequence of S= (a_k, a_k+1,… a_k+p) of elements of sequence A.

Maximum Submatrix

Similar to the maximum subsequence problem, find the submatrix with the maximum sum of all its elements.

References:
Introduction to Algorithms by Cormen et all
Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

1 2 3 4 5 6 7 8 9