Во второй части поста будут рассматриваться “Алгоритмы и концепции”, если вы не читали предыдущий пост или хотите “вспомнить” список тем, то загляните сюда.
Понимание/знание известных алгоритмов сортировки очень важно, поскольку многие решения связанные с сортировкой или поиском, мягко говоря, требуют владения этими алгоритмами. Хороший способ показать свои знания перед интервьюером, когда дана здача на сортировку – это «пробежать» по известным алгоритмам и увидеть/выяснить какой из них лучше всего подходит для решения данной задачи. Вы получите и решение и то, что интервьюер будет довольным вашими «разными» способов решения одной и той же задачи.
Например, "у вас есть большой массив обьектов Employee, сортируйте служащих по возрастам".
Здесь нужно обратить внимание, как минимум, на две вещи. Во-первых, массив большой, значит эффективность прежде всего, а во-вторых сортировка базируется на возрастах, то есть нам уже ясно, что значения находятся в маленьком интервале. Можно спокойно использовать алгоритм блочной сортировки.
Какие алгоритмы следует знать (какие же эти «известные»):
«У вас два сортированных массива A и B, размер А больше настолько, чтобы содержать массив B. Напишите метод, слияющий B в А сохраняя порядок сортировки».
С поиском вы оказываетесь в более «выгодном» положении, достаточно знать линейный и бинарный алгоритмы и дело, так сказать, в шляпе.
«Дан массив, в котором каждая строка и каждый столбец сортированы, напишите функцию находящую элемент в массиве».
Взгляните на решение ниже и предложите лучшее решение:
Заметьте, что здесь не очень-то имеет значение, что код в посте приведен на С++, в большинстве случаев тот же код без особых изменений синтаксически эквивалентен, например, коду на Java или C#.
Задачи для размышления:
«Реализуйте алгоритм бинарного поиска».
«Как организовать сортировку миллиона чисел с плавающей точкой?».
«Реализуйте сортировку массива из обьектов Employee по зарплатам (будем считать, что Employee содержит поля для имени, возраста, зарплаты и адреса)».
Есть огромное множество задач с рекурсией, многие задачи подчиняются шаблону. Если задачу можно разбить на подзадачи, то это уже подсказка, что задача «рекурсивная». Если вы услышите задачи, вроде «Напишите код, выводящий первые n…», «Реализуйте функцию считающую все...», то сперва попытайтесь использовать, ну хотя бы подумать использовать, рекурсивный метод решения.
Нужно заметить, что во всех случаях практика – ваш лучший друг, как много задач вы решите, тем легче для вас становится не только решение новой, но и ориентировка на метод решения, собственно, задачи.
И так, сначала попытайтесь распознать подзадачи. Решите/найдите «базовую» задачу, ту, при которой рекурсия остановится (в основном это жестко кодированное значение). Решите задачу для 2-й подзадачи и поймите как решить третью подзадачу, базируясь на второй. Обобщайте решение для n-й подзадачи.
Помните, любая задача, решаемая с помощью рекурсии, имеет и итеративное решение. И еще, рекурсивный алгоритм может быть очень неэффективным в смысле свободного места.
«Напишите функцию, генерирующую n-ое число Фибоначчи».
Рекурсивный вариант:
Итеративный вариант:
Для размышления:
"Как бы вы улучшили решение задачи выше?"
«Напишите функцию, которая возвращает все подмножества некоторого множества».
«Решите задачу ферзя»
Манипуляция битами может быть страшной для многих кандидатов, хотя не должна.
Достаточно просто делать ошибку при решении этих задач, так что будьте осторожны, вернее – внимательны. Рассматривайте внимательно каждую строку написанную вами кода.
Не забудьте про сдвиг, x << y (левый сдвиг) означает, что x сдвиган налево на y бит и x >> y (правый сдвиг), соответственно, у бит в правую сторону.
Есть одна достаточно популярная задача, попробуйте решить ее сами (привожу с «обратной стороны») – «Объясните следующий код: (( n & (n — 1) ) == 0)».
«Даны два 32-битовые числа, N и M. Еще есть две позиции битов, i и j. Напишите функцию, которая установит все биты между i и j в N равную M(то есть M становится подстрокой N)
Пример:
Вход: N = 100000000, M = 101, i = 2, j = 3
Выход: N = 100010100».
Для размышлении: «Дано число с плавающей точкой в виде строки, выведите бинарное представление.»
Вопросы по ООП (здесь П — проектирование) имеют огромную важность, по крайней мере я так думаю. Знание ООП оказывает некоторое доверие на интервьюера, поскольку становиться понятным, что кандидат «поймет» диаграммы классов того проекта, на котором будет работать. Это только маленький плюс, есть другие немаловажные достоинства ООП, выступающие в пользу кандидата. А вот отсутствие знании вызовет у интервьюера чувство «кто там следующий?». Это, конечно, относится к должностям, связанным с ООП, а то, по-мне разработчику драйверов вряд-ли спросят об ООП. Тем не менее, во время интервью будьте готовы, что вас попросят спроектировать некоторое приложение, или даже «не-приложение», например, телевизор. Попросят рассказать об отношениях между, скажем, пультом и телевизором. Будьте готовы на вопросы типа «Чем отличается “is-a” от “has-a”?».
«Спроектируйте чат-сервер».
Это простой пример, в реальности вопросы/задачи бывают «неплохого качества».
Для размышлении: «Спроектируйте структуры данных для онлайн-читалки книг».
Думаю этого достаточно, в следующих постах есть намерение написать не только о языке программирования, но и о других темах/вопросах, которые будут относится к более сложным интервью.
Алгоритмы и концепции
Сортировка и поиск
Понимание/знание известных алгоритмов сортировки очень важно, поскольку многие решения связанные с сортировкой или поиском, мягко говоря, требуют владения этими алгоритмами. Хороший способ показать свои знания перед интервьюером, когда дана здача на сортировку – это «пробежать» по известным алгоритмам и увидеть/выяснить какой из них лучше всего подходит для решения данной задачи. Вы получите и решение и то, что интервьюер будет довольным вашими «разными» способов решения одной и той же задачи.
Например, "у вас есть большой массив обьектов Employee, сортируйте служащих по возрастам".
Здесь нужно обратить внимание, как минимум, на две вещи. Во-первых, массив большой, значит эффективность прежде всего, а во-вторых сортировка базируется на возрастах, то есть нам уже ясно, что значения находятся в маленьком интервале. Можно спокойно использовать алгоритм блочной сортировки.
Какие алгоритмы следует знать (какие же эти «известные»):
- Пузырьковая сортировка (bubble sort).
- Сортировка выбором (selection sort).
- Сортировка слиянием (merge sort).
- Быстрая сортировка (quick sort).
- Блочная сортировка (bucket sort).
«У вас два сортированных массива A и B, размер А больше настолько, чтобы содержать массив B. Напишите метод, слияющий B в А сохраняя порядок сортировки».
void merge(int a[], int b[], int n, int m)
{
int k = m + n - 1;
int i = n - 1;
int j = m - 1;
while (i >= 0 && j >= 0) {
if (a[i] > b[j]) {
a[k--] = a[i--];
} else {
a[k--] = b[j--];
}
}
while (j >= 0) {
a[k--] = b[j--];
}
}
С поиском вы оказываетесь в более «выгодном» положении, достаточно знать линейный и бинарный алгоритмы и дело, так сказать, в шляпе.
«Дан массив, в котором каждая строка и каждый столбец сортированы, напишите функцию находящую элемент в массиве».
Взгляните на решение ниже и предложите лучшее решение:
bool find_element(int** mat, int elem, int M, int N)
{
int row = 0;
int col = N - 1;
while (row < M && col >= 0) {
if (mat[row][col] == elem) {
return true;
} else if (mat[row][col] > elem) {
--col;
} else {
++row;
}
}
return false;
}
Заметьте, что здесь не очень-то имеет значение, что код в посте приведен на С++, в большинстве случаев тот же код без особых изменений синтаксически эквивалентен, например, коду на Java или C#.
Задачи для размышления:
«Реализуйте алгоритм бинарного поиска».
«Как организовать сортировку миллиона чисел с плавающей точкой?».
«Реализуйте сортировку массива из обьектов Employee по зарплатам (будем считать, что Employee содержит поля для имени, возраста, зарплаты и адреса)».
Рекурсия
Есть огромное множество задач с рекурсией, многие задачи подчиняются шаблону. Если задачу можно разбить на подзадачи, то это уже подсказка, что задача «рекурсивная». Если вы услышите задачи, вроде «Напишите код, выводящий первые n…», «Реализуйте функцию считающую все...», то сперва попытайтесь использовать, ну хотя бы подумать использовать, рекурсивный метод решения.
Нужно заметить, что во всех случаях практика – ваш лучший друг, как много задач вы решите, тем легче для вас становится не только решение новой, но и ориентировка на метод решения, собственно, задачи.
И так, сначала попытайтесь распознать подзадачи. Решите/найдите «базовую» задачу, ту, при которой рекурсия остановится (в основном это жестко кодированное значение). Решите задачу для 2-й подзадачи и поймите как решить третью подзадачу, базируясь на второй. Обобщайте решение для n-й подзадачи.
Помните, любая задача, решаемая с помощью рекурсии, имеет и итеративное решение. И еще, рекурсивный алгоритм может быть очень неэффективным в смысле свободного места.
«Напишите функцию, генерирующую n-ое число Фибоначчи».
Рекурсивный вариант:
int fibonacci(int n)
{
if (0 == n) {
return 0;
}
if (1 == n) {
return 1;
}
// или более красиво if(0 == n || 1 == n) { return n; }
if (n > 1) {
return fibonacci(n - 1) + fibonacci(n - 2);
}
return -1; // в случае ошибки
}
Итеративный вариант:
int fibonacci(int n)
{
if (n < 0) { return -1; }
if (n == 0) { return 0; }
int a = 1, b = 1;
for (int i = 3; i <= n; ++i) {
int c = a + b;
a = b;
b = c;
}
return b;
}
Для размышления:
"Как бы вы улучшили решение задачи выше?"
«Напишите функцию, которая возвращает все подмножества некоторого множества».
«Решите задачу ферзя»
Манипуляция битами
Манипуляция битами может быть страшной для многих кандидатов, хотя не должна.
Достаточно просто делать ошибку при решении этих задач, так что будьте осторожны, вернее – внимательны. Рассматривайте внимательно каждую строку написанную вами кода.
Не забудьте про сдвиг, x << y (левый сдвиг) означает, что x сдвиган налево на y бит и x >> y (правый сдвиг), соответственно, у бит в правую сторону.
Есть одна достаточно популярная задача, попробуйте решить ее сами (привожу с «обратной стороны») – «Объясните следующий код: (( n & (n — 1) ) == 0)».
«Даны два 32-битовые числа, N и M. Еще есть две позиции битов, i и j. Напишите функцию, которая установит все биты между i и j в N равную M(то есть M становится подстрокой N)
Пример:
Вход: N = 100000000, M = 101, i = 2, j = 3
Выход: N = 100010100».
int update_bits(int n, int m, int i, int j)
{
int max = ~0; // все 1'ы
//все 1'ы до позиции j, потом 0'и
int left = max - ((1 << j) - 1);
//1'ы после позиции i
int right = ((1 << i) - 1);
// 1'ы с нулями между i и j
int mask = left | right;
//"чистка" от i до j и вставка m
return (n & mask) | (m << i);
}
Для размышлении: «Дано число с плавающей точкой в виде строки, выведите бинарное представление.»
Обьектно-ориентированное проектирование
Вопросы по ООП (здесь П — проектирование) имеют огромную важность, по крайней мере я так думаю. Знание ООП оказывает некоторое доверие на интервьюера, поскольку становиться понятным, что кандидат «поймет» диаграммы классов того проекта, на котором будет работать. Это только маленький плюс, есть другие немаловажные достоинства ООП, выступающие в пользу кандидата. А вот отсутствие знании вызовет у интервьюера чувство «кто там следующий?». Это, конечно, относится к должностям, связанным с ООП, а то, по-мне разработчику драйверов вряд-ли спросят об ООП. Тем не менее, во время интервью будьте готовы, что вас попросят спроектировать некоторое приложение, или даже «не-приложение», например, телевизор. Попросят рассказать об отношениях между, скажем, пультом и телевизором. Будьте готовы на вопросы типа «Чем отличается “is-a” от “has-a”?».
«Спроектируйте чат-сервер».
enum status_type
{
online,
offline,
away
};
struct status
{
status_type m_status_type;
std::string m_status_message;
};
struct add_request;
class user
{
private:
std::string m_username;
std::string m_display_name;
std::list<user*> m_contact_list;
std::list<add_request*> requests;
public:
bool update_status(status_type stype, const std::string& msg);
bool add_user_with_username(const std::string& name);
bool approve_request(const std::string& username);
bool deny_request(const std::string& username);
bool remove_contact(const std::string& username);
bool send_message(const std::string& username, const std::string& message);
};
struct add_request
{
user* m_from_user;
user* m_to_user;
};
class server
{
user* get_user_by_username(const std::string& username);
};
Это простой пример, в реальности вопросы/задачи бывают «неплохого качества».
Для размышлении: «Спроектируйте структуры данных для онлайн-читалки книг».
Думаю этого достаточно, в следующих постах есть намерение написать не только о языке программирования, но и о других темах/вопросах, которые будут относится к более сложным интервью.
