Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 26

Вы, возможно, неоднократно слышали, что работодатели хотят видеть «хороший» и «чистый» код. Но что это такое и как продемонстрировать его на собеседовании? О хорошем коде всегда можно сказать, что он:

• правильный: код корректно обрабатывает все корректные и некорректные входные данные;

• эффективный: код максимально эффективен с точки зрения времени и пространства (памяти). Эффективность включает асимптотическую («О-большое») и практическую (реальную) эффективность. При расчете зависимости времени выполнения программы от ее сложности постоянный коэффициент можно отбросить, но в реальной жизни он может оказать влияние на эффективность;

• простой: если вы можете реализовать алгоритм в десяти строках, не пишите сто. Создайте код максимально быстро;

• читаемый: другой разработчик должен прочитать ваш код и понять, что и как делается. Для читаемого кода необходимы комментарии, они делают код более понятным. Сдвига строк недостаточно;

• обслуживаемый: код должен легко адаптироваться к изменениям, которые возникают на протяжении жизненного цикла продукта, он должен обслуживаться другими программистами так же легко, как и разработчиком.

Следование всем этим правилам требует определенных компромиссов. Например, стоит принести в жертву немного эффективности, но сделать код более удобным в сопровождении и наоборот.

Вы должны думать обо всех этих аспектах, когда пишете программный код на собеседовании.

Структуры данных

Предположим, что вас попросили написать функцию, выполняющую сложение двух простых полиномов, представленных в виде Ax^a+Bx^b+…. Интервьюер не хочет, чтобы вы делали парсинг строк, ему нужно, чтобы вы использовали структуру данных, способную хранить полином.

Есть много разных способов решить такую задачу.

Неудачная реализация

Плохая реализация подразумевает хранение полинома в виде массива чисел с двойной точностью, где k-й элемент соответствует элементу x^k. Такая структура может стать причиной ошибок при необходимости представить полином, содержащий отрицательные или дробные степени. Кроме того, для хранения полинома, содержащего только один член x¹⁰⁰⁰, потребуется массив из 1000 элементов.

1 int[] sum(double[] poly1, double[] poly2) {

2…

3 }

Чуть лучшая реализация

Чуть лучшая реализация подразумевает хранение полинома в двух массивах – coefficients и exponents. Полином в этом случае может храниться в любом порядке, но i-й член полинома должен иметь вид coefficients[i] *x^exponents[i].

Таким образом, если coefficients[p] =k и exponents[p] =m, то p-й член будет равен kx^m.

Хотя данная реализация не имеет таких ограничений, как предыдущее решение, она все еще далека от идеала. Мы должны использовать пару массивов для каждого полинома. Если массивы будут разной длины, то в полиноме оказываются «неопределенные» значения. Да и результат будет не очень удобным, так как при вызове функция будет возвращать два массива.

1??? sum(double[] coeffs1, double[] expon1,

2 double[] coeffs2, double[] expon2) {

3…

4 }

Хорошая реализация

Хорошая реализация – разработка собственной структуры данных для хранения полинома.

1 class PolyTerm {

2 double coefficient; 3 double exponent;

4 }

5

6 PolyTerm[] sum(PolyTerm[] poly1, PolyTerm[] poly) {

7…

8 }

Кое-кто будет утверждать, что это «сверхоптимизация». Возможно, да, а возможно – нет. Независимо от вашего мнения, это решение продемонстрирует, что вы думаете о коде и не пытаетесь решить задачу самым простым (и самым быстрым) способом.

Обоснованное многократное использование кода

Предположим, что вас попросили написать функцию, проверяющую на равенство двоичное и шестнадцатеричное представление числа, хранимое в виде строки. Изящная реализация этой задачи подразумевает повторное использование кода:

1 public boolean compareBinToHex(String binary, String hex) {

2 int n1 = convertToBase(binary, 2);

3 int n2 = convertToBase(hex, 16);

4 if (n1 < 0 || n2 < 0) {

5 return false;

6 } else {

7 return n1 == n2;

8 }

9 }

10

11 public int digitToValue(char c) {

12 if (c >= '0' && c <= '9') return c – '0';

13 else if (c >= 'A' && c <= 'F') return 10 + c – 'A';

14 else if (c >= 'a' && c <= 'f') return 10 + c – 'a';

15 return -1;

16 }

17

18 public int convertToBase(String number, int base) {

19 if (base < 2 || (base > 10 && base!= 16)) return -1;

20 int value = 0;

21 for (int i = number.length() – 1; i >= 0; i-) {

22 int digit = digitToValue(number.charAt(i));

23 if (digit < 0 || digit >= base) {

24 return -1;

25 }

26 int exp = number.length() – 1 – i;

27 value += digit * Math.pow(base, exp);

28 }

29 return value;

30 }

Возможно, вы смогли бы написать отдельный код, преобразующий двоичное число в шестнадцатеричное, но это сделает нашу программу более громоздкой и тяжелой в обслуживании. Поэтому мы используем код повторно, вызывая общие методы convertToBase и digitToValue.

Модульность

Написание модульного кода подразумевает выделение изолированных блоков программы в отдельные методы. Это делает код более удобным, читаемым и тестируемым.

Допустим, что вам нужно написать код, меняющий местами минимальный и максимальный элементы в целочисленном массиве. Эту задачу можно реализовать в одном методе.

1 public void swapMinMax(int[] array) {

2 int minIndex = 0;

3 for (int i = 1; i < array.length; i++) {

4 if (array[i] < array[minIndex]) {

5 minIndex = i;

6 }

7 }

8

9 int maxIndex = 0;

10 for (int i = 1; i < array.length; i++) {

11 if (array[i] > array[maxIndex]) {

12 maxIndex = i;

13 }

14 }

15

16 int temp = array[minIndex];

17 array[minIndex] = array[maxIndex];

18 array[maxIndex] = temp;

19 }

Но эту же задачу можно решить с использованием модульного кода, выделив относительно изолированные блоки кода в отдельные методы.

1 public static int getMinIndex(int[] array) {

2 int minIndex = 0;

3 for (int i = 1; i < array.length; i++) {

4 if (array[i] < array[minIndex]) {

5 minIndex = i;

6 }

7 }

8 return minIndex;

9 }

10

11 public static int getMaxIndex(int[] array) {

12 int maxIndex = 0;

13 for (int i = 1; i < array.length; i++) {

14 if (array[i] > array[maxIndex]) {

15 maxIndex = i;

16 } 17 }

18 return maxIndex;

19 }

20

21 public static void swap(int[] array, int m, int n) {

22 int temp = array[m];

23 array[m] = array[n];

24 array[n] = temp;

25 }

26

27 public static void swapMinMaxBetter(int[] array) {

28 int minIndex = getMinIndex(array);

29 int maxIndex = getMaxIndex(array);

30 swap(array, minIndex, maxIndex);

31 }

Немодульный код не так уж и плох, но модульный код значительно легче протестировать, так как каждый его компонент можно проверить по отдельности. Чем код сложнее, тем оправданнее его модульность. Такой подход облегчит чтение и поддержку кода. Ваш интервьюер хочет увидеть, насколько вы владеете этими навыками.

Гибкость и надежность

Когда интервьюер просит написать код для проверки игрового поля для игры в крестики-нолики, это еще не означает, что доска имеет размер 3×3. Почему бы сразу не написать универсальный код для доски произвольного размера N×N?

Гибкий и универсальный код предполагает использование констант вместо переменных или шаблонов/обобщений, позволяющих решить задачу. Если мы можем написать код, решающий задачу в общем виде, мы должны это сделать.

Конечно, всему есть предел. Если решение для общего случая оказывается слишком сложным и громоздким, то лучше ограничиться простым случаем, который фигурирует в задании.

Проверка

Отличительной чертой предусмотрительного программиста является то, что он не делает предположений о входных данных. Вместо этого он проверяет введенную последовательность с помощью операторов ASSERT или if. Вернемся к написанному ранее коду, преобразующему числа из системы счисления по основанию i (двоичной или шестнадцатеричной системы) в целое число (int).

1 public int convertToBase(String number, int base) {

2 if (base < 2 || (base > 10 && base!= 16)) return -1;

3 int value = 0;

4 for (int i = number.length() – 1; i >= 0; i-) {

5 int digit = digitToValue(number.charAt(i));

6 if (digit < 0 || digit >= base) {

7 return -1;

8 }

9 int exp = number.length() – 1 – i;

10 value += digit * Math.pow(base, exp);

11 }

12 return value;

13 }

В строке 2 мы проверяем, корректно ли выбрана система счисления (если основание больше 10, то это шестнадцатеричная система). В строке 6 мы производим еще одну проверку: нужно убедиться, что каждая цифра находится в пределах допустимого диапазона.

Подобные проверки очень важны в реальных программах, а значит, их оценят и на собеседовании. Конечно, проверка ошибок – утомительное занятие и на собеседовании отнимает много драгоценного времени. Но вам важно продемонстрировать свое умение сделать обработку ошибок. Если требуемая проверка на ошибки оказывается сложнее, чем оператор if, лучше оставить свободное место на листке и сказать интервьюеру, что собираетесь заполнить его кодом проверки ошибок, когда закончите основную часть программы.