За последнюю неделю опубликовано 131 новых материалов.
Инструкция новичку Путеводитель по форуму Прокси для Telegram Показать подсказки , это бомба!

Задачи на собеседованиях #214. Задачи от Stack Group и решение задач от Virtuozzo

  • Поучаствуй (в качестве покупателя) в любых пяти совместных покупках (кроме завершённых и "Моментальных") и получи группу "Новичок" навсегда -> ссылка на раздел
  • Получай до 480 рублей за каждого приглашенного пользователя!
    представляем Вам очередное расширение партнерской программы, подробности описаны тут -> ссылка
  • 90% материалов доступно к скачиванию после простой регистрации!
    Если же ты хочешь скачивать материалы без требования оставлять отзывы то получи группу "Новичок", 10 способов повышения описаны тут -> ссылка
  • К сожалению количество битых ссылок растет и мы уже не можем их оперативно восстанавливать поэтому просим помощи у каждого нашего пользователя.
    С сегодняшнего дня, за каждую восстановленную ссылку мы заплатим Вам.
    Подробнее тут -> ссылка
  • Перенесем твои заслуги с другого ресурса!
    Мы понимаем как сложно прокачивать аккаунты на форумах, вроде раскачал аккаунт, а тут появляется ресурс в 100 раз круче но тоже с системой прокачки и снова качать аккаунт...
    Предлагаем вам перенести Ваши заслуги на другом подобном ресурсе к нам.
    Подробности описаны тут -> ссылка
  • Вы можете получать по 2.5% с каждой покупки и продажи на маркете! Подробности в теме Партнёрская программа

News_Bot

Бот новостей и статей
Бот форума
29 Сен 2016
3.023
38
20
Содержание статьи
  • Задачи
  • Куда слать решения?
  • Наш победитель: Jack Black и его решения
  • Разбор решения задач от победителя: комментирует Юрий Пудгородский
  • IT-компании, шлите нам свои задачки!
Как насчет свежей порции облачных ноябрьских задачек? А вот и нет! Задачки-то обычные, приземленные. «Облачная» — это компания, нам с тобой эти задачи задает. Встречай — Stack Group, которая предоставляет весь спектр соответствующих услуг: IaaS, storage, VDI / VDI GRID, DRaaS и другие. Облако Stack Group корпоративного класса, построено на базе собственного ЦОД — М1, а также партнерских дата-центров в Москве, Франкфурте и Амстердаме. Как видишь, работодатель большой и завидный :).

Призы и (впервые в нашей рубрике!) утешительные призы от Stack GroupПервым трем правильно решившим: скидка 50% на IaaS в течение года (а это не шутки).

Утешительные призы первым пяти решившим правильно, но с незначительными неточностями: портативное зарядное устройство для телефона.



Задачи
Исходные данные:
Код:
order_header
— таблица заголовка заказа:
Код:
id INT IDENTITY(1,1) Идентификатор таблицы заказа reg_number VARCHAR(MAX) NOT NULL Регистрационный номер заказа on_date DATETIME NOT NULL дата формирования заказа
Код:
order_details
— таблица деталей заказа:
Код:
id INT IDENTITY(1,1) идентификатор строки деталей заказа hdr_id INT NOT NULL идентификатор заказа good_id INT NOT NULL идентификатор товара amount DECIMAL(19,4) NOT NULL количество товара price DECIMAL(19,2) NOT NULL цена за единицу измерения товара для данного заказа
Для реализации на Transact-SQL:
  1. Напишите скрипты создания таблиц со связями между собой, скрипты должны пересоздавать таблицы.
  2. Выберите все заказы и для каждого заказа выберите строку деталей с максимальной суммарной стоимостью товара в заказе; если детали две, то выбрать одну с максимальной стоимостью единицы товара.
  3. Напишите хранимую процедуру, которая выполнит обновление всех заказов с заданной даты @date_from по заданную дату @date_to, в которых присутствует товар с заданным идентификатором @good_id_old, и заменит его на товар с идентификатором @good_id_new (данный товар тоже может уже быть в заказе, его следует также просуммировать с существующим). Задачу необходимо выполнить без использования циклов и курсоров.
  4. Выполнить предыдущую задачу, если известно, что записей в таблице очень много (~10 миллионов) и таблица является высоконагруженной.
Для реализации на C#:
  1. Напишите отображения двух таблиц в Entity Framework согласно нотации Code First, используя синтаксис Fluent.
  2. Напишите выборку LINQ, в которой выберите все заказы и для каждого заказа — строку детали с максимальной суммарной стоимостью товара в заказе; если детали две, то выбрать одну с максимальной стоимостью единицы товара.
Для реализации на ASP.NET MVC 5, синтаксис представления Razor:
  1. Напишите форму в представлении с использованием HTML и разметки Razor для редактирования строки создания и редактирования строки заказа.

Куда слать решения?
Свои варианты ответов шли на pobeditel@stackgroup.ru



Наш победитель: Jack Black и его решения

Приз читателю: Virtuozzo Storage на год!Наши друзья из Virtuozzo подогнали читателю крутой приз — безлимитную по объему триальную лицензию сроком на год. А поскольку формально она триальная, ставить ее можно на несколько кластеров :).


Задание 1 (Приложение: run.c)Окружение создается с помощью механизмов Linux namespaces. Создаем копию дерева ФС для текущего процесса:
Код:
if (unshare(CLONE_NEWNS) == -1) { printf("Error: cannot unshare (%s)
", strerror(errno)); return 1; }
Приватно монтируем
Код:
/dev/shm
, чтобы избежать конфликтов семафоров программы:
Код:
if (mount("tmp", "/dev/shm", "tmpfs", MS_NOSUID, "") == -1) { printf("Error: cannot mount /dev/shm (%s)
", strerror(errno)); return 1; }
Дальше следует обычный exec.
Задание 2 (приложение: json.patch)Первое, что бросается в глаза, если посмотреть лог strace, — это повторяющиеся системные вызовы каждую итерацию. Например,
Код:
stat("/dev/random", {st_mode=S_IFCHR|0666, st_rdev=makedev(1, 8), ...}) = 0 <0.000006>
Если посмотреть код UUID библиотеки, то можно увидеть
Код:
static int have_random_source(void) { struct stat s; return (!stat("/dev/random", &s) || !stat("/dev/urandom", &s)); } void uuid_generate(uuid_t out) { if (have_random_source()) uuid_generate_random(out); else uuid_generate_time(out); }
Таким образом, прямой вызов
Код:
uuid_generate_random()
может избавить от лишней проверки. Однако остается комбинация
Код:
open("/dev/urandom", O_RDONLY|O_CLOEXEC) = 3 <0.000007> fcntl(3, F_GETFD) = 0x1 (flags FD_CLOEXEC) <0.000006> fcntl(3, F_SETFD, FD_CLOEXEC) = 0 <0.000006> getuid() = 1000 <0.000006> getppid() = 24557 <0.000005>
Решением может стать вызов более низкоуровневой функции
Код:
__uuid_generate_random
библиотеки с указанием количества элементов. Это дает возможность один раз тратить время на генерацию UUID:
Код:
__uuid_generate_random(0x7ffdcded6e60, 0x7ffdcded6e00, 0x7ffdcded6e00, 0) = 0 <0.000534>
А в цикле делать только преобразования:
Код:
uuid_unparse(0x7ffdcded6e70, 0x7ffdcded6e30, 0x7ffdcded6e30, 0) = 0 <0.000077>
Против изначальной издержки итерации:
Код:
uuid_generate(0x7ffd15645a70, 0xffffffff, 0x7efe536a5780, 0) = 0 <0.000167> uuid_unparse(0x7ffd15645a70, 0x7ffd15645a80, 0x7ffd15645a80, 0x7efe533db709) = 0 <0.000076>
Конкретно в случае данной программы можно отказаться от использования JSON-библиотеки:
Код:
json_object_new_object(0x7fffc0cf5960, 0x7fffffdb, 0x7fffc0cf5c64, 36) = 0x19e00c0 <0.000075> json_object_new_string(0x7fffc0cf5c40, 0, 0x19e0370, 0x19e0370) = 0x19e0380 <0.000075> json_object_new_int(0, 0x7fffc0cf5c65, 0xc0ff01d000000000, 0) = 0x19e0400 <0.000074> json_object_new_int(0, 0, 0, 9) = 0x19e0450 <0.000072> json_object_object_add(0x19e00c0, 0x400d64, 0x19e0380, 9) = 0 <0.000140> json_object_object_add(0x19e00c0, 0x400d69, 0x19e0400, 2) = 0 <0.000073> json_object_object_add(0x19e00c0, 0x400d70, 0x19e0450, 6) = 0 <0.000072> json_object_to_json_string(0x19e00c0, 16, 0x19e0230, 3) = 0x19e0520 <0.000077> puts("{ "uuid": "0fb70fdf-218b-4869-9d"...) = 76 <0.000197> json_object_put(0x19e0450, 0x7f8d05d9d000, 0x7f8d057699e0, 0x7f8d05494710) = 1 <0.000127> json_object_put(0x19e0400, 0xffffffff, 0x7f8d05767780, 0) = 1 <0.000078> json_object_put(0x19e0380, 0xffffffff, 0x7f8d05767780, 0x19e0440) = 1 <0.000075> json_object_put(0x19e00c0, 0xffffffff, 0x7f8d05767780, 0x19e03f0) = 1 <0.000074>
в пользу форматированного вывода:
Код:
printf("{ "uuid": "%s", "number": %d, "v"..., "19bde036-3cf5-4d61-b70e-d1ec4e4f"..., 1, 1) = 76 <0.000217>
Результирующий патч в приложении.
Задание 3 (приложение: buils.sh)Пример вызова скрипта:
Код:
./build.sh -f task2.sfx -n task2 -r 3 ./build.sh -f task2.sfx -n task2 -r 3
К сожалению, под рукой была только Ubuntu, делал на ней.

Разбор решения задач от победителя: комментирует Юрий Пудгородский
Задание 1В задании требуется понять с помощью
Код:
strace
, отладчика или еще каким-либо способом, как процессы конфликтуют друг с другом. По итогам запуска strace можно определить, что процесс использует именованные
Код:
posix semaphore
и
Код:
shared memory
объекты. В результате параллельно исполняющиеся процессы конкурируют за имя вновь созданных объектов, только первый создавший объекты может успешно работать.
Очевидное решение — создать такое runtime-окружение для каждого процесса, в котором пространство имен posix semaphore объектов не пересекается. Ранее для таких задач пользовались методом
Код:
runtime interception
системного или библиотечного вызова. В перехваченном вызове подменяли имя на уникальное для каждого процесса. Одно из таких решений — определение собственных
Код:
shm_open()
и
Код:
sem_open()
через
Код:
LD_PRELOAD
, подстановка уникального имени с PID процесса как части имени и затем вызов оригинального API через
Код:
RTLD_NEXT
.
С появлением в Linux специальной файловой системы с точкой монтирования
Код:
/dev/shm
, в пространстве имен которой находятся все semaphore и shared memory объекты, а также per-process namespace для mount points, решение может более простым и идеологически общим. В нем мы создаем приватный mount namespace для child process, монтируем в нем свой собственный экземпляр
Код:
/dev/shm
и исполняем в таком окружении timer process.
Именно такое решение в современном стиле
Код:
process namespaces
было выполнено кандидатом — на 100% корректное и элегантное.
Задание 2Аналогично первому заданию предполагается инструментальное runtime-профилирование с помощью
Код:
strace
и compile-time профилирование для определения узкого места алгоритма. Для начала можно запустить исследуемую программу под time и обратить внимание на соотношение времени исполнения в режиме ядра и пользовательском. Время исполнения в ядре оказывается сравнимым по порядку с пользовательским, что дает нам основание говорить об узком месте, связанном с использованием системных вызовов. Профилирование с помощью strace это подтверждает, также мы получаем не только время исполнения, но и некоторое представление о задаче, решаемой с помощью этих вызовов.
Им оказывается алгоритм генерации случайных UUID, основанный на применении стандартной 3rd party библиотеки libuuid. В процессе генерации libuuid открывает
Код:
/dev/urandom
интерфейс к генератору случайных чисел, предоставляемому ядром Linux, читает необходимое количество случайных данных, закрывает FD и создает случайный UUID на полученной основе. Дальнейшее исследование показывает, что узким местом оказывается именно производительность
Код:
/dev/urandom
. Оптимизации, связанные с устранением многократного повторения
Код:
stat()
или даже модификация исходного текста, чтобы устранить
Код:
open()
/
Код:
close()
для каждого UUID, лишь незначительно снижают общее время. Никакой другой интерфейс, предоставляемый libuuid, не позволяет генерировать большое количество UUID с высокой скоростью.
Решением проблемы может быть использование своего userspace генератора случайных чисел с высокой производительностью и принятие специальных мер для уникальности UUID из разных процессов (примешивание к pseudo-random-данным PID процесса, высокоточной метки времени и так далее). Другими словами, своя собственная реализация UUID-генератора.
После устранения libuuid и обращений к
Код:
/dev/urandom
профилирование покажет, что основная часть userspace-исполнения приходится на JSON-библиотеку. Ее замена на простой форматный
Код:
printf()
дает ускорение приблизительно в три раза и может считаться оправданной в подобных случаях.
Решение кандидата выполнено по двум пунктам из трех, итого оценка 66% из 100% возможных:
  • анализ и профилирование — complete;
  • замена
    Код:
    /dev/urandom
    на userspace pseudo-random — not complete;
  • оптимизация JSON-форматирования — complete.
Задание 3Не самое интересное задание, проверяющее умение пакетировать RPM и скриптово-интеграционные способности.
В задаче не предполагалось кодирование на языке С, наиболее оптимальным будет автоматический скрипт на Shell/Bash/Python или другом подходящем скриптовом языке. Использование изолированного окружения при запуске самораспаковывающегося исполняемого файла необязательно, так как оно явно не требуется в техническом задании, но может быть обосновано соображениями безопасности.
Решение кандидата — без изоляции процесса распаковки, но с помощью профессионально оформленного скрипта на Bash. 100%.

IT-компании, шлите нам свои задачки!
Миссия этой мини-рубрики — образовательная, поэтому мы бесплатно публикуем качественные задачки, которые различные компании предлагают соискателям. Вы шлете задачки — мы их публикуем. Никаких актов, договоров, экспертиз и отчетностей. Читателям — задачки, решателям — подарки, вам — респект от нашей многосоттысячной аудитории, пиарщикам — строчки отчетности по публикациям в топовом компьютерном журнале.
 

Привет!

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

Статистика форума

Темы
384.666
Сообщения
427.695
Пользователи
58.747
Новый пользователь
ivan007

Приложения форума для iOS и Android


У ркн там нет власти ;)
Приватные разговоры
Помощь Пользователи
    Вы не присоединились ни к одной комнате.