fenghaolw

Follow up for " Find Minimum in Rotated Sorted Array ": What if duplicates are allowed? Would this affect the run-time complexity? How and why? When num[mid] == num[tail], we need to linearly move the pointer. The worst case complexity is O(n), but the average will still be better than simple linear search.

Given an array A, generate an array B such that  B[i] = A[0]*A[1]*...A[i-1]*A[i+1]*...A[n-1]. The brute-force approach takes O(n^2) time. One simple improvement would be pre-calculating the product of A[0], A[1] ... and A[n-1]. Then for each A[i], we can easily generate B[i] by dividing the total product by A[i]. We only need O(2n) in time. A few corner cases need to be considered: What if there is one zero in the array, i.e., A[i] = 0? The total product will be 0, and the divide operations are invalid. In this case, B[j] = 0 if j not equals to i, and B[i] is the only non-zero element in the array. What if there are more than 2 zeros in the array? The entire B should be 0. Follow-up: what if divide is not allowed? If divide operation is not allowed, we can still have a linear time solution. The idea is to generate two helper arrays, and then calculate B[i] based on these two arrays. Follow-up: what if extra space is not allowed? Actually there is a pretty neat so

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). Find the minimum element. You may assume no duplicate exists in the array. Classic binary search.

http://www.itint5.com/oj/#26 Evaluate an arithmetic expression. For simplicity, the following assumptions are made: There are only positive integers. There is no overflow.  Only plus, minus, and multiply operations are supported. No parenthesis, divide, and modulo. All inputs are valid arithmetic expressions. Example: Input: 1+4*3-5 Output: 8 Input: 2-3-5*2 Output: -11 Note that multiplication has higher priority than plus and minus. Every time we meet a '*' , we will calculate the number. If we meet a '+' or '-' , we will call the recursion, or push the number into a data structure. Recursive version: Note that for minus operations, instead of using prevNum - calc(expr, currNum, pos) , we need to convert it to negative number (i.e., prevNum + calc(expr, -currNum, pos) ). Otherwise the result will be incorrect. For example, 5-4+2 , if we use the first approach, the result will be 5-(4+2)=-1 . However, it should be 5+(-4+2)=3 . Iterative v

http://www.itint5.com/oj/#4 In a complete binary tree every level, except possibly the last, is completely filled, and all nodes are as far left as possible. How can we count the total number of nodes in a complete binary tree? A straightforward method is to traverse the tree, which takes O(n) in time, where n is the number of nodes. However, this method does not utilize the property of complete binary tree. Since we know the tree is complete, it is very easy to find the height of the tree; the tricky part is how can we find the number of nodes in the last level. We can utilize a binary search method to figure out how many nodes are in the last level. For each node, we check the "left height" of its left subtree and its right subtree, respectively. "Left height" means the depth of the leftmost leaf node. If the "left heights" are the same, we know that the left subtree is full; if the "left heights" are not the same, we know that the r

http://www.itint5.com/oj/#8 Classic DP problem, which has also appeared in Leetcode as Maximum subarray . The only difference is, in this problem, empty subarray (where sum is 0) is allowed. So instead of return ret, we could simply return max(0, ret). http://www.itint5.com/oj/#9 Calculate the maximum subarray for a circular array. For example, [1, 3, -2, 6, -1], we should return 9 since 6 + (-1) + 1 + 3 = 9. The following solution might not be optimized. Suppose that the maximum subarray is from A[i] to A[j]. The idea is, consider the following different scenarios: i <= j: it is the same as classic problem. i > j: the sum is A[i : end] + A[start : j]. So we can use two additional arrays: left[j] = maximum subarray, starts from A[start] and ends no later than A[j] right[i] = maximum subarray, starts no earlier than A[i] and ends at A[end] The following code passes the online judge. However, we need O(4n) in time and O(2n) in space. Not sure how to improve this.