Codility — проверь свой уровень программиста
Только что узнал о замечательном сервисе Codility — попытке создать инструмент для тестирования навыков программистов. Из интереса поучаствовал. Отчёт под катом. Внимание, там спойлер задания. Возможно, Вам лучше будет сначала пройти демо-тест 🙂
Регистрироваться не стал, делал тестовое задание .На всё про всё даётся 30 минут, надо написать функцию, вычисляющую equilibrium index для массива — т.е. индекс, при котором сумма предшествующих элементов равна сумме следующих. То есть, если нам дан массив:
$A = array(-7, 1, 5, 2, -4, 3, 0);
Его индексы равновесия будут равны 3 (-7 + 1 + 5 = -4 + 3 + 0) и 6(-7 + 1 + 5 + 2 + (-4) + 3 = 0). Сумма пустого множества элементов принимается равной нулю. Нужно написать программу, принимающую массив и возвращающую любой индекс равновесия или -1 если индекса нет. Отдельной строкой идёт упоминание что массивы могут быть очень большими.
Писать код можно на Java, C++, C#, C, Javascript, Pascal, Perl, PHPб Python или Ruby. Есть из чего выбрать. Я взял PHP из-за большого количества функций по работе с массивами (изначально нацеливался сделать задание с помощью array_slice и array_sum). Кстати, язык можно менять уже в ходе выполнения задания: если Вы видите, что удобнее было бы реализовать программу на чём-нибудь другом, можно тут же переключиться. Программа проверяется линтом (видимо) и проходит простой тест на правильность ответа. У меня, например, первый вариант выдал индекс за границами массива, о чём я был оповещён весьма информативным сообщением. Это удобно, поскольку позволяет избежать опечаток и мелких ошибок.
В конце Вам выстаавляется оценка в зависимости от затраченного времени и качества программы. Я получил 31 из 100 — моё решение глючило во многих edge cases и не прошло проверку на скорость работы (там написано что последний тест отлавливает функции, выполняющиеся в O(n^2)). Есть над чем подумать 🙂 Мой финальный вариант кода (по времени уложился в 12 минут):
function equi ( $A ) {
$eq = -1;
for ($i = 0; $i < count($A); $i++) {
if (array_sum(array_slice($A, $i)) == array_sum(array_slice($A, $i+1,count($A) - ($i + 1)))) {
$eq = $i;
}
}
return $eq;
}
Не очень то опрятно, и не работает в некоторых случаях. Неудивительно что оценка такая низкая 🙂
Ещё одно — их веб-IDE немного глючит в Хроме, поэтому я просто скопировал заготовку кода к себе, написал его на локальной машине и вставил в окно. Так было гораздо удобнее.
В общем, если хотите проверить свой уровень — Вам сюда. А я пока подумаю, как сделать это быстрее чем O(n^2) 🙂
Механический мир 
Будем популяризовывать Ж):
def equi ( A ): def _sum(lst): res = 0 for n in lst: res += n return res total = _sum(A) eq_i_lst = [] left_sum = 0 right_sum = total for i in xrange(len(A)): curr = A[i] if left_sum == right_sum - curr: eq_i_lst.append(i) right_sum -= curr left_sum += curr return eq_i_lst[0] if eq_i_lst else -1Indent… :)(
Thanks! 🙂
Сделал сразу за О(n), но набрал только 88 :). Загнулось на пустом массиве и больших числах.
Вот решение на C#:
01.int equi ( int[] A ) {
02. int[] L = new int[A.Length];
03. int[] R = new int[A.Length];
04. L[0] = 0;
05. for (int i = 0; i <A>= 0; i—)
15. {
16. R[i] = R[i + 1] + A[i + 1];
17. if (L[i] == R[i])
18. {
19. return i;
20. }
21. }
22. return -1;
23. }
Точнее вот, а там плохо скопировалось из окна Codility.
int[] L = new int[A.Length];
int[] R = new int[A.Length];
L[0] = 0;
for (int i = 0; i = 0; i—)
{
R[i] = R[i + 1] + A[i + 1];
if (L[i] == R[i])
{
return i;
}
}
return -1;
Это фигня с отображением в комментариях. Непонятно только почему…
int[] L = new int[A.Length]; int[] R = new int[A.Length]; L[0] = 0; for (int i = 0; i <A>= 0; i--) { R[i] = R[i + 1] + A[i + 1]; if (L[i] == R[i]) { return i; } } return -1;Да, это WordPress.com что то шалит с тегом code.
Ты извини конечно, но твой код полностью нерабочий! В L[0] по умолчанию будет 0. Зачем 3 строчка? В условии цикла(строчка 4) тебе сразу ошибку выдаст. A — это имя массива. Нельзя сравнивать имя массива с переменной i типа int. А то что внутри цикла, так лучше и не смотреть : заполняешь массив R со всеми нулями элементами из А а потом сравниваешь массив L со всеми нулями с почти копией R массива A….В итоге у тебя в ответе всегда будет -1 кроме случая когда А[1] = 0, тогда вернется 0.
Добавил проверку на равенство длины массива А нулю (возвращаем -1 в таком случае) и поменял у массивов R и L тип с int на long и решение прошло все тесты.
Идея проста массив L хранит сумму слева для индекса массива А, а массив R справа. Одним проходом слева на право заполняется массив L:
L[i] = L[i — 1] + A[i — 1]; (Предварительно L[0] = 0;) А потом проходом справа налево заполняется массив R и сравниваются R[i] и L[i]. Если равны, то ответ i. Если в итоге не нашли возращается -1.
По сути задание на динамическое программирование. 🙂
А dun мой компактный код на гарпе с прохождением всех тестов.
using System; // you can also use other imports, for example: // using System.Collections.Generic; class Solution { public int equi ( int[] A ) { if (A.Length == 0) return -1; long fsum = 0, ssum=0; for (long i = 1;i<A.Length;i++) ssum+= A[i]; if (fsum == ssum) return 0; if (ssum-A[A.Length-1]+A[0] == 0) return A.Length-1; for (int ii = 1;ii<A.Length;ii++) { ssum -= A[ii]; fsum += A[ii-1]; if (fsum == ssum) return ii; } return -1; } }Ого! И правда 100% на Java. Только ругается на long в 9 строке, пришлось переделать на int. Ну и операторы сравнения в 9 и 13 строках конечно. А так все отлично прошло. Поздравляю!
на php:
function solution($A) {
if ((count($A)==0)||(count($A)>100000)) return -1;
$leftSum=$rightSum=0;
for ($i=1;$i<count($A);$i++) $rightSum+=$A[$i];
if ($rightSum==0) return 0;
for ($i=1;$i<count($A);$i++) {
$rightSum-=$A[$i];
$leftSum+=$A[$i-1];
if ($rightSum==$leftSum) return $i;
}
return -1;
}
https://codility.com/demo/results/demoVUJ8VF-H9J/ — сотка
class Solution {
public int solution(int[] A) {
int sumAll = 0;
for( int i=0; i < A.length; sumAll+=A[i++] ) ;
int sumPrev = 0;
int sumNext = sumAll;
for(int i = 0; i < A.length; i++) {
sumNext -= A[i];
if( sumPrev == sumNext )
return i;
sumPrev += A[i];
}
return -1;
}
}
https://app.codility.com/demo/results/demoYH4MW8-ZQE/
сотка, правда по времени уложился впритык — сабмитнул на последних секундах. Причина — начал решать задачу автора (из эотй статьи), а потом понял, что там задание другое выдали, пришлось его срочно делать.