Category Archives: Divide and Conquer

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this … Continue reading →

C++: 01 void quicksort(int A[], int l, int u) 02 { 03   int i, m; 04   if(l>=u) return; 05   swap(A, l, randint(l,u)); 06   m=l; 07   for(i=l+1;i<=u;i++) 08     if(A[i]<A[l]) 09       swap(A,++m,i); 10   swap(A,l,m); 11   quicksort(l,m–1); 12   quicksort(m+1,u); 13 }

Implement pow(x, n). C++: 01 double pow(double x, int n) { 02        if(n==0) 03            return 1; 04        if(n==1) 05            return x; 06        bool … Continue reading →

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is, Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]. C++: … Continue reading →