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 reserved for the max number of servers (physical shards) :- no need to redistribute data when adding more servers
3. counter is per server incremental

Network Interview Summary

Posted on December 5, 2013 by admin

Network Protocols

TCP and UDP

TCP

tcp reliable transmission mechanism

Connection-oriented: three-way handshake + disconnect
1. actually four-way: SYN, SYN/ACK, ACK: SYN/ACK together to save one pkg
2. sender/receiver vs. client/server: initial sequence number (ISN) for both sides ACK=SYNC+1
cumulative retransmission
1. seq number for each byte
2. package by package ack
selective retransmission
1. per package ack

Flow control

receiver side regulate
buffer: sliding window

Congestion control

sender side: algorithms according to ack time out
slow start

UDP

stream (TCP) vs. message/datagram based (UDP) @stackoverflow.com

at the interface, both are datagram internally
UDP
1. send(): send a single message
2. recv(): receive a single message
TCP
1. send()/recv(): send/receive a byte stream

HTTP

Request Message

a request line: method + uri
request headers
an empty line
message body (opt)

Response Message

a Status-Line e.g., HTTP/1.1 200 OK
response headers
an empty line
message body (opt)

Methods: GET, POST, PUT, DELETE, HEAD, etc

Safe methods

only for information retrieval, should not change server states
e.g., GET, HEAD, OPTIONS and TRACE

Idempotent methods

stateless :- idempotent requirement (multiple identical requests==single request)
e.g., PUT and DELETE
POST is not :- PUT is used to create and update (same request not update), POST to create

Stateless connection

servers don't retain information about users

Persistent connection

http connection closed after a single request/response pair
HTTP /1.1 keep-alive-mechanism :- save TCP three-way connections

Secure HTTP

VS.

http vs. REST vs. SOAP http vs. REST@stackovverflow.com REST vs. SOAP

http is a protocol
REST is a set of design rules about how to use http protocol,
SOAP is heavyweight compared to rest

Programmer As Innovator

everything I know

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

Network Interview Summary

Network Protocols

TCP and UDP

TCP

UDP

HTTP

Request Message

Response Message

Safe methods

Idempotent methods

Stateless connection

Persistent connection

Secure HTTP

VS.

http vs. REST vs. SOAP http vs. REST@stackovverflow.com REST vs. SOAP