三道coding challenge from hired.com (Hill,Deviation ,Maximum Difference)

在一个前辈的分享帖里看到了关于hired，然后去试了一下，发现又coding challenge。 已经submit了，但是题目挺有意思，希望大家能讨论一下！

1.Hill
Given an array of integer elements
Your task is to
        write a function that finds the minimum value X that makes possible the following: generate a new array that is sorted in strictly ascending order by increasing or decreasing each of the elements of the initial array with integer values in the [0, X] range.
o        Example: Having the initial array [5, 4, 3, 2, 8] the minimum value for X is 3. Decrease the first element (5) by 3, decrease the second one (4) by 1, increase the third one (3) by 1, increase the forth one (2) by 3 and do nothing to the last one (8). In the end we obtain the array [2, 3, 4, 5, 8] which is sorted in strictly ascending order.
        print the result X to the standard output (stdout)
Note that your function will receive the following arguments:
        v
o        which is the array of integers
Data constraints
        numbers are in ascending order when arranged from the smallest to the largest number
        strictly ascending order means that each element is greater than the preceding one (e.g. [1, 2, 2, 3] is NOT strictly ascending order)
        the length of the array will not exceed 5000
        the elements of any of the arrays are integer numbers in the [1, 231 -1] range
Efficiency constraints
        your function is expected to print the result in less than 2 seconds

2.Deviation
Given an array of integer elements and an integer d please consider all the sequences of d consecutive elements in the array. For each sequence we compute the difference between the maximum and the minimum value of the elements in that sequence and name it the deviation.
Your task is to
        write a function that computes the maximum value among the deviations of all the sequences considered above
        print the value the standard output (stdout)
Note that your function will receive the following arguments:
        v
o        which is the array of integers
        d
o        which is an integer value giving the length of the sequences
Data constraints
        the array will contain up to 100,000 elements
        all the elements in the array are integer numbers in the following range: [1, 231 -1]
        the value of d will not exceed the length of the given array
Efficiency constraints
        your function is expected to print the result in less than 2 seconds
Example
Input        Output
v: 6, 9, 4, 7, 4, 1
d: 3        6
Explanation
The sequences of length 3 are:
        6 9 4 having the median 5 (the minimum value in the sequence is 4 and the maximum is 9)
        9 4 7 having the median 5 (the minimum value in the sequence is 4 and the maximum is 9)
        7 4 1 having the median 6 (the minimum value in the sequence is 1 and the maximum is 7)
        The maximum value among all medians is 6


3.Maximum Difference
Given an array of integer elements, a subsequence of this array is a set of consecutive elements from the array (i.e: given the array v: [7, 8, -3, 5, -1], a subsequence of v is 8, -3, 5)
Your task is to
        write a function that finds a left and a right subsequence of the array that satisfy the following conditions
o        the two subsequences are unique (they don't have shared elements)
o        the difference between the sum of the elements in the right subsequence and the sum of the elements in the left subsequence is maximum
        print the difference to the standard output (stdout)
Note that your function will receive the following arguments:
        v
o        which is the array of integers
Data constraints
        the array has at least 2 and at most 1,000,000 numbers
        all the elements in the array are integer numbers in the following range: [-1000, 1000]
Efficiency constraints
        your function is expected to print the result in less than 2 seconds
Example
Input        Output
v: 3, -5, 1, -2, 8, -2, 3, -2, 1        15
Explanation
The left sequence is : -5, 1, -2 and the right sequence is: 8, -2, 3.

我也做了hired的challenge.当时也卡在hill这个题上了.事后想出的解法:

1.   def hill(self, nums):
   
2.     n = len(nums)
   
3.     if n <= 1: return 0
   
4. 
   
5.     copy = []
   
6.     for i in range(n):
   
7.       copy.append(nums[i] - i)
   
8. 
   
9.     minn, maxn = copy[0], copy[0]
   
10.     mini, maxi = 0, 0
    
11.     maxdiff = 0
    
12.     for i in range(n):
    
13.       n = copy[i]
    
14.       if n < minn:
    
15.         minn, mini = n, i
    
16.       if n > maxn:
    
17.         maxn, maxi = n, i
    
18.       if mini > maxi:
    
19.         maxdiff = max(maxdiff, maxn - minn)
    
20.         
    
21.     return (maxdiff + 1) / 2

复制代码

[i]思路是: 先把每个数减去它的index. 这样[5,4,3,2,8]就变成了[5,3,1,-1,4].
现在问题就变成了怎么样生成一个不降数列 (non descending).
找出一个maxdiff, 等于最大值减去最小值,同时最大值的index小于最小值的index.
结果等于 (maxdiff + 1) / 2[/i]

Hill直接二分答案，可以在O(n)时间check一个X是否合法，并且显然X是monotonic的然后X有upper_bound N因为array length = N，所以就可以O(NlogN)了

大家好，小弟献丑了，我帖2个题目我写的，感觉代码比上面大家讨论的都要简洁一些：
Hill 和 Maximum Difference， 这两个题目都可以用类似dp方法解，都是O(N)复杂度的。
先贴个Hill的：

class MyClass {
    public static void hill(Integer[] v) {
        int maxDiff = 0;
        int max= v[0]-0;
        for (int i=1; i<v.length; i++) {
            max = Math.max(max,v[i]-i);
            maxDiff = Math.max(maxDiff, max-(v[i]-i));
        }
        System.out.println((maxDiff+1)/2);
    }
}

然后是Maximum Difference， 这题实际思路和Leetcode的Best Time to Buy and Sell Stock III 非常类似，大家好好做下那个题吧。
这题的O(N)可以是3N (上面有同学帖的我没仔细看，应该就是扫描3遍的)，我贴一个扫描2遍的，虽然也是O(N) 就是稍微好那么一点吧，其实就是在第2遍从右往左扫的时候顺便把最终结果也给算出来了。

class MyClass {
    public static void maxdiff(Integer[] v) {
        int min_endinghere=0;
        int min_sofarr = 0;
        int[] min_sofar = new int[v.length];
        for (int i=0;i<v.length;i++){
            min_endinghere += v[i];
            if (min_endinghere>0) min_endinghere=0;
            min_sofarr = Math.min(min_sofarr,min_endinghere);
            min_sofar[i] = min_sofarr;
        }
        int max_endinghere=0;
        int max_sofar = 0;
        int max_diff=0;
        for (int i=v.length-1;i>=0;i--){
            max_endinghere += v[i];
            if (max_endinghere<0) max_endinghere=0;
            max_sofar = Math.max(max_sofar,max_endinghere);
            max_diff = Math.max(max_diff,max_sofar-min_sofar[i]);
        }
        System.out.println(max_diff);
    }
}

Hill 是不是可以考虑dynamic programming啊

第一个Hill 我做出来了一个办法，但是可能不是最优化的，复杂度目前是O（NlogN) [因为sort了] ， 应该有可以不用先sort的办法降到O(N）。 抛砖引玉吧，觉得这个比较笨。
主要思想就是找个X的upper_bound， 然后在[1,X_max] 里一个个试. 所以是 O（NlogN) + C*O(n ) = O(NlogN)  C++11的source code ：


int findX(const vector<int> & v)
{

        if (is_sorted(v.begin(),v.end()))
                return 0;  //X=0




        size_t N = v.size() ;
        vector<int> vbuffer(N) ;
        copy(v.begin(),v.end(),vbuffer.begin()); // copy the v content to buffer
        sort(vbuffer.begin(),vbuffer.end()); // sort vbuffer

        int X_max = 0 ;
        for (int i = 0; i < N; ++i)
        {
                int delta=abs(v[i]-vbuffer[i]) ;
                if (delta > X_max)
                {
                        X_max = delta ;
                }
        }


        int * temp = new int[N] ;
        for (int x = 1; x < X_max+1; ++x) // search for minX
        {
                ////////////////// temp array content filling
                temp[0] = v.at(0)-x ;
                for (int j = 1; j < N; ++j)
                 {
                         temp[j] = temp[j-1]+1;
                 }
                 ///////////////////

                int k ;
                for (k = 1; k < N; ++k)
                {       
                        int minimum_next = temp[k-1]+1 ;
                        if (v[k]+x < minimum_next )
                                break; // the current x doesn't satisfy, increment to x+1
                }
                if (k==N)
                        return x ;
                else{continue ; }

        }
       

}

3. Maximum DIfference
if I understand it correctly, the aim is look for max_diff = sum(right_subseq) - sum(left_subseq), I take it that it doesn't mean absolute difference.
Then off the top of my head, I hit a simple O(n^2) algorithm. The idea is simple, for an array [N] , there are N-1 partitions that split the array into left and right sections. We try each of these partition, and in each partition, we find the minimum-sum subseq of left section and maximum-sum subseq of right section (both take O(n_sub) time) and remember the difference. After N-1 iterations, we have N-1 difference values, just pick the max one.

I believe you can do better than O(n^2).

co89757 发表于 2014-1-15 01:49
Hill 是不是可以考虑dynamic programming啊

这题感觉用不了DP，因为看不出什么最优子结构和重叠子问题。。。应该就是先排序再逐对比较，找出相差最大值。

haoranliu1990 发表于 2014-1-15 09:32
这题感觉用不了DP，因为看不出什么最优子结构和重叠子问题。。。应该就是先排序再逐对比较，找出相差最大 ...

那么那个sort后比较的差只能说是X的上限吧？怎么说我的那个算法还靠谱咯

第二题想到用堆，复杂度是O( (n-d) * log d ) 不知道有没有更好的
第三题可以O(n)时间

north212 发表于 2014-6-12 12:14
Hill当时没做出来，后来想想其实挺简单的。只要从最后面开始sort，每次比较两个数就可以了。如果v > v，那 ...

如果array中有很多连续一样的数呢？比如［99，5，5，5，5，5，5，5，5，5，5，5，5，0］