LeetCode

Материал из Кафедра Прикладной Математики
Версия от 20:29, 19 января 2020; Sirius (обсуждение | вклад) (Новая страница: «При устройстве на работу вам будут выдавать тестовое задание, а при очном собеседовании...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску

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


Сайт leedcode.com

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

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

Задача Two Sum


Литкод принимает решения на основных используемых в коммерческой разработке языках. Мы будем ждать решения только на С++ и 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%), но его рассмотрение выходит за тему данного семинара: [1](https://leetcode.com/problems/two-sum/discuss/256370/C%2B%2B-8ms-99.96(Runtime)-98.23(Memory)-with-comments) Он основан на комбинации быстрой сортировки и метода двух указателей.