Здравствуйте, elmal, Вы писали:
E>С текстовыми файлами стремно. Грохнется приложение внезапно, файл не закрылся, и все, логи пропали. А они критичные. Это не страшно, если логи выполняют вспомогательную функцию. Но когда на них логика, когда их нужно показывать по таймштампу и т.д, когда их нельзя потерять — я б на месте ответственных спал бы крайне хреново, если б это было решение на файлах. Я видел систему, где на файлах — но там внутри такой капец был, что это рекомендация как не надо делать.
В системе, которую я видел, хватало всякого рода фиаско. Но вот логирование было сделано хорошо. За все время ни одной записи не потеряли. По крайней мере за то время, что я там работал.
Здравствуйте, ·, Вы писали:
·>Маркировать пройденные узлы.
Ну это не спортивно.
BFE>>·>И отсекается такое решение довольно просто: по условию задачи список нельзя модифицировать. BFE>>Два реверса и список не изменён. ·>Ты это объясни read-only транзакции в субд, например.
Это не список. Длина таблицы известна.
·>Или, например, цикл можно обнаруживать в random number generator. Как ты rng переворачивать будешь?
А вот с rnd вопрос интересный и решается он, как мне кажется, совершенно другим способом, вероятностным. Если без расчёта требуемой вероятности и соответствующих размеров структур, то можно сделать так: заказываем один массив на 10 чисел и один циклический буфер на 20 чисел. С помощью циклического буфера ищем короткие циклы — проверяем, что последние 10 чисел не повторяются, это просто, но не тривиально. А с помощью массива ищем длинные циклы: заполняем массив последовательно выпавшими числами начиная с шага взятого из последовательности Фибоначи (55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711), после заполнения массива проверяем, что числа не выпадут заново до следующего шага заполнения массива. Тогда если в массиве или в циклическом буфере последние выпавшие числа совпали, то с вероятностью (1/n)10 мы нашли цикл. Здесь n — размер диапазона случайных чисел. Можно обойтись и без циклического буфера, если не пытаться искать короткие циклы.
Здравствуйте, B0FEE664, Вы писали:
BFE>·>Маркировать пройденные узлы. BFE>Ну это не спортивно.
Ага, я и говорю, что твоё решение бессмысленное переусложнение для таких условий.
BFE>>>·>И отсекается такое решение довольно просто: по условию задачи список нельзя модифицировать. BFE>>>Два реверса и список не изменён. BFE>·>Ты это объясни read-only транзакции в субд, например. BFE>Это не список. Длина таблицы известна. Число объектов в памяти тоже известно, или, как минимум, элементарно оценивается сверху.
Список связанных записей может быть сильно меньше размера таблицы. Гулять по циклу миллионы раз, для списков в сотни записей?
BFE>·>Или, например, цикл можно обнаруживать в random number generator. Как ты rng переворачивать будешь? BFE>А вот с rnd вопрос интересный и решается он, как мне кажется, совершенно другим способом, вероятностным.
Прошу прощения, я имел в виду pseudo rng, так что зачем тут вероятностное решение, когда есть точное — непонятно.
BFE>Если без расчёта требуемой вероятности и соответствующих размеров структур, то можно сделать так: заказываем один массив на 10 чисел и один циклический буфер на 20 чисел. С помощью циклического буфера ищем короткие циклы — проверяем, что последние 10 чисел не повторяются, это просто, но не тривиально. А с помощью массива ищем длинные циклы: заполняем массив последовательно выпавшими числами начиная с шага взятого из последовательности Фибоначи (55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711), после заполнения массива проверяем, что числа не выпадут заново до следующего шага заполнения массива. Тогда если в массиве или в циклическом буфере последние выпавшие числа совпали, то с вероятностью (1/n)10 мы нашли цикл. Здесь n — размер диапазона случайных чисел. Можно обойтись и без циклического буфера, если не пытаться искать короткие циклы.
Что-то не понял... Допустим, период rng — 1_000_000 при диапазоне 1_000_000_000. Как фиббоначчи помогут?
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, AleksandrN, Вы писали:
AN>Логи пишутся последовательно, т.е. — они уже отсортированы по дате и времени.
В системах с низким откликом логи могут писаться как придётся, очень часто там сиди сервис который ест логи от многопоточной хреновины со всеми вытекающими. Если в него наваливают от души, то gap появится 100%.
Здравствуйте, ·, Вы писали:
·>Ага, я и говорю, что твоё решение бессмысленное переусложнение для таких условий.
В моём случае нет дополнительного расхода памяти, а при маркировании пройденных узлов — есть.
·> Число объектов в памяти тоже известно, или, как минимум, элементарно оценивается сверху.
Да, но на 64-битной архитектуре оценка слишком большая.
·>Список связанных записей может быть сильно меньше размера таблицы. Гулять по циклу миллионы раз, для списков в сотни записей?
Главное, что не вечно.
BFE>>·>Или, например, цикл можно обнаруживать в random number generator. Как ты rng переворачивать будешь? BFE>>А вот с rnd вопрос интересный и решается он, как мне кажется, совершенно другим способом, вероятностным. ·>Прошу прощения, я имел в виду pseudo rng, так что зачем тут вероятностное решение, когда есть точное — непонятно.
Понятно, что pseudo rng, но ведь мы не знаем объём памяти используемый pseudo rng, так что я не вижу способа точного решения. Так же следует учесть, что pseudo rng скорее всего не идеален, так что первые x могут никогда не повторится и этот x не известен.
·>Что-то не понял... Допустим, период rng — 1_000_000 при диапазоне 1_000_000_000. Как фиббоначчи помогут?
Предложенный алгоритм мало чем отличается от прохода по закольцованному списку двумя указателями. Фибоначчи ни при чём. Можно взять другую последовательность.
Здравствуйте, B0FEE664, Вы писали:
BFE>·>Ага, я и говорю, что твоё решение бессмысленное переусложнение для таких условий. BFE>В моём случае нет дополнительного расхода памяти, а при маркировании пройденных узлов — есть.
Можно сами указатели ставить в некое значение, а на многих архитекрурах, например, можно маркировать младший бит указателя.
BFE>·> Число объектов в памяти тоже известно, или, как минимум, элементарно оценивается сверху. BFE>Да, но на 64-битной архитектуре оценка слишком большая. Оценивать надо не по количеству бит, а по занимаемой памяти под кучу/стеки.
BFE>·>Список связанных записей может быть сильно меньше размера таблицы. Гулять по циклу миллионы раз, для списков в сотни записей? BFE>Главное, что не вечно.
Это совсем не главное. Ну поставь ограничение в 2^64 — тоже не вечно. И что?
BFE>>>·>Или, например, цикл можно обнаруживать в random number generator. Как ты rng переворачивать будешь? BFE>>>А вот с rnd вопрос интересный и решается он, как мне кажется, совершенно другим способом, вероятностным. BFE>·>Прошу прощения, я имел в виду pseudo rng, так что зачем тут вероятностное решение, когда есть точное — непонятно. BFE>Понятно, что pseudo rng, но ведь мы не знаем объём памяти используемый pseudo rng, так что я не вижу способа точного решения.
prng занимает фиксированный объём памяти, насколько я знаю, о других я не слышал.
BFE>Так же следует учесть, что pseudo rng скорее всего не идеален, так что первые x могут никогда не повторится и этот x не известен.
Верно, поэтому и нужен алгоритм с константным количеством памяти, чтобы x не было важно.
BFE>·>Что-то не понял... Допустим, период rng — 1_000_000 при диапазоне 1_000_000_000. Как фиббоначчи помогут? BFE>Предложенный алгоритм мало чем отличается от прохода по закольцованному списку двумя указателями. Фибоначчи ни при чём. Можно взять другую последовательность.
Какую другую? Ничего не понял. И зачем это всё? Опять переусложнизм?
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ·, Вы писали:
·> Оценивать надо не по количеству бит, а по занимаемой памяти под кучу/стеки.
Ну как вы её оцените?
·>Это совсем не главное. Ну поставь ограничение в 2^64 — тоже не вечно. И что?
А откуда у вас такая таблица?
·>prng занимает фиксированный объём памяти, насколько я знаю, о других я не слышал.
Ок. Допустим prng занимает фиксированный объём в 1024 байта и генерирует 32-х битные числа. Разве от этого легче?
BFE>>Так же следует учесть, что pseudo rng скорее всего не идеален, так что первые x могут никогда не повторится и этот x не известен. ·>Верно, поэтому и нужен алгоритм с константным количеством памяти, чтобы x не было важно.
Чем вам поможет константное количество памяти?
·>Какую другую? Ничего не понял. И зачем это всё? Опять переусложнизм?
Предложите простой вариант.
Здравствуйте, C0x, Вы писали:
C0x>Тема ещё не понимает видимо что интервью это обоюдное общение двух профессионалов. Если дашь задачу то будь готов и сам доказать кандидату что с тобой можно и интересно работать. Не нужно забывать что не только работодатель выбирает, но и кандидат выбирает с кем ему работать.
Он еще не понимает, что Сидней — город маленький, где слово за слово далеко идет. И что рекрутерам, которые звонят потенциальным кандидатам, только услышав название компании, уже сегодня отвечают "неадекваты мне неинтересны". В результате Тёмино чсв взлетит до небес, ибо беседовать он будет только тот контингент, у которого и выбора-то нет. Ну да, как в поговорке.
Правда, начальству такая слава может не понравиться, но это уж пусть он сам разбирается.
В крупных компаниях вопросы на засыпку на интервью запрещены вплоть до наложения дисциплинарных взысканий.
Здравствуйте, Тёмчик, Вы писали:
Тё>1) школьная на рекурсию (не моя- не буду раскрывать) Тё>2) перевернуть порядок слов (обсудили) Тё>3) Дан файл с integer values от 1 до 2^32-1, они не повторяются за исключением 1 дупликата. Нужно распечатать значение дупликата. Как это сделать? (код не нужен) Тё>4) Дан файл с integer values от 0 до 1000000, без дупликатов, но значения в произвольном порядке. Как их вывести в другой файл в порядке возрастания? Тё>5) Дан файл из записей JSON размером 140GB, но у вас в системе всего 8GB памяти. Нужно вывести записи в другой файл, отсортированные по произвольному полю JSON. Как это сделать? (код не нужен). Тё>6) Напишите код для разворота односвязного списка на доске. Тё>7) Как узнать, есть ли loop в односвязном списке? Напишите код на доске.
Тё>PS Спасибо, что указали на ошибку в условии (3).
Здравствуйте, landerhigh, Вы писали:
L>В крупных компаниях вопросы на засыпку на интервью запрещены вплоть до наложения дисциплинарных взысканий.
Хотя бы одну задачку из этого списка у меня спрашивали практически в каждой компании, куда собеседовался. И ещё бывало достаточно сложное домашнее задание на алгоритмы.
Здравствуйте, Тёмчик, Вы писали:
Тё>Здравствуйте, landerhigh, Вы писали:
L>>В крупных компаниях вопросы на засыпку на интервью запрещены вплоть до наложения дисциплинарных взысканий. Тё>
Тё>Хотя бы одну задачку из этого списка у меня спрашивали практически в каждой компании, куда собеседовался. И ещё бывало достаточно сложное домашнее задание на алгоритмы.
В этом то и проблема что поэтому грош цена этим задачам. Пройдя пару собеседований , ты уже можешь решить практически любую задачку из подобного списка. То есть они абсолютно бесполезны.
Здравствуйте, C0x, Вы писали:
C0x>. Пройдя пару собеседований , ты уже можешь решить практически любую задачку из подобного списка. То есть они абсолютно бесполезны.
Так ведь цель- не найти учёного-алгоритмиста, а просто программиста с зачатками интеллекта. Чтобы потом не появлялось в коде O(N!) на ровном месте.
Здравствуйте, Тёмчик, Вы писали:
Тё>Так ведь цель- не найти учёного-алгоритмиста, а просто программиста с зачатками интеллекта. Чтобы потом не появлялось в коде O(N!) на ровном месте.
Вот тебе еще задача на засыпку. На которую ты не ответишь из за недостатка опыта. Вот пришел ты на легаси проект. Внезапно выясняется, что все тормозит, от тебя требуют быстро разобраться и пофиксить. Твои действия, как будешь решать проблему?
И в отличие от твоих вопросов — это сугубо практический вопрос. Хоть и большинство на нем завалятся, в том числе и ты. Ибо если бы ты знал что делать в таких ситуациях, и если бы ты бывал в таких ситуациях, ты бы понимал, что чаще всего такие проблемы с производительностью очень легко диагностируются, и при необходимости легко и быстро исправляются. При условии, что код компактен, без кучи явных и неявных зависимостей. Но когда ты привык к логике с одним методом на 10 000 строк со сплошной копипастой — да, в этом случае все не так просто будет. Так может просто не набирать людей, которые на ровном месте городят методы на 10 000 строк, что в результате тривиальная проблема производительности становится огромной проблемой? А именно люди, которые привыкли писать код с одним методом на 10 000 строк, как раз с большей вероятностью пройдут твое собеседование, чем умеющие декомпозировать.
И второй вопрос на засыпку. Почему я упомянул метод про 10 000 строк, почему конкретно при ответе на первый вопрос это может быть проблемой? И ответ желателен не через час, а мгновенно, в режиме диалога. Ибо над такими вопросами если тупишь — значит просто начитался книг и сам ничего сложного никогда не писал.
Здравствуйте, elmal, Вы писали:
E>Вот тебе еще задача на засыпку. На которую ты не ответишь из за недостатка опыта. Вот пришел ты на легаси проект. Внезапно выясняется, что все тормозит, от тебя требуют быстро разобраться и пофиксить. Твои действия, как будешь решать проблему? E>И в отличие от твоих вопросов — это сугубо практический вопрос. Хоть и большинство на нем завалятся, в том числе и ты. Ибо если бы ты знал что делать в таких ситуациях, и если бы ты бывал в таких ситуациях, ты бы понимал, что чаще всего такие проблемы с производительностью очень легко диагностируются, и при необходимости легко и быстро исправляются. При условии, что код компактен, без кучи явных и неявных зависимостей. Но когда ты привык к логике с одним методом на 10 000 строк со сплошной копипастой — да, в этом случае все не так просто будет. Так может просто не набирать людей, которые на ровном месте городят методы на 10 000 строк, что в результате тривиальная проблема производительности становится огромной проблемой? А именно люди, которые привыкли писать код с одним методом на 10 000 строк, как раз с большей вероятностью пройдут твое собеседование, чем умеющие декомпозировать.
Если при дизайне системы не задумывались о производительности- то и короткие методы с десятком слоёв не помогут. Вообще, мне неинтересно спрашивать про паттерны просто потому, что птиц-говорунов на эту тематику предостаточно.
E>И второй вопрос на засыпку. Почему я упомянул метод про 10 000 строк, почему конкретно при ответе на первый вопрос это может быть проблемой? И ответ желателен не через час, а мгновенно, в режиме диалога. Ибо над такими вопросами если тупишь — значит просто начитался книг и сам ничего сложного никогда не писал.
Честно говоря, я бы наверное задал встречный вопрос- у вас что, есть прецеденты? Ибо работать с говнокодерами я не нанимался.
Здравствуйте, Тёмчик, Вы писали:
Тё>Честно говоря, я бы наверное задал встречный вопрос- у вас что, есть прецеденты? Ибо работать с говнокодерами я не нанимался.
Есть прецеденты. Буквально несколько дней назад поймали дремавший 2 года баг в производительности. Который даже близко не связан ни с каким О, там с логгером проблемы были. И его не было никаких проблем ни найти, ни исправить. Причем искал даже не я, я когда то давно показал как такие проблемы ищутся. Исправилось редактированием пяти строчек кода, в одном методе, который на 10 строчек, кстати. И множество подобных проблем с производительностью тоже никогда не возникало проблем найти и пофиксить. Самое сложное в таких багах — их воспроизвести. Если воспроизводится — пофиксить и исправить вообще чаще всего не является проблемой.
И кстати о говнокоде. Именно максимально оптимизированный код (рассказываю, так как ты с таким не сталкивался, и не факт что столкнешься) — это с точки зрения человека лютый ужас. Он нечитаем совершенно, там бешенное количество коментов, там тронешь в одном месте, отвалится в другом или дичайшим образом просядет производительность. Этот дичайше оптимизированный код ни хрена не универсален. Малейшее изменение модели данных — и все, оптимизация не работает, как и код. Ради оптимизаций зачастую делаются лишние зависимости, и нарушаются крайне многие постулаты того, как писать правильно. Но в некоторых случаях вот такая дичайшая оптимизация реально оправдана. Но когда весь код вот такой оптимизированный, и оптимизируются места, не являющиеся узким местом — это уже диагноз и явный саботаж.
>Тё3) Дан файл с integer values от 1 до 2^32-1, они не повторяются за исключением 1 дупликата. Нужно распечатать значение дупликата. Как это сделать? (код не нужен)
Как это делается?
>Тё4) Дан файл с integer values от 0 до 1000000, без дупликатов, но значения в произвольном порядке. Как их вывести в другой файл в порядке возрастания?
Как это делается?
>Тё5) Дан файл из записей JSON размером 140GB, но у вас в системе всего 8GB памяти. Нужно вывести записи в другой файл, отсортированные по произвольному полю JSON. Как это сделать? (код не нужен).
Здравствуйте, RussianFellow, Вы писали:
>>Тё3) Дан файл с integer values от 1 до 2^32-1, они не повторяются за исключением 1 дупликата. Нужно распечатать значение дупликата. Как это сделать? (код не нужен) RF>Как это делается?
>>Тё4) Дан файл с integer values от 0 до 1000000, без дупликатов, но значения в произвольном порядке. Как их вывести в другой файл в порядке возрастания? RF>Как это делается?
>>Тё5) Дан файл из записей JSON размером 140GB, но у вас в системе всего 8GB памяти. Нужно вывести записи в другой файл, отсортированные по произвольному полю JSON. Как это сделать? (код не нужен). RF>Как это делается?
Тут нужно по косвенным вопросам догадаться, какое решение ожидает экзаменатор. Тёмчик ожидает
Однако следует заметить, что если в системе всего 8GB памяти (всего 8GB, а не оперативной!), то впихнуть 140GB в 8GB несколько затруднительно. JSON, правда, хорошо сжимается, но вывести записи в другой файл вряд ли представляется возможным. Скорее всего это говорит, что экзаменатор имеет в виду не то, что написано. Ошибки такого рода встречаются во многих тестах, поэтому прежде чем решать задачи следует уточнить у экзаменатора условия, если есть возможность.
Здравствуйте, Тёмчик, Вы писали:
L>>В крупных компаниях вопросы на засыпку на интервью запрещены вплоть до наложения дисциплинарных взысканий. Тё>
Смотри выделенное
Тё>Хотя бы одну задачку из этого списка у меня спрашивали практически в каждой компании, куда собеседовался. И ещё бывало достаточно сложное домашнее задание на алгоритмы.
Здравствуйте, Тёмчик, Вы писали:
Тё>Так ведь цель- не найти учёного-алгоритмиста, а просто программиста с зачатками интеллекта. Чтобы потом не появлялось в коде O(N!) на ровном месте.
У тебя забавный способ искать того, за кем обычно приходится побегать и поуговаривать.
Число объектов в памяти тоже известно, или, как минимум, элементарно оценивается сверху.
