обзор теста codility - pair_sum_even_count - PullRequest
Новая
       11

обзор теста codility - pair_sum_even_count

11 голосов
/ 16 января 2011

Я недавно прошел онлайн-тест на codility как часть процесса найма. Мне дали две простые задачи, которые нужно решить за 1 час. Для тех, кто не знает кодов, это сайт для онлайн-тестирования кода, где вы можете решать проблемы стиля ACM на многих языках.

Если у вас 30 минут или около того, отметьте это http://codility.com/demo/run/

Моим оружием выбора обычно является Java.

Итак, одна из проблем, с которыми я столкнулся, заключается в следующем (я постараюсь вспомнить, должен был сделать снимок экрана)

Допустим, у вас есть массив A [0] = 1 A [1] = - 1 .... A [n] = x

Тогда какой самый разумный способ узнать, сколько раз A [i] + A [j] даже там, где i

Так что, если у нас есть {1,2,3,4,5} у нас есть 1 + 3 1 + 5 2 + 4 3 + 5 = 4 пары, которые даже

Код, который я написал, был похож на 

int sum=0;
for(int i=0;i<A.length-1;i++){
 for (int j=i+1;j<A.length;j++){
   if( ((A[i]+A[j])%2) == 0 && i<j) {
       sum++;
    }
  }
}

Было еще одно ограничение: если количество пар больше 1e9, то оно должно быть повторено -1, но давайте забудем об этом.

Можете ли вы предложить лучшее решение для этого. Количество элементов не будет превышать 1e9 в обычных случаях.

Мне кажется, я получил 27 очков за приведенный выше код (т.е. он не идеален). Codility дает подробную оценку того, что пошло не так, у меня сейчас этого нет.

Ответы [ 12 ]

0 голосов
/ 27 апреля 2012 
    int total = 0;
    int size = A.length;
    for(int i=0; i < size; i++) {
        total += (A[size-1] - A[i]) / 2;
    }
    System.out.println("Total : " + total);
0 голосов
/ 08 февраля 2011

Java-реализация, которая прекрасно работает, основываясь на ответе «Сванте»: 

int getNumSumsOfTwoEven(int[] a) {

    long numOdd = 0;
    long numEven = 0;
    for(int i = 0; i < a.length; i++) {
        if(a[i] % 2 == 0) { //even
            numOdd++;
        } else {
            numEven++;
        }
    }

    //N! / ((N - k)! · k!), where N = num. even nums or num odd nums, k = 2
    long numSumOfTwoEven = (long)(fact(numOdd) / (fact(numOdd - 2) * 2));
    numSumOfTwoEven += (long)(fact(numEven) / (fact(numEven - 2) * 2));

    if(numSumOfTwoEven > ((long)1e9)) {
        return -1;
    }
    return numSumOfTwoEven;

}
// This is a recursive function to calculate factorials
long fact(int i) {
    if(i == 0) {
        return 1;
    }
    return i * fact(i-1);
}
Страница:
...