by Xiaokang Zhang | Jan 22, 2017 | Algorithm & Data Structure
Maximal Rectangle problem Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area. For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 6. Height, left...
by Xiaokang Zhang | Jan 21, 2017 | Algorithm & Data Structure
Regular Expression Matching Problem Implement regular expression matching with support for ‘.’ and ‘*’. ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the...
by Xiaokang Zhang | Jan 20, 2017 | Algorithm & Data Structure
Dynamic programming can be very challenging in that: It is hard to find out whether the question can be solved by dynamic programming or not.It is hard to figure out the correct reduction transition function.It is hard to implement the algorithm correctly. Let’s...
by Xiaokang Zhang | Jan 18, 2017 | Algorithm & Data Structure
Roman to Integer Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. To solve this problem, let’s first take a look at all roman numbers. Roman Number Roman number has the following basic symbols: 1: I 5: V...
by Xiaokang Zhang | Jan 17, 2017 | Algorithm & Data Structure
Course Schedule Problem There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and...
by Xiaokang Zhang | Jan 17, 2017 | Algorithm & Data Structure
Connected components problem Given n nodes label from 0 to n – 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph: You can assume that no duplicate edges will appear...