fenghaolw

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.  Try to solve it in linear time/space.  Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range. In order to solve this in linear time, we cannot use general sorting algorithm. Here we use bucket sort. First, we scan the array to find the min and the max values.   We can then create n - 1 buckets with equal size. Suppose we have n elements in total, then we have n - 2 elements except the min and the max. Scan the array again to put the n - 2 elements into these buckets. We should have at least one empty bucket. For each bucket, we record the min and the max for all the elements within that bucket.  Finally, we scan all the buckets, and maintain the maximum gap. Note that the maximum gap between the successive elements in the sorted array can only be the gap between

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2. Binary search. If mid is the peak, return it. If mid is not the peak, it must be less than or equal to one of its neighbors. Suppose it is less than or equal to its left, then the left half must contains a peak. Why? If the left half is not monotonically decreasing, there must contains a peak. If the left half is monotonically decreasing, the peak is the first element.

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return  null . The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory. This is a classic problem. geeksforgeeks has a very detailed discussion.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.  push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. This problem is included in CC150 (See 3.2 in Chapter 3 ). Further improvement could be save the counter of duplicates (the current version push some duplicates into two stacks).

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