Binary Tree Inorder Traversal (Java)

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: DP

maxProfit[i]=maxProfit[i-1]+prices[i]-prices[i-1] if prices[i]>prices[i-1]

maxProfit[i]=maxProfit[i-1] if prices[i]<=prices[i-1]

Generate Parentheses (Java)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"




Solution: Greedy and Recursive

Take advantage of the feature of parentheses, left side and right side must match each other,  in other words, if there a left side parenthese,  whatever position it is, there must be a right side parenthese to match it.

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution: DP

ways[n]=ways[n-1]+ways[n-2];

No matter what n is,  it must be reached  from n-1 or n-2 , then use array to  record unique ways from 0 to end 

Best Time to Buy and Sell Stock (Java)

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution:
loop through entire list  and  catch min_price and the position of this this price, when current reached price's position after min_price's position then do calculate difference and up max_profit

Unique Paths Java

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Solution:DP 

Ways to destination point is equal to ways to up neighbor of destination point and left neighbor of destination point 

then we can generalize 

ways[m][n]=ways[m-1][n] + ways[m][n-1]

Binary Tree Postorder Traversal (Java)

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution;

For iterative solution, we know postal order is visit children before parent so  a stack could be apply here as a helper structure. Then, we can ' push left child from root until left most leaf into stack. then start pop node  from the stack, however, if the current node which going to be pop out has right node we should start push all left nodes of the right child until to leaf. But the trick point is how to tell if the mid need to be pop out  , We can use a child node to catch every popped out  node, then if the mid's right node equal to child node which mean this mid's right node has been visited, it is a good time to pop out the mid one .

Permutations (Java)

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Minimum Path Sum (Java)

 

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

Apply DFS first failed on time limitation, then adopted DP with 2 dimension matrix passed OJ, finally refector code to use 1 dimension rotational array

Search a 2D Matrix (Java + Python)

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

For an  O (rows * cols) solution is too simple to meet the interviewer’s expectation. So what is the better solution should be? Binary search should be a good tool when I face search problem, however, how BS could be apply  in matrix?   if we regard 0 as start point, total_cols*total_rows-1 as the end point to look the matrix as a array then we can apply BS. However, how could we convert the position to row_NO and col_NO?  We  know row_NO * total_cols+col_NO=position, So in programming  row_NO=postion/total_cols, col_NO=postion%total_cols. then we can adapt this feature in our program  to apply binary search to get O(log(cols+rows)) search

Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Remove Duplicates from Sorted Array II (Python + Java)

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Spiral Matrix II ( Java + Python)

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]