Pull to refresh

Скромное руководство по прохождению интервью: часть 1

Reading time 5 min
Views 29K
Пост подготовлен с целью помочь программистам при подготовке к собеседованиям по программированию. Здесь рассматриваются все основные темы, которые, как минимум, желательно знать перед собеседованием. Использован собственный опыт, опыт и рассказы коллег, специализированная литература.
Некоторые рассмотренные здесь темы могут вообще не пригодиться некоторым программистам, а могут и быть обязательными, решать вам. Мой совет – старайтесь как можно больше изучать темы/разделы/аспекты указанные здесь.
И так, в качестве обязательных знаний:
  • Структуры данных
  • Алгоритмы и «концепции»
  • Язык программирования

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

Структуры данных
  • Массивы и строки
  • Связанные списки
  • Стек и очередь
  • Деревья и графы
Алгоритмы и «концепции»
  • Сортировка и поиск
  • Рекурсия
  • Манипуляция битами
  • Объектно-ориентированное проектирование
Язык программирования
  • Базовые составляющие
  • «Домашние» реализованные проекты
  • Как можно больше
А теперь по полочкам, что, как и почему?

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

Массивы и строки

Вопросы, дающие общее представление о «ситуации»:
«Реализуйте функцию определяющую все ли символы неповторяющиеся в заданной строке».
Для простоты представим, что имеется ASCII набор символов (если нет, нужно будет изменить размер «контейнера», логика по-любому не изменится).

bool are_unique_characters(const std::string& str)
{
	std::vector<bool> char_set(256, false);
	for (int i = 0; i < str.size(); ++i) {
		int val = str.at(i);
		if (char_set[val]) {
			return false;
		}
		char_set[val] = true;
	}
	return true;
}


Сложность в этом случае равна O(n), где n — длина входной строки. Это очень важно, чтобы вы во время интервью упомянули о сложности и смогли реально/правильно вычислять сложность некоторого алгоритма.
Если допустить, что строка состоит только из символов от «a» до «z» (из строчных букв), то следующий код будет более хорошим решением, поскольку можно обойтись без вектора.

bool are_unique_characters(const std::string& str)
{
	int checker = 0;
	for (int i = 0; i < str.size(); ++i) {
		int val = str.at(i) - 'a';
		if ((checker & (1 << val)) > 0) {
			return false;
		}
		checker |= (1 << val);
	}
	return true;
}

Для размышления — классическая задача: «Переверните C-строку (имеется в виду, что “abcd” – это пять символов, пятый – завершающий нуль-символ ‘\0’)».
Сравните ваше решение с этим и ответьте на вопрос, почему ваш код лучше?

void reverse_c_string(char* str)
{
	char* end = str;
	char tmp;
	if (str) {
		while (*end) {
			++end;
		}
		--end;
		while (str < end) {
			tmp = *str;
			*str++ = *end;
			*end-- = tmp;
		}
	}
}


В качестве домашнего задания, попробуйте решить эту задачку: «Дано изображение в виде массива NxN, где каждый элемент – один пиксел и каждый пиксел весит в 4 байта. Напишите функцию, которая перевернет изображение на 90 градусов».

Связанные списки

Вопросы по связанным спискам, мягко говоря, достаточно общие. Вопрос может быть от простого «удалить узел из связанного списка» до более мыслительно-напрягающих. Помните, когда вас спросят про связанные списки, уточните -о каком именно списке идет речь — односвязном или двухсвязном. Вы должны знать, опять таки, обязательно, как создать список и как удалить узел из односвязного списка.

Примеры задач:
"Напишите код удаляющий повторяющиеся элементы из несортированного связанного списка".
Имея
struct list_node
{
	int data;
	list_node* next;
};

Решение будет таким (а ваше?):
void delete_duplicates(list_node* head)
{
	if (NULL == head) { return; }
	list_node* previous = head;
	list_node* current = previous->next;
	while (NULL != current) {
		list_node* runner = head;
		while (runner != current) {
			if (runner->data == current->data) {
				list_node* tmp = current->next;
				previous->next = tmp;
				current = tmp;
				break;
			}
			runner = runner->next;
		}
		if (runner == current) {
			previous = current;
			current = current->next;
		}

	}
}


"Реализуйте алгоритм, который удаляет узел из середины односвязного списка, есть доступ только к этому узлу".
Решение простое, но важно понять, что задача не решима, если удаляемый узел является последним узлом списка и ваш интервьюер желает услышать это.

bool delete_node(list_node* nd) 
{
	if (NULL == nd || NULL == nd->next) {
		return false; // whatta..?
	}
	list_node* nxt = nd->next;
	nd->data = nxt->data;
	nd->next = nxt->next;
	return true;
}

Вопросы для размышления, ака домашнее задание:
"У вас есть два числа представленные в виде связанного списка, где каждый узел содержит одну цифру. Числа хранятся в обратном порядке. Напишите функцию, которая вычилсяет сумму этих чисел и возвращает в виде связанного списка.
Пример: для чисел 295 и 513 в сумме получим 808.
Вход: (5 -> 9 -> 2), (3 -> 1 -> 5)
Выход: (8 -> 0 -> 8)
".

"Найдите середину связанного списка".

Стек и очередь

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

"Напишите класс my_queue, который реализует очередь используя два стека".
"Ниже представлено решение предыдущей задачи, что не так в этом коде?"

template <typename T>
class my_queue
{
private:
	std::stack<T> m_stack1;
	std::stack<T> m_stack2;

	int size() const {
		return m_stack1.size() + m_stack2.size();
	}

	void add(const T& value) {
		m_stack1.push(value);
	}

	T peek() {
		if (!m_stack2.empty()) {
			return m_stack2.top();
		}
		while (!m_stack1.empty()) {
			m_stack2.push(m_stack1.top());
			m_stack1.pop();
		}
		return m_stack2.top();
	}

	T remove() {
		if (!m_stack2.empty()) {
			T tmp = m_stack2.top();
			m_stack2.pop();
			return tmp;
		}
		while (!m_stack1.empty()) {
			m_stack2.push(m_stack1.top());
			m_stack1.pop();
		}
		return m_stack2.top();
	}
};

Для размышления:
"Напишите программу, которая сортирует стек в восходящем порядке".

Деревья и графы

Вопросы по деревьям и графам в основном «бывают» в следующих формах:
  • Реализуйте дерево / найдите узел / удалите узел / другие немаловажные алгоритмы
  • Реализуйте модифицированный вариант известного алгоритма
Строго рекомендуется хорошенько подготовиться по деревьям и графам перед собеседованием и помните — «не все бинарные деревья — бинарные деревья поиска».
Вы должны уметь с легкостью реализовать следующие алгоритмы:
  • Прямой обход дерева (pre-order)
  • Симметричный обход (in-order)
  • Обратный обход (post-order)
  • Вставка узла
Графовые обязательные знания:
  • Поиск в глубину (Depth First Search)
  • Поиск в ширину (Breadth First Search)
"Дан сортированный (в восходящем порядке) массив, напишите алгоритм создающий бинарное дерево минимальной высоты".
Алгоритм:
  1. Вставить в дерево средний элемент массива
  2. Вставить (в левое поддерево) элементы «левого подмассива»
  3. Вставить (в правое поддерево) элементы «правого подмассива»
  4. И так рекурсивно
tree_node* add_to_tree(int arr[], int start, int end) 
{
	if (end < start) {
		return NULL;
	}
	int mid = (start + end) / 2;
	tree_node* n = new tree_node(arr[mid]);
	n->left = add_to_tree(arr, start, mid - 1);
	n->right = add_to_tree(arr, mid + 1, end);
	return n;
}

tree_node* create_min_BST(int arr[]) 
{
	//... SIZE размер массива
	//... arr сам массив
	return add_to_tree(arr, 0, SIZE - 1);
}

Для размышлений:
"Реализуйте не рекурсивный симметричный обход дерева".

UPD: Как заметил Shedal, это руководство, (в основном), — для студентов / джуниоров.

UPD 2: Часть вторая.
Tags:
Hubs:
+94
Comments 125
Comments Comments 125

Articles