Thank you so much for the explanation of this assessment. This is real task from real interviews in global IT companies. I have been asked to solve the similar algorithm. Watching your channel from Silicon Valley and you are doing great job Sergey!
Насчёт задач для собеседований. Очень любят давать задачу на рекурсию. Например, как обойти всю шахматную доску конём. И на динамическое программирование. Известная задача о рюкзаке. У нас имеется N предметов для каждого предмета задан его вес wi и стоимость ci. Имеется рюкзак, который вмещает вес не более W большого килограмм. Нужно набрать в рюкзак предметы как можно больше суммарной стоимости.
Я начинаю только изучать js. Первый вариант видео был одним из тестовых заданий для поступления на продвинутые курсы frontent, где уже нужно уметь работать с базовыми типами данных. На решение 6 задач давалось 24 часа и предлагали гуглить, то что не можем решить. Вот тут возник вопрос, сколько времени дается на собеседовании, что б решить такую задачу? Все решение, вполне понятно, после того как разобраться, что такое рекурсия. Но вот врятли, я бы смогла сама на данном этапе придумать такое решение или похожее. Или собеседование не рассчитано, на придумывание вот таких алгоритмов, а только на адаптацию уже готовых решений под нужную задачу? Или просто мой уровень еще не настолько продвинутый, что б находить такие решения?
Это сложная задача. Думаю, на такую задачу на собеседовании может уйти от 30 до 60 минут. При этом это не чистое время только на написание кода. На собеседовании при решении задачи необходимо озвучивать, что и как ты решаешь, + обычно еще задают сопутствующие вопросы. Бывает что большие задачи дают не на очном собеседовании, а на дом. Например высылают 3-4 задачи на какой-то платформе. И тебе необходимо решить ее так чтобы там прошли тесты изначально заложенные. Времени могут дать как неограниченное количество (но все равно будет видно сколько у тебя заняло решение), так и ограничить выполнение задания, например дать часа 2 на все задачи. Короче вариаций очень много. Поэтому важно уметь решать разного типа задачи, а на собеседовании понять какого типа это задача и применить принцип который уже тебе известен для решения.
Сергей, как вы научились решать такие задачи, какие ресурсы и какой опыт у вас был. Просто знание языка не помогает решить такие задачи, нужна логическая область мышления, как ее развивать?
Стоит тренироваться вначале на простых задачах. И рекомендую выбирать для себя какой-то определенную область и штудировать ее от простого к сложному. Например взять задачи на массивы или на манипуляции со строками и тд. Просто знание языка поможет реализовать задуманное, а вот продумывание самого алгоритма - нарабатывается практикой. Если не получается решить задачу - найти решение например на другом языке программирования. Разобрать его, а после обязательно самому с нуля написать свое решение. И не забыть про проверку на эдж кейсы.
@@frontendscience Ну смотрите, в теории и практики я знаю язык. Т.е я понимаю идеально базу, но есть методы которые я либо не заю,либо плохо понимаю, как они работают. С другой стороны, я могу решать простые задачи вроде "Полиграф". Я могу написать простую логику на js для браузера, например подход под мобильные устройствах. Возможно в базе есть пробелы, но я их не замечаю. При этом, у меня пока не получается решать сложные задачи на логику "рода банкомат". Помогите, подскажите, как дальше продолжать, что пытаться решать и писать.
Рекурсию, особенно с ветвлением было бы наглядно объяснить в виде дерева вызовов функций, а то догадаться откуда пришёл какой вызов рекурсии трудоёмко.
Вот реализация без рекурсии, а также довольно короткая (но не работает при amount = 320): function iWantToGet(amount, limits) { const res = {}; const values = Object.keys(limits).map(Number).sort((a,b) => b - a);
я конечно сильно уставший, но это мне не помешало выяснить как работает в данном моменте рекурсия, хотя это скорее из-за банальной невнимательности, я просто упустил базовый случай с пустым объектом, ввиду того, что мозг уже еле работает свое решение предоставить вряд ли сегодня смогу, а так очень классный выпуск, даже покруче лабиринта))) Отдельно хотелось бы задать вопрос по поводу проведения собесов. Недавно наткнулась на публичные собеседования в "Хекслет" на позицию "джун-фронтенд" и задача, которую задал специалист потенциальному "джуну" мягко скажем была ну очень уж простая, то есть был дан объект в котором ключами являлись буквы из слова "Hello world", а значениями были позиции на которых расположены данные буквы и нужно было лишь собрать это правильно в массив, преобразовать в строку и вуаля, хотя джун честно сказать очень сильно мешкался, волновался может быть, я пока не знаю кого это, сам только готовлюсь, но все таки почитав здесь комментарии видимо либо действительно ждет меня серьезное испытание, либо исходя из собеса на Хекслет это будет легкой прогулкой, так вот мой вопрос: видимо действительно дело случая, когда речь идет о задачах на собесах или все таки преимущественно дают достаточно сложные и Хекслет совсем не показатель? Жду ответа с нетерпением, автор канала реально топ)
Задачи могут быть разными в разных компаниях. Это очень сложно предугадать. Поэтому лучше серьезно готовиться, а потом радоваться, что было легко. И да, собеседование это выход из зоны комфорта и стрессовая ситуация. Лучше почаще тренироваться. Успехов!
@@frontendscience Это так не работает например купюры 10 9 и 1, нужная сумма 18. Ваш алгоритм дает одну купюру 10 и 8 по одной, хотя можно выдать двумя банкнотами по 9.
Моя функция рекурсивно добавляет по одной купюре каждый вызов. Если купюры выдать не удается, возвращается на шаг назад и пробует выдать купюры номиналом ниже. Для каждого вызова создаются новый объект лимитов и количества купюр, которые потенциально могут быть выданы (если данная ветвь не зайдет в тупик). function iWantToGet(amountRequired, limits) { let nominals = Object.keys(limits).map( limit => +limit).reverse(); // [1000, 500, 100, 50, 30] return tryToGive(amountRequired, {}, {...limits}); function tryToGive(required, banknotes, limits) { if (required === 0) return banknotes; for (let nominal of nominals) { if (required >= nominal && limits[nominal] > 0) { let newBanknotes = getNewBanknotes(banknotes, nominal); let newLimits = getNewLimits(limits, nominal);
let result = tryToGive(required - nominal, newBanknotes, newLimits); if (result) return result; } } } function getNewBanknotes(banknotes, nominal) { let clone = {...banknotes}; clone[nominal] = clone[nominal] + 1 || 1; return clone; } function getNewLimits(limits, nominal) { let clone = {...limits}; clone[nominal]--; return clone; } } P.S Решение автора, конечно, более оптимальное, так как в нем изначально берется максимальное число купюр с доступным номиналом, а потом уже идет "отступление" (цикл for) и нет клонирования объектов.
Опять решил со здачами, начало подсмотрел, так как никак не мог начать, а остальное сам function iWantToGet(amount, limits) { let value = new Map() let back = 0 function collect(sum, moneyToGive) { if (sum sum) { back = sum value.set('change', back) return value } } moneyToGive.splice(0, 1) collect(sum, moneyToGive) return value } let sortLimits = Object.keys(limits).map(Number).sort((a, b) => b - a) return collect(amount, sortLimits) } let limits = {1000: 5, 500: 2, 100: 5, 50: 100, 30: 6}
Thank you so much for the explanation of this assessment. This is real task from real interviews in global IT companies. I have been asked to solve the similar algorithm. Watching your channel from Silicon Valley and you are doing great job Sergey!
Really appreciate for your support! Maybe you could share with us another tasks from your interviews?
Спасибо большое) 👍👍👍Просмотрел всё на одном дыхании. Всё очень понятно.
Рады, что было полезно и доступно!
Насчёт задач для собеседований. Очень любят давать задачу на рекурсию. Например, как обойти всю шахматную доску конём. И на динамическое программирование. Известная задача о рюкзаке. У нас имеется N предметов для каждого предмета задан его вес wi и стоимость ci. Имеется рюкзак, который вмещает вес не более W большого килограмм. Нужно набрать в рюкзак предметы как можно больше суммарной стоимости.
Благодарим за отличные идеи!
Интересная задача!!! Лайк + Коммент + Подписка!
Хорошийй контент
Рад, что понравилось! Лайк + Сердечко! :)
Недавно вспоминал тебя, Сергей, помню по курсу года три назад. Потом ты из курсов пропал... В ютубе случайно нашёлся😂 Задачки люблю.
Привет! Отлично, что нашелся :) А что за курс был?
Я начинаю только изучать js. Первый вариант видео был одним из тестовых заданий для поступления на продвинутые курсы frontent, где уже нужно уметь работать с базовыми типами данных. На решение 6 задач давалось 24 часа и предлагали гуглить, то что не можем решить.
Вот тут возник вопрос, сколько времени дается на собеседовании, что б решить такую задачу?
Все решение, вполне понятно, после того как разобраться, что такое рекурсия. Но вот врятли, я бы смогла сама на данном этапе придумать такое решение или похожее. Или собеседование не рассчитано, на придумывание вот таких алгоритмов, а только на адаптацию уже готовых решений под нужную задачу? Или просто мой уровень еще не настолько продвинутый, что б находить такие решения?
Это сложная задача. Думаю, на такую задачу на собеседовании может уйти от 30 до 60 минут. При этом это не чистое время только на написание кода. На собеседовании при решении задачи необходимо озвучивать, что и как ты решаешь, + обычно еще задают сопутствующие вопросы.
Бывает что большие задачи дают не на очном собеседовании, а на дом. Например высылают 3-4 задачи на какой-то платформе. И тебе необходимо решить ее так чтобы там прошли тесты изначально заложенные. Времени могут дать как неограниченное количество (но все равно будет видно сколько у тебя заняло решение), так и ограничить выполнение задания, например дать часа 2 на все задачи. Короче вариаций очень много. Поэтому важно уметь решать разного типа задачи, а на собеседовании понять какого типа это задача и применить принцип который уже тебе известен для решения.
Только написал, что это сложная задача..... пообщался только что с другом, он сказал что у них эта задача на разминку дается :) как-то так :)
@@smashno , если это разминка, то какие тогда у друга будут СЛОЖНЫЕ задачи?)))
Сергей, как вы научились решать такие задачи, какие ресурсы и какой опыт у вас был. Просто знание языка не помогает решить такие задачи, нужна логическая область мышления, как ее развивать?
Стоит тренироваться вначале на простых задачах. И рекомендую выбирать для себя какой-то определенную область и штудировать ее от простого к сложному. Например взять задачи на массивы или на манипуляции со строками и тд. Просто знание языка поможет реализовать задуманное, а вот продумывание самого алгоритма - нарабатывается практикой. Если не получается решить задачу - найти решение например на другом языке программирования. Разобрать его, а после обязательно самому с нуля написать свое решение. И не забыть про проверку на эдж кейсы.
@@frontendscience Ну смотрите, в теории и практики я знаю язык. Т.е я понимаю идеально базу, но есть методы которые я либо не заю,либо плохо понимаю, как они работают. С другой стороны, я могу решать простые задачи вроде "Полиграф". Я могу написать простую логику на js для браузера, например подход под мобильные устройствах. Возможно в базе есть пробелы, но я их не замечаю. При этом, у меня пока не получается решать сложные задачи на логику "рода банкомат". Помогите, подскажите, как дальше продолжать, что пытаться решать и писать.
@@seryozhamangushev9638 тебе он и ответил, бери любой ресурс и решай, от простых к сложным и в определенной области
Рекурсию, особенно с ветвлением было бы наглядно объяснить в виде дерева вызовов функций, а то догадаться откуда пришёл какой вызов рекурсии трудоёмко.
Хорошая идея! Благодарим.
Вот реализация без рекурсии, а также довольно короткая (но не работает при amount = 320):
function iWantToGet(amount, limits) {
const res = {};
const values = Object.keys(limits).map(Number).sort((a,b) => b - a);
values.forEach(value => {
while (limits[value] !== 0 && amount - value >= 0) {
res[value] = res[value] ? res[value] + 1 : 1;
limits[value] -= 1;
amount -= value;
}
});
return amount === 0 ? res : 'Невозможно выдать на данную сумму';
}
Благодарю за решение. Такой вариант будет отлично работать при стандартных купюрах (как в 1м варианте задачи)
У меня как-то так вышло, просидел над ней часа 3, решение еще не смотрел)
const iWantToGet = (ammount, limits) => {
const notes = Object.keys(limits).sort((a, b) => b - a);
for(let i = 0; i < notes.length; i++) {
const note = notes[i];
if (ammount - note < 0 || limits[note] < 1) {
continue;
}
if (ammount - note === 0 && limits[note] > 0) {
limits[note] -= 1;
return {[note] : 1};
}
limits[note] -= 1;
const step = iWantToGet(ammount - note, limits);
if (step) {
step[note] = step[note] + 1 || 1;
return step;
}
limits[note] += 1;
}
return;
};
Отлично получилось! Благодарю за решение.
Ребят эта задача на литкоде есть?
Не смотрел ещё решение, возможно перемудрил немного и можно было сделать проще
'use strict';
function iWantToGet(ammountRequired, limits) {
const limitsArray = Object.keys(limits).map(Number).sort((a, b) => b - a);
let limitsObj = {
...limits
};
let sum = 0;
let result = {};
function calc() {
for (let key of limitsArray) {
if (sum + key > ammountRequired || limitsObj[key] === 0) {
continue;
} else {
sum += key;
limitsObj[key] -= 1;
result[key] = result[key] ? result[key] + 1 : 1;
if (sum !== ammountRequired) {
calc();
}
}
}
}
calc();
if (sum !== ammountRequired) {
for (const key in limitsObj) {
if (!Number.isInteger(ammountRequired / key)) limitsObj[key] = 0;
}
sum = 0;
result = {};
calc();
}
return result;
}
let limits = {
1000: 5,
500: 2,
100: 5,
50: 100,
30: 6,
};
console.log(iWantToGet(230, limits));
console.log(iWantToGet(6600, limits));
console.log(iWantToGet(1000, limits));
console.log(iWantToGet(200, limits));
console.log(iWantToGet(150, limits));
console.log(iWantToGet(120, limits));
console.log(iWantToGet(90, limits));
console.log(iWantToGet(275, limits));
Благодарю за решение
очень жизненная задача кстати, банкоматы так и работают по таким алгоритмам
🙃👌😁🤗👍
Привет. Вот альтернативный вариант решения без рекурсии:
const iWantToGet = function (amountRequired, limits) {
const result = {};
const availableNominals = Object.keys(limits)
.map(Number)
.sort((prev, next) => next - prev);
for (nominal of availableNominals) {
if (amountRequired >= nominal) {
const numberOfBancnots = Math.floor(amountRequired / nominal);
result[nominal] =
numberOfBancnots >= limits[nominal]
? limits[nominal]
: numberOfBancnots;
amountRequired -= nominal * result[nominal];
}
if (amountRequired === 0) break;
}
return result;
};
const limits = { 1000: 5, 500: 2, 100: 5, 50: 100, 30: 6 };
благодарю что поделился решением
С amountRequired = 120 не сработает
Смотрю и думаю - да почему бы не объявить функцию внутри анонимной функции внутри ОБЪЯВЛЕНИЯ ПЕРЕМЕННОЙ. джээс...
я конечно сильно уставший, но это мне не помешало выяснить как работает в данном моменте рекурсия, хотя это скорее из-за банальной невнимательности, я просто упустил базовый случай с пустым объектом, ввиду того, что мозг уже еле работает свое решение предоставить вряд ли сегодня смогу, а так очень классный выпуск, даже покруче лабиринта)))
Отдельно хотелось бы задать вопрос по поводу проведения собесов. Недавно наткнулась на публичные собеседования в "Хекслет" на позицию "джун-фронтенд" и задача, которую задал специалист потенциальному "джуну" мягко скажем была ну очень уж простая, то есть был дан объект в котором ключами являлись буквы из слова "Hello world", а значениями были позиции на которых расположены данные буквы и нужно было лишь собрать это правильно в массив, преобразовать в строку и вуаля, хотя джун честно сказать очень сильно мешкался, волновался может быть, я пока не знаю кого это, сам только готовлюсь, но все таки почитав здесь комментарии видимо либо действительно ждет меня серьезное испытание, либо исходя из собеса на Хекслет это будет легкой прогулкой, так вот мой вопрос: видимо действительно дело случая, когда речь идет о задачах на собесах или все таки преимущественно дают достаточно сложные и Хекслет совсем не показатель? Жду ответа с нетерпением, автор канала реально топ)
Задачи могут быть разными в разных компаниях. Это очень сложно предугадать. Поэтому лучше серьезно готовиться, а потом радоваться, что было легко. И да, собеседование это выход из зоны комфорта и стрессовая ситуация. Лучше почаще тренироваться. Успехов!
Я думал что цель выдать минимальным кол-вом банкнот, в такой постановке задача была бы еще интересней.
Так как мы начинаем с самых крупных банкнот, то мы как раз и пытаемся выдать минимальным количеством бонкнот
@@frontendscience Это так не работает например купюры 10 9 и 1, нужная сумма 18. Ваш алгоритм дает одну купюру 10 и 8 по одной, хотя можно выдать двумя банкнотами по 9.
@@ihorkovryhin1767 в обоих твоих решениях выдается две купюры, наркоман.
const iWantToGet = (value, limits) => {
let result = {}
if(value % 10 === 0){
while(value > 0 && value > 30) {
for (let el of Object.keys(limits).sort((a, b) => b - a)) {
if(limits[el] !== 0){
if(value >= el){
result[el] = result[el] ? result[el] + 1 : 1
value -= el
limits[el] -= 1
break
}
}
}
}
return {result, remainder: value}
}else{
alert('Please write correct number')
}
}
Моя функция рекурсивно добавляет по одной купюре каждый вызов. Если купюры выдать не удается, возвращается на шаг назад и пробует выдать купюры номиналом ниже.
Для каждого вызова создаются новый объект лимитов и количества купюр, которые потенциально могут быть выданы (если данная ветвь не зайдет в тупик).
function iWantToGet(amountRequired, limits) {
let nominals = Object.keys(limits).map( limit => +limit).reverse(); // [1000, 500, 100, 50, 30]
return tryToGive(amountRequired, {}, {...limits});
function tryToGive(required, banknotes, limits) {
if (required === 0) return banknotes;
for (let nominal of nominals) {
if (required >= nominal && limits[nominal] > 0) {
let newBanknotes = getNewBanknotes(banknotes, nominal);
let newLimits = getNewLimits(limits, nominal);
let result = tryToGive(required - nominal, newBanknotes, newLimits);
if (result) return result;
}
}
}
function getNewBanknotes(banknotes, nominal) {
let clone = {...banknotes};
clone[nominal] = clone[nominal] + 1 || 1;
return clone;
}
function getNewLimits(limits, nominal) {
let clone = {...limits};
clone[nominal]--;
return clone;
}
}
P.S Решение автора, конечно, более оптимальное, так как в нем изначально берется максимальное число купюр с доступным номиналом, а потом уже идет "отступление" (цикл for) и нет клонирования объектов.
const iWantToGet3 = (ammountRequired, limits) => {
const key = Object.keys(limits).map(Number).sort((a,b)=>b-a)
let limitsBalance = 0
for (let key in limits) limitsBalance += key * limits[key]
if (ammountRequired > limitsBalance) return 'no many'
return key.reduce((res, index) => {
while ((limits[index] !== 0 && ammountRequired - index) >= 0) {
res[index] = res[index] ? ++res[index] : 1
limits[index]--
ammountRequired -= index
}
return res
}, {})
}
Опять решил со здачами, начало подсмотрел, так как никак не мог начать, а остальное сам
function iWantToGet(amount, limits) {
let value = new Map()
let back = 0
function collect(sum, moneyToGive) {
if (sum sum) {
back = sum
value.set('change', back)
return value
}
}
moneyToGive.splice(0, 1)
collect(sum, moneyToGive)
return value
}
let sortLimits = Object.keys(limits).map(Number).sort((a, b) => b - a)
return collect(amount, sortLimits)
}
let limits = {1000: 5, 500: 2, 100: 5, 50: 100, 30: 6}