Предлагаю помощь ментора Java. Подробности тут: dou.ua/forums/topic/39029

В яндексмейлру никогда не был, не знаю )

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

Кстати, да, я не упомянул, что я из России. Может быть, в Украине все иначе )
Но если говорить про компании из Европы — то в 100% случаев меня озадачивали алгоритмами на интервью.

Не на столько все плохо ) Связный список распишу.
Я поясню немного. Опять же, только про свой опыт. Отследил несколько этапов изучения этой темы и влияния этого на прохождение интервью:
1. Любой вопрос на тему О-нотации, рекурсии, деревьев и т.п. — для тебя не известен и ты просто признаешь на интервью, что ты этого не знаешь. Интервью на этом обычно и заканчивается. Либо продолжают спрашивать дальше, но потом отказывают или пропадают.
2. Стадия, когда ты уже можешь оценить сложность алгоритма (временную, по крайней мере), объяснить, что такое стабильная сортировка, что нового появилось в кишках HashMap в 8 версии java, можешь решить какие-то алгоритмические задачки (скажем, уровня Trapping Rain Water) — даже на бумажке и т.д. Этот этап уже позволяет успешно проходить интервью на позиции уровня middle-senior (за рамками дискуссии остаются все остальные скилы и знания из других областей). Конкретно я сейчас на этом этапе.
3. Стадия, когда требуются более глубокие математические знания (теория вероятности, комбинаторика, теория игр и т.д.) и знания более сложных и редких в использовании структур данных (те же деревья).

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

На доске не напишу )
Но написать такое ни разу не просили, ни на доске, ни еще где-то.

Что значит «не правда»? Я начал свой пост со слов «Мой опыт...», а на моих интервью вы ни разу рядом не стояли ))
Думаю, тут от конкретной компании зависит. Каждая для себя определяет, как отбирать синьоров. Ну и, очевидно, репутация кандидата играет роль. Если интервьюеру очевидно, что перед ним звезда — думаю, разговор пойдет именно так, как вы описали: будут спрашивать, что интересно, а что нет. А если кандидат как раз на стадии перехода на уровень мидл-синьор, о чем и шла речь у ТС, и о нем в данной компании ни разу не слышали — скорее всего будут гонять по вопросам от азов и выше.

1. Не сложно. Скажем так, главная сложность — найти такую вакансию, процесс трудоустройства, количество и сложность этапов интервью такие же, как при трудоустройстве на вакансию в офисе.
2. Зависит от работодателя. Работал удаленно на 3 крупных проектах, трекаю время только на одном из них. Трекаю сам, через toggl, никаких дополнительных средств слежения установить не просили. На двух других ничего не трекал, было важно просто выполнять задачи в срок, быть на связи. На одном проекте — ежедневный стендап команды, в котором я участвовал через скайп.
3. Зависит от конкретного проекта, плюс, как сам договоришься. На двух проектах был график фултайм, на одном — свободный.
4. Один проект — продуктовая. Два — аутсорс.
5. Реально. Я написал про 3 проекта, на которых работал. Во время двух из них — год провел в путешествиях: Индонезия, Австралия, Новая Зеландия. Если грамотно планировать время — то не в ущерб. Самое сложное — это дни, которые уходят на перелеты/переезды, поиск жилья и т.п. — в эти дни, само собой, работать ты не можешь, да и глупо это. Я обычно такие периоды планирую заранее вместе со своим руководителем. Когда прилетел/приехал/заселился/организовал интернет себе — дальше все под твоим контролем.

Мой опыт хождения прохождения интервью говорит о том, что как только начинаешь претендовать на уровень middle или senior, тут же любое интервью начинают с вопросов об основах (коллекции, ООП, стандарные классы и т.п.) и алгоритмах / структурах данных.
Когда искал работу уровня джуниор — это как раз редко спрашивали, работодателя, в основном, интересовало, что конкретно я умею делать и в каких проектах довелось участвовать.
У меня нет профильного образования (я — инженер по технологии машиностроения), поэтому этот переход к алгоритмам на интервью тоже сильно расстроил. Ощущал это как стену какую-то, т.к. начались сплошные отказы. Выход был один — заполнять этот пробел в знаниях, благо, сейчас куча онлайн ресурсов для изучения этих тем и практической тренировки. Например, hackerrank.
За пару месяцев регулярной работы над этим можно сдвинуться с мертвой точки и начать успешно проходить интервью.
Отвечая на ваши вопросы: это не вам так «повезло», это, скорее правило. Нужно уметь решать эти задачки — это значительно расширит ваши возможности по успешному трудоустройству.
А на собеседованиях в иностранные компании — я ни разу не участвовал в интервью, где таких вопросов не задавали, всегда начинают с ООП и алгоритмов.