Решение алгоритмических задач программирования на доске или в веб-редакторе - стандартный этап прохождения интервью во всех крупных западных и некоторых российских компаниях. О том, как научиться решать задачи, написано много книг. Например, в самой популярной из них "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 задач, за это время язык вполне можно освоить.

Не бойтесь выйти из зоны комфорта и попробовать другие варианты. В конце концов, любой язык  — это инструмент и выбирать его стоит в соответствии с поставленной целью, а научиться решать алгоритмические задачи может каждый.

Комментарии (18)


  1. hedger
    06.06.2023 23:30
    +1

    В Питоне можно даже красивее сделать, if char in brackets.keys() / .values() вместо строковых литералов. Чуть медленнее, но нет дублирования данных.


  1. slavap
    06.06.2023 23:30

    Dart (правда Stack нужно подключить из репозитория, в стандартной библиотеке нет):

    bool isValid(String s) {
      var stack = Stack<String>();
      var brackets = {
        ')': '(',
        ']': '[',
        '}': '{',
      };
    
      for (var i = 0; i < s.length; i++) {
        if (brackets.values.contains(s[i]))
          stack.push(s[i]);
        else if (brackets.keys.contains(s[i])) {
          if (stack.isEmpty || brackets[s[i]] != stack.pop()) return false;
        }
      }
      return stack.isEmpty;
    }


  1. aavezel
    06.06.2023 23:30

    Странно что для питона используется dict а для js используется множественные условия. Хотя и там и там можно писать примерно одинаково (разница в скобках):

    function isValid(s) {     
      let stack = [];
      let brackets = {
        ')': '(',
        ']': '[',
        '}': '{'
      }
    
      for (let char of s) {
        if ('([{'.includes(char)) {
          stack.push(char);
        } else if (')]}'.includes(char)) {
          if (stack.length == 0 || brackets[char] != stack.pop()) {
            return false;
          }
        }
      }
    
      return stack.length == 0;
    }


  1. hlogeon
    06.06.2023 23:30

    Может быть я не понимаю сути алгоритмических интервью, но почему не использовать псевдоязык? Зачем использовать настоящий язык программмирования?


    1. TuzSeRik
      06.06.2023 23:30

      Потому что "уникальных" faang-разработчиков 10-ки тысяч, и ещё сотни стоят за дверью. Проверять их должен уметь максимально дешёвый персонал и соответственно алгоритм проверяется не по смыслу (на что у проверяющего не хватает компетенции), а по набору тестов а-ля LeetCode. Для этого код должен компилироваться и работать


      1. hlogeon
        06.06.2023 23:30

        Мне почему-то казалось, что в алгоритмическом интервью на обратной стороне провода должен быть тоже какой-то разработчик. И в моем понимании любой разработчик способен понять псевдокод. Также мне казалось, что помимо компилируется\не компилируется и проходит ли оно тест-кейсы на таких интервью в основном смотрят на "ход мысли" кандидата.


        1. TuzSeRik
          06.06.2023 23:30
          +1

          Я, честно, прям ручаться не могу, но в фаанг-лайк компаниях, емнип, разработчики сидят уже после алгоритмического собеса


    1. Chhed Автор
      06.06.2023 23:30
      +1

      Спасибо за вопрос. Есть 2 вида:
      - С автоматизированной системой: это обычно скрининг или скорее пре-скрининг
      - С человеком: полное интервью или так же скрининг, зависит от компании

      При интервью с человеком - это почти наверняка будет разработчик который умеет читать код. Но код должен быть кодом, иначе он не сможет догадаться можете ли вы писать код хотя бы на 1 языке.
      Ход мысли обязателен, но и задача должна быть закончена. Иначе не сходится


      1. hlogeon
        06.06.2023 23:30

        Разве другие этапы интервью не показывают ли владение человека каким-либо языком программирования? Ну типа live coding какой-нибудь, или тестовое задание. Да и вообще странно, человек идет в MAANG и не может показать публичный код, который он написал? Такое бывает? Я не то что в MAANG не работал, я даже в Яндекс и Тинькофф ни разу не собеседоваля, но могу столько кода на своем гитхабе показать - учитаешься.


  1. bad_imagination
    06.06.2023 23:30
    +1

    Раз уж тут конкурс на самое короткое решение, вот еще один плюсовый вариант

    bool isValid(string s) {
        stack<char> q;
        string u = ")(][}{";
        for (char c : s) {
            auto p = u.find(c);
            if (p & 1) {
                q.push(u[p - 1]);
            } else if (q.empty() || q.top() != c) {
                return false;
            } else {
                q.pop();
            }
        }
        return q.empty();
    }


    1. sergiodev
      06.06.2023 23:30

      По-моему тут не хватает проверки на то, является ли p одной из закрывающих скобочек


      1. bad_imagination
        06.06.2023 23:30

        А зачем такая доп проверка? По условиям задачи на leetcode нам гарантируется, что строка состоит только из символом '()[]{}'. Так что достаточно только проверить что скобка открывающаяся, если же провалились ниже в цепочке if то это уже точно закрывающаяся скобка.


  1. Vanirn
    06.06.2023 23:30
    +1

    То есть что бы устроиться на работу по профилю нужно освоить технологию не по профилю?

    К примеру, занимаюсь я .NET и ничего кроме .NET (и порой TS/JS ни нужно), но что бы устроиться на работу, вместо повышения навыков в основной специализации, нужно распыляться на Питон, Го или ещё что-нить далёкое…

    Это только мне данная ситуация кажется кринжовой?
    PS: к автору никаких претензий не имею, а вот ситуация с наймом очень неоднозначная.


    1. VFaland
      06.06.2023 23:30

      Это ситуация с наймом в большие компании, где поток кандидатов в сотни тысяч человек в год, стандартизация итп. К тому же в МААНГах обычно нет такой привязки к языку/стеку, люди осваивают нужные технологии на ходу. А раньше вон вообще всякие Брейн тизеры давали, типа почему люки круглые, так что сейчас ещё нормально. Ну и всегда есть вариант пойти в компании поменьше/попроще, где будет важен именно ваш стек, коммиты в гитхаб итп.


    1. VFaland
      06.06.2023 23:30

      Например - в МААНГах не нужны ".NET разработчики" или "Java разработчики", а скорее бэкенд-девелоперы в целом, которые могут переучиться на то что будет нужно для решения конкретных проблем


      1. Leetc0deMonkey
        06.06.2023 23:30

        Видел я одного такого "могущего". Его посадили на C++ на инфру. Скулил что ничего непонятно в этом С++. Зато выдроченный литкод, да.


      1. Vanirn
        06.06.2023 23:30

        То есть, в мире полно уникомов способных освоить язык и полноценный фреймворк "условно" за испытательный срок? Я очень сомневаюсь, что МААНГ собрал 100000 людей способных на такое быстрое обучение.

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

        Конечно же я не отрицаю возможность переда между Java Spring - C# .NET - Kotlin - Dart, эти языки очень близки. Программисты этим занимаются уже давно и переходят вполне успешно, но достичь тот же уровень сеньорности потребуется явно не пара месяцев обучения.


  1. Stas911
    06.06.2023 23:30

    Ну вообще профиль впечатляющий - интересно, сколько у вас заняло времени 350+ задач прорешать?