Stanford Algorithms

Блуждая по просторам сети наткнулся на замечательный блог http://larrr.com/

Автор написала множество статей о том, как проходить собеседования в топ IT компании. Больше всего мне понравился собранный в одном файле InterviewPreparationGuide http://larrr.com/hochu-rabotat-v-google-manual-gotov/
Это действительно тот роудмап для программиста мечтающего устроится на работу в топ компанию. Взял его на вооружение и буду применять в своем обучении.

Поэтому, будем основательно осваивать новую профессию (насколько это вообще с программированием возможно). Начал я с алгоритмов, конкретно со стэнфордских курсов на coursera.org. С тех пор как я тут был последний раз, этот крупнейший MOOC портал значительно преобразился. Большинство курсов теперь платные (раньше учеба была бесплатной, купить можно было только подтверждающий сертификат), отдельных курсов практически не осталось – теперь все входит в состав специализаций. Еще одно значительное изменение – изменилась периодичность. Если 4-5 лет назад каждый курс был как праздник, сессии стартовали 1-2 раза в год, то сейчас все на рельсах, присоединиться можно в любой момент, форум де-факто мертвый. Представьте, если бы в ВУЗ можно было бы поступить в любой момент года? Скучно же было бы. Ну и тут что-то похожее.

Итак, специализация Algorithms, состоит из 4-х курсов по 4 недели. Уже прошел два курса из четырех за 5 недель. Изучил асимптотическую сложность, мастер метод, разобрал основные алгоритмы: Merge sort, Quick sort, BFS, DFS. Познакомился со структурами данных Heap, Tree, HashTable, Bloom Filter. Материал достаточно сложный, приходится много читать дополнительно. Не всегда до конца понятны доказательства теорем, по математике я проседаю прилично. Задания в конце каждой недели тоже не простые, но со второй попытки проходятся на 100%. Финальные экзамены оказались совсем простыми, потому что вопросы только по материалам из видео лекций.

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

Поделиться своим решением задач в репозитории – отличный повод завести аккаунт на github, не так ли? Поэтому, если кто-то также проходит курс и столкнулся с проблемой в решении задачек на алгоритмы https://github.com/DKARAGODIN/StanfordAlgorithms

Ну и как не выложить сертификаты? Попотеть ради них таки пришлось.

Парсинг XML по атрибутам

В примере про количество рабочих дней с учетом праздников мы парсили HTML код по атрибутам. Для получения содержимого необходимых тэгов использовали методы getElementsByAttributeValue и getElementsByClass сторонней библиотеки JSOUP.

Для парсинга XML текста , в отличие от HTML, традиционно применяют библиотеки, которые входят в стандартные поставки JDK. Для чтения, как правило, применяют DOM. Но столкнувшись с необходимостью чтения XML документа по значению атрибутов не обнаружил в этом пакете аналогов таких удобных методов, которыми я пользовался при парсинге HTML. Если с getElementsByClass еще это объяснимо, все таки class очень распространенный атрибут в HTML который не часто встретишь в XML, то getElementsByAttributeValue действительно не хватает.

Итак задачка. У нас есть великолепный XML файл, в котором все записано только с помощью одного тэга – parameter. Отличить что есть что можно только по значению атрибута «name» которое бывает или «variable» или «calculator».

<parameter type="Map">
<parameter name="variable">var1</parameter>
<parameter name="calculator">calc1</parameter>
<parameter name="variable">var2</parameter>
<parameter name="calculator">calc2</parameter>
</parameter>

Для начала стандартное создание объекта тип Document из XML файла. Считываем все тэги parameter и помещаем их в NodeLest. Получается несколько избыточно, поскольку видим, что первый тэг с type=”Map” структурно включает 4 других тэга parameter, но ничего лучше не придумал.

DocumentBuilderFactory f = DocumentBuilderFactory.newInstance();
DocumentBuilder builder = f.newDocumentBuilder();
Document doc = builder.parse(new File("src/file.xml"));
doc.normalizeDocument();
NodeList nNodes = doc.getElementsByTagName("parameter");

Теперь нужно пробежаться по ним. Запускаем цикл в котором вытаскиваем одну ноду, считываем все аттрибуты в переменную NameNodeMap attributes. Вытаскиваем значением атрибута “name” и кладем в ноду attr. Далее идет блок оператора if, которым мы проверяем значение атрибута и если оно нас устривает, то вытаскиваем текст тэга из ноды методом getTextContent.

for (int j = 0; j < nNodes.getLength(); j++){
Node nNode = nNodes.item(j);
NamedNodeMap attributes = nNode.getAttributes();
Node attr = attributes.getNamedItem("name");
if (attr != null) {
if (attr.getTextContent().equals("variable")) {
String s = nNode.getTextContent();
System.out.println(j + ", " + s);
} else if (attr.getTextContent().equals("calculator")) {
String s = nNode.getTextContent();
System.out.println(j + ", " + s);
}
}
}

Output:
1, var1
2, calc1
3, var2
4, calc2

Программа будет работать для любого количества вложений. Например, вот что получится если программе скормить следующий XML:

<parameter type="Map">
<parameter type="Maps">
<parameter type="MoreMaps">
<parameter name="variable">var1</parameter>
<parameter name="calculator">calc1</parameter>
</parameter>
</parameter>
</parameter>

Ouput:
3, var1
4, calc1

Количество рабочих дней с учетом праздников

Рассмотрим следующую задачку: «Написать SQL-запрос подсчитывающий количество рабочих дней между двумя датами учитывая все праздничные, выходные дни и их переносы”.

Без учета праздников эта задачка не представляет никаких трудностей. Просто подсчитываем количество дней, где день недели не равен СБ или ВС:

select count(*)
from (select to_date('01.01.2017','dd.mm.yyyy')+rownum dat,
to_char(to_date('01.01.2017','dd.mm.yyyy')+rownum,'DY') dy
from sys.all_objects)
where dat<=to_date('31.12.2017','dd.mm.yyyy') and dy not in('СБ','ВС')

Получаем 260 дней.

В стандартном пакете Oracle, да и наверное во всех других базах данных, отсутствуют сведения о праздничных днях в России. Значит их нужно откуда-нибудь взять. Будем вытаскивать выходные из производственного календаря системы Консультант плюс. Актуальный календарь на текущий год располагается по адресу http://www.consultant.ru/law/ref/calendar/proizvodstvennye/

Рассмотрим только текущий 2017 год. Парсить html страницу будем в java с помощью библиотеки jsoup (https://jsoup.org/). Для начала проинспектируем наш календарь.

Видим, что месяц заключен в таблицу, которой проставлен класс “month-block”. Именно по этому признаку и будем выделять необходимые тэги. Далее нужно определить какие дни у нас праздничные, а какие рабочие.

Инспектор html кода показал, что дни бывают трех классов: inactively, holiday weekend, work. Мы будем брать только те значения тэгов, у которых выставлен класс которому соответствуют праздничные дни.

Здесь я должен сделать небольшой дисклэймер. Мое творение не является образцом хорошего кодинга на java. В нем совсем не используются возможности объектно-ориентированного программирования, вся программа написана в одном методе main. Это очень плохо. Пока я не особо умею писать по-другому, но все впереди, я только учусь.

Также пока не подобрал хороший плагин для wordpress для отображения кода. Если стандартные тэги Code для SQL еще более-менее смотрятся, то вот java код практически не читабелен. Постараюсь со временем переделать соответствующие блоки.

Итак, можно приступить к программированию. Вот что у меня получилось.

public class ParseConsultant{
public static void main(String args[]) throws IOException, SQLException {
List monthsList = new ArrayList<>(); //сюда поместим все блоки всех месяцев
List daysList = new ArrayList<>(); //сюда поместим блоки с днями
Document doc = Jsoup.connect("http://www.consultant.ru/law/ref/calendar/proizvodstvennye/").get(); //коннекстимся к источнику
Elements monthsElements = doc.getElementsByAttributeValue("class", "month-block"); //добавляем элементы-месяцы
monthsElements.forEach(monthsElement -> {
String aElement = monthsElement.child(0).toString(); //выбираем все содержимаое месяца
monthsList.add(aElement);
});
Locale.setDefault(Locale.ENGLISH); //подключаемся к базе данных
String dbURL = "jdbc:oracle:thin:dksd/1@localhost:1521:XE"; //подключаемся к базе данных
Connection conn = DriverManager.getConnection(dbURL);
if (conn != null) {
System.out.println("Connected");
}
Statement statement = conn.createStatement(); //открываем statement для последующего insert
for (int x = 0; x < 12; x = x + 1) { //открываем цикл для пробега по всем 12-ти месяцам Document mon = Jsoup.parse(monthsList.get(x)); //парсим содержимое массива месяцев для выбора дней. System.out.println(mon.toString()); //смотрим что у нас в месяце Elements mElements = mon.getElementsByClass("holiday weekend"); //выбираем нужные тэги по классу mElements.forEach(mElement -> {
String dElem = mElement.text(); //получаем значение тэга, то есть праздничный день
daysList.add(dElem); //добавляем значение тэга в массив
});
int z = daysList.size(); //считаем сколько добавилось выходных дней в текущем месяце
for (int i = 0; i < z; i = i + 1) { //для каждого дня формируем insert строку
System.out.println(i + "-" + daysList.get(i)); //смотрим какие у нас выходные дни в текущем месяце
int m = x + 1; //для правильного insert месяца, который не может быть равен нулю
String insertSQL = "insert into holidays (HOLIDAY) VALUES (to_date('" + daysList.get(i) + "." + m + ".2017','dd.mm.yyyy'))";
statement.executeUpdate(insertSQL); //добавлем строки в таблицу holidays
}
daysList.clear(); //очищаем массив в конце цикла
}
}
}

Программа с помощью библиотеки jsoup коннектится к запрашиваемой странице, выбирает все блоки где имелся класс «month-block». Потом каждый блок еще раз парсится на предмет текста тэга, содержащего класс «holiday weekend». Сохраняет все в ArrayList и подставляет в строку для инсерта в базу данных.

Выполнив эту программу получаем даты всех выходных дней в предварительно созданной таблице HOLIDAYS, состоящей из одной колонки HOLIDAY. Их должно получиться 118.

Теперь модифицируем SQL запрос.

select count(*)
from (select to_date('01.01.2017','dd.mm.yyyy')+rownum dat
from sys.all_objects)
where dat<=to_date('31.12.2017','dd.mm.yyyy') and dat not in (select holiday from holidays)

Получаем 247 дней. На целых 13 дней меньше))