Concurrency Freaks: Concurrency Pattern: Distributed Cache-Line Counte...

Concurrency Freaks: Concurrency Pattern: Distributed Cache-Line Counte...: On the previous post we showed a Counter that can be used for single-Writer scenarios, this time we have one that works for multiple-writers...

Print object properties in Javascript

Print object properties in Javascript

var print = function(element) {
    var str = "";
    for (var prop in element){
        if (typeof(element[prop]) == "string") {
            str += prop + ": " + element[prop] + "<br/>";
        }
     else if (typeof(element[prop]) == "function") {
            str += prop + ": (function)<br/>";
     }
     else {
            str += prop + ": { <br/>" + print(element[prop]) + "}";
        }
    }

    return str;
}

CTRL+A, CTRL+C, CTRL+V

Imagine you have a special keyboard with the following keys:

1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.
If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.
That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).

I do believe there should be an O(n) solution, but sort of tricky. The O(n^2) solution is quite straightforward in DP problems.

public static int maxChar(int n) {
 int[] dp = new int[n];
 for (int i = 0; i < n; ++i) {
  dp[i] = i + 1;    // type A
 }
 for (int i = 0; i < n; ++i) {
  for (int j = i + 4; j < n; ++j) {
   dp[j] = Math.max(dp[j], dp[i] * (j - i - 3));    // using Ctrl + V
  }
 }
 return dp[n - 1];
}

Interleaving String

Interleaving StringAug 31 '12

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

dp[i][j] == true means the substring of s3 from start to 'i + j'th char is the interleaved string of s2 till 'i'th char and s1 till 'j'th char

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        if (s1.empty()) return s2 == s3;
        else if (s2.empty()) return s1 == s3;
        else if (s3.empty()) return s1.empty() && s2.empty();
        else if (s1.size() + s2.size() != s3.size()) return false;
        
        int lengthS1 = s1.size() + 1, lengthS2 = s2.size() + 1;
        vector<vector<bool>> dp(lengthS2, vector<bool>(lengthS1, false));
        dp[0][0] = true;
        
        for (int i = 1; i < lengthS2; ++i) {
            dp[i][0] = s2[i - 1] == s3[i - 1] ? dp[i - 1][0] : false;
        }
        
        for (int j = 1; j < lengthS1; ++j) {
            dp[0][j] = s1[j - 1] == s3[j - 1] ? dp[0][j - 1] : false;
        }
        
        for (int i = 1; i < lengthS2; ++i) {
            for (int j = 1; j < lengthS1; ++j) {
                if (s1[j - 1] == s3[i + j - 1]) {
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
                }
                if (s2[i - 1] == s3[i + j - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
        
        return dp[lengthS2 - 1][lengthS1 - 1];
    }
};

Surrounded Regions

Surrounded RegionsFeb 22

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Idea: BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (board.size() <= 1) return;
        int rows = board.size();
        int cols = board[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        vector<vector<bool>> checked(rows, vector<bool>(cols, false));
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (!visited[i][j]) {
                    if (board[i][j] == 'O') {
                        if (checkIfSurrounded(i, j, board, visited, checked)) {
                            markChecked(i, j, board, checked);
                        }
                    }
                    else {
                        visited[i][j] = true;
                    }
                }
            }
        }
    }
    
    bool checkIfSurrounded(int i, int j, vector<vector<char>> &board,
        vector<vector<bool>> &visited, vector<vector<bool>> &checked) {
        queue<Pos> q;
        bool result = true;
        
        q.push(Pos(i, j));
        visited[i][j] = true;
        
        while (!q.empty()) {
            Pos pos = q.front();
            q.pop();
            i = pos.row;
            j = pos.col;
            checked[i][j] = true;
            
            if (j - 1 >= 0) {
                if (board[i][j - 1] == 'O' && !visited[i][j - 1]) {
                    q.push(Pos(i, j - 1));
                    visited[i][j - 1] = true;
                }
            }
            else {
                result = false;
            }
            
            if (j + 1 < board[0].size()) {
                if (board[i][j + 1] == 'O' && !visited[i][j + 1]) {
                    q.push(Pos(i, j + 1));
                    visited[i][j + 1] = true;
                }
            }
            else {
                result = false;
            }
            
            if (i + 1 < board.size()) {
                if (board[i + 1][j] == 'O' && !visited[i + 1][j]) {
                    q.push(Pos(i + 1, j));
                    visited[i + 1][j] = true;
                }
            }
            else {
                result = false;
            }
            
            if (i - 1 >= 0) {
                if (board[i - 1][j] == 'O' && !visited[i - 1][j]) {
                    q.push(Pos(i - 1, j));
                    visited[i - 1][j] = true;
                }
            }
            else {
                result = false;
            }
        }

        return result;
    }
    
    void markChecked(int i, int j, vector<vector<char>> &board,
        vector<vector<bool>> &checked) {
        queue<Pos> q;
        bool result = true;
        
        q.push(Pos(i, j));
        
        while (!q.empty()) {
            Pos pos = q.front();
            q.pop();
            i = pos.row;
            j = pos.col;
            
            board[i][j] = 'X';
            checked[i][j] = false;
            
            if (j - 1 >= 0) {
                if (checked[i][j - 1]) {
                    q.push(Pos(i, j - 1));
                    checked[i][j - 1] = false;
                }
            }
            
            if (j + 1 < board[0].size()) {
                if (checked[i][j + 1]) {
                    q.push(Pos(i, j + 1));
                    checked[i][j + 1] = false;
                }
            }
            
            if (i + 1 < board.size()) {
                if (checked[i + 1][j]) {
                    q.push(Pos(i + 1, j));
                    checked[i + 1][j] = false;
                }
            }
            
            if (i - 1 >= 0) {
                if (checked[i - 1][j]) {
                    q.push(Pos(i - 1, j));
                    checked[i - 1][j] = false;
                }
            }
        }
    }
    
    typedef struct Pos {
        int row, col;
        Pos(int i, int j): row(i), col(j) {};
    };
};

Restore IP Addresses

Restore IP AddressesAug 8 '12

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

This one is actually more tricky than it seems to be as it involves several corner cases.
DFS

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size() > 12 || s.size() < 4) return vector<string>();
        return getValidIP(s.c_str(), 0);
    }
    
    vector<string> getValidIP(const char *c, int n) {
        const char *head = c;
        if (n == 3) {
            int num = 0;
            while (*c != '\0') {
                num = num * 10 + *c - '0';
                ++c;
            }
            vector<string> ret;
            
            // last segment requirements
            // at least one digit and at most one leading zero
            if (c - head > 1 && *head == '0' || c == head) return ret;
            
            // segment number cannot exceed 255
            if (num <= 255) {
                string seg(head, c - head);
                ret.push_back(seg);
            }
            return ret;
        }
        int num = 0;
        vector<string> ret;
        for (int i = 0; i < 3; ++i) {
            // reaches end or digits exceed 3
            if (*c == '\0' || c - head > 2) break;
            
            num = num * 10 + *c - '0';
            
            // each segment can be at most 255
            if (num > 255) break;
            
            vector<string> rest = getValidIP(++c, n + 1);
            string add_seg(head, c - head);
            for (auto s : rest) {
                string address(add_seg);
                address += ".";
                address += s;
                ret.push_back(address);
            }
            
            // only one leading 0 allowed
            if (*(c - 1) == '0' && i == 0) break;
        }
        return ret;
    }
};

Reverse Linked List II

Reverse Linked List IIJun 27 '12

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

This looks fairly easy but actually it's pretty tricky. Each recursion takes the node to be processed and returns itself so that the upper level can change the 'next' pointer backwards as stack pops. The special case is that during the backward process, when m == 0 we reach the first node in the region to be reversed (let's call it 'region'). At that time the node before it should get the next node after the 'region'. That's where the nodeAfterN is used. Also the node before m == 0 should get the original last node in the 'region', which now becomes the head node in the 'region'. This is achieved by returning the pointer of that last node to the upper level of recursion, AKA nodeAtN.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        nodeAtN = NULL;
        nodeAfterN = NULL;
        return revHelper(head, m - 1, n - 1);
    }
    
    ListNode *revHelper(ListNode *current, int m, int n) {
        if (!current) return NULL;
        ListNode *ret = current;
        if (m > 0) {
            current->next = revHelper(current->next, m - 1, n - 1);
        }
        else if (n > 0) {
            ListNode *currentNext = revHelper(current->next, m - 1, n - 1);            
            currentNext->next = current;
            if (m == 0) {
                current->next = nodeAfterN;
                ret = nodeAtN;
            }
        }
        else if (n == 0) {
            nodeAtN = current;
            nodeAfterN = current->next;
        }
        return ret;
    }
    
private:
    ListNode *nodeAfterN;
    ListNode *nodeAtN;
};

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

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

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."] L: 16.

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.

click to show follow up.

» 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;
    }
};

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

Remove Nth Node From End of List

Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Idea: use a ring buffer

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode **buffer = new ListNode*[n + 1];
        memset(buffer, NULL, (n + 1) * sizeof(ListNode*));
        int ptr = 0;
        ListNode *current = head;
        
        while (current) {
            buffer[ptr] = current;
            ptr = (ptr + 1) % (n + 1);
            current = current->next;
        }
        
        if (buffer[ptr] == NULL) {
            head = n > 1 ? buffer[1] : NULL;
        }
        else {
            ListNode *last = buffer[ptr];
            last->next = last->next->next;
        }
        delete[] buffer;
        return head;
    }
};

Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (A == NULL || n == 0) return 0;
        int i = 1, j = 1, count = 1;
        
        while (j < n) {
            if (A[j] != A[j - 1]) {
                A[i] = A[j];
                ++i;
                count = 1;
            }
            else if (A[j] == A[j - 1] && count < 2) {
                A[i] = A[j];
                ++i;
                ++count;
            }
            else {
                ++count;
            }
            ++j;
        }
        
        return i;
    }
};

Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (A == NULL || n == 0) return 0;
        int i = 1, j = 1;
        
        while (j < n) {
            if (A[j] != A[j - 1]) {
                A[i] = A[j];
                i++;
            }
            j++;
        }
        
        return i;
    }
};

Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL) return NULL;
        ListNode *fast = head->next, *slow = head;
        int lastVal = head->val;
        
        while (fast) {
            if (fast->val != lastVal) {
                slow->next->val = fast->val;
                slow = slow->next;
            }
            lastVal = fast->val;
            fast = fast->next;
        }
        slow->next = NULL;
        
        return head;
    }
};

Maximum Subarray

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!A || !n) return 0;
        int m = A[0];
        int sumSoFar = 0;
        
        for (int i = 0; i < n; ++i) {
            sumSoFar += A[i];
            if (sumSoFar > m) {
                m = sumSoFar;
            }
            if (sumSoFar < 0) {
                sumSoFar = 0;
            }
        }
        
        return m;
    }
};

Length of Last Word

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given s = "Hello World",
return 5.

class Solution {
public:
    int lengthOfLastWord(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int count = 0;
        bool recount = true;
        
        while (*s != '\0') {
            if (*s != ' ') {
                if (recount) {
                    count = 1;
                    recount = false;
                }
                else {
                    ++count;
                }
            }
            else {
                recount = true;
            }
            ++s;
        }
        
        return count;
    }
};

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

» Solve this problem

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int end = inorder.size() - 1;
        if (end < 0) return NULL;
        return getRoot(inorder, postorder, 0, end, postorder[end], 0);
    }
    
    TreeNode *getRoot(vector &inorder, vector &postorder,
                 int start, int end, int rootVal, int offset) {
        if (start > end) return NULL;
        
        TreeNode *root = new TreeNode(rootVal);
        
        int rootPosInOrder = start;
        for (; rootPosInOrder < end; ++rootPosInOrder) {
            if (inorder[rootPosInOrder] == rootVal) break;
        }
        
        root->left = getRoot(inorder, postorder, start,
               rootPosInOrder - 1, postorder[rootPosInOrder - 1 + offset], offset);
        root->right = getRoot(inorder, postorder, rootPosInOrder + 1,
              end, postorder[end - 1 + offset], offset - 1);
        return root;
    }
};