Внутренний Я(ндекс)

В этой статье я хочу описать (часть) моего опыта взаимодействия со структурой, именуемой в дальнейшем "яндекс", с точки зрения работника. Опишу собеседования и этап "входа".

Да, уже были статьи про собеседование и даже в эту же структуру, некоторые из них я видел, но не во всём с ними согласен, к тому же конкретно С++ разработчиков я там не видел.

Начало

Это был спокойный осенний вечер, ветер играл с листьями, море начало свой вечерний танец с солнцем. Раздался звук. Это было уведомление телеграмма. Ещё одно. За ним последовал грохот всплывающего уведомления о пришедшем емейле. Это были они. они вышли на меня. HR'ы яндекса. Их условие было простым - приди на собеседование. Что ж, была не была, попробуем, подумал я и мы договорились встретится в Zoom.

Как оказалось позже, ставка была ложной, HR система яндекса не так проста, налицо системный подход к безопасности. Каждый HR автономен и не имеет доступа ко всей информации. Даже если главный центр будет уничтожен, каждый из них будет пытаться воссоздать компанию с нуля. Вдохновлялись явно природой.

Поэтому договориться нужно с каждым и даже когда вы работаете в яндексе они вам всё равно пишут.

Мне были любезно предоставлены подготовительные материалы: ссылка на литкод и время.

В свою очередь я добросовестно не открывал эту ссылку, потому что готовиться к собеседованию это и обман самого себя и компании(мне лень), хотя я отлично понимаю тех, кто пытается эту систему обмануть, если она порочна (собеседование не связано с реальной работой)

Первое собеседование

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

Задача №0

сложность: leetcode easy
Вернуть массив k наиболее часто встречающихся элементов данного массива

Причём в массиве всегда хотя бы k элементов, а k > 0, после уточнения: порядок одинаково частых элементов неважен, дубликаты не убирать

И сходу я написал примерно следующее(сейчас уже точно не упомнить):

std::vector<int> most_freq(std::span<const int> nums, int k) {
  assert(k <= size(nums) && k >= 0);
  std::unordered_map<int, size_t> counts;
  for (int x : nums) ++counts[x];
  std::vector<int> out(k);
  auto to_freq_proj = [&] (int x) { return counts[x]; };
  std::ranges::partial_sort_copy(nums, out, std::greater{}, to_freq_proj);
  return out;
}

Собеседующий был явно ошарашен, но принял решение

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

Задача №1

сложность: leetcode hard

Даны высоты столбиков, посчитать сколько воды могло бы собраться в этих столбиках в дождь (подробнее на литкоде по ссылке https://leetcode.com/problems/trapping-rain-water/)

Немного пришлось подумать конечно, но в итоге я придумал алгоритм за O(N) по времени и O(1) по памяти и написал его, а потом принялся за самое сложное - доказать собеседующему, что решить с такой сложностью возможно. Но собеседующий был приятный и в беседе мы продебажили код и разобрали крайние случаи

Решение у меня сохранилось, так как я прямо после собеседования пошёл и вставил его как было в литкод, чтобы убедится в его правильности

class Solution {
public:
    int trap(vector<int>& vec) {
        if(vec.size() < 2)
          return 0;
        auto max_it = std::max_element(begin(vec), end(vec));
        int max_height = *max_it;
        int max_water = vec.size() * max_height;
        max_water -= std::accumulate(begin(vec), end(vec), 0);
        auto go = [&] (auto it, auto e) {
            int count = 0;
            int cur_max = *it;
            ++it;
            while(it != e) {
                ++count;
                if(*it >= cur_max) {
                    max_water -= count * (max_height - cur_max);
                    cur_max = *it;
                    count = 0;
                }
                ++it;
            }
        };
        go(begin(vec), max_it == end(vec) ? max_it : std::next(max_it));
        go(rbegin(vec),
           max_it == begin(vec) ?
           std::reverse_iterator(max_it) : std::next(std::reverse_iterator(max_it)));
        return max_water;
    }
};

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

Фидбек:

Ну, усложнение это конечно давать хард с литкода на собеседовании, но удивляет тут другое

• давай ещё одну секцию с задачами