Задача "Перемещение нулей (MoveZeros)"

Сегодня будет немного не обычная задачка.
Мне её задали в МТС Банке на позицию Java Engineer. Естественно, она была на Java. Я слегка адаптировал под PL/SQL.
На позиции "Oracle-разработчик" такие задачи не дают. Однако для того, чтобы размять мозг она подойдет 🧠

Суть задач "с LeetCode" - реализация функционала за как можно меньшую сложность - O. Условно, если задачу можно решить за O(N*N), то скорее всего, есть более оптимальное решение. На собесах обязательно учитывают смог ли ты решить задачу оптимально.

Условия

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:
Input: [0,12,0,1,3]
Output: [12,1,3,0,0]

Нашел эту задачку на Leetcode. К сожалению, там нет PL/SQL, зато есть другие языки.

Заготовка под код

Разберем задачу в четверг 🎓

Обсудить в чатике 💬

#задача #leetcode
Oracle Developer

Задача "Перемещение нулей (MoveZeros)". Решение

Друзья, всем привет!

Во вторник опубликовал не типичную задачу для собеседования на позицию Oracle Developer. Однако, такие задачи очень часто встречаются на позиции Front/Backend-разработчиков.

Как это происходит на собеседовании
🔹 Вы либо шарите экран, либо подключаетесь к online IDE, в которой есть подсветка синтаксиса. Чаще всего, скомпилировать код возможности нет. Автоподсказок то же (хотя встречались с наличием).
🔹 У вас есть ограниченное количество времени (30м-1ч) на решение задачи.
🔹 От вас хотят услышать размышления вслух хода решения.
🔹 Требуется быстрое (O) и низкое, по затратам памяти, решение.

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

А как насчет написать дерево и пройтись по нему? найти его максимальную глубину? Или инвертировать односвязный список? Да, то, что старательно забыто после окончания универа 😊

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

Задача вторника может быть решена разными способами
Когда она мне попалась на собесе, я решил таким алгоритмом (на Java, конечно). В целом, это удовлетворило интервьювера. Я не утверждаю, что нет более идеального решения, вполне возможно, но в стрессовой ситуации за 30 минут родилось именно это.
Ребята в чатике накидали довольно много разных решений 🔥

Если такой тип задач интересен, могу публиковать время от времени 😉

Обсудить в чатике 💬

#решениезадачи #leetcode
Oracle Developer

Leetcode. Two Sum (Легкий уровень)

Друзья, всем привет!

Что-то давно у нас не было технических задачек. А сегодня как раз пятница, можно размяться на последок и пойти пить пивко/молочко.

На этот раз задачка будет с LeetCode. Я уже делал пару постов на тему LeetCode. На собесах на разработчика БД это скорее диковинка. Для всех остальных специальностей, алгоритмическая секция - это обязательная часть. Поэтому я периодически разминаю мозг, нужно быть в тонусе 🧠

Задача
Дано массив целых чисел nums и целое число target. Найдите индексы двух чисел, которые в сумме дают target.

Пример
Input: nums = [2, 7, 11, 15], target = 9
Output: [1, 2] // Потому что nums[1] + nums[2] = 2 + 7 = 9

Реализуем на PL/SQL.
—

Я нашел как минимум два способа решения этой задачки. Один - с хреновой трудоемкостью, второй - лучше.
Будет интересно, сколькими способами решите вы. Пишите в чатик.

Рекомендую справиться без ChatGPT :
▫️на собесе не будет возможности;
▫️развиваете 🧠

Ответы опубликую вечером 🎓

Обсудить в чате 💬

#задача #leetcode
Канал Oracle Developer | Чатик💬

Leetcode. Two Sum (Легкий уровень). Решение

Два моих варианта.

1️⃣ В лоб. Цикл в цикле

declare
  type t_nums is table of number(38);

  v_nums     t_nums := t_nums(-2, -7, 11, 15);
  v_target number(38) := -9;
begin
  for i in 1 .. v_nums.count() - 1 loop  
    for j in i + 1 .. v_nums.count() loop

      if v_nums(i) + v_nums(j) = v_target then
        dbms_output.put_line('Answer: ' || i || ' - ' || j);
        exit;
      end if;    

    end loop;  
  end loop;

end;
/

🔸Суть решения: проходим по массиву дважды, перебирая все возможные комбинации.
🔸Трудоемкость: O(N*N). Далеко не самая лучшая.
🔸Собеседующие ждут от вас более элегантного решения. С такой трудоемкостью могут не зачесть. В любом случае, лучше хотя бы так, чем совсем никак.


2️⃣ Ассоциативный массив

declare
  type t_assoc is table of number(38) index by pls_integer;
  type t_nums is table of number(38);

  v_nums      t_nums := t_nums(2, 7, 11, 15);
  v_index_num t_assoc;
  v_target    number(38) := 9;
  v_rest      number(38);
begin

  for i in 1 .. v_nums.count() loop
    v_rest := v_target - v_nums(i);
    
    if v_index_num.exists(v_rest) then
      dbms_output.put_line('Answer: ' || v_index_num(v_rest) || ' - ' || i);
      exit;
    end if;
    
    v_index_num(v_nums(i)) := i;
  
  end loop;

end;
/

🔸Суть решения: заполняем ассоциативный массив элементами, где ключ - это число, значение - позиция в исходном массиве. Рассчитывая каждый раз остаток (v_rest) мы проверяем, есть ли подходящее значение в ассоциативном массиве.
🔸Трудоемкость: O(N).
🔸 Чего-то такого от нас хотят увидеть на собесе.

Надеюсь вам понравилось. Всем хорошей пятницы и выходных!
Если сегодня собираешься хлопнуть пивка ставь 🍺, если трезвенник/язвенник ставь 🍼

На следующей недели будет очень интересный материал. Не переключайтесь 😄

Обсудить в чате 💬

#задача #leetcode
Канал Oracle Developer | Чатик💬