Основная тема семинара — подготовка к выполнению практических заданий, плюс немного комбинаторики. Надо объяснить что такое те ресурсы, которые мы будем использовать, как к ним подключиться, что они позволяют делать. Дать базовую справку о том, что там есть и что будет.

Leetcode

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

На литкоде есть большое количество задач, причём не только на алгоритмы, но и на базы данных и прочее.

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

Литкод принимает решения на основных используемых в коммерческой разработке языках. Мы будем ждать решения только на С++ и Python. Давайте рассмотрим одну самую простую задачу, чтобы вам было легче втянуться.

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

Далее идёт наивное решение задачи.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (size_t i = 0; i < nums.size(); i++)
            for (size_t j = i + 1; j < nums.size(); j++) 
                if (nums[i] + nums[j] == target)
                    return {i, j};
        return {0, 0};
        }
};

Решение заходит, но получаем что наше решение быстрее, чем 36% решений. Значит есть 64% тех, кто решил задачу быстрее. Вопрос в том как они смогли это сделать?

Решаем задачу через map.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> all_elems;
        
        for (size_t i = 0; i < nums.size(); i++)
            all_elems[nums[i]] = i;
        
        for (size_t i = 0; i < nums.size(); i++) {
            int cur = target - nums[i];
            if (all_elems.find(cur) != all_elems.end() && i != all_elems[cur])
                return {i, all_elems[cur]};
        }
        return {0, 0};
        }
};

Это решение быстрее чем 67% всех решений. Здесь выглядит некрасиво, что мы добавляем элементы последовательно. Добавлять элементы последовательно — лучший способ замедлиться. Причём мы загоняем весь массив, тогда, когда нам это может быть не нужно. Давайте будем добавлять их только уже после того, как их прошли.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> all_elems;
        
        for (size_t i = 0; i < nums.size(); i++) {
            int cur = target - nums[i];
            if (all_elems.find(cur) != all_elems.end() && i != all_elems[cur])
                return {i, all_elems[cur]};
            else
               all_elems[nums[i]] = i; 
        }
        return {0, 0};
        }
};

Это уже быстрее чем 92% всех решений, что были отправлены и значит что из 100 человек, претендующих на вашу должность, вы обошли уже 92. У первого алгоритма сложность O(n^2), у второго O(n).

Вот здесь можно посмотреть код, который считается одним из самых быстрых (> 98%), но его рассмотрение выходит за тему данного семинара: https://leetcode.com/problems/two-sum/discuss/256370/C%2B%2B-8ms-99.96(Runtime)-98.23(Memory)-with-comments Он основан на комбинации быстрой сортировки и метода двух указателей.