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

第一题：
https://gist.github.com/2bethere/680aebe7a9da8744b838

用的是回溯，关键的一步：
c= -upperRange;
相当于从最低到最高。
O(n^2)

感觉应该有更好的解法。

第二题：
Range Minimum Query. 两个segmented tree，一个min一个max。O(n) construction, O(1) lookup, O(n)结果。还没写code。过两天update.

第三题：
Maximum subarray problem, 用Kadane's algorithm。下面有解释。这道题好变态，泥马不可能45分钟做出来无bug。
https://gist.github.com/2bethere/821f0b129775a58864d0

不得不解释一下，一共3个pass,最后算是6n= O(n)
第一个pass用Kadane's algorithm，分别从左往右和从右往左算Max和Min。
输入： {3, -5, 1, -2, 8, -2, 3, -2, 1}
Max so far from left: [3, -2, 1, -1, 8, 6, 9, 7, 8]
Min so far from left: [3, -5, -4, -6, 2, -2, 1, -2, -1]

Max so far from right: [3, 3, 8, 7, 9, 1, 3, -1, 1]
Min so far from right: [3, -6, -1, -2, 6, -2, 1, -2, 1]


第二个pass分别从左和右算出这一段之后的min/max，比如说
[3, -2, 1, -1, 8, 6, 9, 7, 8]
[3, 3, 1, -1, 8, 6, 9, 7, 8] <-- 因为是从左,3>-2
[3, 3, 3, -1, 8, 6, 9, 7, 8] 3>1
[3, 3, 3, 3, 8, 6, 9, 7, 8]
[3, 3, 3, 3, 8, 6, 9, 7, 8]
[3, 3, 3, 3, 8, 8, 9, 7, 8]
[3, 3, 3, 3, 8, 8, 9, 7, 8]
[3, 3, 3, 3, 8, 8, 9, 9, 8]
[3, 3, 3, 3, 8, 8, 9, 9, 9] <-结果

下面算min
[3, -5, -4, -6, 2, -2, 1, -2, -1]->[3, -5, -5, -6, -6, -6, -6, -6, -6]


右边向左：
Max: [3, 3, 8, 7, 9, 1, 3, -1, 1]->[9, 9, 9, 9, 9, 3, 3, 1, 1]
Min: [3, -6, -1, -2, 6, -2, 1, -2, 1]->[-6, -6, -2, -2, -2, -2, -2, -2, 1]


好，这时候你肯定很费解为毛要这样算。我们把他们拼在一起：
MaxLeft :[3, 3, 3, 3, 8, 8, 9, 9, 9]
MinRight:[-6, -6, -2, -2, -2, -2, -2, -2, 1]

如果计算MaxLeft[n]-MinRight[n+1]的最大绝对差，就可以得到不重叠的两个sub array的max。
同理计算MinLeft和MaxRight，两轮最后胜出的就是结果。

你妹啊！这么复杂谁45分钟能做出来啊？

我做的第一题Hill的解法：时间复杂度O(nlogn)，利用Java本身的api对一个新的array，取名为int index[]{1,2,3,4,...,n}进行排序，排序的依据是自建的一个MyComparator；这个Comparator把index[]按照 原始array 的值从小到大 进行排序，需要O(nlogn)的时间；然后遍历一遍整个index[]，计算出 Math.max(index - i) 的最大值即可。
奇怪的是可以通过自带的test case [5, 4, 3, 2, 8] 和 自己写的一些其他的case，比如［99，5，5，5，5，5，5，5，5，5，5，5，5，0］；但是提交结果却一个case都无法通过。很困惑？？？

1.     public static void hill(Integer[] v) {
   
2.         // Write your code here
   
3.         // To print results to the standard output you can use System.out.println()
   
4.         // Example: System.out.println("Hello world!");
   
5.         Integer[] index = new Integer[v.length];
   
6.         for (int i = 0 ; i < index.length; i++) {
   
7.             index[i] = i;
   
8.         }
   
9.         Arrays.sort(index, new MyComparator(v));
   
10.         int X = 0;
    
11.         
    
12.         System.out.println(Arrays.toString(index));
    
13.         for (int i = 0; i < index.length; i++) {
    
14.             X = Math.max(X, Math.abs(index[i] - i));
    
15.         }
    
16.         System.out.println(X);
    
17.     }
    
18.    
    
19.     public static class MyComparator implements Comparator<Integer> {
    
20.         Integer[] array = null;
    
21.         public MyComparator(Integer[] v) {
    
22.             array = Arrays.copyOf(v, v.length);
    
23.         }
    
24.         @Override
    
25.         public int compare(Integer o1, Integer o2) {
    
26.             return array[o1] - array[o2];
    
27.         }
    
28.     }
    

复制代码

貌似不用太在意复杂度，时限2s 感觉只要不是exponential的怎么都能过

north212 发表于 2014-7-12 06:14
嗯，我这个方法是错的，不用看了。。。

第一题能否用二分法替代一个一个增加方法，这样可以降到 nlgn吧

shohoku11wrj 发表于 2014-8-6 17:07
我做的第一题Hill的解法：时间复杂度O(nlogn)，利用Java本身的api对一个新的array，取名为int index[]{1,2, ...

感觉楼主的方法找到的是一个可行解，并不是下限

这几题我也在线做了一下，当时硬是卡死在Hill这题上了。提交后我又仔细想了想这题，其实只要找出输入序列中某对降序的最大差值再平均一下就对了。当然，还要为了strictly ascending order， 还要考虑一下数值对所在位置上的差值（第i个数至少要比第j个数大j-i）。下面是我的代码，我自己想了几个test case是都对的。有不对的地方，望童鞋们指正。
时间复杂度我肯定是小于O（n^2）的，因为我在遍历时随时记录当前最大值。如果后面的要比较的base比max小，就可以直接跳过了。

1.     int findX (int[] values) {
   
2.         if (values == null || values.length < 2) {
   
3.             return 0;
   
4.         }
   
5.         
   
6.         int result =0;
   
7.         
   
8.         int maxVal = values[0];
   
9.         int maxDiff = 0;
   
10.         int len = values.length;
    
11.         for (int i=0; i<len; i++) {
    
12.             int base = values[i];
    
13.             if (base < maxVal) {
    
14.                 continue;
    
15.             } else {
    
16.                 maxVal = base;
    
17.                 for (int j=i+1; j<len; j++) {
    
18.                     int compare = values[j];
    
19.                     if (compare + i < base + j && (base-compare+j-i) > maxDiff) {
    
20.                         maxDiff = base-compare+j-i;
    
21.                     }
    
22.                 }
    
23.             }
    
24. 
    
25.         }
    
26.         
    
27.         result = (maxDiff+1)/2;
    
28.         
    
29.         return result;
    
30.     }

复制代码

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

我也做了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]

O(n) 时间复杂度 代码检验通过

public int maxDiff(Integer[] A) {

            //DP: left array recording the minimum value; right array recording the maximum value
            int[] left=new int[A.length];
            int[] right=new int[A.length];
           
             int max=Integer.MIN_VALUE,current=0;
         
         for(int i=A.length-1;i>=0;i--){
             current+=A[i];
             max=current>max?current:max;
             current=current<0?0:current;
             left[i]=max;
         }
         
         
         
         int min=Integer.MAX_VALUE;
                         current=0;
         
         for(int i=0;i<A.length;i++){
             current+=A[i];
             min=current<min?current:min;
             current=current>0?0:current;
             right[i]=min;
         }
         
         
         int difference=Integer.MIN_VALUE;
          for(int i=0;i<A.length;i++){
                  if(left[i]-right[i]>difference){
                          difference=left[i]-right[i];
                  }
          }
         
          return difference;
    } // end of method