Tuesday, February 15, 2011

Вопросы с собеседований Google, часть 5

Доброго времени суток, уважаемый читатель.
В связи с проходящим, в данный момент, NASA Tournament Lab Marathon Match я немного забросил свой блог. Но это временно и, чтобы как-то прервать затянувшееся молчание, публикую очередную серию вопроссов с собеседований.

Итак, вопросы:

21) Вам дан 1 миллион целых чисел, как их эффективно отсортировать?
22) В чем разница между static, final и const в Java? (Если вы не знаете Java, аналогичный вопрос будет задан по другому языку программирования)
23) Расскажите о каком-нибудь вашем университетском или рабочем проекте. Как бы вы могли его сделать более эффективным с точки зрения алгоритмов.



21) Вам дан 1 миллион целых чисел, как их эффективно отсортировать?

Задачка не так проста как может показаться на первый взгляд. И для того, чтобы дать исчерпывающий ответ требуется хорошее знание теории и много уточняющих вопросов. Я бы начал ответ с уточняющих вопросов:
- ограничены ли числа в каком-нибудь диапазоне?
- влезают ли они в память? 1млн * 4 байт ~ 4 Мб
- есть ли какие-либо предположения о изначальном порядке чисел?
- что такое эффективно? быстро или, может быть, без использования дополнительной памяти? Или, может быть, достаточно быстро но с достаточно разумным потреблением памяти?
- в каком виде эти числа нам предоставлены? Массив или связный список?
- вообще говоря, имеет значение даже компилятор и процессор на котором это выполняется, но это уже тонкости.

Теперь, по пунктам:
- если числа ограничены в каком-то диапазоне то имеет смысл вспомнить про поразрядную сортировку (Radix sort) и сортировку подсчетом (Counting sort). Первый способ имеет смысл применять в случае если целые числа ограничены в большом диапазоне, например 32 или 64 бита, второй способ если диапазон возможных значений существенно меньше, например от 0 до 1000.

- если числа в память не влезают, что, конечно, маловероятно в наше время, ведь 4 Мб не проблема даже для карманных устройств, то следует вспомнить внешние сортировки. В этом случае мы разбиваем исходные данные на части влезающие в память, сортируем каждую часть и потом объединяем их в единое целое слиянием.

- если числа, к примеру, почти отсортированы, то эффективным способом может оказаться сортировка вставками (Insertion sort). Существует так же, малоизвестный способ сортировки Timsort, который является вариацией сортировки слиянием и сортировки вставками.

- если требуется обойтись без использования дополнительной памяти то пожалуй стоит вспомнить сортировку Шелла, а так же, снова сортировку вставками.

- если вдруг так случилось, что данные у нас представлены в виде связного списка, то мы снова приходим к сортировке слиянием (Merge sort)

Читатель, наверное, заметил уже, что во всем этом перечислении я не упомянул одну из самых популярных, быструю сортировку Quick sort. Я это сделал нарочно. Действительно, в общем случае quick sort является одним из наиболее эффективных способов сортировки. Хотя, в реальных реализациях как правило используется не классический quick sort а одна из его модификаций, например интроспективная сортировка. В первую очередь, это связано с известной проблемой быстрой сортировки, когда, в худшем случае, сложность возрастает до O(n2)

22) В чем разница между static, final и const в Java? (Если вы не знаете Java, аналогичный вопрос будет задан по другому языку программирования)

Начнем с const. const это зарезервированное ключевое слово в Java, однако оно никак не используется. Это значит, что использовать его где-либо в программе (за исключением, естественно, комментариев) нельзя.

final – используется в различных контекстах и означает, что нечто не может быть изменено. Например, final класс не может иметь наследников. Final метод не может быть переопределен в дочернем классе, final переменная это переменная значение которой присваивается лишь однажды и потом не может быть изменено.

static – так же используется в различных контекстах. Переменная, объявленная static, называется переменной класса и все экземпляры класса используют одну и ту же копию этой переменной. Более того, такая переменная может быть использована вообще без создания экземпляров класса. Статический метод так же может быть вызван без создания экземпляра класса. Кроме того, static может использоваться в объявлении класса, обычно, таким способом, объявляют небольшие вспомогательные классы, которые тесно связаны с каким-то другим, основным классом. Например класс HashEntry в AbstractHashedMap

23) Расскажите о каком-нибудь вашем университетском или рабочем проекте. Как бы вы могли его сделать более эффективным с точки зрения алгоритмов.

Признаюсь честно, мне не доводилось в реальной работе сталкиваться с проектами требующими серьезного алгоритмического подхода. Хотя, я видел ситуации, когда изменение одной строчки кода (замена ArrayList на LinkedList) увеличивало скорость работы на два! порядка.
Гораздо чаще, основные проблемы с производительностью были вызваны не неэффективными алгоритмами, а неудачной архитектурой (например: неправильная грануляция веб-сервисов), неподходящей технологией (типа XML базы данных для управления правами пользователей), или банально неправильно расставленными индексами в базе данных.
Гораздо больше алгоритмических изощрений встречается в личных проектах или исследованиях. Вот там да, там можно рассказать про полный спектр всевозможных ухищрений.

2 comments:

  1. Насчёт final ответ не исчерпывающий. Значение final поля может быть переопределено с помощью Reflection или JNI. Кроме того, final поля обладают тем свойством, что их настоящее значение гарантированно доступно другим потокам, как только объект данного класса родился. Если поле не final, то другой поток, обратившись к полю рождённого объекта, может увидеть там 0. Это очень важный момент.

    ReplyDelete
  2. Евгений, спасибо за комментарий, очень интересная информация.

    ReplyDelete