воскресенье, 15 июля 2012 г.

Покорение одной крупной фирмы или простое решение тестовых задач

Всем привет!

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

Для начала глянем, что же нам предлагают
  1.     Преобразование численного представления IP адреса в строку.
  2.     Проверка корректности введенной строки по некоторому шаблону.
  3.     Магический SQL запрос
  4.     Получение содержимого страницы с помощью telnet

Однако же, задачи просты и тривиальны. Рассмотрим решение первой из них.

 

Преобразование записи IP адреса


Здесь все просто, главное понять, чего от нас хотят. IP адресс записывается в формате

xxx.xxx.xxx.xxx

где xxx максимально может быть от 0 до 255, что есть один байт.

Наш int 32-х битный, соответственно, хранит в себе 4 байта, то есть - последовательность четырех независимых друг от друга чисел, каждое из которых может быть от 0 до 256.

Ничего не напоминает?)

Дальше дело за малым. Битовыми сдвигами и логическим И добиваем все это до приемлемого вида и записываем в StringBuilder. Код решения

int ipAdress = 32589; // любое целое число, представляющее IP адрес 

StringBuilder sb = new StringBuilder(); 
sb.append(ipAdress & 0xFF).append(".")
    .append((ipAdress >> 8) & 0xFF).append(".")
    .append((ipAdress >> 16) & 0xFF).append(".")
    .append((ipAdress >> 24) & 0xFF);

System.out.println(sb.toString());

Разберемся, что здесь происходит.

sb.append(ipAdress & 0xFF)

здесь мы выполняем логическое И с первыми 8 битами в записис IP адресса, причем конъюнкция (логическое И) выполняется с 0xFF, что есть 256 или если рассматривать двоичную запись числа в 32-х битном формате:

000000000000000000000011111111

Наше число ipAdress = 32589 в двоичном виде выглядит следующим образом:

000000000000000111111101001101

Применяя к нему логическое И, мы вытянем первые 8 ноликов и единичек:

000000000000000111111101001101 

&
000000000000000000000011111111 
000000000000000000000001001101

Если перевести в десятичную систему счисления - это будет 77.

По аналогии дальше происходит постоянный сдвиг и конъюнкция.

Так как нам надо извлечь все такие непересекающиеся 8-ми битные последовательности, дальше просто делаем постоянной битовый сдвиг с шагом 8 и опять же выполняем конъюнкцию с OxFF. Полученный результат печатаем на консоль. У меня напечаталось:

77.127.0.0

Первое задание выполнено! =) Переходим ко второму.

 

Распознавание логина

Второе задание - распознавание слова, которое должно соответствовать какому то определенному шаблону.  Делать это можно разными способами, но я предлагаю остановиться на самом коротком из них - использование регулярных выражений. Класс регулярных языков не так обширен, как класс различных грамматик, но данная задача попадает в класс регулярных языков, поэтому смело берем и подключаем стандартный package regexp.

Способов работы с ним полным полно в интернете, очень прозрачны и официальные доки.

Нам понадобится один класс из этого пакета -  Pattern. Класс Pattern - это класс, представляющий собой функциональную обертку для строки регулярного выражения.

Слова должны удовлетворять следующим условиям:

- Логин должен начинаться с латинской буквы

- Может состоять из латинских букв, цифр, точки и минуса

- Должен заканчиваться латинской буквой или цифрой

- Минимальная длина логина – 1 символ, максимальная – 20 символов

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

(^([a-zA-Z])([a-zA-Z0-9\\.\\-\\_]){0,18}([a-zA-Z0-9])$)

Теперь разберем по частям, что из себя это выражение представляет.

Логически оно состоит из трех блоков - это  распознавание первой буквы, распознавания всего логина без первой и последней буквы и распознавание последней буквы логина.

^([a-zA-Z]) - распознавание первой буквы

([a-zA-Z0-9\\.\\-\\_]){0,18} - распознавание без первой и последней буквы

([a-zA-Z0-9])$ - распознавание последней буквы


Регулярные выражения чрезвычайно просты в использовании и вариантов решения этой задачи может быть очень много, но я специально решил остановится на самом простом и очевидном решение - решении в лоб.



Разберемся с первой буквой. В условии задачи сказанно, что слово должно обязательно начинаться с латинской буквы. Как раз именно это и сделаем:


^([a-zA-Z])

 Здесь галочка ^ обозначает начало слова, а далее - буквенный интервал, в верхнем и нижнем регистре.



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

  •     у нас добавляются дополнительный буквы ".", "_", "-"
  •     их количество может быть от 0 до 18

Сам код:

([a-zA-Z0-9\\.\\-\\_]){0,18}

 Почему так? В условии задачи сказано, что слово должно быть не длиннее 20 букв. Первую и последнюю мы распознаем отдельно, следовательно, нам надо распознать еще от 0 до 18 букв, что мы и делаем. Для обозначения интервала количества повторения используются фигурные скобки и указание границ интервала.


Примечание: так как ".", "_", "-" служебные знаки в регулярных выражениях, мы их экранируем двойными слешами, чтобы они распознавались как буквы

Ну и рассмотрим заключительную часть - распознавание последней буквы. Здесь же задача ничем не отличается от самой первой задачи по распознаванию первой буквы с той лишь разницей, что вместо галочки мы используем знак $ - символ конца строки.


Вот код:
 

([a-zA-Z0-9])$

Вот в общем то и все с регулярными выражениями. Далее я приведу сам код программы.

 

System.out.println("Enter name, please:"); 

String login =
    new BufferedReader(new InputStreamReader(System.in)).readLine();

boolean isMatched =  

   Pattern.matches("(^([a-zA-Z])([a-zA-Z0-9\\.\\-\\_]){1,18}(([a-zA-Z])|([0-9]))$)", login);
 
if(isMatched){
    System.out.println("Name: " + login + " - passed"); 

} 
else{ 
   System.out.println("Name: " + login + " - not passed"); 
}

Вот мы и одолели второе задание.

 

Люди и количество загрузок. Третье задание.


Теперь давайте разберем третье задание. Нам необходимо вывести все пары чисел (количество_загрузок, количество пользователей), в которых количество пользователей не равно 0. Создаем сначала view в SQL


CREATE VIEW download_count_view AS
SELECT download_time, user_id, COUNT (download_id) AS download_count
FROM track_downloads
WHERE download_time = '19.11.2010'
GROUP BY user_id

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

 

SELECT download_count, COUNT(user_id) 

FROM download_count_view 
GROUP BY download_count



Эта простая выборка и даст нам необходимый результат.

Я не буду особо останавливаться на реализации запроса и вьюхи, так как это SQL и все достаточно тривиально, а главной тематикой блога является все таки программирование.

 

Последнее задание. Путь к победе.

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

telnet test.host.ru 80 

GET /test/testpage.xml HTTP/1.1 Host: test.host.ru


В общем то, здесь особо нечего рассказывать. test.host.ru - имя хоста, к которому будем подключаться, 80 - номер порта, дальше команда GET - для получения содержимого страницы, указание версии протокола и хоста для команды GET. Все весьма тривиально.

 

Заключение. 

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


До новых встреч!

Комментариев нет:

Отправить комментарий