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