Самые неожидаемые вопросы на собеседовании?
Нужно было дать определение парадигмы программирования и назвать все направления. 
 я бы задал еще и определение слова  абстракция
народ реально потерянный от простых определений... никто не заставляет дать точное определение, но своими словами то можно... голова же есть, мысли свяжите и озвучьте
просьба дать определение -- примитивный способ выявить способность излагать мысль/мыслить просто
Или я может что-то не понимаю и пошли новые веяния? И типа нужно садиться и заново зубрить все основы программирования?
Основы разработки программного обеспечения и информатики нужно понимать, равно как и архитектуру ПК, операционные системы, сети, основные парадигмы программирования, алгоритмы и тому подобное. Это просто фундаментальные знания. В зависимости от специализации понимать вышеперечисленное нужно на разном уровне.
Касательно новых веяний, программист учится всю жизнь... Или сидит в каком-нибудь НИИ, гос. предприятии, очередной веб-студии, которая клепает однотипные сайты-поделки и т.п. и только называется программистом. Т.е.  тут не получиться заниматься интересными вещами и получать сравнительно много денег, но при этом постоянно не самосовершенствоваться.
И да, к собеседованиям надо готовиться. То что у вас 5-7-10-15 лет формального опыта не значит вообще ничего. Тут играют роль только знания, умения, навыки и уровень решаемых задач/возможность решать задачи определённого уровня.Очень интересует какие еще бываю вопросы на собеседованиях?
Это очень расплывчатый вопрос. Всё что угодно из того, что я написал в первом абзаце + специфические знания, например, по профильному стеку технологий, которым вы владеете. Часто ещё и социальные навыки проверяют, но это уже в основном на позиции выше мидла.