[LeetCode] Unique Binary Search Trees II, DP Solution

Posted on March 20, 2014 by admin

Facts

How many binary tree and binary search tree can be made on n nodes with key values 1, 2, …, n?

# of BST - (2n)C(n) /(n+1) -- catalan number
# of BT - catalan number * n! = 2n ! / (n+1) !

In BT the layout matters, but the position doesn't. 1-2-3 is same as 2-1-3 if 2 and 1 as roots. In BST, they are different.

Solutions

not so good solution in post: O(2^n) complexity because overlapping sub-trees in the same (start, end) range is not reused.

Two-dimension dp is used (similar to the matrix problem in CLRS). only that the result for each range is a vector

For BT, only one-dimension dp is necessary, i.e., # of nodes

Implementation

// enum version for BST
// two dimension dp + vector for result
// only store tree node ptrs so
vector<TreeNode*> UniqueBinarySearchTree(int n){
    vector<vector<vector<TreeNode*>>> dp;
    dp.reserve(n);

    // init: push null to all dp[i][j] where i>j
    // dp[0][y] is not
    for(int i=0; i<n; i++)
        dp[i].reserve(n);
        for(int j=0; j<i; j++){
            dp[i][j].push_back(null);
        }

    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++){
            // use any node between i and j as root
            for(int k=i; k<=j; k++){
                // loop over all subtrees
                for(int m=0; m<dp[i][k-1].size(); m++)
                    for(int n=0; n<dp[k+1][j].size(); n++){
                        TreeNode* root=new TreeNode(k);
                        root->left=dp[i][k-1][m];
                        root->right=dp[k+1][j][n];
                        dp[i][j].push_back(root);
                    }
            }
        }

    return dp[0][n-1];
}

// enum version for BST

// two dimension dp + vector for result

// only store tree node ptrs so

vector<TreeNode*> UniqueBinarySearchTree(int n){

vector<vector<vector<TreeNode*>>> dp;

dp.reserve(n);

// init: push null to all dp[i][j] where i>j

// dp[0][y] is not

for(int i=0; i<n; i++)

dp[i].reserve(n);

for(int j=0; j<i; j++){

dp[i][j].push_back(null);

}

for(int i=1; i<=n; i++)

for(int j=i; j<=n; j++){

// use any node between i and j as root

for(int k=i; k<=j; k++){

// loop over all subtrees

for(int m=0; m<dp[i][k-1].size(); m++)

for(int n=0; n<dp[k+1][j].size(); n++){

TreeNode* root=new TreeNode(k);

root->left=dp[i][k-1][m];

root->right=dp[k+1][j][n];

dp[i][j].push_back(root);

}

return dp[0][n-1];

}

A String Problem Using Invert Index

Posted on March 5, 2014 by admin

Problem

Given a list of sentences, find two sentences with the maximum common words. e.g.,

This is a good day

This is a bad day

That was good day

You need to return the first and the second sentences because they share four common words.

Implementation

public int maxCommon(List<String> sentences) {
    int maxCommonWords = 0;

    // This will hold our reverse index
    // It will map from a word to the indexes of the sentences that contain
    // that word.
    Map<String, List<Integer>> reverseIndex = new HashMap<String, List<Integer>>();

    // So the first step is to populate this reverse index
    for (int i = 0; i < sentences.size(); i++) {
        for (String word : sentences.get(i).split("[ \t]+")) {
            if (!reverseIndex.containsKey(word)) {
                reverseIndex.put(word, new ArrayList<Integer>());
            }
            reverseIndex.get(word).add(i);
        }
    }

    // This is our matrix that holds number of common words between
    // two sentences. 
    int[][] commonWords = new int[sentences.size()][sentences.size()];

    // Now we go through the indexes stored in reverseIndex.
    // We increment every possible combination of sentences contained
    // within the list of sentence indexes. Adjust the maxCommonWords as needed.
    for (String word : reverseIndex.keySet()) {
        List<Integer> indexes = reverseIndex.get(word);
        for (int i = 0; i < indexes.size(); i++) {
            for (int j = i + 1; j < indexes.size(); j++) {
                commonWords[indexes.get(i)][indexes.get(j)] += 1;
                if (commonWords[i][j] > maxCommonWords) {
                    maxCommonWords = commonWords[i][j];
                }
            }
        }
    }

    return maxCommonWords;
}

public int maxCommon(List<String> sentences) {

int maxCommonWords = 0;

// This will hold our reverse index

// It will map from a word to the indexes of the sentences that contain

// that word.

Map<String, List<Integer>> reverseIndex = new HashMap<String, List<Integer>>();

// So the first step is to populate this reverse index

for (int i = 0; i < sentences.size(); i++) {

for (String word : sentences.get(i).split("[ \t]+")) {

if (!reverseIndex.containsKey(word)) {

reverseIndex.put(word, new ArrayList<Integer>());

}

reverseIndex.get(word).add(i);

}

// This is our matrix that holds number of common words between

// two sentences.

int[][] commonWords = new int[sentences.size()][sentences.size()];

// Now we go through the indexes stored in reverseIndex.

// We increment every possible combination of sentences contained

// within the list of sentence indexes. Adjust the maxCommonWords as needed.

for (String word : reverseIndex.keySet()) {

List<Integer> indexes = reverseIndex.get(word);

for (int i = 0; i < indexes.size(); i++) {

for (int j = i + 1; j < indexes.size(); j++) {

commonWords[indexes.get(i)][indexes.get(j)] += 1;

if (commonWords[i][j] > maxCommonWords) {

maxCommonWords = commonWords[i][j];

}

return maxCommonWords;

}

1d and 2d local minimum problem

Posted on February 28, 2014 by admin

O(lgn) 1d local minimum implementation

int findLocalmin(int a[], int n){
  int low=0;
  int high=n-1;
  while(low<=high){
    mid = low + (high-low)/2;
    if((mid-1 < 0 || a[mid] <= a[mid-1])&&
       mid+1 > n-1 || a[mid] <= a[mid+1]){
      return a[mid];
    }elseif(mid-1 >= 0 && a[mid] > a[mid-1]){
      high = mid-1;
    }else{
      low = mid+1;
    }
  }
}

int findLocalmin(int a[], int n){

int low=0;

int high=n-1;

while(low<=high){

mid = low + (high-low)/2;

if((mid-1 < 0 || a[mid] <= a[mid-1])&&

mid+1 > n-1 || a[mid] <= a[mid+1]){

return a[mid];

}elseif(mid-1 >= 0 && a[mid] > a[mid-1]){

high = mid-1;

}else{

low = mid+1;

}

O(lgn) 2d local minimum implementation (downhill)

int findLocalmin( int arr[], int start_x, int start_y, int sz_x, int sz_y ){
  int mid_x = start_x + sz_x/2;
  int mid_y = start_y + sz_y/2;

  // Default min
  int min_x = mid_x;
  int min_y = start_y;
  int min_val = arr[ mid_x + start_y*width ];

  // Min of cross-shape
  for( int i=1; i<sz_y; i++ ){
    if( arr[ mid_x + (start_y+i)*width ] < min_val ){
      min_y = start_y + i;
      min_val = arr[ mid_x + (start_y+i)*width ]; 
    }
  }
  for( int i=0; i<sz_x; i++ ){
    if( arr[ (start_x+i) + mid_y*width ] < min_val ){
      min_x = start_x+i;
      min_y = mid_y;
      min_val = arr[ (start_x+i) + mid_y*width ]; 
    }
  }

  // min at the center of cross
  if((min_y-1 < 0 || arr[min_x+min_y*width] <= arr[min_x+(min_y-1)*width]) &&
     (min_x-1 < 0 || arr[min_x+min_y*width] <= arr[min_x-1+min_y*width]) &&
     (min_x+1 > sz_x-1 || arr[min_x+min_y*width] <= arr[min_x+1+min_y*width]) &&
     (min_y+1 > sz_y-1 || arr[min_x+min_y*width] <= arr[min_x+(min_y+1)*width]){
       return arr[min_x + min_y*width];
  }

  // min in the vertical line
  if( min_x == mid_x ){
    if( sz_x == 1 ){
      return min_x + min_y*width;
    }else{
      int new_min_x = min_x;
      if( arr[ (mid_x-1) + min_y*width ] < min_val ){
        new_min_x = mid_x-1;
        min_val = arr[ (mid_x-1) + min_y*width ];
      }
      if( sz_x > 2 && arr[ (mid_x+1) + min_y*width ] < min_val ){
        new_min_x = mid_x+1;
        min_val = arr[ (mid_x+1) + min_y*width ];
      }
      int new_start_y;
      int new_sz_y;
      if( min_y < mid_y ){
        new_start_y = start_y;
        new_sz_y = mid_y - start_y;
      }else{
        new_start_y = mid_y+1;
        new_sz_y = start_y + sz_y - mid_y -1;
      }
      if( new_min_x == min_x ){
        return min_x + min_y*width;
      }else if( new_min_x < min_x ){
        return findLocalmin( start_x, new_start_y, mid_x-start_x ,new_sz_y );
      }else{
        return findLocalmin( min_x+1, new_start_y, start_x+sz_x-mid_x-1 ,new_sz_y );
      }
    }
  }else{
    // min in the horizental line
    if( sz_y == 1 ){
      return min_x + min_y*width;
    }else{
      int new_min_y = min_y;
      if( arr[ min_x + (mid_y-1)*width ] < min_val ){
        new_min_y = mid_y-1;
        min_val = arr[ min_x + (mid_y-1)*width ];
      }
      if( sz_y > 2 && arr[ min_x + (mid_y+1)*width ] < min_val ){
        new_min_y = mid_y+1;
        min_val = arr[ min_x + (mid_y+1)*width ];
      }
      int new_start_x;
      int new_sz_x;
      if( min_x < mid_x ){
        new_start_x = start_x;
        new_sz_x = mid_x - start_x;
      }else{
        new_start_x = mid_y+1;
        new_sz_x = start_x + sz_x - mid_x -1;
      }
      if( new_min_y == min_y ){
        return min_x + min_y*width;
      }else if( new_min_y < min_y ){
        return findLocalmin( new_start_x, start_y, new_sz_x, mid_y-start_y );
      }else{
        return findLocalmin( new_start_x, min_y+1, new_sz_x, start_y+sz_y-mid_y-1 );
      }
    }
  }

int findLocalmin( int arr[], int start_x, int start_y, int sz_x, int sz_y ){

int mid_x = start_x + sz_x/2;

int mid_y = start_y + sz_y/2;

// Default min

int min_x = mid_x;

int min_y = start_y;

int min_val = arr[ mid_x + start_y*width ];

// Min of cross-shape

for( int i=1; i<sz_y; i++ ){

if( arr[ mid_x + (start_y+i)*width ] < min_val ){

min_y = start_y + i;

min_val = arr[ mid_x + (start_y+i)*width ];

}

for( int i=0; i<sz_x; i++ ){

if( arr[ (start_x+i) + mid_y*width ] < min_val ){

min_x = start_x+i;

min_y = mid_y;

min_val = arr[ (start_x+i) + mid_y*width ];

}

// min at the center of cross

if((min_y-1 < 0 || arr[min_x+min_y*width] <= arr[min_x+(min_y-1)*width]) &&

(min_x-1 < 0 || arr[min_x+min_y*width] <= arr[min_x-1+min_y*width]) &&

(min_x+1 > sz_x-1 || arr[min_x+min_y*width] <= arr[min_x+1+min_y*width]) &&

(min_y+1 > sz_y-1 || arr[min_x+min_y*width] <= arr[min_x+(min_y+1)*width]){

return arr[min_x + min_y*width];

}

// min in the vertical line

if( min_x == mid_x ){

if( sz_x == 1 ){

return min_x + min_y*width;

}else{

int new_min_x = min_x;

if( arr[ (mid_x-1) + min_y*width ] < min_val ){

new_min_x = mid_x-1;

min_val = arr[ (mid_x-1) + min_y*width ];

}

if( sz_x > 2 && arr[ (mid_x+1) + min_y*width ] < min_val ){

new_min_x = mid_x+1;

min_val = arr[ (mid_x+1) + min_y*width ];

}

int new_start_y;

int new_sz_y;

if( min_y < mid_y ){

new_start_y = start_y;

new_sz_y = mid_y - start_y;

}else{

new_start_y = mid_y+1;

new_sz_y = start_y + sz_y - mid_y -1;

}

if( new_min_x == min_x ){

return min_x + min_y*width;

}else if( new_min_x < min_x ){

return findLocalmin( start_x, new_start_y, mid_x-start_x ,new_sz_y );

}else{

return findLocalmin( min_x+1, new_start_y, start_x+sz_x-mid_x-1 ,new_sz_y );

}

}else{

// min in the horizental line

if( sz_y == 1 ){

return min_x + min_y*width;

}else{

int new_min_y = min_y;

if( arr[ min_x + (mid_y-1)*width ] < min_val ){

new_min_y = mid_y-1;

min_val = arr[ min_x + (mid_y-1)*width ];

}

if( sz_y > 2 && arr[ min_x + (mid_y+1)*width ] < min_val ){

new_min_y = mid_y+1;

min_val = arr[ min_x + (mid_y+1)*width ];

}

int new_start_x;

int new_sz_x;

if( min_x < mid_x ){

new_start_x = start_x;

new_sz_x = mid_x - start_x;

}else{

new_start_x = mid_y+1;

new_sz_x = start_x + sz_x - mid_x -1;

}

if( new_min_y == min_y ){

return min_x + min_y*width;

}else if( new_min_y < min_y ){

return findLocalmin( new_start_x, start_y, new_sz_x, mid_y-start_y );

}else{

return findLocalmin( new_start_x, min_y+1, new_sz_x, start_y+sz_y-mid_y-1 );

}

Server Metrics Design

Posted on February 27, 2014 by admin

Problem

Given a server that has requests coming in. Design a data structure such that you can fetch the count of the number requests in the last second, minute and hour.

Implementation

   final int SIZE=60*60; //seconds in one hour
    int[] arr=new int[SIZE];
    int hour=0;
    int minute=0;
    long last=0;

    long currSecond(){
        return System.currentTimeMillis()/1000;
    }

    long clear(){
        long curr=currSecond();
        if(curr>last){
            if(curr-last>=SIZE){
                hour=0;
                minute=0;
                Arrays.fill(arr,0);
            }
            else{
                if(curr-last>=60){
                    minute=0;
                }
                else{
                    for(long i=last-60+1;i<=curr-60;i++){
                        minute-=arr[(int)(i%SIZE)];
                    }
                }

                for(long i=last+1;i<=curr;i++){
                    int p=(int)(i%SIZE);
                    hour-=arr[p];
                    arr[p]=0;
                }
            }
            last=curr;
        }

        return curr;
    }

    void request(){
        long curr=clear();
        arr[(int)(curr%SIZE)]++;
        hour++;
        minute++;
    }

    int lastSecond(){
        long curr=clear();
        return arr[(int)(curr%SIZE)];
    }

    int lastMinute(){
        clear();
        return minute;
    }

    int lastHour(){
        clear();
        return hour;
    }

final int SIZE=60*60; //seconds in one hour

int[] arr=new int[SIZE];

int hour=0;

int minute=0;

long last=0;

long currSecond(){

return System.currentTimeMillis()/1000;

}

long clear(){

long curr=currSecond();

if(curr>last){

if(curr-last>=SIZE){

hour=0;

minute=0;

Arrays.fill(arr,0);

}

else{

if(curr-last>=60){

minute=0;

}

else{

for(long i=last-60+1;i<=curr-60;i++){

minute-=arr[(int)(i%SIZE)];

}

for(long i=last+1;i<=curr;i++){

int p=(int)(i%SIZE);

hour-=arr[p];

arr[p]=0;

}

last=curr;

}

return curr;

}

void request(){

long curr=clear();

arr[(int)(curr%SIZE)]++;

hour++;

minute++;

}

int lastSecond(){

long curr=clear();

return arr[(int)(curr%SIZE)];

}

int lastMinute(){

clear();

return minute;

}

int lastHour(){

clear();

return hour;

}

tail -f implementation using circular buffer

Posted on February 27, 2014 by admin

#include <stdio.h>
#include <stdlib.h>

class TailPrinter{
	private:
		int sz;
		int* queue;
		long i_start;
		long i_end;

		void printEnd( FILE* fp ){
			// Check if there is line to print
			if( i_end + 1 == i_start ){
				return;
			}

			// Goto the start of the ending N lines
			fseek( fp, queue[ i_end % sz ], SEEK_SET );

			// print N lines
			int cnt = 0;
			char c;
			while( (c=fgetc(fp))!=EOF && cnt < sz-1 ){
				putc( c, stdout );
				if( c == '\n' ){
					cnt++;
				}
			}

			// Adjust queue index
			i_end = i_start-1;
		}

		void enqueue( int val ){
			// If queue is full, remove one element
			if( (i_start-i_end)%sz==0 && (i_start-i_end)!=0  ){
				i_end++;
			}
			// Enqueue
			queue[ i_start++ % sz ] = val;
		}

	public:
		TailPrinter( int aTargetNum ): sz( aTargetNum + 1 ), i_start(0), i_end(0) {
			queue = new int[ aTargetNum + 1];
		}	

		~TailPrinter(){
			delete[] queue;
		}

		void printTail( FILE* fp ){
			char c;
			fseek( fp, 0, SEEK_SET );
			enqueue( 0 );
			for(;;){
				c = fgetc( fp );
				if( c == EOF ){
					//If end of file is reached, print the tail
					printEnd( fp );
				}else if( c == '\n' ){
					//For each new line, maintain reference point (keep only last N points)
					enqueue( ftell( fp ) );
				}
			}
		}
};

int main( int argc, char* argv[] ){
	//Check argument number
	if( argc != 2 ){
		printf("Usage: %s <filename>\n", argv[0] );
		return -1;
	}
	//Check if file can be opened
	FILE* fp = fopen(argv[1], "rt");
	if( fp == NULL ){
		printf("Could not open file named \"%s\"\n", argv[1] );
		return -1;
	}
	//Print tail
	TailPrinter* tp = new TailPrinter( 10 );
	tp->printTail( fp );
	fclose( fp );
	return 0;
}

#include <stdio.h>

#include <stdlib.h>

class TailPrinter{

private:

int sz;

int* queue;

long i_start;

long i_end;

void printEnd( FILE* fp ){

// Check if there is line to print

if( i_end + 1 == i_start ){

return;

}

// Goto the start of the ending N lines

fseek( fp, queue[ i_end % sz ], SEEK_SET );

// print N lines

int cnt = 0;

char c;

while( (c=fgetc(fp))!=EOF && cnt < sz-1 ){

putc( c, stdout );

if( c == '\n' ){

cnt++;

}

// Adjust queue index

i_end = i_start-1;

}

void enqueue( int val ){

// If queue is full, remove one element

if( (i_start-i_end)%sz==0 && (i_start-i_end)!=0 ){

i_end++;

}

// Enqueue

queue[ i_start++ % sz ] = val;

}

public:

TailPrinter( int aTargetNum ): sz( aTargetNum + 1 ), i_start(0), i_end(0) {

queue = new int[ aTargetNum + 1];

}

~TailPrinter(){

delete[] queue;

}

void printTail( FILE* fp ){

char c;

fseek( fp, 0, SEEK_SET );

enqueue( 0 );

for(;;){

c = fgetc( fp );

if( c == EOF ){

//If end of file is reached, print the tail

printEnd( fp );

}else if( c == '\n' ){

//For each new line, maintain reference point (keep only last N points)

enqueue( ftell( fp ) );

}

};

int main( int argc, char* argv[] ){

//Check argument number

if( argc != 2 ){

printf("Usage: %s <filename>\n", argv[0] );

return -1;

}

//Check if file can be opened

FILE* fp = fopen(argv[1], "rt");

if( fp == NULL ){

printf("Could not open file named \"%s\"\n", argv[1] );

return -1;

}

//Print tail

TailPrinter* tp = new TailPrinter( 10 );

tp->printTail( fp );

fclose( fp );

return 0;

}

DP Solution for Regular Expression Matching

Posted on February 11, 2014 by admin

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null)
            return false;

        int ls = s.length();
        int lp = p.length();
        boolean[][] dp = new boolean[ls+1][lp+1];
        dp[0][0] = true;

        for (int i = 1; i <= p.length(); i++) {
            dp[0][i] = (p.charAt(i-1) == '*' ? dp[0][i-2] : false);
        }

        for (int i = 1; i <= ls; i++) {
            for (int j = 1; j <= lp; j++) {
                if (p.charAt(j-1) != '*' || j == 1) {
                    dp[i][j] = (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j
-1) == '.') && dp[i-1][j-1];
                }
                else {
                    int it = i;
                    dp[i][j] = false;
                    while (!dp[i][j] && it >= 1) {
                        if((s.charAt(it-1) == p.charAt(j-2) || 
                           '.' == p.charAt(j-2)) && dp[it-1][j-2]) {
                            dp[i][j] = true;
                        }
                        it--;
                    }
                }
            }
        }

        return dp[ls][lp];
    }
}

public class Solution {

public boolean isMatch(String s, String p) {

if (s == null || p == null)

return false;

int ls = s.length();

int lp = p.length();

boolean[][] dp = new boolean[ls+1][lp+1];

dp[0][0] = true;

for (int i = 1; i <= p.length(); i++) {

dp[0][i] = (p.charAt(i-1) == '*' ? dp[0][i-2] : false);

}

for (int i = 1; i <= ls; i++) {

for (int j = 1; j <= lp; j++) {

if (p.charAt(j-1) != '*' || j == 1) {

dp[i][j] = (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j

-1) == '.') && dp[i-1][j-1];

}

else {

int it = i;

dp[i][j] = false;

while (!dp[i][j] && it >= 1) {

if((s.charAt(it-1) == p.charAt(j-2) ||

'.' == p.charAt(j-2)) && dp[it-1][j-2]) {

dp[i][j] = true;

}

it--;

}

return dp[ls][lp];

}

Interview Question: topological sort in Tree

Posted on February 2, 2014 by admin

Problem

Given a text file with 3 columns -- all integers:
id,parent,weight
each line is a node, 'parent' refers to 'id' of another node.
Print out, for each node, the total weight of a sub-tree below this node.

Solution

void PrintSubTreeSum(vector<vector<int> > &Input)
{
    int size = Input.size();
    if(size == 0)
    return;
    vector<int> InDegree(size, 0);
    vector<int> TotalWeight(size,0);
    vector<int> ParentIdx(size,-1);

    for(int i=0;i<size;i++)
    {
        InDegree[Input[i][1]]++;
        TotalWeight[Input[i][0]] = Input[i][2];
        ParentIdx[Input[i][0]] = Input[i][1];
    }

    queue<int> dq;
    for(int i=0;i<size;i++)
    {
        if(InDegree[i]==0)
        dq.push(i);
    }

    while(!dq.empty())
    {
        int curIdx = dq.front();
        dq.pop();

        cout << "Id : " << curIdx << " with subTree weight : " <<
        TotalWeight[curIdx] << endl;

        int ParIdx = ParentIdx[curIdx];
        if(ParIdx<0)
        continue;
        InDegree[ParIdx]--;
        TotalWeight[ParIdx] += TotalWeight[curIdx];
        if(InDegree[ParIdx]==0)
        dq.push(ParIdx);
    }
}

void PrintSubTreeSum(vector<vector<int> > &Input)

{

int size = Input.size();

if(size == 0)

return;

vector<int> InDegree(size, 0);

vector<int> TotalWeight(size,0);

vector<int> ParentIdx(size,-1);

for(int i=0;i<size;i++)

{

InDegree[Input[i][1]]++;

TotalWeight[Input[i][0]] = Input[i][2];

ParentIdx[Input[i][0]] = Input[i][1];

}

queue<int> dq;

for(int i=0;i<size;i++)

{

if(InDegree[i]==0)

dq.push(i);

}

while(!dq.empty())

{

int curIdx = dq.front();

dq.pop();

cout << "Id : " << curIdx << " with subTree weight : " <<

TotalWeight[curIdx] << endl;

int ParIdx = ParentIdx[curIdx];

if(ParIdx<0)

continue;

InDegree[ParIdx]--;

TotalWeight[ParIdx] += TotalWeight[curIdx];

if(InDegree[ParIdx]==0)

dq.push(ParIdx);

}

K Most Frequent Words in a Stream C++ implementation

Posted on January 31, 2014 by admin

C++ implementation for this problem@geeksforgeeks

#define MAX_CHAR 26

struct TrieNode{
    bool isEnd;
    TrieNode* children[MAX_CHAR];
    int indexMinHeap;
    unsigned frequency;
}

struct HeapNode{
    string word_;
    TrieNode* root_;
    HeapNode(const string word, TrieNode* root): word_(word), root_(root){};
}

struct minHeap{
    int count_;
    int capacity_;
    HeapNode* heap_arr;
    minHeap(int capacity): count_(0), capacity_(capacity), heap_arr(new HeapNode*[capacity_]) {};
    ~minHeap(){ delete[] heap_arr;}

    buildMinHeap();
    minHeapify(int indexNode);
    insertIntoMinHeap();
    insertUtils(); // insert both into trie and min heap
    friend class TrieNode;
}

void minHeap::
minHeapify(int indexNode){
    int smallest=indexNode;
    while(smallest<=n/2){
        int left=2*smallest+1;
        int right=2*smallest+2;
        if(heap_arr[left].root->frequency < heap_arr[smallest].root->frequency){
            smallest=left;
        }

        if(heap_arr[right].root->frequency < heap_arr[smallest].root->frequency){
            smallest=right;
        }

        if(smallest!=indexNode){
            heap_arr[smallest].root_->indexMinHeap = indexNode;
            heap_arr[indexNode].root_->indexMinHeap = smallest;
            swap(heap_arr[smallest], heap_arr[indexNode]);
            indexNode=smallest;
        }
        else{
            break;
        }
    }
}

void minHeap::
buildMinHeap(){
    for(int i=(count_-2)/2; i>=0; i--){
        minHeapify(i);
    }
}

void minHeap::
insertIntoMinHeap(TrieNode* root, const string& word){
    // case 1: exist in heap
    if(root->indexMinHeap!=-1){
        minHeapify(root->indexMinHeap);
    // case 2: heap is not full
    }else if(count_ < capacity_){
        root->indexMinHeap=count_;
        heap_arr[count_++]=new HeapNode(word, root);
        buildMinHeap();
    // case 3: replace min in heap
    }else{
        if(heap_arr[0]->root->frequency < root->frequency){
            heap_arr[0]->root->indexMinHeap=-1;
            heap_arr[0]->root=root;
            root->indexMinHeap=0;
            minHeapify(0);
        }
    }
}

// insert into heap and trie
void minHeap::
insertUtils(TrieNode** root, const string& word, int i){
    if(!*root){
        *root=new TrieNode();
    }

    if(i<word.length()){
        insertUtil(root->children[word[i] - 97], word, i+1);
    }else{
        root->isEnd=true;
        root->frequency++;
        insertIntoMinHeap(root, word);
    }    
}

void minHeap::
insertIntoTrieAndHeap(TrieNode**root, const string& word){
    insertUtils(root, word, 0);
}

100

101

102

103

#define MAX_CHAR 26

struct TrieNode{

bool isEnd;

TrieNode* children[MAX_CHAR];

int indexMinHeap;

unsigned frequency;

}

struct HeapNode{

string word_;

TrieNode* root_;

HeapNode(const string word, TrieNode* root): word_(word), root_(root){};

}

struct minHeap{

int count_;

int capacity_;

HeapNode* heap_arr;

minHeap(int capacity): count_(0), capacity_(capacity), heap_arr(new HeapNode*[capacity_]) {};

~minHeap(){ delete[] heap_arr;}

buildMinHeap();

minHeapify(int indexNode);

insertIntoMinHeap();

insertUtils(); // insert both into trie and min heap

friend class TrieNode;

}

void minHeap::

minHeapify(int indexNode){

int smallest=indexNode;

while(smallest<=n/2){

int left=2*smallest+1;

int right=2*smallest+2;

if(heap_arr[left].root->frequency < heap_arr[smallest].root->frequency){

smallest=left;

}

if(heap_arr[right].root->frequency < heap_arr[smallest].root->frequency){

smallest=right;

}

if(smallest!=indexNode){

heap_arr[smallest].root_->indexMinHeap = indexNode;

heap_arr[indexNode].root_->indexMinHeap = smallest;

swap(heap_arr[smallest], heap_arr[indexNode]);

indexNode=smallest;

}

else{

break;

}

void minHeap::

buildMinHeap(){

for(int i=(count_-2)/2; i>=0; i--){

minHeapify(i);

}

void minHeap::

insertIntoMinHeap(TrieNode* root, const string& word){

// case 1: exist in heap

if(root->indexMinHeap!=-1){

minHeapify(root->indexMinHeap);

// case 2: heap is not full

}else if(count_ < capacity_){

root->indexMinHeap=count_;

heap_arr[count_++]=new HeapNode(word, root);

buildMinHeap();

// case 3: replace min in heap

}else{

if(heap_arr[0]->root->frequency < root->frequency){

heap_arr[0]->root->indexMinHeap=-1;

heap_arr[0]->root=root;

root->indexMinHeap=0;

minHeapify(0);

}

// insert into heap and trie

void minHeap::

insertUtils(TrieNode** root, const string& word, int i){

if(!*root){

*root=new TrieNode();

}

if(i<word.length()){

insertUtil(root->children[word[i] - 97], word, i+1);

}else{

root->isEnd=true;

root->frequency++;

insertIntoMinHeap(root, word);

}

void minHeap::

insertIntoTrieAndHeap(TrieNode**root, const string& word){

insertUtils(root, word, 0);

}

Interview Question: iterator implementation

Posted on January 21, 2014 by admin

Design Pattern Gist
1. iterator object is dynamically created from container object :- begin(), end() return iterator obj
2. iterator object keeps the pos state (_cur ptr) :- manipulator for the pos is in iterator
Interface
1. functions: begin(), end(), cur(), next()
2. operators: n/a,n/a,*,++
concrete iterator object
1. current ptr
2. composition to the container object -: one(aggregate) to many(iterators) relations

concrete container object

iterator class == friend class
begin(), end() return iterator object (copy, not reference)

template<typename T>
class Node{ //used by List
    Node(T data, Node<T>* next):_data(data), _next(next){}
    T _data;
    Node<T>* _next;
    friend class List<T>; //only friend can call private
    friend class ListIterator<T>;
};

template<typename T>
class List{
    public:
    List(Node<T>* head=NULL, Node<T>* tail=NULL);
    List(const List<T>& orig);
    List<T>& operator=(const List<T>& orig);
    push_front();push_end();pop_front();pop_end();

    //the following are used for iterator:
    typedef ListIterator<T> iterator;
    iterator begin(){return iterator(_head); }
    iterator end(){return iterator(); }
    private:
    Node<T>* _head, *_tail;
};

template<typename T>
class ListIterator{
    Node<T>* _cur;
    public:
    ListIterator(Node<T>* cur= NULL): _cur(cur){}
    ListIterator(const ListIterator<T>& orig){_cur = orig._cur;}
    ListIterator& operator=(const ListIterator<T>& orig){_cur = orig_cur;
    return *this;}
    bool operator==(const ListIterator<T>& orig){return _cur == orig._cur;}
    ListIterator<T>& operator++(){_cur = _cur->_next; return *this; }
    ListIterator<T> operator++(int i){ ListIterator a(*this); _cur = _cur->_
    next; return a; }
    const T operator*() const {return _cur->_data;}
};

template<typename T>

class Node{ //used by List

Node(T data, Node<T>* next):_data(data), _next(next){}

T _data;

Node<T>* _next;

friend class List<T>; //only friend can call private

friend class ListIterator<T>;

};

template<typename T>

class List{

public:

List(Node<T>* head=NULL, Node<T>* tail=NULL);

List(const List<T>& orig);

List<T>& operator=(const List<T>& orig);

push_front();push_end();pop_front();pop_end();

//the following are used for iterator:

typedef ListIterator<T> iterator;

iterator begin(){return iterator(_head); }

iterator end(){return iterator(); }

private:

Node<T>* _head, *_tail;

};

template<typename T>

class ListIterator{

Node<T>* _cur;

public:

ListIterator(Node<T>* cur= NULL): _cur(cur){}

ListIterator(const ListIterator<T>& orig){_cur = orig._cur;}

ListIterator& operator=(const ListIterator<T>& orig){_cur = orig_cur;

return *this;}

bool operator==(const ListIterator<T>& orig){return _cur == orig._cur;}

ListIterator<T>& operator++(){_cur = _cur->_next; return *this; }

ListIterator<T> operator++(int i){ ListIterator a(*this); _cur = _cur->_

next; return a; }

const T operator*() const {return _cur->_data;}

};

Distributed Hash Table Techniques

Posted on January 2, 2014 by admin

DHT wiki

OS slides 10

CMU slides on distributed system
part 1
system requirement
part 2

replication + caching
partition:
1. horizontal partitioning + consistent Hashing consistent hashing wiki: implication on usage !implementation article shard_wiki
2. master/tablet

data consistency

Yahoo sherpa wiki

Generating IDs
instagram paper more summary
current understanding

timestamp at higher bits :- time sortable IDs
dedicated server: e.g., Apache zookeeper: similar idea as Flickr: single server for generating IDs. Flickr: a ticket server built on mysql's auto-increment and transaction.
sharding by Instagram:
1. timestamp(41 bits)+sharding_id(13 bits)+counter(10bits)
2. logical shards are for each schema
3. counter is per server incremental

Programmer As Innovator

everything I know

[LeetCode] Unique Binary Search Trees II, DP Solution

Facts

Solutions

Implementation

A String Problem Using Invert Index

Problem

Implementation

1d and 2d local minimum problem

O(lgn) 1d local minimum implementation

O(lgn) 2d local minimum implementation (downhill)

Server Metrics Design

Problem

Implementation

tail -f implementation using circular buffer

DP Solution for Regular Expression Matching

Interview Question: topological sort in Tree

Problem

Solution

K Most Frequent Words in a Stream C++ implementation

Interview Question: iterator implementation

Distributed Hash Table Techniques