Решение алгоритмических задач программирования на доске или в веб-редакторе - стандартный этап прохождения интервью во всех крупных западных и некоторых российских компаниях. О том, как научиться решать задачи, написано много книг. Например, в самой популярной из них "Cracking the Coding Interview" вы найдете много полезных советов, а веб-ресурсы, такие как Leetcode, дадут возможность потренироваться в решении и обсуждении их. Поэтому в данной статье я не буду давать рекомендации об этом, а хочу поговорить о том, какое практическое значение имеет язык программирования при прохождении интервью. Многие компании дают на выбор несколько языков, а некоторые говорят "решайте на любом, главное - грамотно".
О пользе алгоритмических интервью ходят споры. Есть те, кто их не любит и считает неэффективными. С этим можно соглашаться или нет, но оставим дискуссии за рамками. Я не могу повлиять на систему проведения интервью, но могу помочь справиться с ними.
Обо мне
Сейчас я работаю в одной из компаний МААНГ. В процессе трудоустройства я прошел не один раунд, несколько итераций, успел побывать в разных компаниях и мог сравнить это на своем опыте. Мой профиль на Leetcode не самый завораживающий, но его хватило при условии, что я не решал алгоритмические задачки до этого совсем.
Почему мой любимый / основной язык не всегда самый лучший?
При выборе языка большинство скажет: "Конечно же, мой любимый язык Ч" или "Тот, который я знаю лучше всего". Это имеет смысл: интервью - это стресс, и хочется полагаться на наиболее знакомый и проверенный инструмент. Однако, как и любой инструмент, он может лучше подходить для одних задач и хуже для других. В целом, я бы свел критерий, когда стоит менять язык под задачу, к следующему алгоритму:
Приведу пример из личного опыта. Я люблю Golang и несколько лет назад, когда я только начинал решать задачи, я решил использовать его. Однако, во всех задачах, где требовалось реализовать очередь, стек или вычислить min/max, мне приходилось писать свою реализацию. Да, это не сложно, но требует фокуса и немного времени. В итоге, я даже собрал свой GitHub репозиторий (только для любопытных), но получалось не складно. Поэтому спустя некоторое время я решил подобрать язык, который бы вызывал у меня минимум проблем при достижении цели. Все же решение алгоритмических задач сильно отличается от продуктовой разработки. Вам не требуется многопоточность и вся мощь ООП, достаточно читабельного, понятного кода, который будет работать с хорошей алгоритмической сложностью.
Критерии выбора
Давайте разберем по порядку, что означает критерий "решение алгоритмических задач на интервью".
Алгоритмическое интервью это:
Интервью где вам за короткое время необходимо решить алгоритмическую задачу.
Время на решение задачи варьируется от 15 до 30 минут, в зависимости от компании и сложности.
В ходе решения вам необходимо выяснить все исходные данные, частные случаи и условия (часто задача дана просто заголовком), придумать решение, написать его, протестировать и внести исправления.
Интервью обычно проходит с живым человеком, с которым необходимо активно общаться: получать те самые данные, объяснять свои действия и рассказывать пошагово, как работает программа. Наилучшей практикой считается возможность писать и говорить одновременно, но можно и последовательно.
Использование продвинутых итераторов считается не самой лучшей практикой (list comprehension, LINQ, лямбды и т.д.), читать и разбирать такой код сложнее. Почти в любом языке есть возможность написать программу в 1 строчку. Разобрать это сможет только эксперт этого языка, ваш интервьюер может таковым не быть.
Если интервью проходит онлайн, писать предстоит в веб-редакторе (с подсветкой синтаксиса, но без подсказок), а если лично, то зачастую на доске.
Код не всегда просят компилировать, часто необходимо доказать интервьюеру, что решение будет работать.
Алгоритмическая задача это:
Задача в которой необходимо обработать входную информацию и дать ответ (т.е. реализовать функцию)
Знания, для имплементации грубо сводятся к стандартным знаниям программирования, регулярно требуется применение структур данных из стандартных библиотек. Т.е. использование очередей, стеков, связных списков это нормальная практика.
Иногда требуется реализовать класс с набором определенных функций или использовать вспомогательный класс. Тогда подразумевается использование ООП и без него крайне трудно обойтись. Несмотря на абстрагированность от языка, ряд задач имеют ООП бэкграунд.
Использование сложных задач, написание именных алгоритмов, dynamic programming встречается крайне редко и вас скорее всего заранее предупредят, если таковое может быть.
Допускается, что если код не требует компиляции и какой-то структуры данных нет в стандартной библиотеке, то ее можно просто озвучить, как будто она есть и не писать. Тут есть "но" и "если", поэтому спокойнее, если она все же есть.
Итого, мы имеем мало времени и кучу стресса, поэтому все вышеописанное в отношении выбора можно свести к:
Минимизация времени написания кода (т.е. меньше символов и лаконичнее синтаксис).
Легко читаемый код, не сокращенный с помощью сложных итераторов.
Наличие стандартных контейнеров и поддержка ООП должны быть.
Сравнение на задаче
Давайте сравним решение одной и той же задачи, реализованное на разных языках. В качестве примера возьмем популярную задачу “Валидация скобочной последовательности” (Valid parentheses):
Дана строка, которая состоит из круглых, фигурных и квадратных скобок. Нужно определить, является ли скобочная последовательность верной. Строка является верной, если:
1) Открытая скобка закрыта скобкой такого же типа.
2) Все скобки закрыты в верном порядке.Допущения:
1) В строке встречаются только следующие скобки: '()[]{}'.
2) Строка вмещается в память
С++
class Solution {
public:
bool isValid(string s) {
stack<char> st;
unordered_map<char, char> brackets = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (st.empty() || brackets[c] != st.top()) {
return false;
}
st.pop();
}
}
return st.empty();
}
};Java
public class BracketValidator {
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
HashMap<Character, Character> brackets = new HashMap<>();
brackets.put(')', '(');
brackets.put(']', '[');
brackets.put('}', '{');
for (char c : s.toCharArray()) {
if (brackets.containsValue(c)) {
stack.push(c);
} else if (brackets.containsKey(c)) {
if (stack.empty() || brackets.get(c) != stack.pop()) {
return false;
}
}
}
return stack.empty();
}
}C#
public class Solution {
public bool IsValid(string s) {
var stack = new Stack<char>();
var brackets = new Dictionary<char, char>()
{
{')', '('},
{']', '['},
{'}', '{'}
};
foreach (char c in s)
{
if (brackets.ContainsValue(c))
{
stack.Push(c);
}
else if (brackets.ContainsKey(c))
{
if (stack.Count == 0 || brackets[c] != stack.Pop())
{
return false;
}
}
}
return stack.Count == 0;
}
}
Python
class Solution:
def isValid(self, s: str) -> bool:
stack = []
brackets = {
')': '(',
']': '[',
'}': '{'
}
for char in s:
if char in '([{':
stack.append(char)
elif char in ')]}':
if len(stack) == 0 or brackets[char] != stack.pop():
return False
return len(stack) == 0
JavaScript
var isValid = function(s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (s[idx] == '{') {
stack.push('}');
} else if (s[idx] == '[') {
stack.push(']');
} else if (s[idx] == '(') {
stack.push(')');
}
else if (stack.pop() !== s[idx]) {
return false;
}
}
return !stack.length;
};
Go
func isValid(s string) bool {
var stack []rune
push := func(r rune) {
stack = append(stack, r)
}
pop := func() rune{
r := stack[len(stack)-1]
stack = stack[:len(stack)-1]
return r
}
length := func() int{
return len(stack)
}
for _, c := range s {
switch c {
case '(':
push(')')
case '{':
push('}')
case '[':
push(']')
default:
if length() == 0 && c != 0 || length() > 0 && c != pop() {
return false
}
}
}
return length() == 0
}
C++: ведет себя довольно лаконично, имеет богатейшую коллекцию стандартных контейнеров, что требует дополнительных навыков для грамотного их применения. 286 символов.
Java: имеет тяжелый синтаксис инициализации и длинные названия встроенных функций. 406 символов.
С#: так же длинные названия встроенных функций и требует много места, поскольку принято переносить открывающую скобку на новую строку. 321 символ.
Python: наиболее лаконичен, даже при наличии типизации функции, краткая и довольно понятная нотация, множество встроенных функций. 219 символов.
JavaScript: версия решения несколько отличается, но она все равно краткая, есть все функции, хотелось бы иметь хотя бы типизированную сигнатуру функции. 240 символов.
Go: в языке приняты краткие названия переменных, что сильно экономит время когда их надо полностью печатать, нотация также короткая, но реализация стека портит картину. 393 символов со стеком или 231 символов если считать что стек реализован.
Разбор одной задачи не является статистикой, поэтому вы можете продолжить сравнение. Я же старался подобрать такую задачу, которая могла бы выступить собирательным образом и отразить спектр нюансов, которые вносит язык.
По всем критериям победителем для меня стал Python. Я никогда не был его фанатом, поскольку для решения рабочих задач предпочитаю типизированные языки с хорошей многопоточностью, но в ситуации, когда задачу нужно решать на время, минимизировать ошибки и ментальную нагрузку, Python’у равных я не нашел.
Если же количество языков, из которых вы можете выбирать, ограничено, всегда можно выбрать наиболее лаконичный из доступных, чтобы сэкономить драгоценное время на наборе кода и использовать его для анализа задачи и проверки решения. В этом отношении, например, Java или C# часто проигрывают из-за громоздкого синтаксиса.
Заключение
Есть ситуации, когда имеет смысл сменить свой привычный язык на тот, который позволит решать вам задачи быстрее и освоить его до уровня интервью может оказаться проще чем вы думаете. Для качественной подготовки вам все равно предстоит решить как минимум 50-100 задач, за это время язык вполне можно освоить.
Не бойтесь выйти из зоны комфорта и попробовать другие варианты. В конце концов, любой язык — это инструмент и выбирать его стоит в соответствии с поставленной целью, а научиться решать алгоритмические задачи может каждый.