норм. edge case 🙂
Ага
Evgeniy
Evgeniy
Причём в таких рандомных задачах знание исходных данных у теста не даёт ничего)
Evgeniy
Изначально рандом брал с 1. А потом, думаю, сделаю с нуля
Evgeniy
Вот и попался
Viktor
ну да, в рандомных задачах грейдер проверяет правильность явно не сравнивая в точности аутпут 🙂
Viktor
сложнее понять поэтому
Evgeniy
https://leetcode.com/problems/random-pick-with-weight/discuss/671865/C-O(n)-time-solition-using-prefix-sum-and-binary-search
Viktor
ну да, сперва подумал чё париться, а потом понял зачем 😄
Evgeniy
Слишком много чисел, ага)
Evgeniy
Я задачу с удалением узла не через окно челленжа сдал. Теперь останусь без футболки 😁
Viktor
Я отчаялся получить футболку 😄
Evgeniy
А нам так хотели её подарить
Evgeniy
Так хотели...
Evgeniy
Не оправдали надежд
Viktor
Нормас объяснение 😃
Viktor
Если важны термины (нет), то исходный массив - это функция вероятности дискретной случайной величины, а массив с частичными суммами - функция распределения этой случайной величины. 🤓
Evgeniy
да уж
Evgeniy
всё идеально понятно
Порридж В Ко-ливинге
Трындец расценки у челов, прицените — http://verbetcetera.com/eng-mentorship , 9к за одно мок-интервью, шта?! 😄
Капец, это мок интервью с Пэйджом?
Viktor
На кодилити классные задачки в челенджах. Например, с утра решал — https://app.codility.com/programmers/task/tree_range/. Отчёт хороший получается. Решил за O(N^3) и некоторые тесты таймаутятся. Причем сложность он сам детектит и отчёт по каждому тесту показывает.
Viktor
хз как быстрее решить, чтобы 100% скор получить.
Yuri
На кодилити классные задачки в челенджах. Например, с утра решал — https://app.codility.com/programmers/task/tree_range/. Отчёт хороший получается. Решил за O(N^3) и некоторые тесты таймаутятся. Причем сложность он сам детектит и отчёт по каждому тесту показывает.
Сложность сам детектит?! Что за чёрная магия?
Viktor
Сложность сам детектит?! Что за чёрная магия?
https://app.codility.com/demo/results/trainingWYGHUR-SFM/
Viktor
Вот он пишет estimated complexity N**3. И это похоже на правду, учитывая, что я запускаю поиск в глубину для каждой пары узлов.
Viktor
> Detected time complexity
Viktor
мне кажется, что он это определяет исходя из того какие тесты прошли. типа если была бы больше сложность — тогда больше было бы TLE
Viktor
ну, т.е. как-то с помощью своих эвристик, явно он код не анализирует
Viktor
задачка прикольная
Viktor
подумаю ещё над N^2 решением. как видно из отчёта, я сидел 69 минут и решил «пора сдать что есть» 😄
Yuri
мне кажется, что он это определяет исходя из того какие тесты прошли. типа если была бы больше сложность — тогда больше было бы TLE
мож ast-строит и смотрит на циклы внутри?
Yuri
или там call-стек считает
Yuri
вообще безумие, как так можно вообще
Yuri
ну да
Viktor
не очень ясно как это работает. моё предположение — эвристики. надо погуглить.
Yuri
последний раз так удивлялся когда увидел вольфрама, считающего интегралы аналитическим способом
Viktor
ахаха, нормас 😄
Viktor
надеюсь wolframalpha, а не самого Вольфрама встретил где-нибудь в коридоре, а он считает интегралы.
Evgeniy
Viktor
последний раз так удивлялся когда увидел вольфрама, считающего интегралы аналитическим способом
погуглил чутка, вот там чувак пишет в первом ответе — https://cs.stackexchange.com/questions/48505/how-does-the-automatic-complexity-analysis-of-codility-work
Viktor
примерно про это я и думал. как на самом деле, правда, хз, но звучит логично.
Viktor
он реально круто определяет, прицените два отчёта: https://app.codility.com/demo/results/trainingJYV7UE-2PA/ и https://app.codility.com/demo/results/trainingQT5EA8-5T8/
Evgeniy
Впечатляет. В первом даже разницу учёл
Viktor
Ага, т.е. если бы там шаг не K был, а 1, типа проверить каждое число и взять остаток от деления, то было бы B - A. грейдер реально время измеряет и пытается наложить на известные функции для данной задачи.
Порридж В Ко-ливинге
Товарищи
Порридж В Ко-ливинге
Интересная Задачка из ВУЗовской программы
Порридж В Ко-ливинге
Поле шахматной доски определяется парой натуральных чисел, первое из которых задаст номер вертикали, а второе - номер горизонтали. Определить, на сколько всего разных полей может переместиться слон, стоящий на поле (k, l) на пустой доске. Натуральные числа k и l вводятся с клавиатуры. Если пользователь введѐт некорректные данные – вывести соответствующее сообщение.
Порридж В Ко-ливинге
ВРоде простая, но что-то...
Uladzimir
Нет ограничений на k,l, но в таком случае ращений может быть множество, если размеры доски не фиксированы. Тогда я бы предположил, что это обычная шахматная доска с 64 клетками
Порридж В Ко-ливинге
Да, 64 клетки
Порридж В Ко-ливинге
Я на самом деле прифигел от такой задачки
Uladzimir
Слон по диагонали ходит)
Порридж В Ко-ливинге
Да, такое я тоже вкурсе
Порридж В Ко-ливинге
Как сделать адекватный алгоритм
Uladzimir
Полагаю, надо рассмотреть худший случай, когда слон ходит в 4 стороны, тогда 4 квадрата, найти диагональ каждого, если известна сторона
Uladzimir
Я в алгоритмах не силён, но тут же вроде обычная математика
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Пока сократил до того, что поле зеркально и стоит рассматривать только четверть доски
Порридж В Ко-ливинге
https://pastebin.com/vs6L2v8K
Порридж В Ко-ливинге
Ну так, надо было подумать
Null
Happy Monday! 👋
На этой неделе пишем HashSet с нуля — https://bit.ly/3dDuTF7
Как работают хэш-таблицы (наши любимые словари под капотом), что такое хэш-функции и коллизии.
Постарался рассказать как можно практичнее, без «рассмотрим 10 лемм прежде чем перейти к теореме».
Viktor
Поле шахматной доски определяется парой натуральных чисел, первое из которых задаст номер вертикали, а второе - номер горизонтали. Определить, на сколько всего разных полей может переместиться слон, стоящий на поле (k, l) на пустой доске. Натуральные числа k и l вводятся с клавиатуры. Если пользователь введѐт некорректные данные – вывести соответствующее сообщение.
кажется, что ответ будет всегда одно и то же число, нет? я вот сейчас открыл картинку шахматной доски и прикинул, что куда бы ты не поставил слона — он может переместиться на сумму диагоналей клеток минус 1 (клетку где он сам).
Viktor
или там в задании вопрос не в количестве клеток куда он может сходить относительно данной?
Evgeniy
Зависит от расположения
Evgeniy
или там в задании вопрос не в количестве клеток куда он может сходить относительно данной?
Я так понял, что вопрос именно в этом
Порридж В Ко-ливинге
Viktor
Любопытная задачка — https://leetcode.com/problems/text-justification/ , интересно почему так много дизлайков.
Viktor
По крайней мере, выглядит как пример из реального мира, а-ля «реализуй функцию justify текста в ворде».
Evgeniy
Любопытная задачка — https://leetcode.com/problems/text-justification/ , интересно почему так много дизлайков.
Возможно, из-за неоднозначного описания: "If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right."
Evgeniy
Любопытная задачка — https://leetcode.com/problems/text-justification/ , интересно почему так много дизлайков.
Если интересно, решил.
https://leetcode.com/problems/text-justification/discuss/678815/C-O(n)-solution-using-StringBuilder
Viktor
Если интересно, решил.
https://leetcode.com/problems/text-justification/discuss/678815/C-O(n)-solution-using-StringBuilder
ага, я тоже доделал. теперь понял почему столько дизлайков — это муторная хрень, которая не подходит для собеседования. я постарался разбить аккуратно на методы, чтобы какая-то структура была, в итоге, это полотно кода.
Viktor
https://gist.github.com/vitkarpov/3806379d4225ddbf7a44cf5d7bdf9ee5
Viktor
даже если комменты убрать
Evgeniy
Evgeniy
Например, с последней строкой