*inorder*traversal of its nodes' values.

Given binary tree

`{1,#,2,3}`

,1 \ 2 / 3

`[1,3,2]`

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

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

For example:

Given binary tree

Given binary tree

`{1,#,2,3}`

,1 \ 2 / 3

return

`[1,3,2]`

.
Say you have an array for which the *i*th 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]

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:

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

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.

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

Say you have an array for which the *i*th 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

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

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]

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

For example:

Given binary tree

Given binary tree

`{1,#,2,3}`

,1 \ 2 / 3

return

`[3,2,1]`

.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 .

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]`

.

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

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

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.

Follow up for "Remove Duplicates":

What if duplicates are allowed at most*twice*?

What if duplicates are allowed at most

For example,

Given sorted array A =

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]`

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

For example,

Given*n* =

You should return the following matrix:Given

`3`

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

Given a *m* x *n* matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Did you use extra space?

A straight forward solution using O(*m**n*) space is probably a bad idea.

A simple improvement uses O(*m* + *n*) space, but still not the best solution.

Could you devise a constant space solution?

A straight forward solution using O(

A simple improvement uses O(

Could you devise a constant space solution?

Given an index *k*, return the *k*th row of the Pascal's triangle.

For example, given *k* = 3,

Return

Return

`[1,3,3,1]`

.Could you optimize your algorithm to use only

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:Given the below binary tree and

`sum = 22`

,5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1

return true, as there exist a root-to-leaf path

`5->4->11->2`

which sum is 22.
Given two integers *n* and *k*, return all possible combinations of *k* numbers out of 1 ... *n*.

For example,

If*n* = 4 and *k* = 2, a solution is:

If

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

Solution: a classical DFS problem, pay attention to the format of solve this question which can be apply to many other DFS problems

Given a linked list, remove the *n*th node from the end of list and return its head.

For example,

Given linked list:1->2->3->4->5, and. After removing the second node from the end, the linked list becomesn= 21->2->3->5.

Given

Try to do this in one pass.

Follow up for problem "*Populating Next Right Pointers in Each Node*".

What if the given tree could be any binary tree? Would your previous solution still work?

- You may only use constant extra space.

For example,

Given the following binary tree,

Given the following binary tree,

1 / \ 2 3 / \ \ 4 5 7

After calling your function, the tree should look like:

1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4-> 5 -> 7 -> NULL

Solution : The main idea actually is tree level traversal, we can just use one node called current represent current level (start from root) and two other nodes which called nextLevelHead and nextLevelEnd to record next level's left child and right child and when current node is null then exchange current and nextLevelHead until nextLevelHead is also null

Determine whether an integer is a palindrome. Do this without extra space.

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem

Given a binary tree containing digits from

`0-9`

only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path

`1->2->3`

which represents the number `123`

.
Find the total sum of all root-to-leaf numbers.

For example,

1 / \ 2 3

The root-to-leaf path

The root-to-leaf path

`1->2`

represents the number `12`

.The root-to-leaf path

`1->3`

represents the number `13`

.
Return the sum = 12 + 13 =

`25`

.
When I met this question, I intuitively come out that recursion may be a good way to solve this problem. For a recursive solution, the base case is extremely important and it is always the key point to solve a question.

Depend on my experience, for a tree question, the root==null is always a base case, another base case in this question is decided when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this situation and it also should be a base case here.
Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum variable.
The reason I use an array to hold the same value is because Java can only passed by value. For example,

in a=1;
void calculate(int a){
a=a+1;
}
System.out.println(a); // the result is still 1 , not 2
In order to track sum value of each calculation and not return the value of sum, we should use a collection or a wrapper class to hold it

So I use an array here to hold this sum value. If you anybody has another way to solve this problem, please leave a comment for me.

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,

`0 1 2 4 5 6 7`

might become `4 5 6 7 0 1 2`

).
You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.
Search a item in sorted array we should think about binary search. Cause the given array has been rotated unknow times, so binary search can not be apply directly here.

Throgh observation we can see, no matter how a sorted array be rotated, there is

always one side is sorted.

So we can pick the middle item at first and compare it with given array's leftMost and rightMost items to check which side is sorted, for given example 4, 5 , 6, 7 , 0 , 1, 2

mid is 7, leftMost is 4, rightMost is 2, because of 4<7 so we can know left side is sorted.

Depend on the conclusion we got above, if the given target is between 4->7, such as 6, we can just seach left side for it, otherwise we search the right side.

A trick situation is when duplicate exist in the array, discard the requriement of this quesiton, my solution will also cover duplicate exist situation.

If duplicate exist, then leftMost or rightMost item may equal to middle item, if only one of them equal to mid such as A[leftMost]==A[mid] then from leftMost to Mid should have same value. then we can only search the right side from mid to right most. If both A[rightMost] and A[leftMost] equal to A[Mid] we have to search both sides.

Given *n* non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given

Given

`[0,1,0,2,1,0,1,3,2,1,2,1]`

, return `6`

.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. **Thanks Marcos** for contributing this image!

Solution: DP

To calculate the total volume is to calculate volumes can hold at each position.

To calculate how many volumes can hold at each position is to calculate it's right bound height and right bound height

Current position can hold water only at the situation when the low side among both sides higher than the height at current position

If so, use the lower one minus current height as height to multiply the width 1 is how many volumes can hold at current position

How to calculate the height of both sides for each position? We can apply DP theory to record highest height bound can get from left to current and highest height bound can get from right to current

HigehstLeftSideHeight so far from giving example, should be 0,1,1,2,2,2,2,3,3,3,3,3

HighestRightSideHeight so far for given example is 1,2,2,2,3,3,3,3,3,3,3,3

Then loop through giving array for each position to calculate how many volumes can hold there and update the total volume it can hold

Given a string containing just the characters

`'('`

, `')'`

, `'{'`

, `'}'`

, `'['`

and `']'`

, determine if the input string is valid.
The brackets must close in the correct order,

`"()"`

and `"()[]{}"`

are all valid but `"(]"`

and `"([)]"`

are not.
Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character

`'.'`

.
A partially filled sudoku which is valid.

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Solution: Helpe table

Declare 9 boolean array with length 9 separately for rows, columns and blocks and hold them in ArrayList. Because the number range of sudoku is 1-9, so each number in each row, col and block should be unique, then we can go through every position of given board, check if the number has been

Found in current row,current column and current block. If so, return false;

*** Be careful about the index of block in blockChecker

*** Be careful about the index of block in blockChecker

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:Given the below binary tree and

`sum = 22`

,5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1

return

[ [5,4,11,2], [5,8,4,5] ]

Apply DFS check every possible combination, record result if meet requirement

Subscribe to:
Posts (Atom)