Задачи на собеседованиях #211. Задачи от Postgres Professional и награждение победителей от «Лаборатории Касперского»

Когда мы, программисты, думаем (и говорим) о себе, мы всегда представляем себя интеллектуальными личностями, которые постоянно вынуждены заниматься самосовершенствованием и повышением квалификации, ведь этого (и формально так оно и есть) требует от нас постоянно меняющийся мир информационных технологий. Несмотря на эти красивые слова, многие из нас (так, нас точно читают только программисты или здесь и шпионы затесались?) в реальности киснут на монотонной и стереотипной работе, требующей скорее опыта, старого багажа знаний и представления о том, где можно найти решение проблемы, буде она у нас вдруг возникнет. С каждым годом, прожитым после окончания института, нашему мозгу все меньше хочется узнавать новое, переосмысливать узнанное и искать новые пути решения проблем, но это не значит, что мы не должны периодически его заставлять работать на повышенных оборотах. Еще как должны! Мозг тоже мышца :), и без тренировки его функции будут ухудшаться и ухудшаться. Поэтому решай наши задачки ежемесячно, и твой мыслительный орган навсегда останется быстрым, мощным и извилистым :).

Обе компании, которые участвуют в сегодняшнем выпуске, тебе точно известны. Одна — во всех подробностях, вторая — как минимум по одному слову в названии. Слово это — Postgres.

Postgres Professional — относительно небольшая компания, трудится в ней около пятидесяти человек. В ее основе — разработчики известной СУБД PostgreSQL (среди основателей — три ведущих разработчика и активных участника международного сообщества). В 2016 году компания выпустила собственную СУБД Postgres Pro, представляющую собой улучшенную версию PostgreSQL. Передаю им слово!

Как проходит собеседование в компании Postgres Professional

У нас нет многоступенчатых собеседований, психологических тестирований, словом, мы не мучаем кандидатов формальностями, как это встречается в крупных компаниях. Когда человек, который хочет работать в Postgres Professional, приходит на собеседование, с ним разговаривают сразу несколько сотрудников: начальник отдела, куда кандидат устраивается на работу, HR-специалист, представитель высшего руководства, иногда — основатели компании. Решение принимается после одного-двух собеседований, на них обсуждаются различные профессиональные вопросы, в итоге становится понятен и уровень квалификации соискателя, и подходим ли мы друг другу для командной работы.

Конечно, с кандидатами в разработчики мы не просто разговариваем, а даем каждому решить одну-две задачи вроде тех, что предложены сегодня в этой рубрике. И обязательно задаем вопросы практической направленности, предлагаем ответить на типичный клиентский запрос. Какими могут быть эти практические задания? Например, компания оказывает услуги по техподдержке PostgreSQL и нашей собственной разработки — СУБД Postgres Pro. Обычно для систем, которые создаются на базе свободного ПО, поддержка — вопрос проблемный. В России мы единственные, кто ее предоставляет, и для нас это — дело большой важности. Для техподдержки в Postgres Professional выделены специальные сотрудники, а остальные разработчики могут подключаться, когда у клиентов возникают проблемы. Для каждого соискателя мы моделируем ситуацию вроде тех, которые встречаются у заказчиков, и просим найти решение.

Задачи от Postgres Professional

Задача 1

Есть таблицы пользователи usr(id int,name text), друзья friend(usr_id int, friend_usr_id int) и посты post(id int, usr_id int, content text, added timestamptz). Напишите максимально эффективный запрос, возвращающий десять последних постов друзей заданного пользователя (могут быть многочисленные друзья с большим количеством постов в прошлом).

Задача 2

Можно ли в строке, состоящей из символов ( и ), проверить баланс скобок? Как?

Задача 3

Есть большая таблица работников employee(id int, occupation text, sex text). Так получилось, что таблица состоит исключительно из бульдозеристов-мужчин и нянечек-женщин. При эксплуатации выяснилось, что иногда запрос

select 'found' where exists (
  select * from employee
  where occupation=$1 and sex=$2
)

работает очень медленно. Когда это происходит и как этого можно избежать?

Задача 4

Есть таблицы parent(id int) и child(id int, parent_id int references parent(id)). Накладываются ли какие-либо блокировки на строки таблицы parent при добавлении строк в таблицу child? Если да, то какие? Если нет, то почему?

Задача 5

На каком уровне изоляции может выполняться запрос проверки бухгалтерского баланса для получения непротиворечивого результата (предполагается, что операции перевода средств работают корректно):

select sum(
  case when type='debet'  then  amount
       when type='credit' then -amount
  end
) from ledger?

Задача 6

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

with upd as(
  update tusr set name='name2' where id=1 returning 1
),
ins as(
  insert into tusr(id,name)
  select 1, 'name'
  where not exists(select * from upd)
  returning 2
)
select * from ins

Задача 7

Для обеспечения уникальности строк была создана следующая триггерная функция:

create or replace function check_uniq() returns trigger as
$code$
begin
  if exists (select * from tbl t where t.col=new.col) then
    raise exception 'Unique violation';
  end if;
end;
$code$
language plpgsql

Почему такой триггер некорректен? Как его сделать корректным?

Задача 8

Какое сообщение выведет этот блок кода?

do $code$
declare
  ctx text;
begin
  raise sqlstate 'ER001';
exception
  when sqlstate 'ER000' then
    raise notice 'ER000';
  when sqlstate 'ER001' then
    raise notice 'ER001';
end;
$code$

Победители задач от «Лаборатории Касперского»

Вот они, эти мощные парни. Прославим же их всем миром!

1. Octo Xor <oct0xor@gmail.com> — первое место. Эталонные решения! Эксперты ЛК в восторге.
2. Nikolenko Konstantin <knikolenko@yandex.ru> — молодец, все верно, но вторую задачу можно было бы расписать и подробнее.
3. sysenter <sysenter@inbox.ru> — заслуженное третье место.

А пока победители наслаждаются своей заслуженной славой, сувенирами и программами от «Лаборатории Касперского», давай ознакомимся с правильными ответами!

Задание 1 (решение от Константина Николенко)

Ключ: rxrfrf54c5s3t6thbkfekd8b8i5iz2wj

Шифрограмма:

from Crypto.Cipher import AES
import sys
import time
import md5

Quick and dirty solution

def DecryptFile(filename, password):
    inF = open(filename, 'r')
    inData = inF.read()
    inF.close()

    for timestamp in range(1467117929, 1497117929 ):
        PASSWORD_LEN = 32
        password = ''
        ts = timestamp
        alphabet = 'abcdefghijklmnopqrstuvwxyz0123456789'
        for i in range(0, 32):
            password += alphabet[ts % len(alphabet)]
            ts = ( ( ts * 0xB11924E1 ) + 0x27100001 ) >> 8

        aes = AES.new(password, AES.MODE_ECB)
        outData = aes.decrypt(inData)

        pad = ord(outData[-1])
        padStart = len(outData) - pad
        good = 1

        if ( padStart <= 0 ) or ( pad < 16 ) :
            good = 0
        else:
            for i in range(padStart, padStart+pad):
                if ( ord(outData[i]) != pad ):
                    good = 0
                    break
        if good == 1:
            print 'Password: ' + password

    outData = outData[:-ord(outData[-1])]

    decryptedFileName = filename + '.dec'
    outF = open(decryptedFileName, 'w')
    outF.write(outData)
    outF.close()

    print 'Written ' + decryptedFileName

def EncryptFile(filename):
    PASSWORD_LEN = 32
    password = ''
    ts = int(time.time())
    alphabet = 'abcdefghijklmnopqrstuvwxyz0123456789'
    for i in range(0, 32):
        password += alphabet[ts % len(alphabet)]
        ts = ( ( ts * 0xB11924E1 ) + 0x27100001 ) >> 8

    print 'Password: ' + password

    inF = open(filename, 'r')
    inData = inF.read()
    inF.close()

    length = 32 - (len(inData) % 16)
    inData += chr(length)*length

    aes = AES.new(password, AES.MODE_ECB)
    outData = aes.encrypt(inData)

    encryptedFileName = filename + '.enc'
    outF = open(encryptedFileName, 'w')
    outF.write(outData)
    outF.close()

    print 'Written ' + encryptedFileName

if ( len(sys.argv) <= 1 ):
    print 'Usage:\n -e encrypt_file_name\n -d decrypt_file_name password\n'
    exit(0)

if ( sys.argv[1] == '-d' ) :
    if ( len(sys.argv) < 4 ) :
        print 'Need filename and password\n'
        exit(1)
    DecryptFile(sys.argv[2], sys.argv[3])

if ( sys.argv[1] == '-e' ) :
    if ( len(sys.argv) < 3 ) :
        print 'Need filename\n'
        exit(1)
    EncryptFile(sys.argv[2])

Задание 2 (решение от Octo Xor)

0x78 байт в шапке, значит, шелл-код сжат злибом. Качаем offzip с сайта автора, делаем:

offzip -z 0 backup_001337.BIN uncompresed 0x200

Загружаем бинарник в IDA Pro/Starter/Demo и видим:

seg000:00000021  loc_21:
seg000:00000021  mov  esi, [edx+28h] // Ищем модуль kernel32
seg000:00000024  mov  eax

seg000:00000055  cmp  dword ptr [eax], 905A4Dh // Проверяем хидер

seg000:00000087  mov  [ebp+var_4], eax
seg000:0000008A  mov  [ebp+var_8], 7373h
seg000:00000091  mov  [ebp+var_C], 65726464h
seg000:00000098  mov  [ebp+var_10], 41636F72h
seg000:0000009F  mov  [ebp+var_14], 50746547h
seg000:000000A6  lea  esi, [ebp+var_14]
seg000:000000A9  push esi
seg000:000000AA  push eax
seg000:000000AB  call sub_10B // Получаем адрес GetProcAddress
seg000:00000087  mov  [ebp+var_4], eax
seg000:0000008A  mov  [ebp+var_8], 7373h
seg000:00000091  mov  [ebp+var_C], 65726464h
seg000:00000098  mov  [ebp+var_10], 41636F72h
seg000:0000009F  mov  [ebp+var_14], 50746547h
seg000:000000A6  lea  esi, [ebp+var_14]
seg000:000000A9  push esi
seg000:000000AA  push eax
seg000:000000AB  call sub_10B // Получаем адрес LoadLibraryA
seg000:000001E5  mov  dword ptr [ecx+8], 72657375h
seg000:000001EC  mov  dword ptr [ecx+0Ch], 3233h
seg000:000001F3  push ecx
seg000:000001F4  push ecx
seg000:000001F5  add  [esp+48h+var_48], 8
seg000:000001F9  mov  esi, ecx
seg000:000001FB  call dword ptr [ecx+4] // Грузим модуль user32

seg000:00000207  mov  edi, eax
seg000:00000209  lea  esi, [esi-0Ch] // MessageBoxA
seg000:0000020C  push esi
seg000:0000020D  push edi
seg000:0000020E  call dword ptr [ecx] // GetProcAddress

seg000:0000022D  loc_22D: ; CODE XREF: sub_177+BB j
seg000:0000022D  xor  byte ptr [edx], 31h
seg000:00000230  inc  edx
seg000:00000231  dec  ecx
seg000:00000232  jnz  short loc_22D // Анксорим «Hello good people!»
seg000:00000234  pop  edx
seg000:00000235  pop  ecx
seg000:00000236  push 0
seg000:00000238  push 0
seg000:0000023A  push edx
seg000:0000023B  push 0
seg000:0000023D  call eax // Выводим на экран при помощи MessageBoxA

Для тех, кто не любит читать даже откомментированный код :), Константин Николенко суммирует: «Получаем шелл-код, выводящий MessageBox с текстом Hello good people!. В шелл-коде перед вызовом MessageBox имеется INT 3 без обработчика SEH/VEH».