Вот часто пишут, что задачи на собеседованиях оторваны от реальности. Я решил хоть на толику разрушить этот миф и опубликовать парочку вопросов, с которыми сталкивался по работе. Изначально я про них никому не рассказывал, думая, что вот когда-нибудь стану сениором-помидором и буду такой важный задавать хитрые задачки. Сейчас я не уверен, что хочу следовать этим путём, поэтому пусть хоть кто-то поломает голову =)
1. Имеется API с векторной графикой со всеми обычными функциями: moveTo, lineTo и т.д. На вход подаётся объект типа "холст", угол и шаг. В результате работы алгоритма холст должен быть заштрихован линиями, идущими с заданным шагом и под заданным углом. Шаг произвольный, угол произвольный.
2. Имеются две программы: клиент и сервер. Клиент общается с сервером через TCP/IP и одновременно пишет в сетевую файловую систему (NFS), которая физически расположена на той же машине, что и серверный процесс. Таким образом получается два типа очень активного траффика: прикладной и NFS. Прикладной трафик является очень важным и должен доходить до сервера с минимальными задержками, трафик NFS тоже является важным, но время тут некритично, важно, чтобы данные в конечном итоге были записаны. Так же важно, что клиенту нельзя создавать параллельные потоки из-за наличия GIL, но можно использовать неблокирующийся ввод/вывод. Характер работы NFS таков, что данные сперва пишутся в локальный буфер, и когда он накапливается, содержимое буфера отсылается по сети, и происходит запись в файловую систему. Настроить параметры этого процесса практически невозможно, и это становится проблемой — в момент, когда данные из буфера пересылаются по сети, процесс клиента блокируется на непозволительно долгое время. Задачу нужно решить с минимальными модификациями.
Сразу скажу, что решение я публиковать не буду. Но если кто-то решит тем способом, что решил я, я об этом сообщу. Могу лишь сказать, что у первой задачи есть поистине красивое с точки зрения кодирования решение, которое можно уместить буквально в несколько строк. Вторая задача не такая сложная, поэтому я ожидаю, что многие её быстро решат, но мне, опять же, понравилась простота решения. Что интересно, в отличие от первой задачи, изящное решение которой я нашёл просто от нечего делать, решение второй задачи было обусловлено именно такой постановкой: внезпно и вероломно обрушившийся говнокод стал причиной того, что робот зависал
, и мне так и сказали: "Рефакторить нет времени и вообще ты нам ещё тут пояснишь потом за технический дизайн, а сейчас быстро запилил мне однострочник, который решит проблему"
Здравствуйте, cppguard, Вы писали:
C>Вот часто пишут, что задачи на собеседованиях оторваны от реальности. Я решил хоть на толику разрушить этот миф и опубликовать парочку вопросов, с которыми сталкивался по работе. Изначально я про них никому не рассказывал, думая, что вот когда-нибудь стану сениором-помидором и буду такой важный задавать хитрые задачки. Сейчас я не уверен, что хочу следовать этим путём, поэтому пусть хоть кто-то поломает голову =)
1 — это какой-то стандартный алгоритм, еще турбо паскаль умел в заливку многоугольников.
2 — клиент шлет файлы на сервер через тот же TCP/IP и уже сервер пишет их в NFS (или в локальный каталог, я не очень хорошо знаком с NFS)?
C>1. Имеется API с векторной графикой со всеми обычными функциями: moveTo, lineTo и т.д.
А можно для тех кто не очень знаком к векторной графикой перечислить эти функции?
C>В результате работы алгоритма холст должен быть заштрихован линиями, идущими с заданным шагом и под заданным углом.
Не очень понятно что значит заштрихован.
Линии под углом, от одного края до другого?
вот так?
Здравствуйте, scf, Вы писали:
scf>1 — это какой-то стандартный алгоритм, еще турбо паскаль умел в заливку многоугольников.
Залить и заштриховать это разные вещи.
scf>2 — клиент шлет файлы на сервер через тот же TCP/IP и уже сервер пишет их в NFS (или в локальный каталог, я не очень хорошо знаком с NFS)?
Для клиента NFS выглядит как обычная файловая система, соответственно, чтение и запись файлов происходит через стандартные для этого функции. Данные на сервер отправляет драйвер NFS.
C>1. Имеется API с векторной графикой со всеми обычными функциями: moveTo, lineTo и т.д. На вход подаётся объект типа "холст", угол и шаг. В результате работы алгоритма холст должен быть заштрихован линиями, идущими с заданным шагом и под заданным углом. Шаг произвольный, угол произвольный.
Представление холста какое?
Если пиксельное, то алгоритм Брезенхема.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
C>>1. Имеется API с векторной графикой со всеми обычными функциями: moveTo, lineTo и т.д. LVV>Представление холста какое?
Векторное же. Грубо говоря задача сводится к расчёту точек пересечений линий и canvas bounding box
Здравствуйте, cppguard, Вы писали:
C>1. Имеется API с векторной графикой со всеми обычными функциями: moveTo, lineTo и т.д. На вход подаётся объект типа "холст", угол и шаг. В результате работы алгоритма холст должен быть заштрихован линиями, идущими с заданным шагом и под заданным углом. Шаг произвольный, угол произвольный.
Холст прямоугольный? Зная угол и шаг, найти шаги по горизонтальной/вертикальной границе и шагать.
Здравствуйте, CreatorCray, Вы писали:
CC>Векторное же. Грубо говоря задача сводится к расчёту точек пересечений линий и canvas bounding box
Всё верно. Соль в том, что в зависимости от угла наклона линий точки концов одной линии могут быть располагаться как на соседних сторонах прямоугольника, так и на противоположных.
Здравствуйте, Ip Man, Вы писали:
IM>Холст прямоугольный? Зная угол и шаг, найти шаги по горизонтальной/вертикальной границе и шагать.
Верно, но концы одной линии могут оказаться как на соседних сторонах, так и на противоположных. Я сначала такое решение и написал, и столкнулся с тем, что слишком много if-ов было.
Здравствуйте, cppguard, Вы писали:
C>Всё верно. Соль в том, что в зависимости от угла наклона линий точки концов одной линии могут быть располагаться как на соседних сторонах прямоугольника, так и на противоположных.
Это как раз не проблема вовсе: считаешь оба пересечения, берёшь ближайшее.
Здравствуйте, cppguard, Вы писали:
C>2. Имеются две программы: клиент и сервер. Клиент общается с сервером через TCP/IP и одновременно пишет в сетевую файловую систему (NFS), которая физически расположена на той же машине, что и серверный процесс. Таким образом получается два типа очень активного траффика: прикладной и NFS. Прикладной трафик является очень важным и должен доходить до сервера с минимальными задержками, трафик NFS тоже является важным, но время тут некритично, важно, чтобы данные в конечном итоге были записаны.
Можно, например, написать клиента NFS: https://github.com/Cyberax/go-nfs-client — это примерно так 500 строк кода на Питоне, не считая сгенерированного кода RPC-обёрток. Или взять готового (есть обёртки для libnfs).
Ну а дальше просто на прикладном уровне делать rate-limit/приоритизацию для трафика.
Здравствуйте, cppguard, Вы писали:
C>2. Имеются две программы: клиент и сервер. Клиент общается с сервером через TCP/IP и одновременно пишет в сетевую файловую систему (NFS), которая физически расположена на той же машине, что и серверный процесс. Таким образом получается два типа очень активного траффика: прикладной и NFS. Прикладной трафик является очень важным и должен доходить до сервера с минимальными задержками, трафик NFS тоже является важным, но время тут некритично, важно, чтобы данные в конечном итоге были записаны. Так же важно, что клиенту нельзя создавать параллельные потоки из-за наличия GIL, но можно использовать неблокирующийся ввод/вывод. Характер работы NFS таков, что данные сперва пишутся в локальный буфер, и когда он накапливается, содержимое буфера отсылается по сети, и происходит запись в файловую систему. Настроить параметры этого процесса практически невозможно, и это становится проблемой — в момент, когда данные из буфера пересылаются по сети, процесс клиента блокируется на непозволительно долгое время. Задачу нужно решить с минимальными модификациями.
Вроде это не про программирование как таковое, т.к. тут писать ничего не надо. У NFS и основного траффика будут разные порты, хотя и один и тот же хост назначения. Значит всё это довольно легко и просто решается через правила iptables или что там на машине вместо него.
Здравствуйте, kaa.python, Вы писали:
KP>Вроде это не про программирование как таковое, т.к. тут писать ничего не надо. У NFS и основного траффика будут разные порты, хотя и один и тот же хост назначения. Значит всё это довольно легко и просто решается через правила iptables или что там на машине вместо него.
Разбираемся. Во-первых, iptables, как и любой другой firewall, не позволяет настроить приоритезацию трафика. Это можно сделать в ядре, поменяв queuing discipline. Но проблема остаётся — запись в файл и запись прикладных данных в порт не могут быть параллельными, потому что GIL, и очередной вызов write(2) может вызвать сброс буфера NFS, что приведёт к долгой паузе.
Здравствуйте, Cyberax, Вы писали:
C>Можно, например, написать клиента NFS: https://github.com/Cyberax/go-nfs-client — это примерно так 500 строк кода на Питоне, не считая сгенерированного кода RPC-обёрток. Или взять готового (есть обёртки для libnfs).
C>Ну а дальше просто на прикладном уровне делать rate-limit/приоритизацию для трафика.
Переписать в нуля это всегда универсальное решение, если вы не FAANG, где можно бросить целый отдел на написание и поддержку библиотеки, то, увы, на практике оно непременимо.
Здравствуйте, CreatorCray, Вы писали:
C>>Всё верно. Соль в том, что в зависимости от угла наклона линий точки концов одной линии могут быть располагаться как на соседних сторонах прямоугольника, так и на противоположных. CC>Это как раз не проблема вовсе: считаешь оба пересечения, берёшь ближайшее.
Ну так-то да =) Но это решение в лоб с переходом от целых чисел к дробным, ещё нужно аккуратно посчитать округление и протестировать все условные переходы.
Здравствуйте, cppguard, Вы писали:
C>Переписать в нуля это всегда универсальное решение, если вы не FAANG, где можно бросить целый отдел на написание и поддержку библиотеки, то, увы, на практике оно непременимо.
Зависит. Некоторые вещи можно делать даже в одно рыло.
Здравствуйте, cppguard, Вы писали:
C>Разбираемся. Во-первых, iptables, как и любой другой firewall, не позволяет настроить приоритезацию трафика. Это можно сделать в ядре, поменяв queuing discipline. Но проблема остаётся — запись в файл и запись прикладных данных в порт не могут быть параллельными, потому что GIL, и очередной вызов write(2) может вызвать сброс буфера NFS, что приведёт к долгой паузе.
В iptables ты можешь использоваться (hash)limit и отбрасывать часть пакетов NFS что даст преимущество твоему стандартному трафику. GIL всегда легко обходился через multiprocessing, куда вполне можно затолкать записать в/из файла и сокеты в NFS. Это, конечно, кривое решение, но ты же сам просил самое короткое, правильные тебе не нравятся
Здравствуйте, cppguard, Вы писали:
C>1. Имеется API с векторной графикой со всеми обычными функциями: moveTo, lineTo и т.д. На вход подаётся объект типа "холст", угол и шаг. В результате работы алгоритма холст должен быть заштрихован линиями, идущими с заданным шагом и под заданным углом. Шаг произвольный, угол произвольный.
Тут должно быть просто: надо рассчитать шаг по x и по y и с этими шагами пройти по периметру прямоугольника... Только не понятно, что за шаг задан на входе? Расстояние между линиями? Тогда один шаг — это синус угла, второй — косинус, ну и цикл "по периметру"...
C>2. Имеются две программы: клиент и сервер. Клиент общается с сервером через TCP/IP и одновременно пишет в сетевую файловую систему (NFS), которая физически расположена на той же машине, что и серверный процесс. Таким образом получается два типа очень активного траффика: прикладной и NFS. Прикладной трафик является очень важным и должен доходить до сервера с минимальными задержками, трафик NFS тоже является важным, но время тут некритично, важно, чтобы данные в конечном итоге были записаны. Так же важно, что клиенту нельзя создавать параллельные потоки из-за наличия GIL, но можно использовать неблокирующийся ввод/вывод. Характер работы NFS таков, что данные сперва пишутся в локальный буфер, и когда он накапливается, содержимое буфера отсылается по сети, и происходит запись в файловую систему. Настроить параметры этого процесса практически невозможно, и это становится проблемой — в момент, когда данные из буфера пересылаются по сети, процесс клиента блокируется на непозволительно долгое время. Задачу нужно решить с минимальными модификациями.
Просто в вставить вызов flush() после каждой записи данных на NFS.
