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

Здравствуйте, sergey2b, Вы писали:

S>несколько хороших задачь которымиможно заменить разоворот списка
Уф, щас опять этот срач начнётся по новой.
Поищи лучше по форумам, каждый год эта тема всплывает с одними и теми же результатами.

Здравствуйте, sergey2b, Вы писали:

S>несколько хороших задачь которымиможно заменить разоворот списка

Хорошая задачка, зачем заменять?

Но вот к примеру, выпендриться: напишите на доске функцию, которая считает арифметическое выражение и печатает результат.

String calculate(String expression).

Пример входных значений: "2+2", "2*2", "2+3*2".

S>несколько хороших задачь которымиможно заменить разоворот списка

1. Найти смещение знакоместа в видеопамяти (для текстового режима — так проще). Количество знакомест в строке — константа (скажем, 80). Одно знакоместо — один байт. Операцию умножения — не использовать.
странное дело, но мало кто может решить из тех, с кем я сталкивался

2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

Здравствуйте, xarcass, Вы писали:

X>1. Найти смещение знакоместа в видеопамяти (для текстового режима — так проще). Количество знакомест в строке — константа (скажем, 80). Одно знакоместо — один байт. Операцию умножения — не использовать.
X> странное дело, но мало кто может решить из тех, с кем я сталкивался

Константа произвольно задаваемая, или 80?

offset = row * 80 + col. row * 80 = row * 64 + row * 16 = row << 6 + row << 4. Такой алгоритм предполагается?

vsb>Константа произвольно задаваемая, или 80?

Конечно любая — можно даже нечётную. Смысл не меняется.

vsb>offset = row * 80 + col. row * 80 = row * 64 + row * 16 = row << 6 + row << 4. Такой алгоритм предполагается?

Конечно. Удивительно то, как много матёрых перцев на этом буксуют.

Здравствуйте, Тёмчик, Вы писали:
Это задачка из К и Р

И человек знающий про обратную польскую Наталию решит ее за недолго

Здравствуйте, xarcass, Вы писали:

vsb>>Константа произвольно задаваемая, или 80?

X>Конечно любая — можно даже нечётную. Смысл не меняется.

vsb>>offset = row * 80 + col. row * 80 = row * 64 + row * 16 = row << 6 + row << 4. Такой алгоритм предполагается?

X>Конечно. Удивительно то, как много матёрых перцев на этом буксуют.

Просто они не желают вникать, что именно за херню у них попросили решить.
По-моему опыту более 90% кандидатов, увидев такие задачки на собеседовании, тут же выключают мозг.
Настолько, что даже не желают парсить чего конкретно за условия задачи и к чему это всё можно свести.
Оставшиеся 10% делятся на две группы, ни одну из которых на работу лучше никогда не нанимать.

Здравствуйте, Тёмчик, Вы писали:

Тё>Здравствуйте, sergey2b, Вы писали:

S>>несколько хороших задачь которымиможно заменить разоворот списка

Тё>Хорошая задачка, зачем заменять?

Именно так, дураков с идиотами должно быть видно из далека
Спросили подобное — встаёшь и уходишь. А в современно мире, просто «кладёшь трубку» и идёшь общаться с другими.

Здравствуйте, xarcass, Вы писали:

X>Конечно. Удивительно то, как много матёрых перцев на этом буксуют.

Такая задача к матёрости не имеет никакого отношения. Просто говорит о наличии специфического опыта.

Здравствуйте, a7d3, Вы писали:

A>Настолько, что даже не желают парсить чего конкретно за условия задачи и к чему это всё можно свести.
A>Оставшиеся 10% делятся на две группы, ни одну из которых на работу лучше никогда не нанимать.

Что за группы? Получается, ты не возьмёшь человека за знание сдвига?

Сдвиг обычно знают те, кто имеет опыт работы
1. с битовыми операцими
2. низкоуровневыми оптимизациями

Почему таких людей не надо нанимать?

Здравствуйте, xarcass, Вы писали:

vsb>>offset = row * 80 + col. row * 80 = row * 64 + row * 16 = row << 6 + row << 4. Такой алгоритм предполагается?

X>Конечно. Удивительно то, как много матёрых перцев на этом буксуют.

Кто на 8080 не программировал, те и буксуют.

Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, a7d3, Вы писали:

A>>Настолько, что даже не желают парсить чего конкретно за условия задачи и к чему это всё можно свести.
A>>Оставшиеся 10% делятся на две группы, ни одну из которых на работу лучше никогда не нанимать.

I>Что за группы? Получается, ты не возьмёшь человека за знание сдвига?

I>Сдвиг обычно знают те, кто имеет опыт работы
I>1. с битовыми операцими
I>2. низкоуровневыми оптимизациями

I>Почему таких людей не надо нанимать?

Хорошие специалисты относятся к тем 90%, у кого мозг выключается сразу же, как только на собеседовании начинают тратить их время на такие вот задачки.
Если же человек готов тратить время на эту мутоту, то значит он изрядно неуверен в себе и полагает, что слабо востребован на рынке труда, в силу тех или иных обстоятельств.

Здравствуйте, a7d3, Вы писали:

I>>Почему таких людей не надо нанимать?

A>Хорошие специалисты относятся к тем 90%, у кого мозг выключается сразу же, как только на собеседовании начинают тратить их время на такие вот задачки.

Непонятно, что это за специалист, у которого мозг выключается

A>Если же человек готов тратить время на эту мутоту, то значит он изрядно неуверен в себе и полагает, что слабо востребован на рынке труда, в силу тех или иных обстоятельств.

Битовые операции никакая не мутота. Оптимизации, протоколы, низкоуровневая работа с данными, системные функции — это неполный список того, где битовые операции не редкость.

Здравствуйте, xarcass, Вы писали:

S>>несколько хороших задачь которымиможно заменить разоворот списка

X>1. Найти смещение знакоместа в видеопамяти (для текстового режима — так проще). Количество знакомест в строке — константа (скажем, 80). Одно знакоместо — один байт. Операцию умножения — не использовать.
X> странное дело, но мало кто может решить из тех, с кем я сталкивался

X>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

Организация занимается написанием драйверов или микрокода для GPU?

Здравствуйте, xarcass, Вы писали:

S>>несколько хороших задачь которымиможно заменить разоворот списка

X>1. Найти смещение знакоместа в видеопамяти (для текстового режима — так проще). Количество знакомест в строке — константа (скажем, 80). Одно знакоместо — один байт. Операцию умножения — не использовать.
X> странное дело, но мало кто может решить из тех, с кем я сталкивался

X>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

Только такие задачки нужно задавать в определенном контексте.
Ну то есть кандидату совсем неочевидно, почему "Операцию умножения — не использовать". И сходу хочется объяснить постановку задачи "придурью интервьювера"
А вот если сказать "операция критична по времени" — все сразу ясно.

С поворотами — тоже не все хорошо. Формулу поворота помнят не только лишь все. Ее придется выводить прямо на собеседовании.

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

Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, a7d3, Вы писали:

A>>Если же человек готов тратить время на эту мутоту, то значит он изрядно неуверен в себе и полагает, что слабо востребован на рынке труда, в силу тех или иных обстоятельств.

I>Битовые операции никакая не мутота. Оптимизации, протоколы, низкоуровневая работа с данными, системные функции — это неполный список того, где битовые операции не редкость.

И надо быть редкостным идиотом, чтобы проверять умение этим пользоваться во время интервью-собеседования
Подбор и найм людей не сводится к тому, чтобы взять и сравнить между собой кандидатов. Каждый год, последние 20 лет, подрастает очередное поколение, которое спотыкается на этом простом моменте.

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

Здравствуйте, Gradiens, Вы писали:

G>Здравствуйте, xarcass, Вы писали:

S>>>несколько хороших задачь которымиможно заменить разоворот списка

X>>1. Найти смещение знакоместа в видеопамяти (для текстового режима — так проще). Количество знакомест в строке — константа (скажем, 80). Одно знакоместо — один байт. Операцию умножения — не использовать.
X>> странное дело, но мало кто может решить из тех, с кем я сталкивался

X>>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

G>Только такие задачки нужно задавать в определенном контексте.
G>Ну то есть кандидату совсем неочевидно, почему "Операцию умножения — не использовать". И сходу хочется объяснить постановку задачи "придурью интервьювера"
G>А вот если сказать "операция критична по времени" — все сразу ясно.

G>С поворотами — тоже не все хорошо. Формулу поворота помнят не только лишь все. Ее придется выводить прямо на собеседовании.

G>В общем, задачи конечно интересные, но их нужно давать только в контексте поиска человека, который в работе должен жонглировать битовыми масками и выполнять другую акробатику. И при этом заранее озвучив, что вам нужно именно максимально эффективное по времени решение.


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

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

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

Например, прочитав сообщение, я вспомнил, про то, что изучал что-то похожее, когда был студентом, но потом на практике не использовал. А могу и не вспомнить про то, что изучал, но не использовал. А получится ли самому додуматься до оптимального решения или нет — не знаю.

Здравствуйте, a7d3, Вы писали:

A>И надо быть редкостным идиотом, чтобы проверять умение этим пользоваться во время интервью-собеседования

Ну вот пришел к тебе товарищ, что заявляется экспертом по всякому низкоуровневому программированию, опыт в эмбеде и тд, и не может битовые операции.
Как быть? Простить, поощрить, дать глянуть конспект?

A>Подбор и найм людей не сводится к тому, чтобы взять и сравнить между собой кандидатов. Каждый год, последние 20 лет, подрастает очередное поколение, которое спотыкается на этом простом моменте.
A>Каждый год подрастает очередная волна имбецилов, которые не осознают, что интервью-собеседование это не то самое, когда даёшь человеку задачки и смотришь как он с ними справляется. Крики, вопли, брызганье слюной по этому вопросу всегда сводятся к простой вещи — эти имбецилы понятия не имеют, а как ещё можно проводить собеседование и как вообще людей подбирать-нанимать

А как нужно интервью и что еще есть кроме как сравнить кандидатов?

Здравствуйте, a7d3, Вы писали:

A>Хорошие специалисты относятся к тем 90%, у кого мозг выключается сразу же, как только на собеседовании начинают тратить их время на такие вот задачки.
A>Если же человек готов тратить время на эту мутоту, то значит он изрядно неуверен в себе и полагает, что слабо востребован на рынке труда, в силу тех или иных обстоятельств.

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

Идеально — набрать тех, кто хотя бы имеет привычку иногда мозг включать.

Здравствуйте, Тёмчик, Вы писали:

Тё>Но вот к примеру, выпендриться: напишите на доске функцию, которая считает арифметическое выражение и печатает результат.
Это как раз именно что для выпендриться.

Здравствуйте, xarcass, Вы писали:

X>Операцию умножения — не использовать.
А сдвиги или LEA использовать можно?

Здравствуйте, a7d3, Вы писали:

A>И надо быть редкостным идиотом, чтобы проверять умение этим пользоваться во время интервью-собеседования
А никто не проверяет умение. Проверяют способность применять имеющиеся знания для генерации алгоритма решения задачи.
Грубо говоря это тест на наличие инженерного мышления.

AN>Для поворота картинки нужно использовать матрицы поворота. Но наверняка есть библиотеки, в которых это реализовано и задача, скорее на понимание работы с графикой.

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

AN>Но такие задания имеет смысл давать, если это связано с рабочими задачами.

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

зы. если что — с реверса списка тема и началась

G>С поворотами — тоже не все хорошо. Формулу поворота помнят не только лишь все. Ее придется выводить прямо на собеседовании.

G>В общем, задачи конечно интересные, но их нужно давать только в контексте поиска человека, который в работе должен жонглировать битовыми масками и выполнять другую акробатику. И при этом заранее озвучив, что вам нужно именно максимально эффективное по времени решение.

Какая там формула может быть? Школьная тригонометрия. Задача из реальной жизни. Люди писали карточную игру (довольно давно). Надо было сделать анимацию вращения спрайта карты. Промежуточные состояния генерировались прямо во время анимации — на лету. Причём на палме, у которого процессор дохлее тех, что сейчас в клавиатуры ставят (и без плавающей точки заодно). И ничего сделали. Но немного побуксовали — есть там одна тонкость, но её не понять, пока не попробуешь.

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, a7d3, Вы писали:

A>>И надо быть редкостным идиотом, чтобы проверять умение этим пользоваться во время интервью-собеседования
CC>А никто не проверяет умение. Проверяют способность применять имеющиеся знания для генерации алгоритма решения задачи.
CC>Грубо говоря это тест на наличие инженерного мышления.

Этот тест не работает, потому что люди давно научились его обманывать. Появилась цела когорта таких обманщиков — хорошо показывают себя на решении подобных задач во время собеседований, но при этом неспособны работать. Таких специалистов называют рыбами лазающими по деревьям.

Здравствуйте, alzt, Вы писали:

A>Здравствуйте, a7d3, Вы писали:

A>>Хорошие специалисты относятся к тем 90%, у кого мозг выключается сразу же, как только на собеседовании начинают тратить их время на такие вот задачки.
A>>Если же человек готов тратить время на эту мутоту, то значит он изрядно неуверен в себе и полагает, что слабо востребован на рынке труда, в силу тех или иных обстоятельств.

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

Это не работает. Потому что хороший специалист не станет тренироваться решать задачки на собеседованиях, а тот человек, который работать не умеет и ничего из себя не представляет — будет смотреться замечательно на фоне всех остальных. Поскольку у него выбора иного нету.

Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, a7d3, Вы писали:

A>>И надо быть редкостным идиотом, чтобы проверять умение этим пользоваться во время интервью-собеседования

I>Ну вот пришел к тебе товарищ, что заявляется экспертом по всякому низкоуровневому программированию, опыт в эмбеде и тд, и не может битовые операции.
I>Как быть? Простить, поощрить, дать глянуть конспект?

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

I>А как нужно интервью и что еще есть кроме как сравнить кандидатов?

В первую очередь стоит задуматься, а с чего вдруг эта идея возникла — сравнивать кандидатов между собой?
Какая цепочка рассуждений с доводами и аргументами привела к такому ложному выводу?

Здравствуйте, xarcass, Вы писали:

AN>>Но такие задания имеет смысл давать, если это связано с рабочими задачами.

X>Кто в своей повседневной работе использовал разворот односвязного списка — пусть первый бросит в меня камень.

Что такое "в повседневной работе"? По десять раз на дню?
У нас в программе использовались односвязные списки. На основе стандартного вектора, с хранением удаленных элементов, с поддержкой Undo/Redo.
Использовались для хранения полигонов, проводников на печатной плате.
При объединении пары списков один из них нужно развернуть.

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

Получи камень!

Здравствуйте, sergey2b, Вы писали:

S>Здравствуйте, Тёмчик, Вы писали:
S>Это задачка из К и Р

S>И человек знающий про обратную польскую Наталию решит ее за недолго

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

Здравствуйте, a7d3, Вы писали:

S>>>несколько хороших задачь которымиможно заменить разоворот списка

Тё>>Хорошая задачка, зачем заменять?

A>Именно так, дураков с идиотами должно быть видно из далека
A>Спросили подобное — встаёшь и уходишь. А в современно мире, просто «кладёшь трубку» и идёшь общаться с другими.

Ну если ищется по принципу "5 за пучок", да. А на серьезные задачи будь добр хотя бы первый курс института осилить (разворот списка).

Здравствуйте, CreatorCray, Вы писали:

Тё>>Но вот к примеру, выпендриться: напишите на доске функцию, которая считает арифметическое выражение и печатает результат.
CC>Это как раз именно что для выпендриться.

Ну можно кидать подсказки, начать с простых вводов (без приоритета операций). Неужели ты в работе ни разу с задачей преобразовать выражение не сталкивался? Чем ты вообще занимаешься?

Здравствуйте, Тёмчик, Вы писали:

Тё>Здравствуйте, sergey2b, Вы писали:

S>>Здравствуйте, Тёмчик, Вы писали:
S>>Это задачка из К и Р

S>>И человек знающий про обратную польскую Наталию решит ее за недолго

Тё>Алгоритм Дейкстры для преобразования в польскую нотацию.


У нас на первом курсе было домашнее задание написать на Паскале калькулятор

Здравствуйте, Тёмчик, Вы писали:

CC>>Это как раз именно что для выпендриться.
Тё>Ну можно кидать подсказки, начать с простых вводов (без приоритета операций).
Да пофигу. Это в общем случае плохая задача для собеседования.

Тё>Неужели ты в работе ни разу с задачей преобразовать выражение не сталкивался?
Дитятко, у меня уже давно есть свой калькулятор с формулами и функциями, считает в big number fractions
И компилятор я писал ещё более давно, вместе с виртуальной машиной для пошаговой отладки для железки под которую это всё должно было работать.

Тё> Чем ты вообще занимаешься?
Системшиной.

Здравствуйте, a7d3, Вы писали:

A>Этот тест не работает, потому что люди давно научились его обманывать.
Потому что применять его тоже надо умеючи а не как Артёмка пару лет назад, когда он про тест услышал а про что он собственно тестирует и на что надо смотреть — нет.
Решение как таковое никого не интересует, интересует рассуждение в процессе решения, потому что это не вопрос — ответ а повод поговорить, спросить об альтернативных вариантах решения той же задачи. Потому переворот списка плохая задача — там в общем то одно нормальное решение, можно придумать пачку плохих, как в той байке про барометры но лучше таки взять другую задачу, которую можно решить множеством способов.

Здравствуйте, xarcass, Вы писали:

X>Если представить, что у нас есть просто массив байтов (условно двумерный), то для того, чтобы его попиксельно повернуть достаточно базовых знаний тригонометрии.
Если делать в лоб то будут глюки типа tearing.

X>Кто в своей повседневной работе использовал разворот односвязного списка — пусть первый бросит в меня камень.
От меня щас прилетит пару вёдер камней.
В системщине односвязные списки используются весьма часто, одна из причин — вставка "в голову" делается атомарно, не приходя в сознание.

Здравствуйте, CreatorCray, Вы писали:

X>>Операцию умножения — не использовать.
CC>А сдвиги или LEA использовать можно?

lea — это первый приз.

CC>Если делать в лоб то будут глюки типа tearing.

Пять баллов! Тут и буксовали. А надо было просто заменить "в лоб" на "по лбу"

X>>Кто в своей повседневной работе использовал разворот односвязного списка — пусть первый бросит в меня камень.
CC>От меня щас прилетит пару вёдер камней.
CC>В системщине односвязные списки используются весьма часто, одна из причин — вставка "в голову" делается атомарно, не приходя в сознание.

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

Здравствуйте, CreatorCray, Вы писали:

Тё>>Неужели ты в работе ни разу с задачей преобразовать выражение не сталкивался?
CC>Дитятко, у меня уже давно есть свой калькулятор с формулами и функциями, считает в big number fractions

У меня были реально задачи разобрать выражение и построить дерево индикаторов (с зависимостями) и другая- разобрать regexp и потом отсортировать результаты по приоритету по количеству matched сегментов. Дедуля.

CC>И компилятор я писал ещё более давно, вместе с виртуальной машиной для пошаговой отладки для железки под которую это всё должно было работать.
Может, ты там только кирпичи подносил, а написал другой человек? Судя по твоему пригару на несложные задачки.

Тё>> Чем ты вообще занимаешься?
CC>Системшиной.

Т.е. любую минимальную логику держат в usermode (и это правильно), а у тебя профессиональная деформация?

Здравствуйте, xarcass, Вы писали:

CC>>Если делать в лоб то будут глюки типа tearing.

X>Пять баллов! Тут и буксовали. А надо было просто заменить "в лоб" на "по лбу"

Что за бред? С какого боку тут tearing? Нужно аффинное преобразование. А это умножение матриц. Быстро умножать матрицы- отдельная, большая (больная) тема.

Здравствуйте, sergey2b, Вы писали:

S>У нас на первом курсе было домашнее задание написать на Паскале калькулятор

Ну вот, 1 курс. В принципе, наверное это неплохое несложное задание на дом для фулстек (вместе с гуем), на отсев неадекватов.

Здравствуйте, Тёмчик, Вы писали:

Тё>У меня были реально задачи разобрать выражение и построить дерево индикаторов (с зависимостями) и другая- разобрать regexp и потом отсортировать результаты по приоритету по количеству matched сегментов.
meh

CC>>И компилятор я писал ещё более давно, вместе с виртуальной машиной для пошаговой отладки для железки под которую это всё должно было работать.
Тё>Может, ты там только кирпичи подносил, а написал другой человек?
Я это всё в одно рыло написал.

Тё>>> Чем ты вообще занимаешься?
CC>>Системшиной.
Тё>Т.е. любую минимальную логику держат в usermode
Сразу видно ыксперта.

Хотел напрыгнуть но промахнулся и плюхнулся в лужу? Обтекай молча.

Здравствуйте, xarcass, Вы писали:

X>А надо было просто заменить "в лоб" на "по лбу"
И таки ведь да.
Я подобной графикой в до-аккселераторные времена занимался. Романтика пёрла просто атас. Особенно когда в итоге оно не тормозило. А теперь не интересно уже — всё есть готовое.

X>Ну мне вот за более чем 30 лет стажа разворачивать список понадобилось ни разу.
Да просто у меня задачи специфические, где такая азбука на каждом столбе.

Здравствуйте, Sharowarsheg, Вы писали:

CC>>А сдвиги или LEA использовать можно?
S>lea — это первый приз.

Эх, сколько я им наперемножал когда на асме писал
Оченно удобная инструкция.

Здравствуйте, CreatorCray, Вы писали:

Тё>>У меня были реально задачи разобрать выражение и построить дерево индикаторов (с зависимостями) и другая- разобрать regexp и потом отсортировать результаты по приоритету по количеству matched сегментов.
CC>meh
Это всего лишь пример использования в работе.

CC>>>И компилятор я писал ещё более давно, вместе с виртуальной машиной для пошаговой отладки для железки под которую это всё должно было работать.
Тё>>Может, ты там только кирпичи подносил, а написал другой человек?
CC>Я это всё в одно рыло написал.

Ну если ты это делал "в одно рыло", в чём твоя претензия?

Вот развернуть или посчитать биты- этот вопрос уместен в embedded/drivers и неуместен everywhere else.

Здравствуйте, Тёмчик, Вы писали:

Тё>Что за бред? С какого боку тут tearing? Нужно аффинное преобразование. А это умножение матриц. Быстро умножать матрицы- отдельная, большая (больная) тема.

А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица?

Здравствуйте, a7d3, Вы писали:

I>>Ну вот пришел к тебе товарищ, что заявляется экспертом по всякому низкоуровневому программированию, опыт в эмбеде и тд, и не может битовые операции.
I>>Как быть? Простить, поощрить, дать глянуть конспект?

A>Не важно в какой сфере человек себя специалистом позиционирует, а проверять задачками не самозванец ли — это сильно лишнее.

Задача это способ показать квалификацию. Как у женглёра — показать мастерство в действии, а не рассказать про него.

I>>А как нужно интервью и что еще есть кроме как сравнить кандидатов?

A>В первую очередь стоит задуматься, а с чего вдруг эта идея возникла — сравнивать кандидатов между собой?

У кого эта идея возникла? И почему ты отвечаешь вопросом на вопрос?

A>Какая цепочка рассуждений с доводами и аргументами привела к такому ложному выводу?

Обычно хамство и уход от ответа есть достаточно сильный признак некомпетентности. А у тебя как с этим?

Здравствуйте, Тёмчик, Вы писали:

Тё>Это всего лишь пример использования в работе.
И?

Тё>>>>>Неужели ты в работе ни разу с задачей преобразовать выражение не сталкивался?
CC>>>>И компилятор я писал ещё более давно, вместе с виртуальной машиной для пошаговой отладки для железки под которую это всё должно было работать.
Тё>>>Может, ты там только кирпичи подносил, а написал другой человек?
CC>>Я это всё в одно рыло написал.

Тё>Ну если ты это делал "в одно рыло", в чём твоя претензия?
Где ты у меня тут увидел претензии?

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, a7d3, Вы писали:

A>>Этот тест не работает, потому что люди давно научились его обманывать.
CC>Потому что применять его тоже надо умеючи а не как Артёмка пару лет назад, когда он про тест услышал а про что он собственно тестирует и на что надо смотреть — нет.
CC>Решение как таковое никого не интересует, интересует рассуждение в процессе решения, потому что это не вопрос — ответ а повод поговорить, спросить об альтернативных вариантах решения той же задачи. Потому переворот списка плохая задача — там в общем то одно нормальное решение, можно придумать пачку плохих, как в той байке про барометры но лучше таки взять другую задачу, которую можно решить множеством способов.

Именно это и зовётся system design interview — несколько взаимосвязанных между собой задач, имеющих различные варианты решения. И при этом, все упакованные в одну небольшую «постановку», формулируемую одной фразой. От кандидата ожидается не только порассуждать на тему вариантов решения, но и вообще увидеть эти самые задачи путём диалога с интервьюером.

Адепты решения абстрактных задачек на собеседовании никогда не отрицают полезность system design interview. Они всего лишь полагают, что перед этим надо типа «разогреть кандидата». Или же не считают нужным всех и вся сразу же допускать до system design interview, а хотят как-то отфильтровать толпу народу. Классический случай, когда «благими намерениями» губят всю процедуру (найма), сводя на нет любую возможность диалога.

Отсобеседовав криво с десяток людей — автоматом лишаешь себя трёх-четырёх сотен потенциальных кандидатов. Фигово отсобеседованный кандидат приводит к тому, что в компанию не придёт 30-40 других, тех кому напрямую или через вторые руки расскажут об идиотизме. В итоге, компания обрекает себя на вечное ковыряние в абы каком человеческом материале.

Здравствуйте, Ikemefula, Вы писали:

I>Задача это способ показать квалификацию. Как у женглёра — показать мастерство в действии, а не рассказать про него.

Это крайне печальное заявление, потому что собеседование не является испытанием и квалификацию на нём никто не проверяет.

I>>>А как нужно интервью и что еще есть кроме как сравнить кандидатов?
A>>В первую очередь стоит задуматься, а с чего вдруг эта идея возникла — сравнивать кандидатов между собой?
I>У кого эта идея возникла? И почему ты отвечаешь вопросом на вопрос?

Диалога не будет, ровно до тех, пока тебе не станет ясно, что интервью-собеседование не служит и для сравнивания кандидатов.

A>>Какая цепочка рассуждений с доводами и аргументами привела к такому ложному выводу?
I>Обычно хамство и уход от ответа есть достаточно сильный признак некомпетентности. А у тебя как с этим?

Покажи на хамство пальцем.
Все люди находятся на разном уровне развития и осознания — отдельных компетенций. И до тех пор, пока тебе не станет ясно «А», то и бесполезно говорить с тобой про «Б». Однако, ты можешь и не подозревать о том, насколько некомпетентен и выяснять это лишь случайно, входе каких-то мимолётных контактов где-то с кем-то. Если такая картинка мира устраивает, то начни с самоконтроля:
— какая именно цепочка рассуждений с доводами/аргументами привела к посылу, что собеседование является способом сравнивания кандидатов.

На данный момент, выявлено две жуткие дурости, т.е. придётся осознать две вещи:
1. на собеседовании квалификацию не показывают, это не испытание кандидатов
2. собеседование проводят не для того, чтобы кандидатов между собой сравнивать

Здравствуйте, a7d3, Вы писали:

A>На данный момент, выявлено две жуткие дурости, т.е. придётся осознать две вещи:
A>1. на собеседовании квалификацию не показывают, это не испытание кандидатов
A>2. собеседование проводят не для того, чтобы кандидатов между собой сравнивать

Для чего проводят собеседование?

Здравствуйте, xarcass, Вы писали:

X>Какая там формула может быть? Школьная тригонометрия. Задача из реальной жизни.
Так вот именно! Школьная.
Я вот школу закончил 20+ лет назад. И с тех пор мне эта формула пригодилась один раз — когда учасвтовал в https://russianaicup.ru/

Зачем спрашивать эту формулу на собесе? Ну то есть ты правда хочешь понять, помнит ли кандидат эту формулу?

И давай будем честными. каждый из нас помнит или не помнит совершенно случайные вещи. И каждого можно завалить школьными вопросами.
Навскидку:
Назови основания ДНК (не гуглить).
Железо бросили в соляную кислоту, напиши реакцию.
Вычисли синус 15 градусов (без калькулятора)
Уровень воды в ванне — 50 см. с какой скоростью вода будет выливаться, когда откроют пробку?

Можешь ответить на эти, безусловно школьные вопросы?

Допустим, ответил. ЧТо это мне скажет? только то, что ты помнишь приблизительно те же вещи, что и я. О твоем профессионализме это не скажет ничего.

Здравствуйте, xarcass, Вы писали:

X>Кто в своей повседневной работе использовал разворот односвязного списка — пусть первый бросит в меня камень.

X>зы. если что — с реверса списка тема и началась

А часто спрашивают разворот списка на собеседовании? Меня, например — ни разу. Разговоры про списки, деревья и прочие контейнеры были, но спрашивали, как они устроены и какая сложность вставки и поиска значений.

А список развернёт любой первокурсник, который вчера лабу на эту тему делал.

G>Зачем спрашивать эту формулу на собесе? Ну то есть ты правда хочешь понять, помнит ли кандидат эту формулу?

Да нет там никаких формул вообще. Зато есть один весьма программистский нюанс. На который в реальной жизни реальные люди и наступили. И слегка побуксовали.

И вообще, чем критиковать чужие задачки накидал бы кто своих. А то кроме меня и тёмчика пока никто не сподобился.

Здравствуйте, xarcass, Вы писали:

G>>С поворотами — тоже не все хорошо. Формулу поворота помнят не только лишь все. Ее придется выводить прямо на собеседовании.

G>>В общем, задачи конечно интересные, но их нужно давать только в контексте поиска человека, который в работе должен жонглировать битовыми масками и выполнять другую акробатику. И при этом заранее озвучив, что вам нужно именно максимально эффективное по времени решение.

X>Какая там формула может быть? Школьная тригонометрия. Задача из реальной жизни.

Это сразу сужает перечень кандидатов до бывших школьников, студентов математических специальностей и тех, кто именно в этой теме и работает.

Скажем, если ты такую задачу будешь задавать бакенду или фронтенду, то велик шанс фейла. Вместо этого гораздо более результативно спрашивать по самому профилю кандидата.
В порядке убывания важности:
1. опыт, роли, обязанности — интересует прежде всего уровень коммуникации, масштаб работ, умение принимать решения и вникать в суть дела
2. интересы
3. технические скилы — желательно понимание основ, проектирования, а не сами баззворды

Обычно всё наоборот — спрашивают за баззворды, а всё остальное мало кто вообще берется спрашивать. На самом деле хороший сотрудник это далеко не всегда тот, кто уже на входе знает нужный баззворд. Более того, знатоки баззвордов слишком часто теряют интерес, например, на долгоиграющих проектах.

Здравствуйте, Gradiens, Вы писали:

G>Допустим, ответил. ЧТо это мне скажет? только то, что ты помнишь приблизительно те же вещи, что и я. О твоем профессионализме это не скажет ничего.

Кажется, что в программировании практически никогда не бывает так, что кандидат удовлетворяет всем необходимым требованиям. Разве что в 1С получить все сертификаты и можно на любой проект. Поэтому на собеседовниях смотрят:
1. Какой частью их необходимых знаний обладает кандидат.
2. Как быстро он учится.
3. Как умеет разбираться с незнакомыми проблемами.

В зависимости от результатов собеседования, можно взять кандидата со знаниями в предметной области и с низкой скоростью обучения или, наоборот, с высокой обучаемостью, но без знаний. В зависимости от проекта, укомплектованности команды и бюджета принимается решение. Или у тебя не так?
Возвращаясь к вопросу, например, о синусе можно понять насколько быстро кандидат разберётся с задачами, где будет немного математики.

Здравствуйте, xarcass, Вы писали:

X>И вообще, чем критиковать чужие задачки накидал бы кто своих. А то кроме меня и тёмчика пока никто не сподобился.

Лично я не фанат задач. Но две категории задач могут быть полезны.

1) любые на понимание алгоритмической сложности.
пример простой задачи: как максимально эффективно по времени отсортировать массив из 10^9 чисел, учитывая, что каждое из них не больше 10^6

2) любые на алгоритмическое мышление. Просто, чтобы посмотреть, как кандидат мыслит. И что делает, если у него не все получается.
пример простой задачи: есть массив с числами от 1 до N, все числа кроме одного не повторяются. Найти повторяющееся число.
пример задачи посложнее: есть указатель на однонаправленый связанный список. Как не выделяя динамической памяти узнать, закольцован список, или нет.

неплохо, если задача сразу принадлежит обеим категориям. Пример: найти все вхождения подстроки в строке.

Остальные типы задач — от лукавого. Лично я не вижу, как другие типы головоломок помогут понять, подходит кандидат, или нет.
Да и задачи на мышление — спорная тема. Можно потратить кучу времени, завалить хорошего кандидата, который хорошо программирует но плохо решает задачи "про гномиков"

Здравствуйте, Ikemefula, Вы писали:

I>Битовые операции никакая не мутота. Оптимизации, протоколы, низкоуровневая работа с данными, системные функции — это неполный список того, где битовые операции не редкость.
Замена умножения на сдвиг это разве оптимизация для стандартных CPU, компиляторов и С/С++? Я еще лет 10 назад пробовал разные варианты just for fun и выходило примерно шило на мыло

Здравствуйте, Nuzhny, Вы писали:

N>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица?
Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.

Здравствуйте, Gradiens, Вы писали:

G>Ну то есть кандидату совсем неочевидно, почему "Операцию умножения — не использовать".
Так это же прямая отсылка к сдвигу.

G>И сходу хочется объяснить постановку задачи "придурью интервьювера"
G>А вот если сказать "операция критична по времени" — все сразу ясно.
Да не ясно. Еще большой вопрос будет ли сдвиг эффективнее. А вот запрет на умножение прямо говорит про сдвиг.
Все эти сдвиги на практике нужны в первую очередь не для скорости, а для адресации внутри байта, когда есть серьезные ограничения по памяти.

Здравствуйте, Skorodum, Вы писали:

G>>И сходу хочется объяснить постановку задачи "придурью интервьювера"
G>>А вот если сказать "операция критична по времени" — все сразу ясно.
S>Да не ясно. Еще большой вопрос будет ли сдвиг эффективнее. А вот запрет на умножение прямо говорит про сдвиг.
S>Все эти сдвиги на практике нужны в первую очередь не для скорости, а для адресации внутри байта, когда есть серьезные ограничения по памяти.

Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.

Запрет на умножение говорит... хз что он говорит, но любые запреты без объяснения причин — дорога в ад.

Что такое адресация внутри байта? чтобы выполнить сдвиг — навиг не нужно ничего адресовать внутри байта. Это атомарная операция. Одна инструкция процессора. Разве нет?

Сдвиги на практике нужны именно что из-за скорости.
А какая память расходуется при умножении? Лично я не вижу, где там перерасход по сравнению со сдвигом.

Здравствуйте, Тёмчик, Вы писали:

N>>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица?
Тё>Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.

А как будет выглядеть эта матрица? Вполне может быть так, что для оптимального решения тебе не понядобятся ни матрицы, ни вектора, а простая школьная тригонометрия даст результат и лучше и быстрее, да ещё и в целых числах (что круто, если это не на видеокарте делать).
С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.

Здравствуйте, Nuzhny, Вы писали:

N>>>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица?
Тё>>Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.

N>А как будет выглядеть эта матрица? Вполне может быть так, что для оптимального решения тебе не понядобятся ни матрицы, ни вектора, а простая школьная тригонометрия даст результат и лучше и быстрее, да ещё и в целых числах (что круто, если это не на видеокарте делать).
Давай пример. Целых чисел там не будет, только fixed float можно попробовать для ускорения.

N>С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.

Матрица поворота — частный случай или составная часть матрицы афинного преобразования. Видишь, я не занимался этим 15 лет, но попал в точку. А ты готов изобретать велосипед.

Здравствуйте, Skorodum, Вы писали:

I>>Битовые операции никакая не мутота. Оптимизации, протоколы, низкоуровневая работа с данными, системные функции — это неполный список того, где битовые операции не редкость.
S>Замена умножения на сдвиг это разве оптимизация для стандартных CPU, компиляторов и С/С++? Я еще лет 10 назад пробовал разные варианты just for fun и выходило примерно шило на мыло

"Современных процессоров" довольно большое количество и устроены сильно по разному, соответсвенно качество компиляторов далеко не всегда не высшем уровне. Более того, не все ведь к С++ сводится. Часто это джыт, который, вобщем, сильно дохлый супротив обычного компилятора. А умножение и сдвиг до сих пор отличаются по производительности, как то так.

Здравствуйте, sergey2b, Вы писали:

S>Здравствуйте, Тёмчик, Вы писали:
S>Это задачка из К и Р
S>И человек знающий про обратную польскую Наталию решит ее за недолго

Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.

Здравствуйте, Тёмчик, Вы писали:

Тё>Давай пример. Целых чисел там не будет, только fixed float можно попробовать для ускорения.

Пример чего? Я уже несколько раз намекал, что аффинное преобразование — это оверкилл. Ты никак не можешь этого понять.

Тё>Матрица поворота — частный случай или составная часть матрицы афинного преобразования. Видишь, я не занимался этим 15 лет, но попал в точку. А ты готов изобретать велосипед.

Я не готов изобретать велосипед, потому что никакого велосипеда тут нет. Никто в здравом уме не будет поворачивать картинку аффинным преобразованием. Если это надо делать быстро на CPU, то умножение матрицы (3х3) на вектор (3х1) будет слишком медленным, когда можно сделать в несколько раз быстрее (в целых числах в том числе). Если же на GPU, то float, но тоже не умножением матриц.
Призываю посчитать, сколько операций надо для поворота картинки, а сколько для аффинного преобразования: в аффинном случае у тебя для каждого пикселя будет 4 лишних умножения на 0, 3 лишних умножения на 1, 4 лишних операции сложения. Не оверкилл? Если мы будем пачками обрабатывать многопегапиксельные снимки, то вообще туши свет — я лично обвиню тебя в ускорении приближения глобального потепления.

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Что такое "в повседневной работе"? По десять раз на дню?
SVZ>У нас в программе использовались односвязные списки. На основе стандартного вектора, с хранением удаленных элементов, с поддержкой Undo/Redo.
SVZ>Использовались для хранения полигонов, проводников на печатной плате.
SVZ>При объединении пары списков один из них нужно развернуть.
Зачем?

Здравствуйте, Gradiens, Вы писали:

G>Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.
Речь про то, что оптимизатор может превратить умножение/деление в сдвиг. Уже много лет как. И он это 100% сделает в вслучае x * 80.
Это тривиальнейшая оптимизация реализованная много лет назад. Если собеседующий этого не знает...

G>Запрет на умножение говорит... хз что он говорит, но любые запреты без объяснения причин — дорога в ад.
Да нет никаких веских причин. Собеседующий прочитал задачку в интернете вот и все причины.

G>Что такое адресация внутри байта?
Обращение к битам

G>Сдвиги на практике нужны именно что из-за скорости.
Нет. Компиляторы уже умеют это делать сами лет дцать как.

G>А какая память расходуется при умножении? Лично я не вижу, где там перерасход по сравнению со сдвигом.
Битовые операции используются, чтобы один байт памяти использовался для хранения 8 (*) бит информации, а не одного.

* байт бывает и не 8 бит.

Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, sergey2b, Вы писали:

S>>Здравствуйте, Тёмчик, Вы писали:
S>>Это задачка из К и Р
S>>И человек знающий про обратную польскую Наталию решит ее за недолго

BFE>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.


А какие операции доступны и можно ли использовать скобки в выражениях

Здравствуйте, xarcass, Вы писали:

S>>несколько хороших задачь которымиможно заменить разоворот списка

X>1. Найти смещение знакоместа в видеопамяти (для текстового режима — так проще). Количество знакомест в строке — константа (скажем, 80). Одно знакоместо — один байт. Операцию умножения — не использовать.
X> странное дело, но мало кто может решить из тех, с кем я сталкивался

Заполняем константный массив размером 80xRows числами от 0 до 79 и потом, по смещению в массиве получаем смещение знакоместа в видеопамяти. Но вы ведь не этого ждали, правда?

X>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

Без искажений эта задача не имеет решения.

Здравствуйте, Nuzhny, Вы писали:

N>Я не готов изобретать велосипед, потому что никакого велосипеда тут нет. Никто в здравом уме не будет поворачивать картинку аффинным преобразованием. Если это надо делать быстро на CPU, то умножение матрицы (3х3) на вектор (3х1) будет слишком медленным, когда можно сделать в несколько раз быстрее (в целых числах в том числе). Если же на GPU, то float, но тоже не умножением матриц.

Не 3x3 на 3x1, а 2x2 на 2x1.

N>Призываю посчитать,
Призываю расписать здесь операции для поворота, основанные на школьных тригонометрических знаниях.

Как быстро будем считать гипотенузу, или можно сразу повернуть тангенс?

N> сколько операций надо для поворота картинки, а сколько для аффинного преобразования: в аффинном случае у тебя для каждого пикселя будет 4 лишних умножения на 0, 3 лишних умножения на 1, 4 лишних операции сложения. Не оверкилл? Если мы будем пачками обрабатывать многопегапиксельные снимки, то вообще туши свет — я лично обвиню тебя в ускорении приближения глобального потепления.
А разве алгоритмическая сложность не C * O(N)? Умножаем матрицу на каждую координату (0..N-1), N раз.

Здравствуйте, sergey2b, Вы писали:

S>>>Здравствуйте, Тёмчик, Вы писали:
S>>>Это задачка из К и Р
S>>>И человек знающий про обратную польскую Наталию решит ее за недолго

BFE>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
S>А какие операции доступны и можно ли использовать скобки в выражениях
Числа только в десятичной системе исчисления?

Здравствуйте, Ikemefula, Вы писали:

I>"Современных процессоров" довольно большое количество и устроены сильно по разному, соответсвенно качество компиляторов далеко не всегда не высшем уровне.
Неплохо было бы подтвердить свои слова. Найдите компилятор и целевую архитектуру, когда x*80 не будут разложены на сдвиг и сложение.

I>Более того, не все ведь к С++ сводится. Часто это джыт, который, вобщем, сильно дохлый супротив обычного компилятора.
Джытами не пользуюсь, но вот что мне гугл дает:

There’s effectively zero difference between using division versus a shift with numbers this small. Those are nanoseconds, after all. Using a negative number shows no difference in the result.

With this we can now definitely say that replacing value / 2 with value >> 1 offers no benefit. Stop doing it for arithmetic operations and reserve it only for strictly bitwise things!

I>А умножение и сдвиг до сих пор отличаются по производительности, как то так.
Код и бенчмарк в студию.

Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, sergey2b, Вы писали:

S>>>>Здравствуйте, Тёмчик, Вы писали:
S>>>>Это задачка из К и Р
S>>>>И человек знающий про обратную польскую Наталию решит ее за недолго

BFE>>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
S>>А какие операции доступны и можно ли использовать скобки в выражениях
BFE>Числа только в десятичной системе исчисления?

В восьмеричной шестначтиричной или двоичной

Здравствуйте, xarcass, Вы писали:

vsb>>Константа произвольно задаваемая, или 80?

X>Конечно любая — можно даже нечётную. Смысл не меняется.

vsb>>offset = row * 80 + col. row * 80 = row * 64 + row * 16 = row << 6 + row << 4. Такой алгоритм предполагается?

X>Конечно. Удивительно то, как много матёрых перцев на этом буксуют.

Было две мысли:
1. Цикл. Тут хотя бы можно в любой момент менять ширину.
2. Использовать сдвиг.

Оба варианта изврат.
Была еще мысль №0 — вопрос какой то дебильный, пора валить.

Интересно, почему мониторы были 80*25, а не 64*32 или 128*32.... Сдвиг вроде быстрее.

Здравствуйте, B0FEE664, Вы писали:

SVZ>>У нас в программе использовались односвязные списки. На основе стандартного вектора, с хранением удаленных элементов, с поддержкой Undo/Redo.
SVZ>>Использовались для хранения полигонов, проводников на печатной плате.
SVZ>>При объединении пары списков один из них нужно развернуть.

BFE>Зачем?

Чтобы из двух получить один, сохранив форму.

K
o---+L
    |
    |
    |
   M+-------+N
            |
            |
           \|/
            o Z
           /|\
            |
            |
            |
           R+---------o P

Была дорожка K-L-M-N-Z, нарисовали еще одну дорожку P-R-Z.
В точке Z нужно обе дорожки объединить в одну. Для этого одну из них необходимо развернуть.
На выходе должно получиться либо K-L-M-N-Z-R-P, либо P-R-Z-N-M-L-K.

Здравствуйте, B0FEE664, Вы писали:

BFE>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.

Стек ведь необязательно держать в памяти. Можно завести в файле, и читать произвольный инпут. Сложность линейная. Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.

Здравствуйте, Pzz, Вы писали:

Pzz>Кто на 8080 не программировал, те и буксуют.

кто программировал синклер графику, разбивают себе лицо фейспалмом

Здравствуйте, CreatorCray, Вы писали:

X>>Если представить, что у нас есть просто массив байтов (условно двумерный), то для того, чтобы его попиксельно повернуть достаточно базовых знаний тригонометрии.
CC>Если делать в лоб то будут глюки типа tearing.

tearing то откуда возьмётся ?

Здравствуйте, Тёмчик, Вы писали:

Тё>Нужно аффинное преобразование. А это умножение матриц. Быстро умножать матрицы- отдельная, большая (больная) тема.

не нужно там ничего умножать

Здравствуйте, IID, Вы писали:

CC>>Если делать в лоб то будут глюки типа tearing.

IID>tearing то откуда возьмётся ?

Так CC у нас — признанный эксперт. Хотя, может он так стебётся над автором задачки.

Здравствуйте, B0FEE664, Вы писали:

X>>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

BFE>Без искажений эта задача не имеет решения.

Картинка на пиксельном мониторе — это уже искажения
Хинт — у тебя вращение текстурированной херни протестов не вызывает ?

Здравствуйте, Тёмчик, Вы писали:

Тё>Не 3x3 на 3x1, а 2x2 на 2x1.
Тогда это не аффинное преобразование по определению.

Тё>А разве алгоритмическая сложность не C * O(N)? Умножаем матрицу на каждую координату (0..N-1), N раз.
Ну, да. Но константа для аффинного преобразования будет больше раз в... 10!

Здравствуйте, IID, Вы писали:

Тё>>Нужно аффинное преобразование. А это умножение матриц. Быстро умножать матрицы- отдельная, большая (больная) тема.

IID>не нужно там ничего умножать

Эээээ давай своё решение. Там в условии произвольный угол.

Здравствуйте, Nuzhny, Вы писали:

Здравствуйте, xarcass, Вы писали:

X>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

Очень просто.
Обходим попиксельно destination буфер.
Для смещений по X к координатам источника добавляем (сos;sin).
Для смещений по Y -//- (sin;cos).
Всё!
Если домножить на коэффициет (масштаб) — то ещё увеличиваться и уменьшаться будет. Если возвращать источник с обратной стороны при выходе за границу — то с эффектом "мозаики".

Можно в fixed point если регистров и скорости хватает.
Можно в целых, если развернуть цикл, и добавление заменить инкрементами в тех случаях, когда накопленная дробная часть округляется до целого (но это не позволит сильно играть с сильным уменьшением масштаба, начнутся проскоки на более чем 1 пиксель).

Крутили такое на 8 битах при 3,5мгц, при этом ещё ухитряясь синхриться с развёрткой луча на ЭЛТ, увеличивая цветовое разрешение вдвое.

Пруф (с 2:34):
https://youtu.be/dl3wWxJmIZw?t=154

А вот в VGA для 386 (с 4:42)
https://youtu.be/rFv7mHTf0nA?t=282

Здравствуйте, Тёмчик, Вы писали:

Тё>Эээээ давай своё решение. Там в условии произвольный угол.

тут

Автор: IID
Дата: 06.10.20

Здравствуйте, Тёмчик, Вы писали:

N>>Тогда это не аффинное преобразование по определению.
Тё>Да что ты. Пространство ведь 2-мерное. Не хромает ли твоя математика?

Неа. Попробуй своей аффинной матрицей в 2D пространстве задать сдвиг, поворот и масштаб. Если получится — снимаю шляпу и всячески превозношу твой профессионализм.

Тё>Ты это, давай выкладывай свои катеты с гипотенузами, и посчитаем количество операций. Как там будут квадраты и корни квадратные считаться, да ещё и только в целых числах (!).

Эээ, нет. Там вообще никаких катетов не будет.

Здравствуйте, Nuzhny, Вы писали:

N>Эээ, нет. Там вообще никаких катетов не будет.

Блин, после поста IID я таки нагуглил ответ. Эту хрень можно знать, если однажды её сделал.

s = sin(90 - angle);
c = cos(90 - angle);
w2 = width / 2;
h2 = height / 2;

for (i=0..N-1) {
  newX[i] = (X[i] - w2) * c - (Y[i] - h2) * s + w2;
  newY[i] = (X[i] - w2) * s + (Y[i] - h2) * c + h2;
}

Здравствуйте, Skorodum, Вы писали:

I>>"Современных процессоров" довольно большое количество и устроены сильно по разному, соответсвенно качество компиляторов далеко не всегда не высшем уровне.
S>Неплохо было бы подтвердить свои слова. Найдите компилятор и целевую архитектуру, когда x*80 не будут разложены на сдвиг и сложение.

Для примера, в Атоме сдвиг это 1 такт, умножение 3..6 тактов, div — 9..41. https://software.intel.com/content/dam/develop/public/us/en/documents/intel-atom-tremont-microarchitecture-throughput-and-latency.pdf
В микроконтроллерах всяких дело будет еще хуже.

То есть, выиграть есть где. На счет компилера трудновато будет, я как то давно отошел от таких дел.

Здравствуйте, Тёмчик, Вы писали:

Тё>Эту хрень можно знать, если однажды её сделал.

необязательно именно ее. Афинное текстурировние (а я его тоже упоминал) более общий случай той же самой задачи. И та же самая реализация — растеризатор заполняет построчно пиксели, шарясь по байтам текстуры.

Здравствуйте, Ikemefula, Вы писали:

I>Для примера, в Атоме сдвиг это 1 такт, умножение 3..6 тактов, div — 9..41. https://software.intel.com/content/dam/develop/public/us/en/documents/intel-atom-tremont-microarchitecture-throughput-and-latency.pdf
Прекрасно, только это ровно ничего не доказывает, т.к. разговор не про то, что в процессоре умножение/деление более дорогая операция чем сдвиг, а про то, что в программе нет смысла заменять умножение на константу на сдвиг.

I>В микроконтроллерах всяких дело будет еще хуже.
Может, но к обсуждаемому случаю это вообще никак не относится.

I>То есть, выиграть есть где.
Конечно есть: если писать на ассемблере. А так нет.
Более того, это намного хуже читается.

I>На счет компилера трудновато будет, я как то давно отошел от таких дел.
Давно это когда? В 2010 это точно уже было в gcc.

Хорошая иллюстрация, что с вопросами на собеседовании надо быть аккуратнее (да, это не вы этот вопрос предложили).

Здравствуйте, IID, Вы писали:

IID>необязательно именно ее. Афинное текстурировние (а я его тоже упоминал) более общий случай той же самой задачи. И та же самая реализация — растеризатор заполняет построчно пиксели, шарясь по байтам текстуры.

Т.е. по сути нужно разобраться в видах растеризаторов. Мне не довелось с этим сталкиваться. Поигрался немного с 3D для чартов и отсечением невидимых граней (была идея получить векторную картинку для печати) и забросил. В 2004-2005г это было. Насколько оно у меня тормозило вручную на CPU, настолько летало в OpenGL.

Здравствуйте, Skorodum, Вы писали:

S>Прекрасно, только это ровно ничего не доказывает, т.к. разговор не про то, что в процессоре умножение/деление более дорогая операция чем сдвиг, а про то, что в программе нет смысла заменять умножение на константу на сдвиг.

I>>В микроконтроллерах всяких дело будет еще хуже.
S>Может, но к обсуждаемому случаю это вообще никак не относится.

Не надо передёргивать — просто утверждение без конкретики.

I>>То есть, выиграть есть где.
S>Конечно есть: если писать на ассемблере. А так нет.

Ты точно в курсе, что все джыты всех языков сделают лучше? А если микроконтроллер?

I>>На счет компилера трудновато будет, я как то давно отошел от таких дел.
S>Давно это когда? В 2010 это точно уже было в gcc.

Цитирую себя "не все ведь к С++ сводится"

IID>Очень просто.
IID>Обходим попиксельно destination буфер.

Про это и задача. Тут то и нюанс. Многие начинают обходить source буфер. И всё — приплыли.

Здравствуйте, sergey2b, Вы писали:

S>несколько хороших задачь которымиможно заменить разоворот списка
Проще можно. На собеседовании предлагаешь кандидату поднять штангу. Поднимет больше 150 килограмм — это сильный программист, сеньер — берем. Поднимет 100 килограмм — это средний программист, много денег не дадим. Пожнимет килограмм 70 — это юниор, этого на стажера в лучшем случае и платить чтоб с голоду не умер. А кто меньше поднимет — это не программисты!

И главное, такое собеседование занимает несколько минут, и можно сравнивать кандидатов! Плохо что удаленно не получится собеседовать, а удаленно кандидат может надувные блины поставить. Ну удаленно можно заставить подтягиваться. Подтянется раз 30 на одной руке — сеньер. 30 раз просто — средний. Подтянулся раз 10 — это юниор, только на стажера потянет.

А то списки какие то, задачки. Совсем собеседовать не умеют, ужас!

S>Все эти сдвиги на практике нужны в первую очередь не для скорости, а для адресации внутри байта, когда есть серьезные ограничения по памяти.

лет 20 назад это было исключительно для скорости. Ибо даже целочисленное умножение было очень медленным. Не говоря уже о том, что на некоторых платформах (старые ARM-ы, например) количество тактов операции умножения зависело от значений операндов.

Здравствуйте, Тёмчик, Вы писали:

BFE>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
Тё>Стек ведь необязательно держать в памяти. Можно завести в файле, и читать произвольный инпут. Сложность линейная.

Ага. И всё это расписать прямо на доске.

Тё>Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.
Интересные новости про условия задачи!

Здравствуйте, IID, Вы писали:

X>>>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.
BFE>>Без искажений эта задача не имеет решения.

IID>Картинка на пиксельном мониторе — это уже искажения
Если картинка пиксельная, то какие искажения?

IID>Хинт — у тебя вращение текстурированной херни протестов не вызывает ?
Вызывает.

Здравствуйте, Ikemefula, Вы писали:

I>А если микроконтроллер?
Тогда надо добавить в исходные условия: "есть микроконтроллеи и JIT где операция умножения дорогая и не оптимизируется...".
Иначе такие вопросы больше говорят о квалификации того, кто их задает.

S>>Давно это когда? В 2010 это точно уже было в gcc.
I>Цитирую себя "не все ведь к С++ сводится"
Gnu Compiler Collection...

Здравствуйте, sergey2b, Вы писали:

S>>>>>Это задачка из К и Р
S>>>>>И человек знающий про обратную польскую Наталию решит ее за недолго
BFE>>>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
S>>>А какие операции доступны и можно ли использовать скобки в выражениях
BFE>>Числа только в десятичной системе исчисления?
S>В восьмеричной шестначтиричной или двоичной
Двоичные числа записывать в прямом, обратном или дополнительном коде?
Почему нет поддержки троичной системы?

Здравствуйте, xarcass, Вы писали:

X>лет 20 назад это было исключительно для скорости.
Это никогда не было искючительно для скорости, т.к. доступ к битам требовался всегда.

Здравствуйте, B0FEE664, Вы писали:


BFE>>>Числа только в десятичной системе исчисления?
S>>В восьмеричной шестначтиричной или двоичной
BFE>Двоичные числа записывать в прямом, обратном или дополнительном коде?

наверное более универсально с дополнением до двух

BFE>Почему нет поддержки троичной системы?

потому что я ее не знаю

Здравствуйте, Skorodum, Вы писали:

I>>А если микроконтроллер?
S>Тогда надо добавить в исходные условия: "есть микроконтроллеи и JIT где операция умножения дорогая и не оптимизируется...".
S>Иначе такие вопросы больше говорят о квалификации того, кто их задает.

Разумеется, про то уже говорилось, что просто так такие вопросы смысла не имеют.

I>>Цитирую себя "не все ведь к С++ сводится"
S>Gnu Compiler Collection...

Я все время думал, что gcc это gnu c++

Здравствуйте, Ikemefula, Вы писали:

I>>>Цитирую себя "не все ведь к С++ сводится"
S>>Gnu Compiler Collection...

I>Я все время думал, что gcc это gnu c++

C, C++, Objective-C, Fortran, Ada, Go, and D.

Здравствуйте, B0FEE664, Вы писали:

BFE>>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
Тё>>Стек ведь необязательно держать в памяти. Можно завести в файле, и читать произвольный инпут. Сложность линейная.

BFE>Ага. И всё это расписать прямо на доске.

Тё>>Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.
BFE>Интересные новости про условия задачи!


Так ты сам усложнил задачу! В исходном сообщении было 2+2 и 2+2*3. Для этого достаточно встроенных операций и памяти под стек.

Здравствуйте, sergey2b, Вы писали:

BFE>>>>Числа только в десятичной системе исчисления?
S>>>В восьмеричной шестначтиричной или двоичной
BFE>>Двоичные числа записывать в прямом, обратном или дополнительном коде?
S>наверное более универсально с дополнением до двух

Без поддержки деления и чисел с плавающей точкой?
Нужна поддержка экспоненциальной формы для целых чисел?

BFE>>Почему нет поддержки троичной системы?
S>потому что я ее не знаю

А чего там знать-то: 0,1,2,10,11,12,20,21,22,100,101,... ?

Здравствуйте, Skorodum, Вы писали:

S>Замена умножения на сдвиг это разве оптимизация для стандартных CPU, компиляторов и С/С++? Я еще лет 10 назад пробовал разные варианты just for fun и выходило примерно шило на мыло

Помнится, во времена MS-DOS и 16-битных 80x86, был такой Watcom C Compiler, который считался очень крутым в плане кодогенерации. Так вот, он любил умножение на константу в виде последовательности сдвигов и сложений расписивать. Бывало, на полстраницы ассемблерного текста развернется. У древних x86 действительно был медленный умножатор, не то, что теперь.

Здравствуйте, Тёмчик, Вы писали:

BFE>>Ага. И всё это расписать прямо на доске.

Тё>>>Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.
BFE>>Интересные новости про условия задачи!
Тё>Так ты сам усложнил задачу!
Я? А вы предполагаете, что числа в выражении могут состоять только из одной цифры?

Тё>В исходном сообщении было 2+2 и 2+2*3. Для этого достаточно встроенных операций и памяти под стек.
В исходном сообщении было "2+2", "2*2", "2+3*2". Для этого вообще не нужно никаких операций кроме сравнения:

if ( expression == "2+2" ) printf("4");
if ( expression == "2*2" ) printf("4");
if ( expression == "2+3*2" ) printf("8");

В этот раз я ничего не усложнил?

Здравствуйте, alzt, Вы писали:

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

Ну тогда, казалось бы, надо поставить перед ним вазочку с конфетами, и посмотреть, сколько сожрет. Сразу станет понятно, как он с глюкозой разбирается: путем отключения мозгофф, или путем пожирания конфет.

Только тут важно учитывать тот момент, что иные кандидаты иные конфеты ни за что жрать не станут.

Здравствуйте, a7d3, Вы писали:

A>Это не работает. Потому что хороший специалист не станет тренироваться решать задачки на собеседованиях, а тот человек, который работать не умеет и ничего из себя не представляет — будет смотреться замечательно на фоне всех остальных. Поскольку у него выбора иного нету.

Ну с другой стороны, я вот список, напремер, разверну и даже отсортирую. Потому, что я и в боевом коде так иногда делаю.

Здравствуйте, wraithik, Вы писали:

W>Интересно, почему мониторы были 80*25, а не 64*32 или 128*32.... Сдвиг вроде быстрее.

Потому, что в перфокарте было 80 символов, а 24 было разумным компромисом между удобством использование и ценой изделия. Почему на PC 24 превратилось в 25, я не знаю, но предполагаю потому, что 25 — это почти 24, и при этом хорошо согласуется с телевизионным стандартом по числу строк.

Здравствуйте, xarcass, Вы писали:

X>Кто в своей повседневной работе использовал разворот односвязного списка — пусть первый бросит в меня камень.

Я использовал. Подставляй голову.

P.S. Я даже умудрился в повседневной работе использовать функцию, которая переставляет местами две "половины" массива разного размера, используя O(1) дополнительной памяти и за время O(n):

[AAAAA][BBBBBBBBBBBBBB] -> [BBBBBBBBBBBBBB][AAAAA]

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>При объединении пары списков один из них нужно развернуть.

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

Здравствуйте, B0FEE664, Вы писали:

это же тест на один час а не курсовая работа

Здравствуйте, Gradiens, Вы писали:

G>неплохо, если задача сразу принадлежит обеим категориям. Пример: найти все вхождения подстроки в строке.

А тебе как больше понравится, strstr в цикле, или алгоритм Морисса-Пратта на пальцах объяснить?

P.S. Того, кто применил бы алгоритм Морисса-Пратта в маловажных по скорости задачах в боевом коде, я бы убил на месте

Здравствуйте, Gradiens, Вы писали:

G>Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.

А за сколько тактов выполняется умножение на современном Пентиуме?

Здравствуйте, Pzz, Вы писали:

Pzz>Здравствуйте, Gradiens, Вы писали:

G>>Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.

Pzz>А за сколько тактов выполняется умножение на современном Пентиуме?

Вот тут https://www.agner.org/optimize/instruction_tables.pdf пишут, что 1-7 в зависимости от процессора.

Здравствуйте, sergey2b, Вы писали:

Адептам разворота списка пора переходить в следующее измерение — задавать повернуть квадратную матрицу на угол кратный 90° inplace, без использования дополнительной памяти.

Или оставаться в 1D, но двигаться дальше — циклический сдвиг массива на k N позиций влево или вправо, само собой, тоже inplace.

Здравствуйте, Pzz, Вы писали:


Pzz>Да вообще, если читаешь откуда-нибудь односвязанный список, то проще построить его задом наперед, а потом развернуть.

В таком случае, где у дождевого червяка списка голова, а где хвост — это всего лишь условность, зависящая от направления движения.

Здравствуйте, xarcass, Вы писали:

X>Конечно. Удивительно то, как много матёрых перцев на этом буксуют.

Они не ожидают такого разгула дебилизма от интервьюера.

Здравствуйте, PM, Вы писали:



PM>Или оставаться в 1D, но двигаться дальше — циклический сдвиг массива на k N позиций влево или вправо, само собой, тоже inplace.

эту задачку давали в google на разминке в 15 году

Здравствуйте, Pzz, Вы писали:

Pzz>Здравствуйте, a7d3, Вы писали:

A>>Это не работает. Потому что хороший специалист не станет тренироваться решать задачки на собеседованиях, а тот человек, который работать не умеет и ничего из себя не представляет — будет смотреться замечательно на фоне всех остальных. Поскольку у него выбора иного нету.

Pzz>Ну с другой стороны, я вот список, напремер, разверну и даже отсортирую. Потому, что я и в боевом коде так иногда делаю.

Вопрос же не в том можешь или нет. А тех обстоятельствах, в которых тебя вынуждают этим заниматься.
Мне жаловались разные люди, что обстановка на собеседованиях не располагает ни разу, к такого рода занятиям. Грубо говоря пыхтеть на листочке бумаги ручкой, когда рядом восседает откровенно зевающий собеседователь.
Т.е. задачка дерьмо, потому что есть лишь один годный вариант решения, но есть ряд вариантов облажаться при этом. Проверить мышление-рассуждение кандидата задачка не позволяет. Даётся задачка в таких обстоятельствах, что почти наверняка нетренированный человек в чём-нибудь да ошибётся. И в этом ожидании ошибки от кандидата и весь смысл, весь сок давания данной задачи. Чтобы у собеседующего появилась возможность ткнуть кандидата в некую ошибку в некой очень простетской задачке.

Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, a7d3, Вы писали:

A>>На данный момент, выявлено две жуткие дурости, т.е. придётся осознать две вещи:
A>>1. на собеседовании квалификацию не показывают, это не испытание кандидатов
A>>2. собеседование проводят не для того, чтобы кандидатов между собой сравнивать

I>Для чего проводят собеседование?

Для того чтобы людей подбирать?
Так и откуда же тогда взялась вся эта дурь, что двумя пунктами выше процитирована?
Ещё раз, через собеседование людей подбирают, а не отбирают.

Здравствуйте, sergey2b, Вы писали:

PM>>Или оставаться в 1D, но двигаться дальше — циклический сдвиг массива на k N позиций влево или вправо, само собой, тоже inplace.

S>эту задачку давали в google на разминке в 15 году

Ну-ну, кто бы в этом сомневался. Во что пишет про алгоритм block swap Дж. Бентли в "Жемчужинах программирования"

Б. Керниган и П. Дж. Плоджер пользовались именно этим методом для перемещения строк в текстовом редакторе в своей книге (В. Kernighan, P. J. Plauger, Software Tools in Pascal, 1981). Керниган пишет, что эта функция заработала правильно с первого же запуска, тогда как их предыдущая версия, использовавшая связный список, содержала несколько ошибок. Этот же код используется в некоторых текстовых редакторах, включая тот, в котором я впервые набрал настоящую главу. Кен Томпсон (Ken Thompson) написал этот редактор с функцией reverse в 1971 году, и он утверждает, что она уже тогда была легендарной.

Здравствуйте, a7d3, Вы писали:

A>Вопрос же не в том можешь или нет. А тех обстоятельствах, в которых тебя вынуждают этим заниматься.
A>Мне жаловались разные люди, что обстановка на собеседованиях не располагает ни разу, к такого рода занятиям. Грубо говоря пыхтеть на листочке бумаги ручкой, когда рядом восседает откровенно зевающий собеседователь.

Ну вообще говоря, собеседующему лучше на некоторое время выйти, показав собеседуемому тропинку к сортиру и к источнику чая с крекерами, или чем там изба богата.

A>Т.е. задачка дерьмо, потому что есть лишь один годный вариант решения, но есть ряд вариантов облажаться при этом. Проверить мышление-рассуждение кандидата задачка не позволяет. Даётся задачка в таких обстоятельствах, что почти наверняка нетренированный человек в чём-нибудь да ошибётся. И в этом ожидании ошибки от кандидата и весь смысл, весь сок давания данной задачи. Чтобы у собеседующего появилась возможность ткнуть кандидата в некую ошибку в некой очень простетской задачке.

По таким задачкам видно, склонен ли соискатель проверять, например, корректность входных данных. Хотя эта, наверное, даже и для этой цели слишком проста.

Здравствуйте, a7d3, Вы писали:

I>>Для чего проводят собеседование?

A>Для того чтобы людей подбирать?

Подбирать по какому принципу?

Здравствуйте, sergey2b, Вы писали:

S>несколько хороших задачь которымиможно заменить разоворот списка

Пришла идея ещё одной бессмысленной задачи на собеседовании — написать "универсальную" функцию, которая может использоваться для обхода двусвязного списка как в прямом, так и в обратном направлении.

struct linked_list
{
    struct node
    {
        int data;
        node* next;
        node* prev;
    };
    node* head;
    node* tail;
};

linked_list list;

void traverse(linked_list list, ...);

traverse(list, ???); // forward
traverse(list, ???); // backward

Дополнительный бонус за решение без if, штраф за читерство с шаблонами С++ или макросами С. В реализуемости на управляемых языках не уверен.

Здравствуйте, Skorodum, Вы писали:

I>>Более того, не все ведь к С++ сводится. Часто это джыт, который, вобщем, сильно дохлый супротив обычного компилятора.
S>Джытами не пользуюсь, но вот что мне гугл дает:
S>

S>There’s effectively zero difference between using division versus a shift with numbers this small. Those are nanoseconds, after all. Using a negative number shows no difference in the result.

S>With this we can now definitely say that replacing value / 2 with value >> 1 offers no benefit. Stop doing it for arithmetic operations and reserve it only for strictly bitwise things!

Это написано чтобы люди перестали в С коде фигачить shifts везде где ни попадя. Компилятор же вполне может поменять div на shr.

Здравствуйте, Тёмчик, Вы писали:

N>>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица?
Тё>Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.

Это ты щас ядрёной боНбой по таракану собрался бить.

Здравствуйте, xarcass, Вы писали:

X>Тут то и нюанс. Многие начинают обходить source буфер. И всё — приплыли.
Ага, у таких появляются "дырки" в результате.
Знал людей которые упирались и ни в какую не хотели "перевернуть" логику и ходить таки по destination, ибо "так будет дольше!" и упорно изобретали велосипед по предотвращению tears.

Здравствуйте, IID, Вы писали:

IID>tearing то откуда возьмётся ?
Не тот tearing который VSync, а когда результат получается с прорехами, когда итерацию делают не по dest а по src.