ТГиК-2019-Семинар-02.09.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

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

Leetcode

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


Сайт 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) Он основан на комбинации быстрой сортировки и метода двух указателей.

Про сложность

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#099014c021604d258a73e2f0a3072f29)

Примеры оценки сложности.

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#38e7b42a243a4d28a5f03de2ba658b5d)

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#6951a19d78a7454f85daaa15d5f3b290)

Но суть не в этом, когда вы прорешаете много задач, которые мы вам дадим и которые вы найдёте сами, вы сможете показать своему работодателю такую красивую страничку:

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#81d81b6e178f4f22aac0f910ddb76648)

Coursera

Coursera - образовательная платформа, на которой можно изучать онлайн-курсы (за денежку и нет) от ведущих вузов и организаций в мире. Также можно проходить платные курсы бесплатно, оформив финансовую помощь, и через 2 недели получить доступ ко всем его материалам. После прохождения курса вы получаете сертификат :) Некоторые курсы можно проходить бесплатно без получения сертификата.

Мы предлагаем вам проходить специализацию "Искусство разработки на современном C++", который был создан Яндексом и МФТИ для людей с нулевым знанием программирования, можно научиться кодить на с++ и получить хорошие знания по этому языку. Он разделен на 5 курсов (от самого простого-белого до самого сложного-черного поясов). В свою очередь каждый курс поделен на недели, в которых изучается несколько тем. Есть видеоуроки, тестовые задания с вариантами ответов и, конечно же, задания по программированию, которые проверяются автоматически системой. Курс учит решать задачи, с которыми разработчики сталкиваются каждый день.

Во-первых, нужно зайти на сайт [2](https://www.coursera.org/) и зарегистрироваться.

Во-вторых, заходим на нужную специализацию [3](https://www.coursera.org/specializations/c-plus-plus-modern-development) и оформляем финансовую помощь :)

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#1e8cc2d0af6e4b6d95d981274add0e28)

Далее прокурутим страничку вниз и увидим, что здесь описаны все курсы в специализации. Для примера выберем черный пояс :)

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#41a4440e4cb7459ca3bacaad4ca71de2)

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#7d738df968b54431bc199679767271d5)

Нажимаем на "Доступна финансовая помощь"

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#b5930d30b05444d99823b28b4fecda02)

Перейдем к заявлению :)

Далее нужно будет заполнить заявление и написать немного о себе :)

Письмо о себе нужно будет писать на английском языке. Примеры можете найти в интернете. Я пишу примерно что-то следующее:

  • Hello, my name is Kate.* *I am a student of the MPEI of the 4 course, due to a rather complex program of studies, I practically have no free time to work and earn enough money to pay for this course / specialization. At the same time, the scholarship at MPEI is quite small: 2400, 2700 or 3000 (for excellent students), so it is also impossible to pay for this course for a scholarship. Not to say that I have particularly rich parents, so that they also do not want to charge for this course. In this regard, please provide me with financial support.*
  • These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words.*
  • I firmly decided that I want to become a developer. In my faculty I study different courses in computer science. Unfortunately, I need more practice and information in programming. This course will allow me to gain basic knowledge in this area for further development. In addition, this specialization allows me to find a job after completing all the courses, which interested me even more.*
  • These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words. These words are required to enter 150 words.*

И да, если вы проходите белый, желтый и красный пояса, получаете автомат по нашему предмету :)

- Ещё полезные курсы:

   1. По  комбинаторике: [4](https://www.coursera.org/learn/kombinatorika-dlya-nachinayushchikh)
   2. По теории графов: [5](https://www.coursera.org/learn/teoriya-grafov)
   3. По теории вероятностей: [6](https://www.coursera.org/learn/probability-theory-basics)?
   4. Специализация по машинному обучению и анализу данных: [7](https://www.coursera.org/specializations/machine-learning-data-analysis)?
   5. Тоже по машинному обучению: [8](https://www.coursera.org/learn/vvedenie-mashinnoe-obuchenie)?

Также, если вы хотите слушать классные лекции, можно найти их на сайте ШАДа [9](https://yandexdataschool.ru/edu-process/program/data-scientist

Git и GitHub

Когда-то перед программистами, да и однажды перед всеми вами встал вопрос о том, как удобнее хранить код. Разумеется, многие из вас делали папки project_1, project_1_copy_1, project_1_copy_1_copy_1 и так далее. Но всё это несколько, согласитесь, запутывает и не даёт разобраться. Тем более совсем непонятно что именно лежит в каждой из папок, какие изменения были сделаны и так далее.

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

Ещё из этого вырос механизм ветвления, который позволял сказать, что вот сейчас мы начнём делать свою версию проекта с ВАЖНЫМ изменением и не надо её трогать. А потом снова вольёмся в общий проект.

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

Как вообще это всё выглядит.

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#3493bf4bdb1e493a93c0fff18b023cfb)

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

Курс по GIT можно посмотреть, к примеру, тут: [10](https://www.youtube.com/playlist?list=PLY4rE9dstrJyTdVJpv7FibSaXB4BHPInb)

На самом деле, тут не очень много. В текстовом виде теория доступна тут: [11](https://git-scm.com/book/ru/v2)

Есть cheat-sheet: [12](https://github.github.com/training-kit/downloads/github-git-cheat-sheet.pdf

Работа с Git

Всё, что нам потребуется в данный момент — это следующие команды:

1. `git add .` — добавление всех файлов в текущем каталоге в систему отслеживания версия. 2. `git commit -a` — фиксация всех изменений, которые произошли. 3. `git push` — отправка на удалённый сервер. 4. `git pull` — получение с удалённого сервера.

Ах да. На какой удалённый сервер? Дело в том, что git позволяет организовывать взаимодействие через удалённый сервер, где хранится весь репозиторий и доступ к которому осуществляется только через git.

Скачать git можно по следующей ссылке: [13](https://git-scm.com/downloads)

После установки у вас появится специальная консоль git-bash.

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#efd0e67af7284441a4451001115f4e1e)

В этой консоли используется идеология unix-подобной ОС. Стандартные диски Windows примонтированы как `/c`, `/d` и так далее.

Вот тут есть cheat sheet для этой консоли: [14](https://rumorscity.com/wp-content/uploads/2014/08/10-Linux-Unix-Command-Cheat-Sheet-3.jpg)

Для работы вам потребуется перейти в директорию с проектов.

Создание удалённого репозитория на GitHub

Теперь посмотрим, как сделать удалённый репозиторий через сервис GitHub.

Регистрируемся, и переходим на страницу Start New Project. Выбираем имя для проекта `tg_mpei_course` к примеру, можем ввести описание и ставим доступ `Public`.

Также можно указать лицензию под которой будет опубликован код (вы, к примеру, могли недавно сходить на лекцию Ричарда Столлмана, автора лицензии GPL, под которой распространяется ОС GNU/Linux).

Важным моментом является файл `.gitignore`, который позволяет указать какие файлы не будут добавлены командой `git add .`, это могут быть разные служебные файлы компиляторов. Если вы выберете какой-то файл, то создадите уже не пустой репозиторий и вам потребуется сперва сделать его локальную копию у себя на машине, а потом перенести туда нужные файлы и папки и отправлять туда уже изменения. Выберем файл игнорировния для служебных файлов VisualStudio и создадим репозиторий.

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#b544f4c7fb2b4425a05417a2db182f15)

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

   git clone git@github.com:siriusfreak/tg_mpei_course.git

Разумеется, у вас будет другой адрес. Получить его можно тут:

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#14e4553eefe14baaa097283110f9c7ea)

На вопрос доверять ли хосту вам потребуется ответить `yes`, а вот потом, скорее всего, вы получите ошибку, связанную с тем, что сервер не может вас опознать.

   git@github.com: Permission denied (publickey).
   fatal: Could not read from remote repository.
   
   Please make sure you have the correct access rights
   and the repository exists.

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

Для этого требуется выполнить

   ssh-keygen

Далее везде нажать <Enter>. После чего вы получите публичный ключ, который надо будет отправить на сервер гитхаба. Для этого потребуется открыть файл `id_rsa.pub`, путь к которому был выведен. Для отображения содержимого файла можно использовать команду `cat`, к примеру:

   cat /c/Users/sirius/.ssh/id_rsa.pub

Этот ключ надо добавить в раздел [15](https://github.com/settings/keys) нажав кнопку "New SSH key". После этого команда `clone` будет успешно выполнена и останется лишь работать теми командами, что были указаны выше.

Теперь вы можете работать с Git и GitHub. Кстати, у гитхаба есть декстопное приложение: [16](https://desktop.github.com/

GCC

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

GCC — набор компиляторов для различных языков программирования, разработанный в рамках проекта GNU. GCC является свободным программным обеспечением, распространяется фондом свободного программного обеспечения (FSF) на условиях GNU GPL и GNU LGPL и является ключевым компонентом GNU toolchain. Он используется как стандартный компилятор для свободных UNIX-подобных операционных систем.

Скачать его версию для Windows можно тут: [17](http://www.mingw.org/)

После запуска установки появится следующее окно, в котором необходимо отметить нужные компоненты:

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#bae92e3f6af347699f7968094564831f)

После завершения установки потребуется прописать путь к gcc в переменную окружения PATH.

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#c5d9411616b5490f8b643e9c5cd655bf)

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#2cbd4c9561434383a11850685cbdbbb0)

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#c95369d55e5547f09d08c2b2c4c33b81)

[](https://www.notion.so/982373df81f0435eaff1939cf2c10051#f2b5a65679bf47a1923f43f6b2fb7dbb)

После этого он станет доступен в консоли `cmd` и скомпилировать любой файл cpp можно будет следующей командой:

   g++ --std=c++17 aplusb.cpp

Здесь `--std=c++17` означает и использование последнего опубликованного стандарта C++.

Получившаяся программа будет доступна в файле `a.exe`.

С этим компилятором умеют работать следующие редакторы и среды разработки (в скобках указаны ссылки на инструкции):

1. CLion [18](https://www.jetbrains.com/help/clion/quick-tutorial-on-configuring-clion-on-windows.html) 2. VS Code [19](https://code.visualstudio.com/docs/cpp/config-mingw)

В качестве дополнительного задания мы рекомендуем попробовать настроить эти связки, чтобы они обеспечивали такую же удобную работу, как и Visual Studio.

И помните что: VI VI VI is editor of the Beast

Python

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

Можно скачать интерпретатор версии 3.7 с оф. сайта: [20](https://www.python.org/downloads/)

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

Далее приведён код на питоне для задачи, которую рассматривали:

   class Solution:
       def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
           for i in range(0, len(nums)):
               for j in range(i + 1, len(nums)):
                   if (nums[i] + nums[j] == target):
                       return [i, j]

Быстрее чем 21% решений.

   class Solution:
       def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
           r_nums = {}
           for i in range(0, len(nums)):
               r_nums[nums[i]] = i
           for i in range(0, len(nums)):
               need = target - nums[i]
               if need in r_nums.keys():
                   if r_nums[need] != i:
                       return [i, r_nums[need]]

Быстрее, чем 99% решений

Итого

Вы решаете задачи, вы отправляете в git, раз в месяц мы делаем ревью задач, и говорим где вы молодцы, а где не очень.

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