Why do you need to try Wealthfront?

Posted on November 30, 2014 by admin

Wealthfront is an investment service firm based on automation and head quartered at Palo Alto, California. The firm was founded by Andy Rachleff and Dan Carronn in 2008. Adam Nash became CEO and president instead of Andy Rachleff in January 2014. He formerly worked for LinkedIn, eBay and Apple. [1]

So what is Wealthfront and what does it actually do? They provide portfolio management services. When you accept their personalized investment plan recommendation you can open an account and they implement the investments for you. They are based on Modern Portfolio Theory and they give priority to the optimal mix of asset classes over security selection.

There’s a lot of good news here. The first $10,000 in your account is managed for free, and amounts above $10,000 are assessed an annual 0.25% fee. It is possible to get up to $15,000 managed for free since Depei Bao is already a client of their services. All you have to do is click the button at the end of this article.

Wealthfront had the simple philosophy of providing sophisticated financial advice to everyone. Medium and small investors found it too expensive to get this advice. To solve this Wealthfront built what is proving to be a very successful investment service which is already managing over $300 million in client assets. [2] They do it by combining highly sophisticated investment knowledge with well designed software and then distributing it through the internet for everyone to use. By doing this, they not only have reached millions of investors but have also reduced the cost tremendously to get high quality professional advice.

How do they give you advice? Well first and foremost they ask you to make a profile. By looking at your profile, they will understand you as an investor and your attitude towards risk. Your profile will be filled up by important information about your financial assets, your activity in different market conditions and your aims. After examining your profile, after it they’ll provide you with a portfolio that is very well diversified and suited to your needs.

If you haven't tried Wealthfront then signup from the link below and get $15,000 managed for free.

After you make your plan, you don’t have to implement it straight away. Wealthfront gives you the option of saving the plan first so you can think about it. If you wish to implement your plan, then you have to go through the formal account opening process first. When you open your account and you fund it you can invest in your recommended portfolio immediately. Prior to opening your account or when your portfolio is already invested, you can alter your risk profile and needs, while doing this, your "asset allocation recommendation" adjusts and you can alter your portfolio to your new parameters.

In between the profiling and recommendation procedure you can choose if you want a plan for an individual taxable account or for a 401(k) rollover, traditional, Roth and SEP IRA accounts. Wealthfront selects, for each asset class, the best ETFs (Exchange Traded Funds) for your portfolio with the lowest management fees. [3] They also provide an ongoing asset management service which makes adjustments immediately to bring you back to your recommended mix, when certain factors in your profile will change. Last but not least, Wealthfront provides a continuous tax loss harvesting service. “Tax loss harvesting is a process of selling the worst performing investments to offset capital gains in winning investments.” [4] They do this automatically throughout the year for accounts that are over $100.000 in assets. [5]

To conclude I will say that Wealthfront is the best investment service in the market and you should definitely use it.

Do share your experience of using Wealthfront with us.

Racer Ranking Problem

Posted on August 21, 2014 by admin

Problem

The Problem: A bunch of racers, each one has start time and end time. Calculate each racer's score based on the following rule:

score ＝ The number of racers who started after and finished earlier than current racer.

Note: There is no duplicated start time or end time.

Implementation (Java)

class Racer
{
    public Racer(int id, int start, int end)
    {
       Id = id;
       Start = start;
       End = end;
       Score = 0;
    }

    public int Id { get; set; }
    public int Start { get; set; }
    public int End { get; set; }
    public int Score { get; set; }
}

void RankRacers(Racer[] racers)
{
    Array.Sort<Racer>(racers, (a, b) => a.Start - b.Start);
    Array.Sort<Racer>(racers, (a, b) => a.End - b.End);

    List<int> StartRanks = new List<int>();
    for (int i = 0; i < racers.Length; ++i)
    {
       // the score is the number of processed racers(ended earlier)
       // whose StartRank is higher than current racer.
       racers[i].Score = BinarySearchInsert(StartRanks, racers[i].StartRank);
    }

    Array.Sort<Racer>(racers, (a, b) => a.Score - b.Score);
}

int BinarySearchInsert(List<int> processedRanks, int startRank)
{
    int index = processedRanks.BinarySearch(startRank);
    index = (index < 0) ? ~index : index;

    int score = processedRanks.Count - index;

    processedRanks.Insert(index, startRank);

    return score;
}

class Racer

{

public Racer(int id, int start, int end)

{

Id = id;

Start = start;

End = end;

Score = 0;

}

public int Id { get; set; }

public int Start { get; set; }

public int End { get; set; }

public int Score { get; set; }

}

void RankRacers(Racer[] racers)

{

Array.Sort<Racer>(racers, (a, b) => a.Start - b.Start);

Array.Sort<Racer>(racers, (a, b) => a.End - b.End);

List<int> StartRanks = new List<int>();

for (int i = 0; i < racers.Length; ++i)

{

// the score is the number of processed racers(ended earlier)

// whose StartRank is higher than current racer.

racers[i].Score = BinarySearchInsert(StartRanks, racers[i].StartRank);

}

Array.Sort<Racer>(racers, (a, b) => a.Score - b.Score);

}

int BinarySearchInsert(List<int> processedRanks, int startRank)

{

int index = processedRanks.BinarySearch(startRank);

index = (index < 0) ? ~index : index;

int score = processedRanks.Count - index;

processedRanks.Insert(index, startRank);

return score;

}

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]!='*');
                if(dp[i][j-2]) { 
                    dp[i][j]=true; 
                    continue;
                }
                int it = i-1;
                dp[i][j] = false;
                while (it > 0 && (s[it-1] == p[j-2] || p[j-2]=='.')) {
                    if(dp[it-1][j-2]) {
                        dp[i][j] = true;
                        break;
                    }
                    it--;
                }
            }
        }
    }
    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]!='*');

if(dp[i][j-2]) {

dp[i][j]=true;

continue;

}

int it = i-1;

dp[i][j] = false;

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

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

dp[i][j] = true;

break;

}

it--;

}

return dp[ls][lp];

}

Programmer As Innovator

everything I know

Why do you need to try Wealthfront?

Racer Ranking Problem

Problem

Implementation (Java)

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