一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 8762|回复: 29
收起左侧

[算法题] 三道coding challenge from hired.com (Hill,Deviation ,Maximum Difference)

[复制链接] |试试Instant~ |关注本帖
纠结帝 发表于 2014-1-14 14:20:15 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
在一个前辈的分享帖里看到了关于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.

评分

1

查看全部评分

本帖被以下淘专辑推荐:

weakbirds 发表于 2014-10-18 11:37:10 | 显示全部楼层
Hill直接二分答案,可以在O(n)时间check一个X是否合法,并且显然X是monotonic的然后X有upper_bound N因为array length = N,所以就可以O(NlogN)了
回复 支持 1 反对 2

使用道具 举报

NdrZmansN 发表于 2014-12-5 06:07:12 | 显示全部楼层
本帖最后由 NdrZmansN 于 2014-12-5 06:23 编辑

我也做了hired的challenge.当时也卡在hill这个题上了.事后想出的解法:
  1.   def hill(self, nums):
  2.     n = len(nums)
  3.     if n <= 1: return 0

  4.     copy = []
  5.     for i in range(n):
  6.       copy.append(nums[i] - i)

  7.     minn, maxn = copy[0], copy[0]
  8.     mini, maxi = 0, 0
  9.     maxdiff = 0
  10.     for i in range(n):
  11.       n = copy[i]
  12.       if n < minn:
  13.         minn, mini = n, i
  14.       if n > maxn:
  15.         maxn, maxi = n, i
  16.       if mini > maxi:
  17.         maxdiff = max(maxdiff, maxn - minn)
  18.         
  19.     return (maxdiff + 1) / 2
复制代码
思路是: 先把每个数减去它的index. 这样[5,4,3,2,8]就变成了[5,3,1,-1,4].
现在问题就变成了怎么样生成一个不降数列 (non descending).
找出一个maxdiff, 等于最大值减去最小值,同时最大值的index小于最小值的index.
结果等于 (maxdiff + 1) / 2

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

denilsen 发表于 2015-1-14 04:45:32 | 显示全部楼层
大家好,小弟献丑了,我帖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);
    }
}

回复 支持 1 反对 0

使用道具 举报

websterww 发表于 2014-10-7 13:10:39 | 显示全部楼层
这几题我也在线做了一下,当时硬是卡死在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.         result = (maxDiff+1)/2;
  27.         
  28.         return result;
  29.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

tsxy 发表于 2014-8-2 16:30:40 | 显示全部楼层
第一题:
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分钟能做出来啊?
回复 支持 1 反对 0

使用道具 举报

astkaasa 发表于 2014-9-15 13:21:52 | 显示全部楼层
本帖最后由 astkaasa 于 2014-9-15 00:08 编辑

为啥感觉第三个最简单……
回复 支持 1 反对 0

使用道具 举报

co89757 发表于 2014-1-15 01:49:56 | 显示全部楼层
Hill 是不是可以考虑dynamic programming啊
回复 支持 反对

使用道具 举报

co89757 发表于 2014-1-15 04:46:27 | 显示全部楼层
第一个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 ; }

        }
       

}
回复 支持 反对

使用道具 举报

co89757 发表于 2014-1-15 05:25:31 | 显示全部楼层
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).
回复 支持 反对

使用道具 举报

haoranliu1990 发表于 2014-1-15 09:32:27 | 显示全部楼层

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

使用道具 举报

co89757 发表于 2014-1-15 15:37:23 来自手机 | 显示全部楼层
haoranliu1990 发表于 2014-1-15 09:32
这题感觉用不了DP,因为看不出什么最优子结构和重叠子问题。。。应该就是先排序再逐对比较,找出相差最大 ...

那么那个sort后比较的差只能说是X的上限吧?怎么说我的那个算法还靠谱咯
回复 支持 反对

使用道具 举报

ilovexiao77 发表于 2014-4-8 00:22:46 | 显示全部楼层
第二题想到用堆,复杂度是O( (n-d) * log d ) 不知道有没有更好的
第三题可以O(n)时间
回复 支持 反对

使用道具 举报

north212 发表于 2014-6-12 12:14:34 | 显示全部楼层
本帖最后由 north212 于 2014-6-12 12:28 编辑

Hill当时没做出来,后来想想其实挺简单的。只要从最后面开始sort,每次比较两个数就可以了。如果v > v[i+1],那么就看这两个数差多少,再平均一下,至于后面sort好的根本不用管。代码如下,没有测试过,不知道我这个想法有没有问题:
public int hill(Integer[] v){
     if(v.length == 1) return 0;
     int change = 0;
     for(int i=v.length-2; i>=0; i++){
          change += sort(v, i, change);
     }
     return change;
}

private int sort(Integer[] v, int curr, int change){
     int next = v[curr+1];
     int num = v[curr];
     for(int i=0; i<change; i++){//if current value can be adjusted within the old change, no more change is needed
          num -= 1;
          if(num < next){
             v[curr] = num;
             return 0;
          }
     }
     int diff = (num-next)/2+1;  //currently v = num-change-diff, v[i+1]=next+diff
     v[curr] = num-diff;     
     return diff;
}





回复 支持 反对

使用道具 举报

hiveser 发表于 2014-7-9 04:07:16 | 显示全部楼层
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]
回复 支持 反对

使用道具 举报

north212 发表于 2014-7-12 06:14:56 | 显示全部楼层
hiveser 发表于 2014-7-9 04:07
如果array中有很多连续一样的数呢?比如[99,5,5,5,5,5,5,5,5,5,5,5,5,0]

嗯,我这个方法是错的,不用看了。。。
回复 支持 反对

使用道具 举报

shohoku11wrj 发表于 2014-8-6 17:07:46 | 显示全部楼层
我做的第一题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.     }
复制代码
回复 支持 反对

使用道具 举报

lcwyc 发表于 2014-9-2 09:02:06 | 显示全部楼层
貌似不用太在意复杂度,时限2s 感觉只要不是exponential的怎么都能过
回复 支持 反对

使用道具 举报

lcwyc 发表于 2014-9-2 13:56:02 | 显示全部楼层
north212 发表于 2014-7-12 06:14
嗯,我这个方法是错的,不用看了。。。

第一题能否用二分法替代一个一个增加方法,这样可以降到 nlgn吧
回复 支持 反对

使用道具 举报

MYcolting 发表于 2014-9-7 21:52:32 | 显示全部楼层
shohoku11wrj 发表于 2014-8-6 17:07
我做的第一题Hill的解法:时间复杂度O(nlogn),利用Java本身的api对一个新的array,取名为int index[]{1,2, ...

感觉楼主的方法找到的是一个可行解,并不是下限
回复 支持 反对

使用道具 举报

yyboyz 发表于 2014-12-16 05:41:27 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 00:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表