Задача с собеседования в Яндекс
Дан массив целых чисел длины N. Массив упорядочен по возрастанию. Написать функцию, которая из этого массива получает массив квадратов чисел, упорядоченный по возрастанию
Пример:
a = [-4, -3, -2, 0, 0, 2, 3, 5] -> [0, 0, 4, 4, 9, 9, 16, 25]

Решение:
Пусть l = максимальной позиции где находится отрицательное число, если такой позиции нет то присвоим -1
Пусть r = минимальной позиции где находится положительное число, если такой позиции нет то присвоим -1
Пусть cntZero = количество нулей в массиве.

Очевидно у нас в ответе будет cntZero нулей. Давайте их сразу выпишем в ответ.
Теперь нам нужно вывести len(a) - cntZero чисел. Если l = -1 мы выводим a[r] * a[r] и увеличиваем указатель r. Если же r = -1 то мы выводим a[l] * a[l] и уменьшаем счетчик, иначе очевидно мы должны возвести в квадрат то число, которое наименьшее из |a[l]|, |a[r]|. Не забываем изменять счетчик и будьте осторожны с выходом заграницы массивы при изменения счетчика.

Время работы алгоритма O(n)

Псевдокод в комментариях: