O(nlgn)-time algorithm to find the LIS
In the spirit of dynamic programming, we first consider what information we would need from previous problems to solve for a longest increasing sub-sequence in A[n]. There are two cases:
Case 1. The length of the LIS(s) of A[n] is equal to the length of the LIS(s) of A[n-1].
This will occur when for all A[k], where A[k] is the last element in a longest increasing sub-sequence
of A[n-1], A[n] <= A[k].
Case 2. The length of the LIS(s) of A[n] is equal to 1 + the length of the LIS(s) of A[n-1].
This will occur when A[n] > than some A[k], where A[k] is the last element in a longest increasing
sub-sequence of A[n-1].Permutations
Description:
Given a list of numbers, return all possible permutations.
Notice:
You can assume that there is no duplicate numbers in the list.
Example:
For nums = [1,2,3], the permutations are:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Questions should be clarified when being interviewed
There are some questions should be clarified when being interviewed. Make sure to communicate with the interviewer and understand the question clearly.
Array:
(1) Sorted or not?
(2) How many elements?
(3) Element type? Int, float, double?
(4) What’s the range of those numbers? Positive or negative?
(5) Contain duplicates or not?
(6) Subsequence: adjacent or not?
Matrix Zigzag Traversal
Description:
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in ZigZag-order.
Example:
Given a matrix:
Continuous Subarray Sum
Description:
Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)
Example:
Give [-3, 1, 3, -3, 4], return [1,4].
分析：
同Maximum Subarray，只是需要记录起始和结束的下标。
Maximum Subarray
Description:
Given an array of integers, find a contiguous subarray which has the largest sum.
Notice:
The subarray should contain at least one number.
Example:
N-Queens
Description:
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.