четверг, 10 октября 2013 г.

Курсы Информационных Технологий (КИТ) от Яндекса - 4-ый набор. Тестовые задания

Добрый день!

Сразу как увидел новость о четвертом наборе на КИТ от Яндекса, сразу подал заявку после небольшого ожидания прислали письмо с доступами к внутренней системе Яндекса. Там я увидел 5 заданий. В данной заметке покажу, как я решил эти задания. Решал я их с помощью (Perl 5.14, Python 2.7, Bash 4.2). Есть много способов решения этих заданий, но тут именно те, до которых додумался я. 

Решать задания можно было на таких языках: Java 6/7, Python 2.7/3.2, Delphi, Free pascal, Perl 5.14, GNU bash 4.2, GNU c (4.6), GNU c x32 (4.6), GNU c++0x x32 (4.6), GNU c++ x32 (4.6), GNU c++0x (4.6), GNU c++ (4.6).


1. Изменить имя хоста и домена в hosts

Ограничение времени1 секунда
Ограничение памяти64Mb
Ввод
стандартный ввод
Вывод
стандартный вывод

Легенда


В текстовом (ASCII, unix) файле hosts задается соответствие имён и адресов.
В подаваемом программе на стандартный вход файле имя машины bar нужно изменить на baz, а ее имя домена domain.tld нужно заменить на donemain.tld
Результат вывести на стандартный вывод

Формат ввода


127.0.0.1       localhost
192.168.1.10    foo.mydomain.org       foo
192.168.1.13    bar.domain.tld      bar.anotherdomain.tld  bar
213.180.204.62    yandex.com      www.yandex.com
# The following lines are desirable for IPv6 capable hosts
::1     ip6-localhost ip6-loopback
fe00::0 ip6-localnet
ff00::0 ip6-mcastprefix
ff02::1 ip6-allnodes
ff02::2 ip6-allrouters

Формат вывода


127.0.0.1       localhost
192.168.1.10    foo.mydomain.org       foo
192.168.1.13    baz.donemain.tld      baz.anotherdomain.tld  baz
213.180.204.62    yandex.com      www.yandex.com
# The following lines are desirable for IPv6 capable hosts
::1     ip6-localhost ip6-loopback
fe00::0 ip6-localnet
ff00::0 ip6-mcastprefix
ff02::1 ip6-allnodes
ff02::2 ip6-allrouters

Примечания




Часть строк могут быть пустыми, в каждой строке текст после символа # считается комментарием и игнорируется. Вместо чтения стандартного ввода и записи в стандартный вывод допускается читать данные из файла input.txt и записывать в output.txt

Решение


Perl 5.14

#!/usr/bin/perl
foreach(<STDIN>){
if ($_ =~ s/(\s+)bar/\1baz/g) {};
if ($_ =~ s/(\s+)baz.domain.tld/\1baz.donemain.tld/g) {};
print $_; }

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




Python 2.7

import re

input = open("input.txt", "r")
output = open("output.txt", "w")
reg1 = re.compile(r"\bbar")
reg2 = re.compile(r"\bbaz.domain.tld")
for line in input:
    line2 = re.sub(reg1, "baz", line)
    line3 = re.sub(reg2, "baz.donemain.tld", line2)
    output.write(line3)

Тут видна существенная разница между Perl и Python, над временем выполнения и израсходуемой памятью:



2. Сосчитать незаблокированных пользователей в shadow

Ограничение времени1 секунда
Ограничение памяти64Mb
Ввод
стандартный ввод
Вывод
стандартный вывод

Легенда


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

Формат ввода


Каждая строка файла содержит 9 полей, разделённых двоеточиями (":"), в первом поле хранится имя пользователя, во втором - зашифрованный пароль. Заблокированные учетные записи содержат во втором поле символ "звездочка" ("*") или восклицательный знак ("!").

Формат вывода


Неотрицательное число в текстовом десятичном виде в кодировке ASCII

Примечания


Записи с пустым полем пароля считаются незаблокированными. Вместо чтения стандартного ввода и записи в стандартный вывод допускается читать данные из файла input.txt и записывать в output.txt

Решение


Perl 5.14

#!/usr/bin/perl
foreach(<STDIN>){
if ($_ =~ /^[\w_-]+?:[^\!\*.]+/) {$i++;}}
print "$i"; 


Python 2.7

i = 0
input = open("input.txt", "r")
output = open("output.txt", "w")
for line in input:
    file = line.split(":")
    if not file[1].startswith("!") and not file[1].startswith("*"):
        i += 1


output.write(str(i))
input.close()
output.close() 




3. В nsswitch.conf установить приоритет преобразования имен через dns перед файлом hosts

Ограничение времени1 секунда
Ограничение памяти64Mb
Ввод
стандартный ввод
Вывод
стандартный вывод

Легенда




В файле nsswitch.conf задаются источники данных для службы имен библиотеки языка Си. Измените файл nsswitch.conf так, чтобы приоритет был у DNS.

Формат ввода




В строке файла, подаваемого на стандартный ввод, начинающейся со слова hosts, задается порядок преобразования имен в адреса. Если слово files в этой строке идет раньше слова dns - содержимое файла /etc/hosts имеет приоритет перед DNS (и наоборот). В строке могут встречаться и другие слова (например, ldap). В файле могут быть другие строки. Часть строк может быть комментариями (первый символ #).

Формат вывода


Все строки входного файла вывести на стандартный вывод в неизменном виде, кроме строки, начинающейся со слова hosts, в которой слово dns переставить на первое после слова hosts место.

Примечания

Вместо чтения стандартного ввода и записи в стандартный вывод допускается читать данные из файла input.txt и записывать в output.txt

Решение


Python 2.7
input = open("input.txt", "r")
output = open("output.txt", "w")
for line in input:
    if line.startswith("hosts"):
        host = line.split()
        dns = host.pop(host.index("dns"))
        host.insert(1, dns)
        output.write(' '.join(host)+"\n")
        continue
    output.write(line)




4. В выводе mtr найти "худший" маршрутизатор

Ограничение времени1 секунда
Ограничение памяти64Mb
Ввод
стандартный ввод
Вывод
стандартный вывод

Легенда




В выводе команды LANG=C mtr --report --report-cycles 9 --no-dns ya.ru найти строку с "худшими" значениями. Искомой считается строка (в порядке приоритета):

  1. с наибольшим процентом потерянных пакетов
  2. с наибольшим стандартным отклонением (StDev) времени отклика
  3. с наибольшим средним временем отклика
Вывести номер этой строки.

Формат ввода




HOST: pooh                        Loss%   Snt   Last   Avg  Best  Wrst StDev
  1.|-- 84.201.169.254             0.0%     9    1.3   1.3   1.0   2.4   0.5
  2.|-- 37.9.74.134                0.0%     9    1.6  18.4   1.2 121.4  39.8
  3.|-- 87.250.239.11              0.0%     9    3.5  14.6   1.5 110.1  35.8
  4.|-- 87.250.239.45              0.0%     9    3.2   8.4   2.9  48.5  15.0
  5.|-- 87.250.239.143             0.0%     9    8.1  21.2   2.3  73.4  24.1
  6.|-- 87.250.250.203             0.0%     9    3.5  13.9   2.1  97.7  31.4

Формат вывода




2

Примечания




Вместо чтения стандартного ввода и записи в стандартный вывод допускается читать данные из файла input.txt и записывать в output.txt.

Решение


Python 2.7


input = open("input.txt", "r")
output = open("output.txt", "w")

all = []
for line in input:
    if line.strip()[0].isdigit():
        line2 = line.strip().split()
        line2[0], line2[2] = line2[0][0], line2[2][:-1]
        all.append(line2)

max_loss = max_st_dev = max_avg = 0.0
max_loss_el = max_st_dev_el = max_avg_el = 0
for string in all:
    if float(string[2]) > max_loss:
        max_loss = float(string[2])
        max_loss_el = string[0]
    if float(string[-1]) > max_st_dev:
        max_st_dev = float(string[-1])
        max_st_dev_el = string[0]
    if float(string[-4]) > max_avg:
        max_avg = float(string[-4])
        max_avg_el = string[0]

if max_loss:
    output.write(max_loss_el)
else:
    if max_st_dev:
        output.write(max_st_dev_el)
    else:
        if max_avg:
            output.write(max_avg_el)

input.close()
output.close()



5. Посчитать пиковое число запросов в секунду по журналу access.log веб-сервера nginx

Ограничение времени1 секунда
Ограничение памяти64Mb
Ввод
стандартный ввод
Вывод
стандартный вывод

Легенда




Веб-серверы записывают каждый запрос в файл стандартного формата access.log
В журнал access.log попадает время с точностью до секунды, в которое был выполнен запрос. В подаваемом на стандартный вход файле посчитайте максимальное число запросов в секунду, которое было получено сервером и выведите это число на стандартный выход.

Формат ввода




127.0.0.1 - - [02/Sep/2013:13:12:19 +0400] "GET /ubuntu/dists/precise/Release HTTP/1.1" 200 3011 "http://localhost/ubuntu/dists/precise/" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/28.0.1500.71 Chrome/28.0.1500.71 Safari/537.36"
10.10.10.10 - - [02/Sep/2013:13:12:36 +0400] "GET / HTTP/1.0" 200 612 "-" "-"
10.10.10.10 - - [02/Sep/2013:17:45:36 +0400] "GET /ubuntu/dists/precise/Release HTTP/1.1" 200 3011 "-" "Wget"
10.10.10.10 - - [02/Sep/2013:17:45:36 +0400] "GET /ubuntu/dists/precise/main/binary-i386/Release HTTP/1.1" 200 96 "-" "Wget"


Формат вывода




2

Примечания




Вместо чтения стандартного ввода и записи в стандартный вывод допускается читать данные из файла input.txt и записывать в output.txt Каждый запрос занимает в файле одну строку, при отображении примера журнала в броузере последняя строка может ошибочно быть "разорвана".


Решение

Bash 2.4


awk '{print $4}' < input.txt | uniq -c | sort -nr | head -1 | perl -pe 's#\s+(\d+).+#\1#' > output.txt
Сама идея принадлежит: http://blog.amet13.name/, но я немного оптимизировал и переделал.

Python 2.7


input = open("input.txt", "r")
output = open("output.txt", "w")

all = {}
for line in input:
    if line.split()[3] in all:
        all[line.split()[3]] += 1
    else:
        all[line.split()[3]] = 1

sorted_all = sorted(all.items(), key=lambda x: x[1])
output.write(str(sorted_all[-1][-1]))
input.close()
output.close()


Вот так и решил данные тесты. 
Больше всего проблем возникли при решении второй задачи с shadow из-за неправильного понимания задачи. Очень понравился у яндекса Source Code Highligth.


Вчера получил письмо с информацией о том, что я успешно выполнил тестовые задания и получил приглашение на КИТ.

1 комментарий: