1/28/2013

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

class Solution {
public:
    vector > generate(int numRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ret;
        if (!numRows) return ret;
        vector<int> firstRow;
        firstRow.push_back(1);
        ret.push_back(firstRow);
        
        for (int i = 1; i < numRows; ++i) {
            vector<int> lastRow = ret[i - 1];
            vector<int> row;
            for (int j = 0; j <= i; ++j) {
                if (j != 0 && j != i) {
                    row.push_back(lastRow[j] + lastRow[j - 1]);
                }
                else if (j == 0) {
                    row.push_back(lastRow[j]);
                }
                else {
                    row.push_back(lastRow[j - 1]);
                }
            }
            ret.push_back(row);
        }
        
        return ret;
    }
};

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = triangle.size();
        if (!n) return 0;
        
        int *sum = new int[n];
        sum[0] = triangle[0][0];
        
        for (int i = 1; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                if (j != 0 && j != i) {
                    sum[j] = min(sum[j - 1], sum[j]) + triangle[i][j];
                }
                else if (j == i) {
                    sum[j] = sum[j - 1] + triangle[i][j];
                }
                else {
                    sum[j] = sum[j] + triangle[i][j];
                }
            }
        }
        
        int m = sum[0];
        for (int i = 1; i < n; ++i) if (sum[i] < m) m = sum[i];
        delete[] sum;
        return m;
    }
};

1/27/2013

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

class Solution {
public:
    inline bool isValidChar(char &c) {
        if (c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
            return true;
        }
        else {
            return false;
        }
    }
    
    inline bool isLetter(char &c) {
        if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
            return true;
        }
        else {
            return false;
        }
    }
    
    inline bool compare(char &c1, char &c2) {
        if (c1 == c2 || isLetter(c1) && isLetter(c2) && abs(c1 - c2) == 32) {
            return true;
        }
        else {
            return false;
        }
    }
    
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = 0, j = s.size() - 1;
        while (i < j) {
            while (i < j && !isValidChar(s[i])) ++i;
            while (i < j && !isValidChar(s[j])) --j;
            if (i < j) {
                if (!compare(s[i], s[j]))
                    return false;
            }
            ++i;
            --j;
        }
        return true;
    }
};

1/22/2013

Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example, words["This", "is", "an", "example", "of", "text", "justification."] L16.
Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
Note: Each word is guaranteed not to exceed L in length.
class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int lb = 0, ub = 0;     //start and end index of the words in the line
        int chcount = 0;
        vector<string> ret;
        while (ub < words.size()) {
            chcount += words[ub].size() + 1;  // assume at least one space between words
            int next = ub + 1;
            if (next != words.size() && chcount + words[next].size() <= L) {
                ++ub;
            }
            else {
                string str;
                chcount -= ub - lb + 1;         // get real character count
                int gapcount = ub - lb;
                int sm = L - chcount;           // space remaining
                
                if (gapcount) {
                    int avgsm = sm / gapcount;
                    int remainder = sm % gapcount;
                    for (int i = lb; i <= ub; ++i) {
                        str.append(words[i]);
                        int space = 0;
                        if (ub != words.size() - 1) {
                            if (i != ub) {
                                space = avgsm;
                                if (remainder) {
                                    ++space;
                                    --remainder;
                                }
                            }
                        }
                        else {
                            if (i != ub) {
                                space = 1;
                            }
                            else {
                                space = sm - gapcount;
                            }
                        }
                        str.append(space, ' ');
                    }
                }
                else {
                    // one word
                    str.append(words[ub]);
                    str.append(sm, ' ');
                }
                ret.push_back(str);
                lb = ++ub;
                chcount = 0;
            }
        }
            
        return ret;
    }
};

Set Matrix Zeroes


Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
» Solve this problem

Idea: Use bitmap
Time complexity: O(mn)
Space complexity: O(max(m, n) / sizeof (int))

class Solution {
public:
    void setZeroes(vector > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int row = matrix.size();
        int col = matrix[0].size();
        
        int s = sizeof(int);
        
        int r = (row + s - 1) / s;
        int c = (col + s - 1) / s;
        int *rm = new int[r];
        int *cm = new int[c];
        memset(rm, 0, r * s);
        memset(cm, 0, c * s);
        
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (!matrix[i][j]) {
                    rm[i / s] |= 1 << (i % s);
                    cm[j / s] |= 1 << (j % s);
                }
            }
        }
        
        
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (rm[i / s] & 1 << (i % s) || cm[j / s] & 1 << (j % s))
                    matrix[i][j] = 0;
            }
        }
        
        delete[] rm;
        delete[] cm;
    }
};

1/21/2013

Javascript: Difference between calling the function directly and using the "new" keyword

Basically "new" changes the "this" reference. Calling the function without using "new" will let "this" refer to window object as usual even if "this" is inside that function. When "new" is used, "this" refers to the function called, like a class object.


Quoted from Stackoverflow by Daniel Howard:

What new does:
  1. It creates a new object. The type of this object, is simply object.
  2. It sets this new object's internal, inaccessible, [[prototype]] property to be the constructor function's external, accessible, prototype object.
  3. It executes the constructor function, using the newly created object whenever this is mentioned.
Once this is done, if an undefined property of the new object is requested, the script will check the object's [[prototype]] object for the property instead. This is how you can get something similar to traditional class inheritance in JavaScript.
The most difficult part about this is point number 2. Every object (including functions) has this internal property called [[prototype]] and there is NO way to access it. The only way to make an object have a particular [[prototype]] is by using the new keyword.
Functions, in addition to the hidden, [[prototype]] property also have a property called prototype, and it is this that you can access, and modify, to provide inherited properties and methods for the objects you make.

Here is an example:

ObjMaker = function() {this.a = 'first';};
// ObjMaker is just a function, there's nothing special about it that makes 
// it a constructor.

ObjMaker.prototype.b = 'second';
// like all functions, ObjMaker has an accessible prototype property that 
// we can alter. I just added a property called 'b' to it like 
// all objects, ObjMaker also has an inaccessible [[prototype]] property
// that we can't do anything with

obj1 = new ObjMaker();
// 3 things just happened
// A new, empty object was created called obj1.  At first obj1 was the same as {}
// The [[prototype]] property of obj1 was set to a copy of the prototype property
// of ObjMaker. The ObjMaker function was executed, with obj1 in place of this
// ...so   obj1.a was set to 'first'

obj1.a;
// returns 'first'
obj1.b;
// obj1 doesn't have a property called 'b', so JavaScript checks 
// its [[prototype]]. Its [[prototype]] is the same as ObjMaker.prototype
// ObjMaker.prototype has a property called 'b' with value 'second'
// returns 'second'
It's like class inheritance because now, any objects you make using new ObjMaker() will also appear to have inherited the 'b' property.
If you want something like a subclass, then you do this:

SubObjMaker = function () {};
SubObjMaker.prototype = new ObjMaker();
// Because we used 'new', the [[prototype]] property of SubObjMaker.prototype
// is now set to a copy of ObjMaker.prototype

SubObjMaker.prototype.c = 'third';  
obj2 = new SubObjMaker();
// [[prototype]] property of obj2 is now set to a copy of SubObjMaker.prototype
// Remember that the [[prototype]] property of SubObjMaker.prototype
// is a copy of ObjMaker.prototype with the additional c property defined
// So now obj2 has a prototype chain!
// obj2 ---> SubObjMaker.prototype ---> ObjMaker.prototype

obj2.c;
// returns 'third', from SubObjMaker.prototype

obj2.b;
// returns 'second', from ObjMaker.prototype

obj2.a;
// returns 'first', from SubObjMaker.prototype, because SubObjMaker.prototype 
// was created with the ObjMaker function, which assigned a for us