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