Task from a front-end interview: Finding the largest container of water | JavaScript
HTML-код
- Опубликовано: 19 июн 2024
- Привет, друзья!
Продолжаем решать задачки с собеседований! Сегодня у нас интересная задача про воду - нам необходимо найти контейнер, вмещающий максимальное количество воды (11. Container With Most Water). Эта задача помечена Medium уровнем сложности на Leetcode.
На вход нам подается массив с числами. Каждое число представляет собой вертикальную линию заданной высоты. Все линии находятся друг от друга на расстоянии 1. Нам необходимо найти такие 2 линии (2 числа) из этого массива, которые, образуя "контейнер", дадут максимально возможное количество воды. В качестве ответа необходимо вернуть максимальный "объем" воды для данного массива с числами.
Для решения данной задачи мы будем использовать популярный алгоритм с двумя указателями (two pointers).
Длина массива от 2 до 100 000. А значения в массиве могут быть от 0 до 10 000.
По условию это все.
Забыл упомянуть в видео, что сложность получившегося алгоритма с двумя указателями по времени у нас линейная O(n), а сложность по памяти - константа O(1).
👍 Присылайте ваше решение в комменатриях! С интересом посмотрю!
👍 Друзья, поддержите наш канал - поставьте этому видео лайк и поделитесь им с друзьями!
Таймкоды:
00:00 Интро
00:33 Условие задачи
02:30 Алгоритм решения брутфорсом
04:04 Алгоритм решения через два указателя
06:39 Пишем код
10:11 Проверяем решение
10:53 Присылайте ваши решения
✅ Задача на Leetcode: leetcode.com/problems/contain...
✅ Код из видео: codepen.io/puzankov/pen/ZEyKm...
👍 🤩 Будем благодарны за поддержку нашего канала на Патреоне: / frontendscience
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-science.com/
Music:
Blue Wednesday "From a friend",
Blue Wednesday & Dillan Witherow - Long Walk Short Dock.
---
#ityoutubersru #фронтенд #алгоритмы #leetcode
Забыл упомянуть в видео, что сложность получившегося алгоритма с двумя указателями по времени у нас линейная O(n), а сложность по памяти - константа O(1).
Пока не буду досматривать видео, попробую решить на литкоде) На первый взгляд просится алгоритм с квадратичной сложностью, а оказывается, можно и одним проходом справиться. Очень круто)
А где доказательство, что такое решение будет максимальным?
@@MrNonameous В видео. Как бы странно это ни звучало)
Весь алгоритм построен на принципе максимизации объема. Что я и объяснял в видео.
А если попадутся 2 одинаковые по высоте линии? Как тогда перемещать указатель?)))
@@user-or1hy4xz8u если две одинаковые по высоте линии тогда без разницы какой указатель двигать. (В видео двигается правый указатель)
Ты уйдёшь, так и не узнав, что самый большой контейнер с водой - это моя дипломная работа...
😂 Ай красавчик!!! Лучше и не скажешь.... Вспомнил как свою дипломную писал!!!
Я не програмер, учился в меде. И должен вас поправить. Гомеопатия - о где главная вода!
Огромное спасибо за полезный контент и доступное объяснение!!))
Что бы я без вас дела ) Спасибо огромное
Нереально годный контент, спасибо!
Класс! И Вам спасибо 😉
Просто кайфую от твоих алгоритмов)
Благодарю! Радуюсь)
Сергей, с праздником Вас!)
Спасибо большое за видео, очень интересно и доходчиво. Жду с нетерпением новых🔥👍
Вау! Точно! И Вас с праздником! 🎈🚀🎉
Спасибо большое за поддержку! Будем стараться))
Хорошая задача, и сама подача видео отличная, спасибо огромное 😌
Класс! И Вам спасибо :)
Нереально крутой контент🔥🔥🔥👍👍👍 Сергей, огромное спасибо за обзор и решение различных задач🤝 много полезного и интересного узнал из твоих видео👍 не сомневаюсь, что в скором времени будешь в трендах на первых местах😉 такой колоссальный труд обязательно будет оценён 💪
Ваау! Как приятно! Благодарю за поддержку и вдохновение! 🚀
отличная задачка и классное решение!
Очень Интересно!!! Спасибо!!! Крутой канал!
Класс! Рады слышать :) Благодарим за поддержку!
Як завжди круто і все чітко роз'яснено! Признаюся не рішав але код в кінці ясний, це вже хоч щось, коли розумієш рядки коду))
Да, это действительно хороший показатель. Через пару недель попробуйте вернуться к задаче, пересмотреть условие и попробовать решить по памяти. 👍
Гений!!! Все так просто решается!!! Код простой но с продуманой логикой. Благодарю за видео!!!
Благодарю Вас за поддержку! Рад, что было полезно)
Большое вам спасибо
Приветствую. Спасибо за очередную головоломку)) Недавно начал изучать js и впервые смог решить вашу задачку. К сожалению не додумался до самого оптимального способа, поэтому решил через 2 цикла.
function maxArea(heights){
let area =0
let areaMax =0
if (heights.length>=2 & heights.length
Круто, что нашли решение! На собеседованиях чаще всего с этого начинают - и потом по подсказкам ищут более оптимальное решение! Успехов Вам!
Хорошая подача, приятная графика
Благодарю за поддержку! Рад, что понравилось)
Качество видео на высоте!
Сколько времени у тебя занимает подготовка одного видео?
Благодарю, приятно слышать) Очень по-разному. На это ушло 3 вечера - съемка и монтаж с отрисовкой анимации. Я ж в свободное время это делаю.
Привет! Все хорошо, нравится твоя подача. Но можно ли музыку потише? Либо твой голос погромче
Забыли проверить без наушников в этот раз, учтем на будущее. Благодарим.
Больше подобного контента
Похоже рекомендации подсказали хороший канал:)
Рады Вам! :)
Дякую
Спасибо за подробные объяснения, я решил через n^2 и был бы готов поспорить, что такую задачу невозможно решить через n, а вот на тебе!
upd. Просмотрел все комментарии, но все решения с двумя простыми циклами немного косячные (т.е. можно подкопаться к использованию let вместо const или избыточному переприсваиванию), поэтому выкладываю свой вариант:
function maxArea(heights) {
let maxArea = 0;
for (let i = 0; i < heights.length; i++) {
for (let j = 0; j < heights.length; j++) {
const area = Math.min(heights[i], heights[j]) * Math.abs(i - j);
if (area > maxArea) maxArea = area;
}
}
return maxArea;
}
Отличный вариант с циклами! Благодарю за решение
День добрый, спасибо за интересный выпуск. А где можно найти такие же задачки, но для начинающих. Пока что сложно решать такого уровня... спасибо.
это задача Medium уровня. Можно посмотреть на задачки easy на leetcode. Или еще можно начать с задачек на codewars - выбрать 8 и 7 q там
@@frontendscience Сергей, подскажите, medium на литкоде каким уровням равен на коудварс(хотя б примерно)? я решал только на коудварс, потому интересно сравнить с литкодом свой уровень😀
Привет, мог бы дать совет, как прокачать нативку, если прям туго очень? Просто решать задачки с того же литкод? Или может есть ещё какие-нибудь варианты?
Привет. Под нативкой Вы имеете в виду нативный JS? или же алгоритмы?
@@frontendscience именно нативный, да)
@@IsrafilGuseinov ну тогда возможно какой-то курс по js пройти, чтобы систематизировать все знания и заполнить пробелы. Или например learnjavascript.ru почитать и поделать задачи.
@@frontendscience спасибо!!
@@IsrafilGuseinov успехов!
Задачу решил, но решение мне самому не нравится, слишком уж громоздкое получилось. Можно сократить за счет функций, но тогда результат вместо "быстрее 85%" будет "быстрее 40%" :)
Алгоритм решения:
1. В первом цикле for нахожу число, которое имеет наибольшую потенциальную площадь (если найдется идеальное второе число).
2. Во втором цикле прохожу по всем числам массива (кроме числа, которое получено в первом цикле) и нахожу то, которое в паре с первым даст максимальную площадь.
3. Может быть такой вариант, что найденная площадь хоть и близка, но не максимальна (это потому, что для расчета площади мы все равно берем наименьшее из двух и если первое число намного больше второго, никакой пользы это не принесет). Для этого начиная от первого числа до ближайшего конца массива ищу значение, которое в паре со вторым могло бы дать еще большую площадь.
function maxArea(height) {
let area = 0;
const last = height.length - 1;
let maxIndex;
let maxHeight;
let maxArea = 0;
let secondIndex;
let secondHeight;
for (let i = 0; i < height.length; i++) {
const current = height[i];
const maxDistance = Math.max(last - i, i);
const maximalArea = maxDistance * current;
if (maximalArea > maxArea) {
maxArea = maximalArea;
maxIndex = i;
maxHeight = current;
}
}
for (let i = 0; i < height.length; i++) {
if (i === maxIndex) continue;
const current = height[i];
const width = Math.abs(maxIndex - i);
const currentArea = width * Math.min(maxHeight, current);
if (currentArea > area) {
area = currentArea;
secondHeight = current;
secondIndex = i;
}
}
if (maxIndex > secondIndex) {
for (let i = maxIndex + 1; i < height.length; i++) {
let current = height[i];
const width = Math.abs(secondIndex - i);
const currentArea = width * Math.min(secondHeight, current);
if (currentArea > area) {
area = currentArea;
maxHeight = current;
maxIndex = i;
}
}
} else {
for (let i = maxIndex - 1; i >= 0; i--) {
let current = height[i];
const width = Math.abs(secondIndex - i);
const currentArea = width * Math.min(secondHeight, current);
if (currentArea > area) {
area = currentArea;
maxHeight = current;
maxIndex = i;
}
}
}
return area;
}
Результат:
Runtime: 84 ms, faster than 85.36%
Memory Usage: 48.9 MB, less than 6.16%
Сложность по времени: O(n)
По памяти: O(1)
необычно вышло - благодарю за решение!
Привет, спасибо за видео. А как доказать, что с помощью 2 указателей мы найдём правильное решение?
Для перебора доказательством было бы то, что по каждому проходим.
А тут мы тоже проходим по «всем большим» так как мы пытаемся максимизировать высоту линии или левой или правой и потом для найденной самой высокой,с одной из сторон, линии ищем с другой стороны линию повыше, а так как мы начинаем с противоположных сторон, мы всегда ищем с самой большой ширины.
@@frontendscience Вроде бы понял, спасибо за ответ.
Кстати мне тоже это неочевидно, поэтому видео бы назвал недостаточным для решения) круто было бы наглядно показать
А как еще более наглядно Вы предлагаете это сделать? Если я уже даже анимацию нарисовал, чтоб визуализировать то, о чем рассказываю.
@@deem5471 Тоже сразу не понял по видео. Я бы предложил следующее объяснение. Ширина вначале у нас максимальная, берем конечные палки. Уровень определяется нижней, т.е. для низкой палки уровень не будет больше ни при какой ширине (которая может быть только меньше). Результат высчитывается и на всякий случай запоминается (вдруг это максимальный окажется). Теперь низкую палку можно откинуть, т.к. для этой ширины результат есть, другой такой ширины быть не может, она максимальная (звучит диковато, но тут и так мозги заворачиваются, так что лучше поподробнее). После откинутой палки остается текущий запомненный максимум и урезанный по ширине лес оставшихся палок. И все повторяется заново.
Честно говоря, материальное представление и после этого у меня страдает, но хотя бы логически можно разрулить.
Да уж, далёк я видимо от фронтенда, хотя хотел учится на эту профессию.
Подскажите какой ide использует автор на видео?
WebStorm
@@frontendscience спасибо, удобные фишки есть, но блин она платная)
А если из бесплатных, какую бы могли посоветовать? (По опыту)
Других не использовал, поэтому, к сожалению, не могу подсказать.
о, отец выспался)
Что за ide используете?
WebStorm
Здравствуйте.
Рекурсия 10**5 раз не очень хорошо (подскажите?), но как вариант.
function getMaxVolume(arr, maxVolume) {
let max = maxVolume || 0
if(arr.length < 2) return max
let item = arr.shift()
max = Math.max(max, ...arr.map((elem, i)=>{
return Math.min(item, elem) * (i+1)
}))
return getMaxVolume(arr, max)
}
Вариант с итерацией (удалил).
UPD
В очередной раз понимаю, что практически нигде не говорится про алгоритмы решения задач, только вы упоминаете алгоритмы.
Программировать научат на любом языке, а решать задачи, по факту, ты можешь слабо, зная только язык.
Какой ресурс почитать для ознакомления со всеми алгоритмами?
Благодарю за решение. Не уверен что такой вариант пройдет на литкод, но такого решения еще не присылали )
По поводу алгоритмов: очень рекомендую книгу cracking the coding interview!
@@frontendscience
Да, на ЛитКоде решение не прошло. Как я и предполагал, слишком много памяти при больших вводных данных.
Спасибо за совет книги, почитаю.
Мой вариант решение задачи. Правда, два цикла "for()".
function maxArea(arr) {
let max = 0, counter, numberA, numberB
for(let i in arr) {
counter = 0
for(let j = i; j < arr.length; j++){
const multiply = Math.min(arr[i], arr[j]) * counter
if(multiply > max){
max = multiply
numberA = arr[i]
numberB = arr[j]
}
counter++
}
}
console.log(`${arr}
Max - ${max}, numberA = ${numberA}, numberB = ${numberB}`)
return max
}
const input = [1,8,6,2,5,4,6,3,7]
console.log(`Input1 - ${maxArea(input)}`)
Благодарю за решение )
function maxArea(arr, step) {
let areas = []
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
areas.push(Math.min(arr[i], arr[j]) * step * (j - i))
}
}
return Math.max(...areas)
}
Про дополнительные условия не вполне понял.
Благодарю за решение! Это как раз брутфорсный вариант. Дополнительные условия просто рассказывают какого размера может быть массив на leetcode и какие значения там бывают. Например из этого можно понять что делать проверку на пустой массив или то что там будет одно только число - не нужно.
@@frontendscience Досмотрел до конца, не думал, что можно так изящно решить задачу за один проход.
Серега, ты в фаанг готовишься ?
Ты мне все задачи перерешал на собеседовании! Приходится теперь новые искать 🥷
Подскажите название редактора кода
WebStorm
function findMaxS(arr) {
let squares = [];
let count = 0;
let last = arr[arr.length-1];
for (let i=arr.length-1; i>0; i--) {
if (arr[i] < last) continue;
if (arr[count] < last) count++;
last = arr[i];
squares.push((Math.min(arr[count], last))*(i-count));
}
return Math.max(...squares)
}
В данном видео скорее находиться площадь, а не объем. Объем - трехмерное пространосво (м3).
Да, м^3. Именно, что при постоянной глубине контейнера в 1 м переумножать на единицу все расчеты не имеет смысла. А вода измеряется объемом, но никак не площадью.
Заполнял заявку, хотел бы пройти собеседование, это возможно?
Алик, если Вы заполнили заявку, она у нас точно есть. Заявок у нас очень много, поэтому существует отбор.
Благодарим за доверие!
Альберт, подготовьте, пожалуйста, резюме, и заполните еще раз заявку. У нас есть лив-стрим, где можно посмотреть на подсказки, как лучше оформлять резюме (если нужно).
самый большой контейнер с водой это курсы Владилена Минина
бесплатные уроки на ютуб имеете ввиду или вы покупали и проходили платные курсы?
@@chcylabrab я скачивал его платнык курсы и как по мне - водянистая вода.
Обьясняете хорошо но фоновая музыка местами слишком громкая
В этом видео забыли проверить громкость без наушников. Учли
function maxArea(heigth) {
let value = 0;
let left = 0;
let right = heigth.length - 1;
while(left < right){
if((right - left) * Math.min(heigth[left], heigth[right]) > value){
value = (right - left) * Math.min(heigth[left], heigth[right])
}
(heigth[left] < heigth[right]) ? ++left : --right
}
return value
}
Мой 4-й сабмит, до этого не проходили тесткейсы(
let maxArea = function (height) {
let leftCurrentHeight = height[0];
let rightCurrentHeight = height[height.length - 1];
let left = 0;
let right =height.length - 1;
let maxS = 0;
while (left rightCurrentHeight) {
right -= 1;
}
}
}
return maxS;
};
благодарю за решение!
Первое что пришло в голову, решил минут за 5.
function maxArea(height) {
let max = 0;
return (function test() {
let currentElem = height[0];
height.forEach((item, index) => {
let min = Math.min(currentElem, item)
if (max < min * index) {
max = min * index;
}
});
height.splice(0, 1)
if(height.length > 1) {
return test(height)
}
return max
})()
}
Благодарю за решение, вышло компактно. PS: к сожалению литкод отдает Time limit exceeded на такие варианты
@@frontendscience да, согласен, но для собеседования думаю хватит такого решения)
@@Vel1ar1 круто, high order function, forEach, IIFE и рекурсия в одном флаконе! Интервьюер точно удивится!
В смысле больше 20 лет, вам сколько лет????
37 :) я начал зарабатывать фронтендом с 1-го курса университета :)
Если двигать только один указатель, результат не изменится. Так зачем нужен этот второй указатель?
Зря написал, надо было сначала подумать)
Java:
public class MaxWater {
public static void main(String[] args) {
int[] array1 = {1, 8, 6, 2, 5, 4, 8, 3, 7}; // 49
int[] array2 = {1, 1}; // 1
int[] array3 = {4, 3, 2, 1, 4}; // 16
int[] array4 = {1, 2, 1}; // 2
System.out.println(maxArea(array1));
System.out.println(maxArea(array2));
System.out.println(maxArea(array3));
System.out.println(maxArea(array4));
}
private static int maxArea(int[] arr){
int max = 0;
int left = 0;
int right = arr.length - 1;
while(left < right) {
int currentVolume = Math.min(arr[left], arr[right]) * (right - left);
max = Math.max(currentVolume, max);
if (arr[left] < arr[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
const input1 = [1, 8, 6, 2, 5, 4, 8, 3, 7]; // 49
const input2 = [1, 1]; // 1
const input3 = [4, 3, 2, 1, 4]; // 16
const input4 = [1, 2, 1]; // 2
function maxArea(height) {
const max = Math.max(...height);
let total = 0;
for (let i = 0; i < max; i++) {
let leftIdx = 0;
let rightIdx = 0;
let totalFromLevel = 0;
for (let j = 0; j < height.length; j++) {
if (height[j] >= i + 1) {
leftIdx = j;
break;
}
}
for (let j = height.length - 1; j >= 0; j--) {
if (height[j] >= i + 1) {
rightIdx = j;
break;
}
}
totalFromLevel = (rightIdx - leftIdx) * (i + 1);
if (totalFromLevel > total)
total = totalFromLevel;
}
return total;
}
console.log(maxArea(input1));
console.log(maxArea(input2));
console.log(maxArea(input3));
console.log(maxArea(input4));
function area() {
let max = 0;
arr.forEach((item, i) => {
arr.forEach((item2, i2) => {
if (max < Math.min(item, item2) * (i2-i)) {
max = Math.min(item, item2) * (i2-i)
}
})
})
return max
}
4:00 кажется тут будет ~ О(n^2 / 2). Мы же проверяем значения по диагонали а не вообще по всему массиву
Рекомендую посмотреть видео про то, как рассчитать сложность по BIG O: ruclips.net/video/Fu4BzQNN0Qs/видео.html
const maxArea = (heights) => {
let l = 0;
let r = heights.length-1;
let maxVolume = 0;
while(l!=r){
const leftHeight = heights[l];
const rightHeight = heights[r];
let minHeight = 0;
const length = r-l;
if(leftHeight > rightHeight){
minHeight = rightHeight;
r--;
}
else{
minHeight = leftHeight;
l++;
}
const currentMax = length * minHeight;
if(maxVolume < currentMax){
maxVolume = currentMax;
}
}
return maxVolume;
};
Благодарю за решение! Классно вышло!
скажите, в 34 года во фронтенд разработчика уже поезд ушел или вполне реально? я НЕ гений, самый обычный ум.
Вполне реально. Выходят и позже. Успехов Вам!
@@frontendscience ну если серьезно, работаю вообще по электронике но образование высшее техническое. Азы программирования как бы знаю и понимаю, но в 34 года мой уровень как у ребят которые в 19 лет. Кому я буду нужен старый весь когда кругом молодые все?
@@user-dl3zo8xf7g ну с таким подходом Вы окажитесь правым. Но я за все годы моей работы ни разу не видел, что 34 года проблема, чтоб начать. За 3 года можно вырасти до таких высот, если поставить себе цель, открыть себе любые двери! Все зависит только от человека и его мотивации. Ну и умения превратить свой прошлый опыт в плюс и ценность на новом месте и для нового работодателя.
кто придумывает такие задачи ?
Доктор, откуда у вас такие картинки (с) 😂
криво косо, но я пытался
function maxArea(height){
let water = 0,
max = 0,
pointer = 0
for(let i = 0; i < height.length - 1; i++){
if(max < height[i]){
max = height[i]
pointer = i
}
water = max > height[i + 1] ? height[i + 1] * (i - poiner + 1) : max * (i - pointer + 1)
}
return water
}
Спасибо огромное за Ваши труды
const maxArea = (heights) => {
return heights.reduce((accum, firstHeight, indexFirstHeight, heights) => {
const maxAreaBetweenFirstElementAndOtherOne = heights.reduce(
(accum, secondHeight, indexSecondHeight) => {
const differenceIndexes = Math.abs(
indexFirstHeight - indexSecondHeight
);
const minHeight =
firstHeight > secondHeight ? secondHeight : firstHeight;
const area = minHeight * differenceIndexes;
return accum < area ? area : accum;
},
0
);
return accum < maxAreaBetweenFirstElementAndOtherOne
? maxAreaBetweenFirstElementAndOtherOne
: accum;
}, 0);
};
Благодарю за поддержку!
Решение вышло хорошее и на базовых тесткейсах отлично работает. Но вот на очень больших входящих данных на литкоде не проходит так сложность решения вышла квадратичная. Пишет: Time Limit Exceeded
Для тех кто изучал С++ эта задача примитивная. Там такие задачи решают: как семечки...