Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.
1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.
Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал).
Я — ок, сравним порядки величин, с разными порядками — сразу не равно, с одним — сравниваем с точностью (имхо, опять же заданной)
Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял)
Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?
Мне: Нет, и так много времени потратили.
Ну, то что я не большой специалист в вопросах численных расчетов с использованием чисел с плавающей точкой с мантиссой фиксированной размерности я и так знал. Но я лично не вижу большой проблемы в этом — вопрос недели, может двух, чтобы изучить вопрос.
Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал. Гномиков не было, но была задача — написать программу подсчета количества слов в строке и букв 'B'. На бумажке, само собой Написал. Даже наверно скомпилировалось бы и работало
Еще устный экзамен по английскому тоже похоже провалил (птсьменный вроде сдал), но там мы вместе с собеседом поржали с моего английского
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ononim, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию O>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно.
Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью
M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял".
Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.
M>Мне говорят: физического значения нет. M>10^6 парсек и 10^2 парсек
Сами не знают, чего хотят. Использовать плавающую точку, чтобы хранить парсеки? О. майн. готт.
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Имхо, глубина рекурсии — это основная потенциальная проблема. Честно погугил что еще подразумевают под проблемами — нашел вот это — т.е. по сути речь о повторном вычислении уже ранее вычисленного (решение — кэширование), но назвать это проблемой рекурсии хз, да и далеко не всегда рекурсия это вычисления.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
.. M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ. M>Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал).
Т.е. подразумевается речь о вещественных числах — возможно хотел услышать о константах epsilon — C++, DBL_EPSILON и проч. — Cи
L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял". L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?
Как много веселых ребят, и все делают велосипед...
Здравствуйте, landerhigh, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно. L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью
Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.
Здравствуйте, std.denis, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
SD>может про проблемы распараллеливания рекурсивных алгоритмов?
M>>delta = a — b < epsilon, то равны.
SD>модуль забыл :P
Можно поподробнее?
Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался
Здравствуйте, pilgrim_, Вы писали:
_>Т.е. подразумевается речь о вещественных числах — возможно хотел услышать о константах epsilon — C++, DBL_EPSILON и проч. — Cи
Тоже подумал про машинное эпсилон, числа считаются равными в данной архитектуре, если |a-b|<eps. Вычисляется обычно итеративно, эпсилон делится на два, пока результат суммы 1+eps еще больше 1.
M> Здравствуйте!
M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? M>Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны. M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ. M>Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал). M>Я — ок, сравним порядки величин, с разными порядками — сразу не равно, с одним — сравниваем с точностью (имхо, опять же заданной) M>Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял) M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос? M>Мне: Нет, и так много времени потратили.
M>Ну, то что я не большой специалист в вопросах численных расчетов с использованием чисел с плавающей точкой с мантиссой фиксированной размерности я и так знал. Но я лично не вижу большой проблемы в этом — вопрос недели, может двух, чтобы изучить вопрос.
M>Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал. Гномиков не было, но была задача — написать программу подсчета количества слов в строке и букв 'B'. На бумажке, само собой Написал. Даже наверно скомпилировалось бы и работало
M>Еще устный экзамен по английскому тоже похоже провалил (птсьменный вроде сдал), но там мы вместе с собеседом поржали с моего английского
M>Интересует, что в пп 1-2 я не понял? M>Ну, и вообще, всё норм с собеседованием?
На счет 2 — от тебя наверное хотели услышать, что полученная погрешность будет в худшем случае пропорциональна количеству элементов в суммах. Ну и за оценку epsilon при сравнении можно грубо взять половину младшего разряда мантиссы суммы, умноженную на n — количество эл-тов в массиве.
Здравствуйте, pilgrim_, Вы писали:
L>>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью _>Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.
Случается, что собеседователи ожидают, что ответ будет совпадать с вычитанным в учебнике.
Здравствуйте, landerhigh, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно. L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью
Да, это может быть. Не помню, по этому или по другому вопросу, я спросил — возможно вы что-то хотите услышать от меня то, что я считаю подразумевающимся, и просто не рассматриваю, и потому не понимаю, что еще вы хотите от меня услышать. Ну или как-то так
M>>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял". L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
Ну да, о таких ловушках я в курсе. Наверно надо было разобраться, почему именно сумма, а не просто два с потолка взятых числа.
L>Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.
M>>Мне говорят: физического значения нет. M>>10^6 парсек и 10^2 парсек
L>Сами не знают, чего хотят. Использовать плавающую точку, чтобы хранить парсеки? О. майн. готт.
Здравствуйте, ononim, Вы писали:
O>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?
Для начала нужно все же с физическим смыслом величин определиться, чтобы не решать несуществующую задачу. А в принципе, наверное, так и поступают. Мне не приходилось это сакральное знание применять на практике.
Здравствуйте, Marty, Вы писали:
M>Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался
Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот.
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что.
Ну, может быть, надо было еще брякнуть что-нибудь про скорость исполнения, что рекурсивная версия скорее всего будет медленнее итеративной.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Надо было переспросить его о каких числах идет речь, целых или с плавающей точкой. Может быть имелись ввиду целые числа, а вы свернули на плавающую точку.
M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос? M>Мне: Нет, и так много времени потратили.
Бегите от них.
Здравствуйте, std.denis, Вы писали:
M>>>>delta = a — b < epsilon, то равны. SD>>>модуль забыл :P M>>Можно поподробнее?
SD>ну обычный модуль же, чтобы знак отбросить: |a — b| < epsilon
Обычный модуль — это из разряда того, что просто подразумевается Я думаю, копать надо глубже
Здравствуйте, landerhigh, Вы писали:
M>>Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался
L>Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот.
А-ха-ха. Кто о чем, а ты о юнит тестах. А я — о сроках. Жизнь научила, что лучше срок поставить долгий, а потом перевыполнить и сделать быстрее, чем малый, а потом оправдываться о его несоблюдении
Здравствуйте, cserg, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. C>Ну, может быть, надо было еще брякнуть что-нибудь про скорость исполнения, что рекурсивная версия скорее всего будет медленнее итеративной.
Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут
M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? C>Надо было переспросить его о каких числах идет речь, целых или с плавающей точкой. Может быть имелись ввиду целые числа, а вы свернули на плавающую точку.
С плавающей, с ней, родимой.
M>>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос? M>>Мне: Нет, и так много времени потратили. C>Бегите от них.
Денег вроде дают. Не так что бы очень, но некоторые перспективы есть.
) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.
Написал. Даже наверно скомпилировалось бы и работало 
