Самый уместный анекдот в моей жизни. Анекдот про UDP⁠⁠

Ну вот поэтому их наверное вообще не стоит такие вопросы сравнивать (по моему мнению). И да оптимизировать надо то шо тормозит, имхо.

Задачки? А они кластические: перемножение матриц вещественных чисел, обращение матрицы, SVD - n^3, вычисление определителя - n! ну и т.д. По отдельности то это все известно и по ним есть даже известные алгоритмы уменьшения сложности (ну например алгоритм Штрассена сокращает сложность умножения матриц с n^3 до n^2.8) - но я бы все равно такое не стал бы спрашивать - страшно! Если ты буквально вчера этого не делал - то не вспомнишь.
Но это все по отдельности, но вот когда все эти матрицы-хуятрицы собираются в кучу, то тогда становится весело. Например есть такое семейство алгоритмов: Affine projection algorithms - ну вот у оптимизированного варианта адаптивного фильтра для эхоподавления на этом алгоритме сложность будет 2N^2 + (N+1)L^2+(2N+1) + L^3 умножений со сложением и 2N+L^2 сложений (книжка Джигана под рукой оказалась с примером), ну и при определенных условиях можно его с оптимизировать - исчезнет первая двойка перед N- ну вот люди этим месяцами (годами?) занимаются и пишут статьи/монографии (диссертации?), а так наверное у этих APA все N^2 * L^2 может быть :-) Или другой пример, есть метод эллипсоидов (для определения пересечения двух выпуклых множеств) - у него сложность что-то около n^6, а есть вот алгоритм Вайда - у того n^4, по ним гуглить в направлении Convex Optimization (щас на эту тему понаписано куча умных книг и статей). Эт причем все сложности сугубо сферические, потом мы сажает за это дело погроммиста и...в общем писец. Короче везде где надо перемножать и крутить-вертеть кучу матриц становится страшно, а когда вместо матриц оказываются вообще многомерные массивы (например с 4-мя измерениями) тогда совсем страшно становится, а это всякие задачи цифровой обработки сигналов, обработки изображений, компьютерная геометрия, всякие там задачи оптимизации (внезапно тоже обучение нейросетей) и т.д.

Ну вот я и держу какой-нибудь злоебучий алгоритм (задачку) когда иду собеседоваться с каким-нибудь злобным работодателем на случай если заикнется и O-big notation - сразу какой-нить контр-вопрос. Ну я хз, вот есть для адаптивной фильтрации LMS (линейный) и RLS (квадратичный) алгоритмы, вот как упростить второй? Ответ: а никак, но вот если забацать блочные варианты этих алгоритмов, то получим у первого NL, а у второго LN^2 и если применить немного магии, то второй можно свести к L*NlogN (если я ниче не попутал).

Что касается ромба - вроде там будут проблемы когда мы мешаем виртуальное и невиртуальное наследование. А так то вроде жить можно - все разруливаемое, но чойт все испугались и напридумывали какие-то интерфейсы, а так была у меня давным давно задача с полиморфной сериализацией-дессериализацией и что бы подружить эту задачу с C# пришлось городить костыли, а ромбик бы ох как помог (даже специально потом проверял)

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

Сурово там у вас. Я хз, мое мнение такое - единственный надежный способ проверки соискателя - дать ему ему несколько тестовых заданий на дом. Конечно тут же все начнут говорить "а вдруг нагуглит?" (гхм..), "а вдруг припряжет кого-нибудь решить эту задачу?" (угу, РФ страна альтруистов, где по каждому вопросу отправляют гуглить в лучшем случае), ну и т.д.