Similar String

Posted on May 13, 2014 by admin

Problem

Similar string is defined as matching by insert/delete/replace one char of any one of string.

Implementation

#include <iostream>
#include <stdlib.h>

using namespace std;

bool similarString(const string& s1, const string& s2){
	int len1=s1.length();
    int len2=s2.length();
	if(abs(len1-len2)>1) return false;

	// replace
	if(len1 == len2){
		int i=-1, count=0;
		while(++i<len1){
            if(s1[i]!=s2[i]){
                 count++;
            }
        }
		return count==1;
    }

	const string* src=&s1;
	const string* dest =&s2;

    if(len1 > len2){
        src=&s2;
        dest=&s1;
        swap(len1,len2);
    }
	
	// insert
	int i=0, j=0;
	int flag = true;
	while (i < len2){
		if((*src)[i]!=(*dest)[j]){
            if(flag){ 
                flag = false; j++;
            }
            else {
                return false;
            }
        } else {
            i++; j++;
        }
    }
    return true;
}

int main(){
    string s1("abcd");
    string s2("abcd");
    cout << s1 << endl;
    cout << s2 << endl;
    if(similarString(s1, s2)) 
        cout << "true" << endl;
}

#include <iostream>

#include <stdlib.h>

using namespace std;

bool similarString(const string& s1, const string& s2){

int len1=s1.length();

int len2=s2.length();

if(abs(len1-len2)>1) return false;

// replace

if(len1 == len2){

int i=-1, count=0;

while(++i<len1){

if(s1[i]!=s2[i]){

count++;

}

return count==1;

}

const string* src=&s1;

const string* dest =&s2;

if(len1 > len2){

src=&s2;

dest=&s1;

swap(len1,len2);

}

// insert

int i=0, j=0;

int flag = true;

while (i < len2){

if((*src)[i]!=(*dest)[j]){

if(flag){

flag = false; j++;

}

else {

return false;

}

} else {

i++; j++;

}

return true;

}

int main(){

string s1("abcd");

string s2("abcd");

cout << s1 << endl;

cout << s2 << endl;

if(similarString(s1, s2))

cout << "true" << endl;

}

[Leetcode] zigzag conversion

Posted on May 1, 2014 by admin

string zigzag(const string& s, int nRow)
{
    if(nRow <=1) return s;
    bool down=true;
    vector<string> res;
    res.reserve(nRow);
    int j=0;
    for(int i=0;i<s.length();s++)
    {
        if(down){
            res[j++].append(s[i]);
            if(j==nRow){
                down=false;
                j=j-2;
            }
        } else {
            res[j--].append(str[i]);
            if(j<0){
                down=true;
                j=j+2
            }
        } 
    }
    string r;
    for(int i=0;i<res.length();i++){
        r += res[i];  
    }
    return r;
}

string zigzag(const string& s, int nRow)

{

if(nRow <=1) return s;

bool down=true;

vector<string> res;

res.reserve(nRow);

int j=0;

for(int i=0;i<s.length();s++)

{

if(down){

res[j++].append(s[i]);

if(j==nRow){

down=false;

j=j-2;

}

} else {

res[j--].append(str[i]);

if(j<0){

down=true;

j=j+2

}

string r;

for(int i=0;i<res.length();i++){

r += res[i];

}

return r;

}

[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 <iostream>
#include <fstream>
#include <stdlib.h>
#include <string>

class TailPrinter{
private:
    int sz;
    int last_file_pos;
    std::string* queue;
    long start;
    long end;
 
public:
    TailPrinter(int capacity): sz(capacity+1), start(0), end(0){
        queue = new std::string[sz];
    }
    ~TailPrinter(){
        delete[] queue;
    }
    void enqueue(const std::string& line ){
        // If queue is full, remove one element
        if( (end+1)%sz == start%sz  ){
            start++;
        }
        // Enqueue
        queue[end++%sz] = line;
    }

    void printTail(std::ifstream &infile){
        infile.seekg(0, std::ios::end);
        int filesize = infile.tellg();
        if(filesize < last_file_pos){
            // new file started
            last_file_pos=0;
        }

        infile.seekg(last_file_pos, std::ios::beg);
        while(!infile.eof()){
            char line[256];
            infile.getline(line, 256);
            last_file_pos = infile.tellg();
            // std::cout << line << "\n";
            enqueue(line);
        }
        // print result and reset circular buffer
        while(start%sz != end%sz){
            std::cout << queue[start%sz] << "\n";
            start++;
        }
    }
};
 
int main( int argc, char* argv[] ){
    //Check argument number
    if( argc != 3 ){
        printf("Usage: %s <filename>\n", argv[1] );
        return -1;
    }

    TailPrinter tp(atoi(argv[2]));
    for(;;){
        std::ifstream infile(argv[1], std::ios::in);
        tp.printTail(infile);
        sleep(1);
    }

    return 0;
}

#include <iostream>

#include <fstream>

#include <stdlib.h>

#include <string>

class TailPrinter{

private:

int sz;

int last_file_pos;

std::string* queue;

long start;

long end;

public:

TailPrinter(int capacity): sz(capacity+1), start(0), end(0){

queue = new std::string[sz];

}

~TailPrinter(){

delete[] queue;

}

void enqueue(const std::string& line ){

// If queue is full, remove one element

if( (end+1)%sz == start%sz ){

start++;

}

// Enqueue

queue[end++%sz] = line;

}

void printTail(std::ifstream &infile){

infile.seekg(0, std::ios::end);

int filesize = infile.tellg();

if(filesize < last_file_pos){

// new file started

last_file_pos=0;

}

infile.seekg(last_file_pos, std::ios::beg);

while(!infile.eof()){

char line[256];

infile.getline(line, 256);

last_file_pos = infile.tellg();

// std::cout << line << "\n";

enqueue(line);

}

// print result and reset circular buffer

while(start%sz != end%sz){

std::cout << queue[start%sz] << "\n";

start++;

}

};

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

//Check argument number

if( argc != 3 ){

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

return -1;

}

TailPrinter tp(atoi(argv[2]));

for(;;){

std::ifstream infile(argv[1], std::ios::in);

tp.printTail(infile);

sleep(1);

}

return 0;

}

DP Solution for Regular Expression Matching

Posted on February 11, 2014 by admin

bool isMatch(const string& s, const string& p) {
    if (s.empty()) return p.empty();

    int ls = s.length();
    int lp = p.length();
    bool dp[ls+1][lp+1];
    dp[0][0] = true;
    assert(p[0]!='*');
    
    for (int i = 1; i <= lp; i++) {
        dp[0][i] = false;
    }

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

bool isMatch(const string& s, const string& p) {

if (s.empty()) return p.empty();

int ls = s.length();

int lp = p.length();

bool dp[ls+1][lp+1];

dp[0][0] = true;

assert(p[0]!='*');

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

dp[0][i] = false;

}

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

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

if (p[j-1] != '*') {

dp[i][j] = (p[j-1] == s[i-1] || p[j-1] == '.') && dp[i-1][j-1];

}

else {

assert(j!=1 && p[j-2]!='*');

int it = i;

dp[i][j] = false;

while (it-- >= 1 && s[it-1] == p[j-2]) {

if(dp[it-1][j-2]) {

dp[i][j] = true;

break;

}

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);

}

Programmer As Innovator

everything I know

Similar String

Problem

Implementation

[Leetcode] zigzag conversion

[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