Skip to content

Codility — проверь свой уровень программиста

26/02/2010

Только что узнал о замечательном сервисе 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)🙂

11 комментариев
  1. mlvl permalink

    Будем популяризовывать Ж):

    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 -1
    
  2. mlvl permalink

    Indent… :)(

  3. mlvl permalink

    Thanks!🙂

  4. SubtleBeetle permalink

    Сделал сразу за О(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. }

    • SubtleBeetle permalink

      Точнее вот, а там плохо скопировалось из окна 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;

      • SubtleBeetle permalink

        Это фигня с отображением в комментариях. Непонятно только почему…

                    
                    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.

        • Никита permalink

          Ты извини конечно, но твой код полностью нерабочий! В L[0] по умолчанию будет 0. Зачем 3 строчка? В условии цикла(строчка 4) тебе сразу ошибку выдаст. A — это имя массива. Нельзя сравнивать имя массива с переменной i типа int. А то что внутри цикла, так лучше и не смотреть : заполняешь массив R со всеми нулями элементами из А а потом сравниваешь массив L со всеми нулями с почти копией R массива A….В итоге у тебя в ответе всегда будет -1 кроме случая когда А[1] = 0, тогда вернется 0.

  5. SubtleBeetle permalink

    Добавил проверку на равенство длины массива А нулю (возвращаем -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.

  6. SubtleBeetle permalink

    По сути задание на динамическое программирование.🙂

  7. Никита permalink

    А 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&lt;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&lt;A.Length;ii++)
        {
          ssum -= A[ii];
          fsum += A[ii-1]; 
          if (fsum == ssum) return ii; 
        }
        return -1;
      }
    }
    

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: