### Blogroll

### Topics

- Array and linked list
- Backtrack
- Binary search
- Bit operation
- C++
- Complexity
- Divide and Conquer
- Dynamic programming
- File operation
- Geometry
- Graph
- Greedy algorithm
- Hashtable and Map
- Heap
- JAVA
- Large scale data
- Number trick
- Object orientated design
- Probability
- Recursive
- Stack and Queue
- String
- Threads and locks
- Tree
- Uncategorized

### Archives

# Monthly Archives: September 2012

## Longest Valid Parentheses

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area. C++: 01 int longestValidParentheses(string s) 02 { 03 stack<int> tmp; 04 int n=s.size(); 05 int max=0; 06 … Continue reading

Posted in Array and linked list, Stack and Queue, String
Leave a comment

## 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. More practice:If you have figured out the O(n) solution, try coding … Continue reading

Posted in Array and linked list
Leave a comment

## Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). C++: 01 double kSmall(int A[],int m,int B[],int n,int k) 02 … Continue reading

Posted in Array and linked list, Binary search
Leave a comment

## Merge Intervals

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. C++: 01 vector<Interval> merge(vector<Interval> &intervals) 02 { 03 vector<Interval> result; 04 int n=intervals.size(); 05 if(n==0) 06 return result; 07 … Continue reading

Posted in Array and linked list
Leave a comment

## Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. C++: 01 void enList(ListNode*& head, ListNode*& tail, ListNode* p) 02 { 03 if(p==NULL) 04 return; 05 if(head==NULL){ … Continue reading

Posted in Array and linked list
Leave a comment

## Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative. C++: 01 void reverse(string& a) 02 { 03 int n=a.size(); 04 for(int i=0;i<n/2;i++){ 05 … Continue reading

Posted in Number trick, String
Leave a comment

## Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = “ADOBECODEBANC” T = “ABC” Minimum window is “BANC”. Note: If there … Continue reading

Posted in String
Leave a comment