Задачки с собеседований


Очередная задачка с собеседований. На этот раз написать функцию для нахождения наибольшего общего делителя. Вариант решения будем писать на JS, но его легко повторить и на других языках, если понять суть.

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

Наибольший общий делитель (НОД) — это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Вариант НОД без рекурсии

Напишем функцию GCD(Greatest Common Divisor) без рекурсии:

function gcd(x, y) {
while (y !== 0) y = x % (x = y);
return x;
}
console.log( gcd(21, 14) ); // = 7

Эта же функция в ES6+ стиле ( just4fun )

const gcd = ($,_)=>((()=>{while (_)(_)=($)%($=_)}) ($),($) );

Спросите что это и зачем я так написал? Отвечу: ради удовольствия. Это чисто размять мозги. Большая часть скобочек бессмысленна и добавлена ради симметрии и красоты запутанности. Код специально написан с повышенной когнитивной нагрузкой, чтобы произошла акселерация мнемонической деятельности мозга. Минимальный рабочий вариант без “выпендрежа” я показал уже и могу позволить себе теперь оттянуться.

Как он родился в таком виде? Я сам себе поставил ограничения:

  • обязательно использовать while
  • нельзя использовать слово return

Так я иногда развлекаюсь вечерами. Как говорится, кто прошел квест https://alf.nu/ReturnTrue и кто туда задеплоил 4 задачи, тот по другому писать не умеет (мой ник MAY✪R , если вдруг что) ☺

Как-нибудь я сделаю разбор задач из этого квеста. Это не про собеседования в прямом смысле, но чтобы решить эти задачи нужно очень хорошо разбираться в вашем инструменте, в нашем случае в JS. Такие головоломки заставляют почитать спеку, документацию, поразбираться в том, как работает V8 и почему он делает то, что делает. Полезное занятие, я вам скажу.

Кстати, если убрать лишние скобочки, то эта функция будет выглядеть немного проще и понятнее:

const gcd = (x,y)=>((_=>{while(y) y=x %(x=y)})(),x);

И конечно же если бы нужно было просто описать ее в ES6+ стиле, то мы просто написали копию первоначальной функции:

const gcd = (x, y) => {
while (y !== 0) y = x % (x = y);
return x;
}

Но это же ску-чно.

Рекурсивный алгоритм на ES6+

Ну и напоследок рабочий вариант с использованием рекурсивной функции.

const gcd = (x, y) =>  x ? gcd(y%x, x) : y;
// или
const
gcd = (x, y) => !y ? x : gcd(y, x%y);

Никакой магии. Все по делу.


Лайк, хлопок, шер. Слушайте меня в iTunes, подписывайтесь на Телеграм канал или Вконтакте.