Yuri
я вообще правильно прикидываю о большое?
Yuri
представляю худший случай и прикидываю, как будет расти количество операций относительно размера массива
Evgeniy
В данном случае правильно
Evgeniy
https://leetcode.com/problems/maximum-subarray/discuss/561729/C-simple-solution-using-dynamic-programming-O(1)-space
Yuri
вообще крутой этот кадан
Evgeniy
это я решал эту задачу
Evgeniy
там чуть грубо вышло, но суть правильная
Evgeniy
https://leetcode.com/problems/longest-palindromic-substring/discuss/607318/C-simple-O(n2)-solution
Evgeniy
А вот примерно то, что ты делаешь, с расширениями в сторону
Evgeniy
Задача только другая, но подход к решению тот же
Viktor
https://leetcode.com/problems/find-the-town-judge/discuss/624693/C-simple-O(n)-solution-using-Dictionary
хорошая идея со счётчиком, действительно вместо того чтобы считать in и out degree отдельно можно просто те же самые счётчики плюсовать-минусовать и будет то же самое т.к. у судьи out degree всё равно ноль — единственный счётчик, который может быть равен N - 1 по итогу
Viktor
не догадался до этого
Evgeniy
хорошая идея со счётчиком, действительно вместо того чтобы считать in и out degree отдельно можно просто те же самые счётчики плюсовать-минусовать и будет то же самое т.к. у судьи out degree всё равно ноль — единственный счётчик, который может быть равен N - 1 по итогу
Мне такая идея пришла после того, как увидел вот этот тест
Evgeniy
Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Evgeniy
Если бы не было [3,1], то судья бы нашёлся
Evgeniy
Изначально я просто считал количество только вторых значений из пары
Evgeniy
Но на верхнем тесте всё сломалось
Yuri
https://leetcode.com/problems/maximum-subarray/discuss/561729/C-simple-solution-using-dynamic-programming-O(1)-space
Неизящно вышло, случай массива из всех отрицательных чисел отдельно обрабатывал
https://leetcode.com/submissions/detail/337374026/
Evgeniy
Yuri
var maxSubArray = function(nums) {
let sum = 0;
let champion = 0;
if(!nums.length) {
return 0;
}
const max = nums.reduce((acc,cur) => (acc>cur) ? acc : cur, nums[0]);
if(max<0) {
return max;
}
for (let current of nums) {
sum += current;
if(sum < 0) {
sum = 0;
}
else {
if(sum>champion) {
champion = sum;
}
}
}
return champion;
};
Yuri
вот это да, у чувака увидел вариант!!! Красота:
var maxSubArray = function(nums) {
let max = nums[0];
let current = nums[0];
for(let i = 1; i < nums.length; i++){
current = Math.max(current + nums[i],nums[i]);
max = Math.max(max, current);
}
return max;
};
Evgeniy
Ну да, тут покороче. И без reduce
Evgeniy
var maxSubArray = function(nums) {
let sum = 0;
let champion = 0;
if(!nums.length) {
return 0;
}
const max = nums.reduce((acc,cur) => (acc>cur) ? acc : cur, nums[0]);
if(max<0) {
return max;
}
for (let current of nums) {
sum += current;
if(sum < 0) {
sum = 0;
}
else {
if(sum>champion) {
champion = sum;
}
}
}
return champion;
};
nums[0] тут как исходное значение для аккумулятора?
Yuri
вот это да, у чувака увидел вариант!!! Красота:
var maxSubArray = function(nums) {
let max = nums[0];
let current = nums[0];
for(let i = 1; i < nums.length; i++){
current = Math.max(current + nums[i],nums[i]);
max = Math.max(max, current);
}
return max;
};
как-то он тут ловко без сбрасывания суммы в нуль избавился
Yuri
а, понял, через максимум. Густой код, прямо вот густой.
Evgeniy
current + nums[i]
Evgeniy
Да, через максимум
Evgeniy
если бы тут было отрицательное, то просто берет nums[i]
Yuri
для пустого массива я бы сказал, что надо нуль возвращать все же
Evgeniy
а там по условию предполагается пустой?
Yuri
ничего не сказано
Yuri
но ведь подсунут падлы рано или поздно
Evgeniy
лучше лишний раз проверить
Порридж В Ко-ливинге
Товарищи
Порридж В Ко-ливинге
Реквестирую разъяснение экспертов
Порридж В Ко-ливинге
Если я создаю массив в зависимости от входных данных, то это O(N), а если известно что маскимальное кол-во данных 1000 и создаю массик O(1001), то это O(N) или O(1)?
Viktor
Если я создаю массив в зависимости от входных данных, то это O(N), а если известно что маскимальное кол-во данных 1000 и создаю массик O(1001), то это O(N) или O(1)?
Если завтра количество входных данных станет охреннилиард, а размер этого массива останется 1001 — то O(1)
Viktor
Важно помнить про относительность в этих оценках.
Null
Happy Monday! 👋
На этой неделе будем искать пропущенные числа в массиве — https://bit.ly/2zog22e
Показываю постепенный переход от простого решения к решению без дополнительной памяти, стараюсь показать ход мыслей, который, на мой взгляд, соответствует реальному интервью.
PS. Нас ровно 2^8 человек, совпадение? Не думаю! 😉 Спасибо, что читаете.
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Как правильно считать память
Viktor
Как правильно считать память
O(N), потому что если завтра N изменится и станет не 1000, то и размер массива придётся изменить. Т.е. это никакая не константа, а переменная.
Viktor
Константой можно назвать скажем массив под алфавит, длины 26. Потому что не придумают завтра новый английский язык с новым алфавитом.
Viktor
Плюс там ещё важно, что мы считаем за N — количество всех людей в городе или количество связей, т.е. длину массива trust. Там это разные переменные должны быть, на память, правда оно не влияет.
Viktor
Как правильно считать память
Хотя можно иначе рассуждать. Можно объявить массив не длины N, а длины 1001, и тогда это формально будет O(1) по памяти. Если изменятся условия задачи, то оценку тоже нужно будет изменить, но для текущих условий — оценка верная. Другой вопрос, что в реальности это больше памяти чем если объявить массив длины N, а не 1001. Т.е. формальная оценка сложности не всегда показывает какая программа больше памяти/времени потребляет, а какая меньше, это грубый способ.
Viktor
Т.е. всё зависит от того относительно чего проводить оценку, что за N брать. Формально можно сказать, что как бы ни изменялись входные данные в программе, сложность всегда O(1) — ограничено сверху временем жизни вселенной.
Viktor
И формально это будет верная оценка.
Viktor
Но, как бы, не слишком точная.
Viktor
Сегодняшняя задачка чисто острова, по-моему 😄
Yuri
Как правильно читать Cracking the Coding Interview
Недавно услышал следующее: «я прочитал весь Cracking the Coding Interview год назад и сейчас уже ничего не помню, открыл LeetCode на днях и не смог решить ни одной задачки». Не правильно вы читаете, дядя Фёдор.
В какой-то момент, для себя, я выработал следующий алгоритм «как правильно читать Cracking the Coding Interview» и он же подходит и для подготовки на LeetCode:
- сперва попробую решить сам;
- если совсем ничего не придумывается через полчаса — смотрю подсказку;
- если не получается ещё через полчаса — смотрю решение.
Есть некоторые общие принципы, техники, структуры данных, и надо научиться определять «что будет работать в данной задаче». Понимание приходит после некоторых мучений над задачей, пока наконец не наступает «aha moment».
По-моему, прогресс на втором шаге: когда уже полчаса помучился, получил инсайт и догадался до полного решения сам.
Если решаешь сразу сам, то задачки слишком простые — планку надо поднимать. Если приходится смотреть чужой код — планку надо опускать, рано для таких задач. Как я уже сказал, по-моему, прогресс где-то между.
А вы как «читаете LeetCode», помните свои aha-моменты? 🙂
у меня додуматься до решения может занять и день и три, и пять (на easy уровне, хаха). Я решил сделать для себя отстойник для старых задач. В подсказки начинаю смотреть через пару часов. В решение - через неделю, при этом в течение недели каждый день достаю задачу и трачу на нее минут 20-30.
Viktor
у меня додуматься до решения может занять и день и три, и пять (на easy уровне, хаха). Я решил сделать для себя отстойник для старых задач. В подсказки начинаю смотреть через пару часов. В решение - через неделю, при этом в течение недели каждый день достаю задачу и трачу на нее минут 20-30.
Хороший метод, спасибо, что делишься 👍
Viktor
Прямо основательно подходишь.
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Но из-за лени - 😴
Порридж В Ко-ливинге
Вот челендж появился, начал наконец-то что-то решать
Порридж В Ко-ливинге
Даже вот вверху CF делал
Порридж В Ко-ливинге
Сам в шоке
Yuri
а вообще, вы чувсвтуете, что со временем алгоритмическая мышца качается?
Порридж В Ко-ливинге
Ну... есть чувство что соображать быстрее начинаю и к языку привыкаю (до этого челенджа на плюсах не писал)
Порридж В Ко-ливинге
Ну вот мне кажется, что любую задачку могу решить, даже хард, только нужно времени много
Порридж В Ко-ливинге
А иногда задача вообще нерешаеммой кажется
Порридж В Ко-ливинге
Но это СКОРЕЕ ВСЕГО ощущения, т.к. вряд ли с рождения одни задачи решаются, другие нет
Порридж В Ко-ливинге
Но чувствуется именно так
Повторюсь - чувствуется, на самом деле даже понятия не имею, умнею ли я. Профессионалы говорят надо практиковаться - практикуюсь 🤣
Yuri
https://dou.ua/lenta/articles/google-interview/
Yuri
я уже раз пять ее перечитал
Yuri
первый раз натурально пот ушанкой вытирал
Порридж В Ко-ливинге
Причем никогда не понимал, это со стороны РФ или Укр блокируют
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Давно кидали, месяц где-то назад
Порридж В Ко-ливинге
Я так и не прочитал
Yuri
для меня она просто бесконечный источник эмоций
Порридж В Ко-ливинге
Мне кажется, что я уже прошел период когда надо читать статьи о программировании, а надо просто кодить, коммитить и участвовать в соревнования
Порридж В Ко-ливинге
для меня она просто бесконечный источник эмоций
У меня так было, когда я начинал прогать (просто говорю, no offense)
Yuri
нене, там сама история отличная
Порридж В Ко-ливинге
Я видосы смотрел сутками
Порридж В Ко-ливинге
Про IT