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

Надеюсь, что все читатели знакомы с массивами и строками, поэтому нет необходимости вникать в детали, лучше мы сфокусируемся на некоторых общих методах работы с этими структурами данных.

Обратите внимание, что вопросы, относящиеся к массивам и к строкам, одинаковы. Таким образом, любой вопрос о массиве можно рассматривать как вопрос о строке и наоборот.

Хэш-таблицы

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

Такая реализация, скорее всего, не будет работать правильно – значение ключа должно быть уникальным, иначе мы можем случайно перезаписать данные. В результате полученный массив окажется громадным: его размер должен превышать суммарный размер всех ключей, только так можно избежать «коллизий».

Вместо огромного массива, заполняемого индексируемыми объектами hash(key), мы можем создать массив меньшего размера и хранить объекты в связном списке по индексу hash(key) % array_length. Чтобы получить объект с определенный ключом, нам придется произвести поиск по связному списку.

Существует и другой способ реализовать хэш-таблицу – бинарное дерево поиска. В этом случае можно обеспечить время поиска O(log N), если дерево будет сбалансированным. Кроме того данный подход позволит использовать гораздо меньше пространства (памяти), поскольку нет необходимости сразу создавать огромный массив.

Попрактикуйтесь в реализации хэш-таблиц перед собеседованием. Это одна из наиболее любимых интервьюерами структур данных.

Вот простейший пример работы с хэш-таблицей на языке Java:

1 public HashMap<Integer, Student> buildMap(Student[] students) {

2 HashMap<Integer, Student> map = new HashMap<Integer, Student>();

3 for (Student s: students) map.put(s.getId(), s);

4 return map;

5 }

Обратите внимание, что хэш-таблицы не всегда являются идеальным решением. Использовать их или нет, решать вам – все зависит от поставленной задачи.

ArrayList (динамический массив)

ArrayList – это массив, размер которого может изменяться во время выполнения программы; он обеспечивает время доступа O(1). Типичная реализация – при заполнении массива его размеры увеличиваются в два раза. Каждое удвоение занимает O(n) времени, но поскольку данное событие происходит довольно редко, считается, что время доступа к массиву остается O(1).

1 public ArrayList<String> merge(String[] words, String[] more) {

2 ArrayList<String> sentence = new ArrayList<String>();

3 for (String w: words) sentence.add(w);

4 for (String w: more) sentence.add(w);

5 return sentence;

6 }

StringBuffer (буфер строк)

Представьте, что вам нужно объединить несколько строк. Каким будет время выполнения программы? Рассмотрим n строк одинаковой длины (x).

1 public String joinWords(String[] words) {

2 String sentence = " ";

3 for (String w: words) {

4 sentence = sentence + w;

5 }

6 return sentence;

7 }

При каждой конкатенации создается новая копия строки, куда копируются посимвольно две строки. При первой итерации будет скопировано x символов. Вторая итерация скопирует 2x символов, третья – 3x. В итоге время выполнения можно оценить как O(x + 2x + … + nx) = O(xn²).

StringBuffer поможет вам избавиться от этой проблемы. Мы просто создаем массив всех строк и копируем их в строку только в случае необходимости.

1 public String joinWords(String[] words) {

2 StringBuffer sentence = new StringBuffer();

3 for (String w: words) {

4 sentence.append(w);

5 }

6 return sentence.toString();

7 }

Отличным упражнением станет создание собственной версии StringBuffer с использованием строк, массивов и общих структур данных.

Вопросы интервью

1.1. Реализуйте алгоритм, определяющий, все ли символы в строке встречаются один раз. При выполнении этого задания нельзя использовать дополнительные структуры данных.

1.2. Реализуйте функцию void reverse(char* str) на C или C++. Функция должна циклически сдвигать строку, заканчивающуюся символом null.

1.3. Для двух строк напишите метод, определяющий, является ли одна строка перестановкой другой.

1.4. Напишите метод, заменяющий все пробелы в строке символами '%20'. Можно предположить, что длина строки позволяет сохранить дополнительные символы и «истинная» длина строки известна. (Примечание: при реализации метода на Java используйте символьный массив.)

Пример:

Ввод: "Mr John Smith "

Вывод: "Mr%20John%20Smith"

1.5. Реализуйте метод, осуществляющий сжатие строки, на основе счетчика повторяющихся символов. Например, строка aabcccccaaa должна превратиться в a2b1c5a3. Если «сжатая» строка оказывается длиннее исходной, метод должен вернуть исходную строку.

1.6. Дано: изображение в виде матрицы размером N × N, где каждый пиксель занимает 4 байта. Напишите метод, поворачивающий изображение на 90°.

1.7. Напишите алгоритм, реализующий следующее условие: если элемент матрицы в точке M × N равен 0, то весь столбец и вся строка обнуляются.

1.8. Допустим, что существует метод isSubstring, проверяющий, является ли одно слово подстрокой другого. Для двух строк, s1 и s2, напишите код проверки, получена ли строка s2 циклическим сдвигом s1, используя только один вызов метода isSubstring (пример: слово waterbottleполучено циклическим сдвигом erbottlewat).

Дополнительные вопросы: манипуляция с битами (5.7), объектно-ориентированное проектирование (7.10), рекурсия (8.3), сортировка и поиск (9.6), C++ (13.10), модерирование (17.7, 17.8, 17.14).