Решение алгоритмических задачек [Re: Нубский вопрос
Так это всё новые тредики.
Я сразу подумал в сторону A*; данные представил матрицей размером 100*N. Надо найти путь между столбцами. Переходы между ячейками делаются исходя из максимального разрешённого расстояния, стоимостью считается значение из того столбца, в который мы попадаем. По идее эту матрицу не обязательно строить в памяти. Вот ячейки с информацией о цене перехода:
[1, 0] (1, 3) (1, 1) (1, 2)
(2, 1) (2, 2) [2, 0] (2, 1)
(3, 2) (3, 1) (3, 1) [3, 0]
(4, 3) [4, 0] (4, 2) (4, 1)
....
(100, 99)
Плюс две вершины start и end, переход из start по цене из первого столбца, переход в end из последнего столбца по цене 0. Топологическую эвристику предлагаю делать по эвклидову расстоянию между ячейками.
После этого я подумал о том, что на собеседовании в гугол меня кастрируют за сложность этого алгоритма и мне придётся думать о динамическом программировании, в котором я настолько слаб, что если применить это к жиму лёжа, то мне будет стыдно ходить в качалку.
Можно о чем-нибудь из конкарренси поговорить.95% девелопмента считает, что это не нужно.
Можно поговорить о проблемах написания zero-alloc rpc фреймворка и зачем это нужно.Можно, но надо определиться, что это значит. Если я вызываю rpc.f(new Class то чтение класса внутри f вызывает меня?
Можно задачку обсудить:Пожалуй, для меня это весьма актуально.
Я сразу подумал в сторону A*; данные представил матрицей размером 100*N. Надо найти путь между столбцами. Переходы между ячейками делаются исходя из максимального разрешённого расстояния, стоимостью считается значение из того столбца, в который мы попадаем. По идее эту матрицу не обязательно строить в памяти. Вот ячейки с информацией о цене перехода:
[1, 0] (1, 3) (1, 1) (1, 2)
(2, 1) (2, 2) [2, 0] (2, 1)
(3, 2) (3, 1) (3, 1) [3, 0]
(4, 3) [4, 0] (4, 2) (4, 1)
....
(100, 99)
Плюс две вершины start и end, переход из start по цене из первого столбца, переход в end из последнего столбца по цене 0. Топологическую эвристику предлагаю делать по эвклидову расстоянию между ячейками.
После этого я подумал о том, что на собеседовании в гугол меня кастрируют за сложность этого алгоритма и мне придётся думать о динамическом программировании, в котором я настолько слаб, что если применить это к жиму лёжа, то мне будет стыдно ходить в качалку.
95% девелопмента считает, что это не нужно.Ну ты ж меня лично спросил. Причем тут раздел. Мое мнение, что наиболее интересно разделу ты знаешь...
Можно что-нибудь из вейт-фри пообсуждать.
Можно про дистрибутед консенсус поговорить.
Можно поковыряться в jmm.
Можно, но надо определиться, что это значит.Значит, что между точкой входа на клиенте и точкой выхода на сервере у тебя как можно меньше malloc'ов и копирований (то есть по сути сериализацию, транспорт, десериализацию, диспатчинг). Ну и в обратную сторону респонс: сервер->клиент.
В идеале драйвер сетевухи у тебя пишет в заранее выделенный буфер, и бизнес-логика читает напрямую оттуда.
Пожалуй, для меня это весьма актуально.В гугл намылился?
мне придётся думать о динамическом программировании, в котором я настолько слаб, что если применить это к жиму лёжа, то мне будет стыдно ходить в качалку.Камон. Где там быть сильным. Это ж как индукция - свел свою задачу к нескольким задачам меньшей размерности, решил, закешировал результат. Твоя структура, кстати, как раз подходит. А* только совсем не нужен, можно проще.
Держи еще (эта вроде без динамического):
You have found an ancient carpet in your attic. It was originally black, but during it's long life it obtained some white stains. Since it is so old we can't remember, maybe it was a white carpet, and the stains are black! You can not tell if it was white or black! Luckily you have found a bottle of Universal Spot Remover. A single drop of this magic liquid can change the color of any white spot to black, no matter how big the spot is. Amazingly, the same drop, if applied to a black spot, would change the color to white! You would like to remove all spots from the carpet. Since you do not know if it was initially black or white, you would be happy to have a carpet that is either completely black OR completely white. Just don't waste the remover!
Your Task:
Write a program that finds the minimum number of drops needed to remove all stains from the carpet.
Assume that the carpet is a MxN rectangle divided into M*N regular checks, some of which are black, some white.
The stain is a group of checks of the same color connected side-by-side. For example, if the carpet were 8x8 (with alternating colors, like a chessboard there would be exactly 32 white and 32 black stains. Note that when you remove a stain, it will merge with other neighboring stains.
вот еще развлекалочка на полчасика.
Камон. Где там быть сильным. Это ж как индукция - свел свою задачу к нескольким задачам меньшей размерности, решил, закешировал результат.Не всё так просто, ведь нужно ещё понять, как грамотно возвращаться в прошлое. Иногда кеш не помогает.
Твоя структура, кстати, как раз подходит. А* только совсем не нужен, можно проще.Хорошо, можно ещё записывать вторым элементом ячейки за сколько мы туда попадаем в лучшем случае. Потом выбираем минимум и разворачиваем путь. Ой, опять путь!111 Ладно, завтра подумаю.
В гугл намылился?Нет, я реалист, в Google, Microsoft и Amazon меня почти наверняка не возьмут. Я же не умею решать все эти задачки за 15-20 минут. Задачки полезны для раскачки мозга перед разными собеседованиями.
Нет, я реалист, в Google, Microsoft и Amazon меня почти наверняка не возьмут. Я же не умею решать все эти задачки за 15-20 минут. Задачки полезны для раскачки мозга перед разными собеседованиями.Ты переоцениваешь наши планки.
You're selling yourself short.
Ну и, между 1 и 2-3 ощутимая разница.
Ну и, между 1 и 2-3 ощутимая разница.
Не всё так просто, ведь нужно ещё понять, как грамотно возвращаться в прошлое. Иногда кеш не помогает.Ммм, не очень понял, но если ты про восстановление пути после того, как таблица-кеш построена - то предыдущий шаг всегда находится из оптимального "индуктивного перехода".
И сохранить эту инфу при построении проблемы тоже проблемы нет, учитывая, что таблица всегда строится снизу вверх.
Ммм, не очень понял, но если ты про восстановление пути после того, как таблица-кеш построена - то предыдущий шаг всегда находится из оптимального "индуктивного перехода".Нет, я писал о динамическом программировании в общем случае. Видимо, я не совсем точно понял, что ты понимаешь под кэшированием. Например, если пересечение состояний можно выражать суммой, то я бы не называл это кэшем.
И сохранить эту инфу при построении проблемы тоже проблемы нет, учитывая, что таблица всегда строится снизу вверх.
You're selling yourself short.Ты просто не знаешь, что я могу начать тупить на ровном месте, особенно при формате 5*45. Может быть, дело не в моих знаниях, а именно в этом формате. Щас посмотрю вторую задачку, а потом ещё добавлю своих.
You have found an ancient carpet in your attic. It was originally black, but during it's long life it obtained some white stains.Сначала я не смог понять, в чём может быть дополнительная хитрость в этой задаче. Обход графа с пометкой пройденных вершин - если встречаем новую вершину какого-то цвета, то увеличиваем счётчик и помечаем все связные с тем же цветом, займёт 2*M*N.
Дальше я подумал, что если раскраска всё поменяет? К слову это заняло минут 5 времени, то есть на интервью меня бы уже тыкали палочкой.
Ещё через 5 минут я нарисовал чёрный крест в квадратике с белым центром размером в одну ячейку. Если пойти по первому пути, то я затрачу 4 капли чернил, а можно затратить всего две капли в центр.Тогда я решил построить другой граф на связных областях. Он получается двудольным, раскрашенным в два цвета. После этого мои знания оказались ограниченными, мне бы пришлось гуглить, что делать дальше. Поэтому я пошёл по такому пути: нужно установить всем вершинам вес, равный количеству ребёр. Выбрать любую вершину с максимальным весом и перекрасить её. Получится новая вершина. В ней вес нужно рассчитать как сумму весов перекрашенных вершин минус текущий вес. Здесь я бы применял heap: несколько удалений и добавление. Вместе с периодическим написанием этого текста я уже потратил 40 минут.
Дальше я сам привёл контрпример, по которому понял, что мой алгоритм работает хуже, чем нужно. Следующая идея заключается в том, что вес вершины должен быть равен максимальной длине минимального пути до любой другой вершины. Тогда нужно просто до упора перекрашивать вершину с минимальным весом. Очевидно, что это решает задачу, но я потратил час, чтобы это сообразить. Алгоритм Дейкстры позволяет найти минимальный путь от заданной до всех других вершин графа. Поскольку у нас веса всех рёбер равны 1, можно применить BFS.
Мне кажется, если ты дошел до этого за час сам без подсказок, то это очень круто.
Про тыкать палочкой через пять минут ты зря, хотя важно не молчать, а озвучивать ход мыслей.
Осталось оценить сложность. Наверное, ты захочешь Флойда-Уоршелла вместо Дейкстры.
Про тыкать палочкой через пять минут ты зря, хотя важно не молчать, а озвучивать ход мыслей.
Осталось оценить сложность. Наверное, ты захочешь Флойда-Уоршелла вместо Дейкстры.
Под кешированием я имел в виду когда у тебя детерминистическая функция, и ты вместо того, чтобы каждый раз вычислять результат, вычисляешь его один раз, и сохраняешь в мапу, где ключ - вход функции, значение - выход.
В рамках этой терминологии я не очень понимаю о каких состояниях, которые можно пересекать и суммировать, ты говоришь
В рамках этой терминологии я не очень понимаю о каких состояниях, которые можно пересекать и суммировать, ты говоришь
Мне кажется, если ты дошел до этого за час сам без подсказок, то это очень круто.Нет, я пролистал информацию по раскраске графов, двудольности и алгоритм Дейкстры. Последний я знаю, но вот не смог вспомнить, какие есть хитрости для поиска всех путей от всех вершин. Собственно, прямо сейчас я помню только Дейкстру, A* и простые обходы. По двудольности тоже уточнял кое-какие аспекты, а не само определение.
И нет, это не круто, ведь в Google надо за 45 минут решить 2 такие задачки.
В рамках этой терминологии я не очень понимаю о каких состояниях, которые можно пересекать и суммировать, ты говоришьВ динамическом программировании под состоянием можно понимать все данные, которые у тебя сейчас есть. После этого у нас получается переход между состояниями, ведь они должны пересекаться. Собственно, этот переход вовсе не обязательно будет использовать кэш, это может быть, например, вычитание числа или ещё что-нибудь.
Думаю, что это уже не имеет значения в тех терминах, что я описал.
Но вообще, в твоем случае, если я правильно понимаю, ты говоришь о том, что чтобы получить значение функции в состоянии А достаточно взять значение в состоянии Б и прибавить к нему что-то. Если так - то я тебя понял, и мое "кеширование" тут сработает, когда ты будешь брать значение в состоянии Б.
Но вообще, в твоем случае, если я правильно понимаю, ты говоришь о том, что чтобы получить значение функции в состоянии А достаточно взять значение в состоянии Б и прибавить к нему что-то. Если так - то я тебя понял, и мое "кеширование" тут сработает, когда ты будешь брать значение в состоянии Б.
Если так - то я тебя понял, и мое "кеширование" тут сработает, когда ты будешь брать значение в состоянии Б.Да, просто если не нужно хранить никакие другие состояния, то я не считаю это кэшем.
Но можно сказать, что это кэш из одного значения.Щас поем и буду копаться в том Java коде. Я только не совсем понял, о чём он, там Accumulator написан неправильно; а воркеры работают последовательно. Или там есть что-то по алгоритмам?
Ой, там сам формат задачки прикольный, мне понравился, а в остальном все просто, разберешься.
Дальше спойлер:
Дальше спойлер:
> Очевидно, что это решает задачу
А умеешь это доказывать?
А умеешь это доказывать?
вот еще развлекалочка на полчасика.Меньше, конечно, и слишком простая.
Ну блин, нельзя ж совсем решение задачки обесценивать...
В принципе, идею легко доработать до не такой вырожденной - всунуть в воркеры функцию посложнее. Повторное хеширование, например. И инпуты подобрать так, чтоб кеширование спасало.
И сделать промежуточные ответы. Чтобы всякие fan-in fan-out потренировать.
В принципе, идею легко доработать до не такой вырожденной - всунуть в воркеры функцию посложнее. Повторное хеширование, например. И инпуты подобрать так, чтоб кеширование спасало.
И сделать промежуточные ответы. Чтобы всякие fan-in fan-out потренировать.
Ну блин, нельзя ж совсем решение задачки обесценивать...Ладно, я ещё хочу решить что-нибудь. Желательно, чтобы ответы не гуглились, как и в случае с двумя предыдущими задачками.
А может быть, мне задать свои, которые я когда-то решал на собеседованиях и по работе?
Given an arraylist of N integers,
(1) find a non-empty subset whose sum is a multiple of N.
(2) find a non-empty subset whose sum is a multiple of 2N.
Compare the solutions of the two questions.
(1) find a non-empty subset whose sum is a multiple of N.
(2) find a non-empty subset whose sum is a multiple of 2N.
Compare the solutions of the two questions.
You have found an ancient carpet in your attic.Вроде можно так:
1. Выделяем одноцветные связные области и рисуем ребра между соседствующими областями. Должен получиться двудольный граф.
2. В этом двудольном графе надо найти минимальное вершинной покрытие (делается нехитро через максимальное паросочетание).
Ну и дальше тыкать в вершины найденного покрытия, перекрашивая содержащие их области.
UPD: неправильное решение
2. В этом двудольном графе надо найти минимальное вершинной покрытие (делается нехитро через максимальное паросочетание).Вот в таком графе (рёбра только по горизонтали и вертикали) минимальное покрытие состоит из любой серединки? Тогда какую из трёх вершин нужно перекрашивать? Если начать с X, то не получится перекрасить его за два раза. Здесь надо начинать с центральной O.
O X O
X O X
O X O
А умеешь это доказывать?Смотря какое доказательство требуется. Если есть какая-то именованная теорема, то придётся гуглить.
Я бы пошёл по каким-нибудь предположениям. Граф окрашен в два цвета, длина всех рёбер равна 1. Вершины одинакового цвета будут либо с чётными, либо с нечётными весами. Закрашиванием можно объединить вершины, не нарушая свойства двудольности. Так можно показать, что граф рано или поздно будет закрашен.
Наверное, не так сложно было бы показать, что количество перекрашиваний равно весу вершины. После перекрашивания из любого места мы уменьшаем длину пути до всех самых далёких вершин на 1, потому что соседние вершины являются частью кратчайшего пути. Когда этот путь равен нулю, мы достигли всех самых далёких вершин.
Как можно было заметить по этому тредику, мне тяжело даются математически точные выкладки. Так что более правильным ответом на твой вопрос будет "нет".
Действительно. Был не прав
Given an arraylist of N integers,Тупил почти час, потом попросил, чтобы меня подтолкнули. Подтолкнули, видимо, слишком сильно, в сторону того, что любое множество натуральных чисел N содержит подмножество, кратное N. Мне кажется, что сам бы я на это точно не ответил, если я просто не туплю и это что-то тривиальное.
(1) find a non-empty subset whose sum is a multiple of N.
(2) find a non-empty subset whose sum is a multiple of 2N.
Compare the solutions of the two questions.
После этого я решил попробовать суммировать остатки от деления, если они равны 0 или N, то получается нужное подмножество. Беда в том, что эта сумма просто так не вычисляется. Подход в лоб имеет гигантскую сложность.
Пошёл второй час, и мне пришла в голову какая-то новая мысль. Я опять подумал о теореме, которую мне рассказали. Если просто просуммировать весь массив, то там будет N сумм. Если в это время какая-то сумма имеет остаток от деления на N, равный 0, то это и есть искомая сумма. Если же есть N сумм, у которых остаток от деления не равен 0, то остатки будут от 1 до N-1, то есть всего N-1 чисел. То есть у нас гарантировано наличие двух последовательных сумм, у которых остаток от деления одинаковый. Если мы вычтем эти суммы, то получим число с остатком от деления, который равен 0. Неужели это и есть ответ на первый вопрос?
В случае с 2N решения может не быть, это видно на примере массива из трёх элементов 1, 1, 1. Что если пойти по пути первого решения и просто вычислить остаток от деления на 2N?
В общем, 2 часа с довольно серьёзной подсказкой, фейл.
В случае с 2N решения может не быть, это видно на примере массива из трёх элементов 1, 1, 1. Что если пойти по пути первого решения и просто вычислить остаток от деления на 2N?В пункте 1 ты перебрал суммы всех возможных одиночных отрезков исходного массива. И доказал, что этого достаточно.
Теперь недостаточно, и теперь надо перебрать всевозможные суммы произвольного количества отрезков.
Сделайте тред обсуждаемым что ли, чтобы решений не ведить.
Теперь недостаточно, и теперь надо перебрать всевозможные суммы произвольного количества отрезков.Я потратил ещё час, но так и не понял, как её решить. Вернее, как рассмотреть суммы этих отрезков. Не проще ли здесь уже выбрать другой сценарий, рассматривая все множества отдельных элементов? Как поиск заданной суммы в массиве элементов, который решается либо сортировкой и двумя индексами, либо хэш таблицей.
Мне вот ещё что подсказали, я правда не совсем точно понял, но (A mod N + B) mod N = (A + B) mod N? Теперь нужно понять, как это решает задачу.
Если рассматривать все множества, то 2^n получится.
Учитывая, что задача набрать из массива чисел так, чтоб получилось 0 по модулю очень смахивает на knapsack, то, вероятно, это и будет солюшен.
Учитывая, что задача набрать из массива чисел так, чтоб получилось 0 по модулю очень смахивает на knapsack, то, вероятно, это и будет солюшен.
Учитывая, что задача набрать из массива чисел так, чтоб получилось 0 по модулю очень смахивает на knapsack, то, вероятно, это и будет солюшен.Разве там не задача оптимизации? Не смог придумать, как её применить к данному случаю.
Короче, мне подсказали окончательное решение этой задачи, которое я смог понять. Идея, которая следует из (A mod N + B) mod N = (A + B) mod N и задачки на поиск суммы в массиве элементов.
Мы должны создать отображение числа (из mod 2*N) в список цифр из массива, которые привели к этому числу (mod 2*N). Например, map<int, vector<int>>, где ключи от 1 до 2*N-1, а списки содержат числа, сумма которых mod 2*N равна ключу.
Идём по всем элементам массива, для каждого элемента перебираем все ключи отображения, добавляем к ним текущий элемент массива и берём mod 2*N. Если получили 0, то берём список по данному ключу, добавляем туда текущий элемент и возвращаем этот список как ответ.
Если получили другое число, то смотрим в отображение. Если такого остатка от деления ещё нет, то нужно добавить новый список, который будет содержать предыдущие элементы плюс текущий.
Оставить комментарий
katrin2201
Ну что сразу бляМожно вот обсудить.
Можно о чем-нибудь из конкарренси поговорить.
Можно поговорить о проблемах написания zero-alloc rpc фреймворка и зачем это нужно.
Можно задачку обсудить:
Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.
If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
You can assume each number in the array is a positive integer and not greater than 100
Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.