DK
а можно сразу ссылкой? (и большое спасибо)
Сейчас найду
Size: a a a
2020 October 18
YP
Denis Krivosheev
Задача решается не на интервью, но она сложнее чем кажется...
Ну не прям простая, конечно, но вроде понятно куда думать. Дома с чаем норм.
DK
а можно сразу ссылкой? (и большое спасибо)
Вот это первая часть https://www.coursera.org/learn/algorithms-part1 (есть вторая)
Вот книга https://algs4.cs.princeton.edu/home/
Вот книга https://algs4.cs.princeton.edu/home/
DK
Yuriy Pachin
Ну не прям простая, конечно, но вроде понятно куда думать. Дома с чаем норм.
Я не знаю вашего уровня, может вам действительно легко кто знает... эффективное решение требует знание префиксных деревьев и алгоритмов над ними
аа
Denis Krivosheev
Это своими словами)
а можно подробнее? с тестами?
DK
Но в современном мире где даже квиксорт это «зачем мне надо» и «вы слишком много от меня хотите», такая задача это слишком
DK
аа ааа
а можно подробнее? с тестами?
Мы все ещё тестируем этой задачей бэкендеров на раст, поэтому полное описание задачи скинуть не могу, сори
MP
Denis Krivosheev
Вот это первая часть https://www.coursera.org/learn/algorithms-part1 (есть вторая)
Вот книга https://algs4.cs.princeton.edu/home/
Вот книга https://algs4.cs.princeton.edu/home/
🤝
DK
Для меня это было сложно... решал три дня и решил неэффективно, алгоритм получлся O(n^3)... но как оказалось я был один из немногих кто вообще хоть как то решил
YP
Denis Krivosheev
Для меня это было сложно... решал три дня и решил неэффективно, алгоритм получлся O(n^3)... но как оказалось я был один из немногих кто вообще хоть как то решил
Да, у меня в голове тоже первая мысль про такой перебор. Следующая про деревья, но что именно префиксные пока не дошел.
YP
Хотя да, префиксное будет. Грубо говоря строим такой лес высот, в таком виде не придется для каждой точки соседей оббегать.
YP
Передумал, не такая простая, пожалуй. Но интересная, прям отлично для тестового.
AP
Denis Krivosheev
Дан двумерный ландшафт местности в виде массива (массив высот). Идёт дождь, за час дождя на каждую единицу поверхности выпадает одна единица осадков. Осадки распределяются естественным образом (вода стекает в низины). Задано как долго будет идти дождь, вычислить каким будет ландшафт после этого
Кек, два скана зазиповать
DK
Кек, два скана зазиповать
Завидую вам Алексей по хорошему
YP
Кек, два скана зазиповать
Я алгоритмические функционально совсем не умею. Можешь накидать схематичное рещение?
AP
Ну я просто вспомнил эту или такую же задачку. Там тоже был ландшафт и дождь. Нужно было посчитать, сколько воды наберётся в низины
AP
Я её с учениками разбирал в своей хаскель-группке год назад
AP
Скажем, у нас есть высоты [1,2,4,2,3,5,6,3,8,5,2]
AP
> scanr1 max [1,2,4,2,3,5,6,3,8,5,2]
[8,8,8,8,8,8,8,8,8,5,2]
> scanl1 max [1,2,4,2,3,5,6,3,8,5,2]
[1,2,4,4,4,5,6,6,8,8,8]MP
погоди) может не надо тут ответ писать?)