Задача с собеседования: Кирпичная Стена | JavaScript

Привет друзья. У нас для вас новая классная задача с JS собеседования — Кирпичная стена (554. Brick Wall). На LeetCode она Medium уровня сложности. Эту задачу нам прислал один из подписчиков, которому она попалась на собеседовании. Поэтому спасибо за вашу активность, присылайте еще!

По условию: у нас есть прямоугольная кирпичная стена высотой n кирпичей. Все кирпичи одинаковой высоты, но могут быть различной ширины. В каждом ряду может быть разное количество различных кирпичей, но ширина всех рядов кирпичей всегда будет одинакова.
Если провести вертикальную линию по стене, то такая линия будет пересекать какое-то количество кирпичей. Необходимо найти, какое минимальное количество кирпичей может пересекать такая вертикальная линия. Важно отметить, что если линия проходит на стыке двух кирпичей, то это не считается пересечением. Еще один момент — мы не можем провести линию с одной из сторон стены — линия должна быть именно во внутренней части стены.

Помним, что все задачи с LeetСode нужно решать наиболее оптимальным способом как по времени, так и по памяти. (Новичкам в этой теме рекомендую прочитать про Big O).

Присылайте свои решения в комментариях! С интересом их посмотрю!

Таймкоды:
00:00 Интро
00:45 Условие задачи
02:31 Алгоритм решения
03:44 Пишем код
08:04 Проверяем решение
08:41 Сложность алгоритма
09:10 Присылайте ваши решения

👍С интересом жду ваши решения в комментариях!
👍Друзья, поддержите наш канал и это видео лайком и репостом!

---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
---

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

---

Music:
Blue Wednesday - Secret Garden
Blue Wednesday - Apple pies & butterflies

---

#itсобеседование #ityoutubersru​ #фронтенд #алгоритмы #leetcode

[KanalReal]

хорошее видео...чтобы понизить самооценку.)

[SerzhNesteruk]

Спасибо за интересную задачу!
Решил почти точно так же:

const leastBricks = wall => {
const map = {};
for (const row of wall) {
let pos = 0;
for (let i = 0; i < row.length - 1; i++) {
pos += row[i];
map[pos] = (map[pos] || 0) + 1;
}
}
return wall.length - Math.max(0, ...Object.values(map));
};

[Doox]

2 час понимал ваше решение. Оно очень хорошее.

[yuriilukianovych]

Очень интересно!!!! Побольше таких задач! Люблю решать задачки))) (наверное, привычка со школы😉)

[VDyrda]

Сергей спасибо за интересную задачу, отличная идея - предлагать ставить на паузу чтобы решить самому! У меня вышло такое решение:

const leastBricks = function(wall) {
const map = {}
let maxUnbroken = 0
wall.forEach(row => row.reduce((acc, brick) => {
map[acc] = 1 + (map[acc] || 0)
maxUnbroken = Math.max(maxUnbroken, map[acc])
return acc + brick
})
)
return wall.length - maxUnbroken
};

Runtime: 84 ms, faster than 88.31% of JavaScript online submissions for Brick Wall.
Memory Usage: 44.1 MB, less than 64.94% of JavaScript online submissions for Brick Wall.

[GreenGotty]

Спасибо большое за задачки! Должен сказать, у Вас дар проводить интервью! Просто до Ваших видео я дольше 5 минут не выдерживал смотреть собеседования..
Смотрю Ваш канал с удовольствием в подготовку к первой работе в IT!
По коду у меня вышло так:
var leastBricks = function(wall) {
const map = {};
for (let i = 0; i < wall.length; i++) {
let hole = 0;
for (let y = 0; y < wall[i].length - 1; y++) {
const brick = wall[i][y];
hole = hole + brick;
map[hole] = (map[hole] || 0) + 1;
}
}

if (Object.keys(map).length === 0) return wall.length;
const maxHoles =

return wall.length - maxHoles;
};
l337Сode пишет 84 ms, faster than 85.36%. По памяти хуже, но я польщен.. хотя не знаю, что там такое сабмитят..)

[HEIT_CHANNEL]

Спасибо за решение, скоро пригодится для устройства на работу

[lostsouls]

Супер решение. Самое сложное это понять и построить алгоритм решения, а реализовать уже намного легче. Сергей скажите когда будут новые "собеседования"?)

[Doox]

Мне очень понравилась эта задача. Побольше видео с задачами!)

[stanosichnuk]

Делал месяц назад эту задачу на пайтоне, но ответ нужен был несколько иной, а именно:
длина от левой стены до места где собственно проводится линия с минимальным количеством пересечений и чтобы программа псевдографикой прорисовала саму стену с кирпичами и пересечениями))

[sergthere]

норм задачка и вполне на джуна кмк
у меня получилось O(m*n*2), считал именно пересечения

const leastBricks = wall => {
// создаю массив с пересечениями на каждом шаге на каждом уровне. 0 — нет пересечения, 1 — есть
const tempWall = wall.map(row => {
// массив с пересечениями на данном уровне
const xs = []
// вспомогательная рекурсивная функция, проставляет 1ки в соответствии с шириной кирпича или 0
const push = x => x ? (xs.push(1), push(x-1)) : xs.push(0)
// собираем пересечения
for (let brick of row) {
push(brick - 1)
}
return xs
})

// считаем общее кол-во пересечений на каждом шаге и сравниваем с минимальным значением
let result = wall.length
for (let x = 0; x < tempWall[0].length-1; x++) {
let sum = 0
for (let y = 0; y < tempWall.length; y++) {
sum += tempWall[y][x]
}
result = Math.min(result, sum)
}

return result
}

[YanasChanell]

Я проводилась два часа, алгоритм придумала быстро, но код у меня получился с макаронной фабрики, раз в пять длиннее наверное :) надо учиться оптимизировать

[yuriilukianovych]

Сергей, а это увеличивает сложность алгоритма, что я максимальный элемент полученного Map искал таким образом: Просто не додумался как Вы сделать с max.

[РоманСарваров-чл]

В bigO получается нужно смотреть не только на аргументы функции? Тут ты сказал n*m, хотя у нас один аргумент - массив...
Я бы изначально ответил O(n)

[disconnect-forever]

Спасибо, очень понравилась и задача, и решение. Сергей, скажите пожалуйста, почему LeetСode, а не Codewars? Слышал, что когда-то на курсах GOIT студенты занимались на Codewars. LeetСode лучше?

[fedordostoevskiy]

Код простой очень, но так и не понял про линию и кирпичи. Что считаем? 😄😄😄

[Youtubeaccount-fb]

В случае [[1][1][1]] ответ не определен, потому что линию нельзя провести по краям стены, а у представленной стены линий внутри стены нет. Это если докопаться

[antontishchenko]

Math.max вызовется намного больше раз, чем можно. Минимально возможное количество вызывов равно количеству элементов в map. А тут вызовется по количеству кирпичей, что всегда больше количества элементов в map, кроме случая с одним рядом кирпичей.

[Fxgleb]

почему в данном примере массив и хеш создаются через let? не правильней ли было их создавать через const?

[NEMEDYINYI]

Скажите пожалуйста на какой обтетив и какую камеру вы снимаете?