Interview Task: Brick Wall | JavaScript

[@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)); };

[@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.

[@frontendscience]

Благодарю за решение! Отлично вышло!

[@donybrorahmanov8068]

Спасибо вам Сергей за контент!

[@Doox911]

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

[@frontendscience]

Рад, что было полезно! Восхищаюсь Вашим упорством! Хорошее качество)

[@yuriilukianovych8660]

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

[@frontendscience]

Рад слышать! Присылайте решения!

[@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 = Math.max(...Object.values(map)); return wall.length - maxHoles; }; l337Сode пишет 84 ms, faster than 85.36%. По памяти хуже, но я польщен.. хотя не знаю, что там такое сабмитят..)

[@frontendscience]

Благодарю за поддержку! Отличное решение!

[@АндрейБочарников-х5ъ]

Ты аж вспотел, ух и задачка)

[@frontendscience]

:) смешно

[@HEIT_CHANNEL]

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

[@frontendscience]

Желаем успехов!

[@pavlo2846]

ого, жара в студии:)

[@Doox911]

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

[@frontendscience]

Рад, что понравилось) Будут обязательно!

[@lostsouls3151]

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

[@frontendscience]

Да часто придумать Как - самое сложное. Но потом реализовать это в коде тоже важно ). Скоро будут! :)

[@stanosichnuk5871]

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

[@frontendscience]

Благодарим, что поделились

[@anton-vr5xw]

Круто, спасибо)

[@frontendscience]

Рад, что понравилось! Спасибо за просмотр)

[@koshakkoshakov7104]

Спасибо за видео!

[@frontendscience]

Рад, если было полезно)

[@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 }

[@frontendscience]

Благодарю за решение! В Big O можно отбрасывать все константы - так что O(n*m*2) => O(n*m)

[@yuriilukianovych8660]

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

[@frontendscience]

общая сложность не изменится

[@talivel118]

return wall.length - map ? map[Math.max(...Object.values(map))] : 0 . Так вроде тоже норм?

[@fedordostoevskiy4209]

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

[@yuryitikhonoff9631]

Great job. Thanks a lot for your efforts.

[@frontendscience]

Thanks a lot for Your support! 💟 We are Your fans!

[@YanasChanell]

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

[@frontendscience]

Класс! Это очень круто, что сами додумались и нашли все же решение. Вдохновляют такие сообщения! Навык оптимизации приходит со временем) Желаю успехов Вам!

[@talivel118]

let wall = [[1,2,2,1],[3,1,2],[],[4,2],[1,5],[]] const leastBricks = function (wall) { let allLine = {} for (let i = 0; i < wall.length; i++) { let next = 0 for (let j = 0; j < wall[i].length; j++) { let current = wall[i][j] next += current current = next if (!allLine[current]) { allLine[current] = 1 } else { allLine[current] += 1 } } } let keyVal = Object.keys(allLine) let last = keyVal.pop() delete allLine[last] let max = 0 keyVal = Object.keys(allLine) for (let i = 0; i < keyVal.length; i++) { if (allLine[keyVal[i]] > max) { max = allLine[keyVal[i]] } } return wall.length - max } console.log(leastBricks(wall)) жду ответочку;)

[@NEMEDYINYI]

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

[@frontendscience]

Canon D800 + canon 50mm 1.8

[@SweettyDavid]

лайк, в мене така була)

[@Fxgleb]

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

[@frontendscience]

«Правильного» ответа нет. Тут это вопрос кодстайла.

[@AzamatAbduvohidov99]

kruto

[@disconnect-forever]

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

[@frontendscience]

Благодарю за поддержку! И то и то - отличные ресурсы. Просто для подготовки алгоритмических собеседований мне больше нравится именно leetcode. Там есть отличные подборки задач которые дают в разных компаниях типа FAANG.Хотя раньше сидел именно на codewars )

[@disconnect-forever]

@@frontendscience Спасибо, обязательно посмотрю на LeetСode )

[@LonliLokli]

@@frontendscience Мне жалко $35 / month :(

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

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

[@frontendscience]

Ну тут дело в том что сам аргумент функции это двумерный массив. Обычно их сложность записывают через «ширину» и «высоту». Так как могут быть задачи где n и m по разному растут. Например n *m^2. Еще можно посмотреть чуть больше информации про BigO здесь: kzbin.info/www/bejne/fKaXc62Hg7Njh9U

[@MrColins710]

класна задачка

[@frontendscience]

Рад что понравилась!

[@antontishchenko294]

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

[@frontendscience]

Вопрос был не в самом количестве операций. Фраза про "дополнительные телодвижения" имела в виду - делать дополнительные обходы. По производительности эти оба варианта практически не отличаются - (я замерял)

[@antontishchenko294]

@@frontendscience Если у вас было два варианта(я делаю такой вывод из того, что вы сравнивали производительность), почему вы выложили видео с тем, что хуже?? И производительность будет зависить от входных данных. На каких данных вы тестировали? Проверяли ли вы производительность такого варинта [[1],[1],[1], ..., [1]]? Когда очень много рядов, но очень мало кирпичей в каждом ряду?

[@frontendscience]

@@antontishchenko294 тестировал разные варианты. Тестировал при 10-20 тысячах строк/кирпичей. С разными вариациями. На этих объемах данных разница была +- 0.1-0.5%. Что в рамках оставшегося времени - не существенно. Я выбрал тот вариант где меньше кода, проще поддержка и будет понятней разобраться.

[@awenn2015]

Привет, можешь решить задачку одну интересную, есть смысл такой, есть лист например бумаги, его можно представить в виде матрицы с определённым размером, и фигуры прямоугольного типа, квадраты и тд, и нужно написать функцию которая переберёт все варианты и разместит фигуры на листе что бы получилось как можно меньше затрат по листам, сам придумал для одной работы но хз как реализовать ))

[@frontendscience]

Тут звучит как задача на динамическое программирование. Рекомендую посмотреть на решение "задачи о рюкзаке". Думаю натолкнет на идеи с решением твоей задачи!

[@awenn2015]

@@frontendscience спасибо )

[@wisarty]

Дякую

[@frontendscience]

Радий, що було корисно!

[@whiteguards43]

Условие задачи понял с трудом, а вот как в массиве в одну строку разглядеть стену, где пересекаются кирпичи, вообще не понял(

[@Youtubeaccount-f5b]

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

[@frontendscience]

как раз таки определен! тебе прийдется проводить линию прямо по кирпичам - что даст пересечение 3х кирпичей! То что мы проводили линию именно по стыкам - дискретно - именно для того найти минимальное количество кирпичей. Линия то может быть проведена в любом месте - не обязательно по стыкам.

[@Youtubeaccount-f5b]

Согласен

[@vvindover]

const bricks = [[1, 2, 2, 1], [3, 1, 2], [1, 3, 2], [2, 4], [3, 1, 2], [1, 3, 1, 1]] const walls = {} for (const b of bricks) { let s = b[0] for (let i = 1; i < b.length; i++) { walls[s] = (walls[s] || 0) + 1 s += b[i] } } console.log(bricks.length - Math.max(...Object.values(walls)))

[@frontendscience]

Благодарю за решение. Но к сожалению на. эджкейсе отрабатывает не корректно: Input [[1],[1],[1]] Output Infinity Expected 3

[@inqvisitor3722]

я тупой( не смог придумать алгоритм. Подскажите, как развить навык составления алгоритмов?

[@frontendscience]

Решать задачи. Это приходит с опытом. Если не получается самому решить то искать и разбирать решения. Потом попробовать самому решить ту де задачу без подсказки. Так лучше запоминаться будет.

[@МаркКонаков-ж8ч]

На питоне так получилось: def leastBricks(wall): new_wall = [] for brick in wall: new_brick = [] for i in range(1, len(brick)): new_brick.append(sum(brick[:i])) new_wall.append(new_brick) dict_counter = {} for brick in new_wall: for v in set(brick): if v in dict_counter: dict_counter[v] += 1 else: dict_counter[v] = 1 if len(dict_counter) > 0: return len(wall) - max(dict_counter.values()) else: return len(wall)

[@frontendscience]

Благодарю за решение.

[@MrShevrin]

сначала ничего не понял,а потом прописал в консоль переменные и снова ничего не понял) потом поставил точки дебага и снова на 5й итерации запутался! пересмотрел видео в 4й раз, описал в консоль.логи переменные как я их понял ("длина кирпича", "расстояние от края" "результирующий hashMap" и как понял!!!

[@frontendscience]

Круто! ))) 👍🤓

[@ghost8652]

при ширине row, равной ширине кирпича (как в последнем примере), у нас в map ничего храниться не будет, т.к. в условии внутреннего цикла for указано условие итерации n < row.length - 1. Объект по-просту не заполнится, отсюда max = 0.

[@Kayander1]

Leetcode не принимает этот код. С условием [[1], [1], [1]] вернётся 0, хотя нужно 3.

[@frontendscience]

Возможно ошиблись когда перепечатывали. Код работает. paste.pics/D68WD

[@Kayander1]

@@frontendscience Да, косяк был в цикле.) Спасибо за видео!

[@Ramosok]

[@DENisHolden1]

Не нравится мое решение. Но что есть(( const leastBricks = function (wall){ let columns = wall[0].reduce((acc, val)=>acc+val) - 1; // кол-во вертикальных колонок для подсчета let maxSum = 0; for (let column = 1; column

[@DENisHolden1]

ну да.. Надо было использовать хэш мап. Теперь буду знать. Спасибо!

[@frontendscience]

Благодарю за решение! Да вышло не оптимально, НО зато сам решил. А это важно!

[@evgeniichikishev2096]

я так сделал function leastBricks(wall) { let countsPath = {}; let path = 0; wall.forEach(row => { row.reduce((currentBrick, nextBrick) => { path = currentBrick + nextBrick; if (path != 1 && path != wall.length) { if (!countsPath[path]) countsPath[path] = 1; else countsPath[path] += 1; } return path; }, 0); }); return wall.length-Math.max(...Object.values(countsPath)); }

[@vadymchecherinda2858]

Решение как всегда простое, начал "копать" не в том направлении ( DFS / BFS ), попытался решить, не вышло. За решение спасибо.

[@frontendscience]

Рад, что понравилось!)

[@kostyakotov3171]

Как то так...) const brickSlice = (temp) => { const res = {} temp.forEach((el, i) => { el.forEach((n, index) => { if(n > 1) temp[i][index] = [...new Array(n-1).fill(0), 1] }) el.flat().forEach((el,i) => { if(!res[i + 1]) res[i + 1] = 0 res[i + 1] += el }) }) return Object.entries(res).sort((a,b) => a[1] - b[1])[0] }

[@Sleep88Walker]

let myWall = [[2, 4], [1, 2, 1, 2], [3, 1, 1, 1], [1, 1, 2, 2]]; let getMinBricks = function (wall) { let length = 0; wall[0].forEach(e => length += e); let joints = []; for (let i = 0; i < length - 1; i++) { joints[i] = 0; } wall.forEach(row => { let pos = -1; //-1 ибо не учитываем нулевой шов row.forEach(brick => { pos += brick; if (pos < length - 1) // последний шов так же не учавствует joints[pos]++; }); }) console.log(joints); return wall.length - Math.max(...joints); } console.log(getMinBricks(myWall));

[@frontendscience]

Благодарю за решение!

[@alexanderkim7241]

Жарко вам 😂Или от задачи вспотели?

[@frontendscience]

Судя по количеству комментариев об этом - это был крутой "маркетинговый" ход для увеличения количества комментариев.😂

[@vitaliyskorickiy8701]

я надеюсь это не джуновская задача? )))

[@frontendscience]

Вряд ли ее дадут джуну. Скорее миддл+

[@eduardgrigoryan6052]

у меня получился вот так 2:19

[@anazkomult]

У меня получилось прямо как у Чарли Шина с забором. На тесте с [[100000000],[100000000],[100000000]] все упало. :))))

[@frontendscience]

😂

[@МишаМихаил-ф7х]

Это задачи уровня не джунского точно, так что кто изучает языки сейчас им на это внимание обращать не стоит. Я бы даже сказал что они наоборот затормозят вас в обучении. Кто учит язык, лучше заняться самим синтаксисом.

[@bw0917]

я думал это на джуна

[@frontendscience]

Ты знаешь, очень зависит от компании. Чаще всего такого рода задачи будут на миддл уровне, бывают случаи, что и на синьора дадут. В Яндексе такое могут и на джуна дать)

[@bw0917]

@@frontendscience Яндекс О_О

[@bw0917]

@@frontendscience это была шутка насчёт Джуна , прост уже реально иногда такое можно встретить ) совсем планку скоро загонят в небеса )) тогда можно будет мемчики делать с песельом , Джун 2005 года вс Джун 2021 года )🤣

[@TheKOTLUIS]

ничего не понятно как это сделано - просто жесть и это же на джуна задачка =_= и это я типа олимпиады с математики выигрывал просто ору в голосину)) а говорят "программистом может стать каждый" ага ага

[@frontendscience]

Во-первых, кто тебе сказал, что это задача на джуна? и, во-вторых, кто сказал, что достаточно в школе олимпиады по математике выигрывать и можно не учить профессию? :)

[@hakooplayplay3212]

Тоже выигрывал олимпиады по математике, но тут немного иной случай. Просто нужно немного иметь опыта решения подобных задач. Литкодом особо не увлекался, но когда 2 месяца назад готовился к тех.интервью недельку провел изучая типы задач и их решения. Как итог в начале видео поставил данную задачу на паузу и даже без листка и ручки нашел решение секунд за 10 просто закрыв глаза. Задача совсем простая и логика ее решения очень прямолинейна. Бывают задачи гораздо более специфичные на знание более узких нишевых алгоритмов, а тут банальная логика. Посидите на литкоде недельку и такие будете щелкать как орешки, это легко тренируется.

[@Doox911]

Решал 3 часа(

[@frontendscience]

Куда-то пропал Ваш коммент с решением. Не могу даже посмотреть. Видать, ютуб из-за ссылки удалил.

[@Doox911]

@@frontendscience Работаю разработчиком 3 года и не думал, что для меня это будет так сложно.. Спасибо вам ещё раз. Отличная подача материала.

[@Doox911]

@@frontendscience doox911\/42fc72339fd3bc61d1111b08dacdf628(Гист)

[@frontendscience]

передачку получил ) благодарю за решение! )