Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 21:17
Оценка: 3 (1)
Здравствуйте!

Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.

1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.
Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал).
Я — ок, сравним порядки величин, с разными порядками — сразу не равно, с одним — сравниваем с точностью (имхо, опять же заданной)
Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял)
Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?
Мне: Нет, и так много времени потратили.

Ну, то что я не большой специалист в вопросах численных расчетов с использованием чисел с плавающей точкой с мантиссой фиксированной размерности я и так знал. Но я лично не вижу большой проблемы в этом — вопрос недели, может двух, чтобы изучить вопрос.

Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал. Гномиков не было, но была задача — написать программу подсчета количества слов в строке и букв 'B'. На бумажке, само собой Написал. Даже наверно скомпилировалось бы и работало

Еще устный экзамен по английскому тоже похоже провалил (птсьменный вроде сдал), но там мы вместе с собеседом поржали с моего английского


Интересует, что в пп 1-2 я не понял?

Ну, и вообще, всё норм с собеседованием?
Маньяк Робокряк колесит по городу
Re: Вопросы на собеседовании (в очередной раз)
От: ononim  
Дата: 06.04.17 21:34
Оценка: 5 (2)
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"
Как много веселых ребят, и все делают велосипед...
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 21:46
Оценка:
Здравствуйте, ononim, Вы писали:

M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
O>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"

Не фирмварь, CAD с плюшками
Маньяк Робокряк колесит по городу
Re: Вопросы на собеседовании (в очередной раз)
От: std.denis Россия  
Дата: 06.04.17 22:14
Оценка: +1
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

может про проблемы распараллеливания рекурсивных алгоритмов?

M>delta = a — b < epsilon, то равны.


модуль забыл :P
Re: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 06.04.17 22:24
Оценка: 3 (1) +9
Здравствуйте, Marty, Вы писали:

M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно.
Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью

M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.


Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял".
Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.

M>Мне говорят: физического значения нет.

M>10^6 парсек и 10^2 парсек

Сами не знают, чего хотят. Использовать плавающую точку, чтобы хранить парсеки? О. майн. готт.
www.blinnov.com
Re: Вопросы на собеседовании (в очередной раз)
От: pilgrim_ Россия  
Дата: 06.04.17 22:27
Оценка:
Здравствуйте, Marty, Вы писали:

M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

Имхо, глубина рекурсии — это основная потенциальная проблема. Честно погугил что еще подразумевают под проблемами — нашел вот это — т.е. по сути речь о повторном вычислении уже ранее вычисленного (решение — кэширование), но назвать это проблемой рекурсии хз, да и далеко не всегда рекурсия это вычисления.

M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?

..
M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
M>Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал).

Т.е. подразумевается речь о вещественных числах — возможно хотел услышать о константах epsilon — C++, DBL_EPSILON и проч. — Cи
Re[2]: Вопросы на собеседовании (в очередной раз)
От: ononim  
Дата: 06.04.17 22:33
Оценка:
L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял".
L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?
Как много веселых ребят, и все делают велосипед...
Re[2]: Вопросы на собеседовании (в очередной раз)
От: pilgrim_ Россия  
Дата: 06.04.17 22:35
Оценка:
Здравствуйте, landerhigh, Вы писали:

M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно.

L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью

Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.
Отредактировано 06.04.2017 22:36 pilgrim_ . Предыдущая версия .
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 22:46
Оценка:
Здравствуйте, std.denis, Вы писали:

M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)


SD>может про проблемы распараллеливания рекурсивных алгоритмов?





M>>delta = a — b < epsilon, то равны.


SD>модуль забыл :P


Можно поподробнее?
Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался
Маньяк Робокряк колесит по городу
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Michael7 Россия  
Дата: 06.04.17 22:46
Оценка:
Здравствуйте, pilgrim_, Вы писали:

_>Т.е. подразумевается речь о вещественных числах — возможно хотел услышать о константах epsilon — C++, DBL_EPSILON и проч. — Cи


Тоже подумал про машинное эпсилон, числа считаются равными в данной архитектуре, если |a-b|<eps. Вычисляется обычно итеративно, эпсилон делится на два, пока результат суммы 1+eps еще больше 1.
Re: Вопросы на собеседовании (в очередной раз)
От: andyp  
Дата: 06.04.17 22:47
Оценка: +1
Здравствуйте, Marty, Вы писали:

  Скрытый текст
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 — количество эл-тов в массиве.
Re[3]: Вопросы на собеседовании (в очередной раз)
От: std.denis Россия  
Дата: 06.04.17 22:49
Оценка:
M>>>delta = a — b < epsilon, то равны.
SD>>модуль забыл :P
M>Можно поподробнее?

ну обычный модуль же, чтобы знак отбросить: |a — b| < epsilon
Re[3]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 06.04.17 22:55
Оценка: +5
Здравствуйте, pilgrim_, Вы писали:

L>>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью

_>Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.

Случается, что собеседователи ожидают, что ответ будет совпадать с вычитанным в учебнике.
www.blinnov.com
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 22:58
Оценка:
Здравствуйте, landerhigh, Вы писали:

M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно.

L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью

Да, это может быть. Не помню, по этому или по другому вопросу, я спросил — возможно вы что-то хотите услышать от меня то, что я считаю подразумевающимся, и просто не рассматриваю, и потому не понимаю, что еще вы хотите от меня услышать. Ну или как-то так


M>>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.


L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял".

L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.

Ну да, о таких ловушках я в курсе. Наверно надо было разобраться, почему именно сумма, а не просто два с потолка взятых числа.


L>Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.


M>>Мне говорят: физического значения нет.

M>>10^6 парсек и 10^2 парсек

L>Сами не знают, чего хотят. Использовать плавающую точку, чтобы хранить парсеки? О. майн. готт.


Думаешь, парсеки лучше в std::size_t хранить?
Маньяк Робокряк колесит по городу
Re[3]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 06.04.17 22:59
Оценка:
Здравствуйте, ononim, Вы писали:

O>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?


Для начала нужно все же с физическим смыслом величин определиться, чтобы не решать несуществующую задачу. А в принципе, наверное, так и поступают. Мне не приходилось это сакральное знание применять на практике.
www.blinnov.com
Re[3]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 06.04.17 23:01
Оценка:
Здравствуйте, Marty, Вы писали:

M>Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался


Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот.
www.blinnov.com
Re: Вопросы на собеседовании (в очередной раз)
От: cserg  
Дата: 06.04.17 23:09
Оценка:
Здравствуйте, Marty, Вы писали:

M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что.
Ну, может быть, надо было еще брякнуть что-нибудь про скорость исполнения, что рекурсивная версия скорее всего будет медленнее итеративной.

M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?

Надо было переспросить его о каких числах идет речь, целых или с плавающей точкой. Может быть имелись ввиду целые числа, а вы свернули на плавающую точку.

M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?

M>Мне: Нет, и так много времени потратили.
Бегите от них.
Re[4]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 23:10
Оценка:
Здравствуйте, std.denis, Вы писали:

M>>>>delta = a — b < epsilon, то равны.

SD>>>модуль забыл :P
M>>Можно поподробнее?

SD>ну обычный модуль же, чтобы знак отбросить: |a — b| < epsilon


Обычный модуль — это из разряда того, что просто подразумевается Я думаю, копать надо глубже
Маньяк Робокряк колесит по городу
Re[4]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 23:15
Оценка: +1
Здравствуйте, landerhigh, Вы писали:

M>>Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался


L>Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот.


А-ха-ха. Кто о чем, а ты о юнит тестах. А я — о сроках. Жизнь научила, что лучше срок поставить долгий, а потом перевыполнить и сделать быстрее, чем малый, а потом оправдываться о его несоблюдении
Маньяк Робокряк колесит по городу
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 23:20
Оценка:
Здравствуйте, cserg, Вы писали:

M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что.
C>Ну, может быть, надо было еще брякнуть что-нибудь про скорость исполнения, что рекурсивная версия скорее всего будет медленнее итеративной.

Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут


M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?

C>Надо было переспросить его о каких числах идет речь, целых или с плавающей точкой. Может быть имелись ввиду целые числа, а вы свернули на плавающую точку.

С плавающей, с ней, родимой.


M>>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?

M>>Мне: Нет, и так много времени потратили.
C>Бегите от них.

Денег вроде дают. Не так что бы очень, но некоторые перспективы есть.
Маньяк Робокряк колесит по городу
Re[3]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 23:50
Оценка:
Здравствуйте, ononim, Вы писали:

L>>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял".

L>>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
O>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?

С массивами — проблема — когда я хотел поговорить о них, мне говорили, что есть два числа для сравнения, и только.
Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы
Маньяк Робокряк колесит по городу
Re[4]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 06.04.17 23:53
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>>>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью

_>>Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.

L>Случается, что собеседователи ожидают, что ответ будет совпадать с вычитанным в учебнике.


Собеседователь вроде был адекватен, не тупил на моих ответах. Хотя, может он просто скипал незнакомое?
Маньяк Робокряк колесит по городу
Re[3]: Вопросы на собеседовании (в очередной раз)
От: cserg  
Дата: 07.04.17 00:34
Оценка:
Здравствуйте, Marty, Вы писали:

M>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут

Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
Re[4]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 00:40
Оценка:
Здравствуйте, cserg, Вы писали:

M>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут

C>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.

Зато место на стеке бесплатное. Не надо ничего в куче выделять
Маньяк Робокряк колесит по городу
Re: Вопросы на собеседовании (в очередной раз)
От: De-Bill  
Дата: 07.04.17 02:14
Оценка: +2
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

В такой формулировке вопрос странный. Точно также можно было бы спросить, какие проблемы могут быть при цикле while? Да какие угодно из-за кривости рук разработчика. Про рекурсию я бы ответил, что идеологически, алгоритм с использованием рекурсии должен быть глубиной O(log(n)). Т.е. все возможные алгоритмы devide & concure. И это правило не стоит нарушать. Например, считать факториал рекурсией — бред. Если правило не нарушено, то единственная проблема — иногда неудобно дебажить рекурсивные функции.

M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?


Думаю, что этот вопрос нормальный только есть в компании надо будет заниматься графикой или подобным. Во всех остальных случаях вопрос непонятно зачем задавался. Я бы ответил, что просто чисел не бывает. В зависимости от реальной решаемой проблемы числа могут быть натуральными, целыми, рациональными, вещественными и тд. В зависимости от требуемой точности и особенностей работы с ними могут быть и разные представления чисел в системе. Например, в некоторых случаях, можно вообще хранить числа в виде отдельного числителя и отдельного знаменателя. Тогда нет никакой проблемы сравнить суммы двух наборов этих чисел.
Re[2]: Вопросы на собеседовании (в очередной раз)
От: opt1k США  
Дата: 07.04.17 02:37
Оценка:
Ты, мне кажется, излишне паришься. Как по мне, так ты собес прошёл неплохо, собеседующий просто хотел посмотреть как ты мыслишь. Имхо, мыслишь ты нормально. Есть, конечно, вариант, что собеседующий сам не знал ответы на свои вопросы, но я его не учитываю, предполагая что ты собеседовался в приличную компанию.
Коплю на ланцер
Re: Вопросы на собеседовании (в очередной раз)
От: aik Австралия  
Дата: 07.04.17 03:01
Оценка:
Здравствуйте, Marty, Вы писали:

M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

Проблемы если не выполняется условие выхода из рекурсии (вообще или очень долго) или получается слишком глубокий стек. Всякая нереентерабельность — это не про рекурсию, это другое (например, обработчик прерывания — там рекурсией и не пахнет).

Вообще, вопрос странный. Я б давал куски хорошего и плохого кода и просил сказать какой хороший и какой плохой, а перечислять какие бывают проблемы вообще — это уже какое то поле чудес с Якубовичем, угадывать надо.

M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?

M>Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.

Если числа суммированы до тебя и тебе дают только a и b — то их и сравнивай через ">" Очень странный вопрос в такой формулировке. Меня обычно спрашивали как суммировать чтоб потерять по дороге по-меньше — типа сначала отсортировать по возрастанию, и суммировать от меньших к большим, а тут —
Re: Вопросы на собеседовании (в очередной раз)
От: mgu  
Дата: 07.04.17 03:38
Оценка:
Здравствуйте, Marty, Вы писали:

M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?


Числа-то хоть все положительные?
Re: Вопросы на собеседовании (в очередной раз)
От: Qt-Coder  
Дата: 07.04.17 03:45
Оценка:
Здравствуйте, Marty, Вы писали:

Про VMPKit в резюме писал?
Re[5]: Вопросы на собеседовании (в очередной раз)
От: alzt  
Дата: 07.04.17 06:51
Оценка:
Здравствуйте, Marty, Вы писали:

M>>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут

C>>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.

M>Зато место на стеке бесплатное. Не надо ничего в куче выделять


Можно пример кода с рекурсией, где за счёт этого будет экономия.
Re[4]: Вопросы на собеседовании (в очередной раз)
От: · Великобритания  
Дата: 07.04.17 07:01
Оценка:
Здравствуйте, Marty, Вы писали:

O>>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?

M>С массивами — проблема — когда я хотел поговорить о них, мне говорили, что есть два числа для сравнения, и только.
M>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы
Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Pzz Россия https://github.com/alexpevzner
Дата: 07.04.17 07:19
Оценка:
Здравствуйте, ononim, Вы писали:

O>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"


По-моему, такого уже не бывает. Под стек просто резервируется сколько-то. Например, в ядре линукса под стек выделено 4К, куда уж меньше. Конечно, при программировании надо это учитывать, и не заводить на стеке больших массивов и структур.
Re[5]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 07:57
Оценка:
Здравствуйте, Marty, Вы писали:

L>>Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот.

M>А-ха-ха. Кто о чем, а ты о юнит тестах. А я — о сроках. Жизнь научила, что лучше срок поставить долгий, а потом перевыполнить и сделать быстрее, чем малый, а потом оправдываться о его несоблюдении

А меня жизнь научила не ставить сроки от балды, ни маленькие, ни большие
www.blinnov.com
Re[3]: Вопросы на собеседовании (в очередной раз)
От: ononim  
Дата: 07.04.17 07:57
Оценка:
O>>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"
Pzz>По-моему, такого уже не бывает. Под стек просто резервируется сколько-то. Например, в ядре линукса под стек выделено 4К, куда уж меньше. Конечно, при программировании надо это учитывать, и не заводить на стеке больших массивов и структур.
В некоторых контроллерах оперативной памяти всего 8КБ. И сюда нужно засунуть глобальные переменные, стек и хип.
Как много веселых ребят, и все делают велосипед...
Re[6]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 07:59
Оценка:
Здравствуйте, alzt, Вы писали:

M>>Зато место на стеке бесплатное. Не надо ничего в куче выделять

A>Можно пример кода с рекурсией, где за счёт этого будет экономия.

Обход дерева без рекурсии требует дополнительной памяти.
www.blinnov.com
Отредактировано 07.04.2017 10:39 landerhigh . Предыдущая версия .
Re[4]: Вопросы на собеседовании (в очередной раз)
От: Pzz Россия https://github.com/alexpevzner
Дата: 07.04.17 08:05
Оценка: +3 :)))
Здравствуйте, ononim, Вы писали:

O>В некоторых контроллерах оперативной памяти всего 8КБ. И сюда нужно засунуть глобальные переменные, стек и хип.


8K — это роскошь. В такой контроллер можно прям настоящую программу затолкать.

Мне тут приходилось программировать контроллер, в котором было только 128 байт. Причем когда мы договаривались об этой работе, мне сказали, что их там 256, а я сдуру поверил на слово. А когда вскрылась правда, было поздно что-то менять
Re[4]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 08:06
Оценка:
Здравствуйте, ononim, Вы писали:

O>В некоторых контроллерах оперативной памяти всего 8КБ.


8 килобайт есть как бы весьма и даже очень дохрена.
www.blinnov.com
Re: Вопросы на собеседовании (в очередной раз)
От: Gradiens  
Дата: 07.04.17 08:08
Оценка:
Здравствуйте, Marty, Вы писали:

M> Здравствуйте!


M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.


M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

Кроме как проблемы переполнения стека еще типичная проблема быстродействия.

M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?

Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.

Но себеседование действительно странное.
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Qulac Россия  
Дата: 07.04.17 08:41
Оценка:
Здравствуйте, Gradiens, Вы писали:

G>Здравствуйте, Marty, Вы писали:


G>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.


G>Но себеседование действительно странное.


А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".
Программа – это мысли спрессованные в код
Re: Вопросы на собеседовании (в очередной раз)
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 07.04.17 08:41
Оценка:
Идиотов хватает, чтобы устраивать такие собеседования.
1613 г. = 2024 г.
Re[2]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 08:41
Оценка:
Здравствуйте, Gradiens, Вы писали:

M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

G>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.

А вот с этого места можно поподробнее?
www.blinnov.com
Re: Вопросы на собеседовании (в очередной раз)
От: SaZ  
Дата: 07.04.17 08:43
Оценка:
Здравствуйте, Marty, Вы писали:

M> Здравствуйте!


M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

Тут уже много написали, но может хотели очевидного? Рекурсия не инлайнится (рантайм рекурсия).
Отредактировано 07.04.2017 8:43 SaZ . Предыдущая версия .
Re[3]: Вопросы на собеседовании (в очередной раз)
От: Gradiens  
Дата: 07.04.17 10:06
Оценка: +1
Здравствуйте, landerhigh, Вы писали:

L>Здравствуйте, Gradiens, Вы писали:


M>>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

G>>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.

L>А вот с этого места можно поподробнее?

На этот вопрос у меня два ответа.
Во-первых, не очень опытные коллеги не всегда представляют вычислительную сложность реализуемого при помощи рекурсии решения. Результат: "ой, зависло".
Во-вторых у рекурсии большие накладные расходы. Если взять надуманный пример расчета факториала в цикле, или с рекурсией, то количество операций умножения будет одинаково. Но для рекурсии накладные расходы для вызова методов офигенны (это ж надо регистры запушить в стек, параметр занести в регистр или стек, провести вызов, после произведенных вычислений вернуть все как было до вызова и вернуть управление вызывающему коду). В результате скорость будет отличаться на порядок.
Re[2]: Вопросы на собеседовании (в очередной раз)
От: ylem  
Дата: 07.04.17 10:08
Оценка:
L>Сами не знают, чего хотят. Использовать плавающую точку, чтобы хранить парсеки? О. майн. готт.

А в чем еще парсеки хранить? Ну или чем это плохо?
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 10:09
Оценка:
Здравствуйте, De-Bill, Вы писали:


M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?


DB>Думаю, что этот вопрос нормальный только есть в компании надо будет заниматься графикой или подобным.


Да, графика
Маньяк Робокряк колесит по городу
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 10:10
Оценка:
Здравствуйте, Qt-Coder, Вы писали:

QC>Про VMPKit в резюме писал?


Всё писал, и про тебя писал
Маньяк Робокряк колесит по городу
Re[6]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 10:11
Оценка:
Здравствуйте, alzt, Вы писали:

M>>>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут

C>>>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.

M>>Зато место на стеке бесплатное. Не надо ничего в куче выделять


A>Можно пример кода с рекурсией, где за счёт этого будет экономия.


Нельзя
Маньяк Робокряк колесит по городу
Re[4]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 10:12
Оценка: +1
Здравствуйте, Gradiens, Вы писали:

G>Во-первых, не очень опытные коллеги не всегда представляют вычислительную сложность реализуемого при помощи рекурсии решения. Результат: "ой, зависло".


Э... ты, наверное, хотел сказать, "ой упало"?

G>Во-вторых у рекурсии большие накладные расходы. Если взять надуманный пример расчета факториала в цикле, или с рекурсией, то количество операций умножения будет одинаково. Но для рекурсии накладные расходы для вызова методов офигенны


В мире существуют не только процессоры x86/x86_64.

G>В результате скорость будет отличаться на порядок.


Такие заявления слуедует подкреплять бенчмарками. А то есть мнение, что толкать регистры в стек полюбому выйдет быстрее обращения к памяти мимо процессорного кеша. Не гворя уже о том, что подготовка и поддержание структуры данных для итеративной обработки взамен простой рекурсии тоже обходится не бесплатно.
www.blinnov.com
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 10:14
Оценка:
Здравствуйте, Gradiens, Вы писали:

M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?

G>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.

Наверно не точно сформулировал, но я так понял, что нужно сравнить на равенство. Может в такой формулировке и кривовато звучит


G>Но себеседование действительно странное.



Маньяк Робокряк колесит по городу
Re[3]: Вопросы на собеседовании (в очередной раз)
От: Qt-Coder  
Дата: 07.04.17 10:17
Оценка:
Здравствуйте, Marty, Вы писали:

M>Всё писал, и про тебя писал

Про меня зря, может поэтому и не взяли
Re[3]: Вопросы на собеседовании (в очередной раз)
От: Gradiens  
Дата: 07.04.17 10:19
Оценка:
Здравствуйте, Qulac, Вы писали:

Q>Здравствуйте, Gradiens, Вы писали:


G>>Здравствуйте, Marty, Вы писали:


G>>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.


G>>Но себеседование действительно странное.


Q>А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".


Ну не знаю.. у сферических чисел должен быть тип.
Например, Int32. Тогда в качестве переменной суммы используем Int64 — и никаких проблем в принципе не будет.
Или, тип чисел в массиве Int64. Тогда для суммы Int64 использовать нельзя, а вдруг переполнится. Надо использовать какой-нить BigInteger (я — дотнетчик, на других платформах должны быть аналоги, ну или их придется писать самому
Если же у нас тип чисел — double — то может быть две проблемы. Переполнение, а также потеря точности при суммировании большого и маленького числа.

Но все равно, не бывает сферических чисел без физического смысла. А также не могу представить себе ситуацию, когда надо выполнить 10^100 + 10^-100. Даже если сложить диаметр вселенной (самое большое что есть в природе) с Планковской длиной (самое маленькое что есть в природе) — и то менее внушительный пример получится. Так что пример надуманный и годится только для затравки разговора, но никак не для реальных выводов.
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 10:19
Оценка:
Здравствуйте, SaZ, Вы писали:


M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

SaZ>Тут уже много написали, но может хотели очевидного? Рекурсия не инлайнится (рантайм рекурсия).



Может быть это. Были вопросы по оптимизации.
Маньяк Робокряк колесит по городу
Re[2]: Вопросы на собеседовании (в очередной раз)
От: De-Bill  
Дата: 07.04.17 10:30
Оценка: +1
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
G>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.

Это не так. Любую рекурсию можно заменить на итеративный алгоритм с использованием структуры данных стек. Только в большинстве случаев, эта структура данных стек будет реализована с использованием динамической памяти, что уже дороже, чем использовать программный стек, так как память надо выделять, освобождать. Можно реализовать стек и без постоянного выделения памяти, но тогда уже нужно потратить время на то, чтобы заранее оценить, какой размер такой структуры данных нужен.
В качестве упражнения, можешь попробовать реализовать quick-sort не рекурсивно. А потом реализовать quck-sort так, чтобы выделение памяти в куче происходило только один раз.
Re[4]: Вопросы на собеседовании (в очередной раз)
От: Qulac Россия  
Дата: 07.04.17 10:31
Оценка:
Здравствуйте, Gradiens, Вы писали:

G>Здравствуйте, Qulac, Вы писали:


Q>>Здравствуйте, Gradiens, Вы писали:


G>>>Здравствуйте, Marty, Вы писали:


G>>>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.


G>>>Но себеседование действительно странное.


Q>>А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".


G>Ну не знаю.. у сферических чисел должен быть тип.

G>Например, Int32. Тогда в качестве переменной суммы используем Int64 — и никаких проблем в принципе не будет.
G>Или, тип чисел в массиве Int64. Тогда для суммы Int64 использовать нельзя, а вдруг переполнится. Надо использовать какой-нить BigInteger (я — дотнетчик, на других платформах должны быть аналоги, ну или их придется писать самому
G>Если же у нас тип чисел — double — то может быть две проблемы. Переполнение, а также потеря точности при суммировании большого и маленького числа.

G>Но все равно, не бывает сферических чисел без физического смысла. А также не могу представить себе ситуацию, когда надо выполнить 10^100 + 10^-100. Даже если сложить диаметр вселенной (самое большое что есть в природе) с Планковской длиной (самое маленькое что есть в природе) — и то менее внушительный пример получится. Так что пример надуманный и годится только для затравки разговора, но никак не для реальных выводов.


"сферические числа в вакууме" у программистов и есть любой тип чисел.
Программа – это мысли спрессованные в код
Re: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 07.04.17 11:36
Оценка: +1
Здравствуйте, Marty, Вы писали:


M>Интересует, что в пп 1-2 я не понял?


По рекурсии я бы выделил три пункта:
1. Глубина рекурсии, т.е. смотреть чтобы не было переполнения стека.
2. Условие по выходу из рекурсии, т.е. оно должно 100 % выполняться.
3. Эффективность, т.е. проверка на повторяемость вычислений (действий). Если одни и те же вычисления повторяются много раз, то рекурсию применять не стоит.

По числам с плавающей точкой, как тут уже сказали, сравнивать нужно по модулю:
bool bEqual = fabs(dSum1 — dSum2) < dEpsilon;
Отредактировано 07.04.2017 11:41 Iso12 . Предыдущая версия .
Re[2]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 11:38
Оценка: +1 :)
Здравствуйте, Iso12, Вы писали:

I>По рекурсии я бы выделил три пункта:

I>1. Глубина рекурсии, т.е. смотреть чтобы не было переполнения стека.
I>2. Условие по выходу из рекурсии, т.е. оно должно 100 % выполняться.

Это уже какое-то собеседование на должность КО получается.

I>3. Эффективность, т.е. проверка на повторяемость вычислений (действий). Если одни и те же вычисления повторяются много раз, то рекурсию применять не стоит.


То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя?
www.blinnov.com
Re[3]: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 07.04.17 12:14
Оценка:
Здравствуйте, landerhigh, Вы писали:

То что я имел ввиду, это например вычисление чисел Fibbonachi:
fib (0) = fib (1) = 1
fib (n) = fib (n – 1) + fib (n – 2), n = 2, 3, ...

L>То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя?

Тут всё зависит от того, что мы хотим получить: скорость выполнения или простоту кода. Если время выполнения критично и есть алгоритм, который это делает быстрей без рекурсии, то рекурсия здесь не уместна.
Отредактировано 07.04.2017 12:24 Iso12 . Предыдущая версия .
Re[4]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 12:44
Оценка:
Здравствуйте, Iso12, Вы писали:


I>То что я имел ввиду, это например вычисление чисел Fibbonachi:


А можно пример не из учебника или арсенала К.О, а встречающийся в реальной жизни?

L>>То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя?

I>Тут всё зависит от того, что мы хотим получить: скорость выполнения или простоту кода. Если время выполнения критично и есть алгоритм, который это делает быстрей без рекурсии, то рекурсия здесь не уместна.

Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией.
www.blinnov.com
Re: Вопросы на собеседовании (в очередной раз)
От: koodeer  
Дата: 07.04.17 13:10
Оценка: 2 (1)
Здравствуйте, Marty, Вы писали:


M>2) Есть два набора чисел ... Производится суммирование и получается две суммы.


Возможно, ждали упоминания про Сложение большого множества чисел, существенно отличающихся по величине.
Re[5]: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 07.04.17 17:21
Оценка:
Здравствуйте, landerhigh, Вы писали:


L>А можно пример не из учебника или арсенала К.О, а встречающийся в реальной жизни?

В математических вычислениях часто встречается.
Что означает К.О. ?


L>Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией.

Если алгоритм с рекурсией самый быстрый и стек позволяет, то его и используйте. Код от этого будет проще и читабельней. Всему своё место. Или вы понимаете слово "Эффетивность" как-то по другому?
Re[6]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 18:02
Оценка:
Здравствуйте, Iso12, Вы писали:

L>>А можно пример не из учебника или арсенала К.О, а встречающийся в реальной жизни?

I>В математических вычислениях часто встречается.

"В математических вычислениях" — это и есть примеры из учебников. Конкретики хочется.

I>Что означает К.О. ?


Ваш капитан Очевидность, вестимо

L>>Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией.

I>Если алгоритм с рекурсией самый быстрый и стек позволяет, то его и используйте. Код от этого будет проще и читабельней. Всему своё место. Или вы понимаете слово "Эффетивность" как-то по другому?

Я прошу пример реализуемого через рекурсию алгоритма, который эффективнее реализовать без оной.
www.blinnov.com
Re: Вопросы на собеседовании (в очередной раз)
От: Zhendos  
Дата: 07.04.17 18:42
Оценка:
Здравствуйте, Marty, Вы писали:


M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что.

В учебниках для детей, когда описывают рекурсию, всегда начинают с того,
что нужно решить вопрос остановки алгоритма. Возможно он хотел именно такую формулировку?


M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?

M>Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.
M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
M>Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал).
M>Я — ок, сравним порядки величин, с разными порядками — сразу не равно, с одним — сравниваем с точностью (имхо, опять же заданной)
M>Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял)

Так есть, ТЗ или нет? То его нет, то оказывается что 10^26 * 3 и 10^18 * 3 это равные величины?


M>Ну, и вообще, всё норм с собеседованием?


Очень странное исходя из моего опыта, если не на junior позицию
Re[7]: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 07.04.17 19:22
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>"В математических вычислениях" — это и есть примеры из учебников. Конкретики хочется.

Программируют не только БД, веб странички и т.п. но и математические расчёты и вычисления . Там и встречается.


I>>Если алгоритм с рекурсией самый быстрый и стек позволяет, то его и используйте. Код от этого будет проще и читабельней. Всему своё место. Или вы понимаете слово "Эффетивность" как-то по другому?


L>Я прошу пример реализуемого через рекурсию алгоритма, который эффективнее реализовать без оной.


Я уже выше привёл: если вы напишите мне функцию для расчёта числа Fibonachi, которая рекурсией считает быстрей чем обычным методом, буду вам очень признателен.

Ещё раз повторю свою мысль: расчёт будет выполнятся всегда быстрее, если вычисление необходимого промежуточного результата будет выполняться один раз и сохранятся для использования в других местах расчёта, чем этот промежуточный результат каждый раз в этих местах по новой вычислять.
Re[8]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 07.04.17 22:33
Оценка:
Здравствуйте, Iso12, Вы писали:

L>>"В математических вычислениях" — это и есть примеры из учебников. Конкретики хочется.

I>Программируют не только БД, веб странички и т.п. но и математические расчёты и вычисления . Там и встречается.

Поконкретнее, пожалуйста.

I>Я уже выше привёл: если вы напишите мне функцию для расчёта числа Fibonachi, которая рекурсией считает быстрей чем обычным методом, буду вам очень признателен.


Э нет, это уже демагогия пошла и натягивание совы на глобус. Рекурсивность вовсе не самоцель, а всего лишь инструмент.
Впрочем, на плюсах пожалуйста, как просили. С точки зрения рантайма — однозначно самый быстрый способ

I>Ещё раз повторю свою мысль: расчёт будет выполнятся всегда быстрее, если вычисление необходимого промежуточного результата будет выполняться один раз и сохранятся для использования в других местах расчёта, чем этот промежуточный результат каждый раз в этих местах по новой вычислять.


Спасибо, кэп. Только при чем тут рекурсия?
www.blinnov.com
Re[5]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 22:58
Оценка:
Здравствуйте, Pzz, Вы писали:


Pzz>8K — это роскошь. В такой контроллер можно прям настоящую программу затолкать.


Pzz>Мне тут приходилось программировать контроллер, в котором было только 128 байт. Причем когда мы договаривались об этой работе, мне сказали, что их там 256, а я сдуру поверил на слово. А когда вскрылась правда, было поздно что-то менять


Прикольная работа. С удовольствием бы занялся
Маньяк Робокряк колесит по городу
Re: Вопросы на собеседовании (в очередной раз)
От: bazis1 Канада  
Дата: 07.04.17 23:01
Оценка:
Здравствуйте, Marty, Вы писали:

M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Как вариант, в том, в стеке будет нужно (размер локальных переменных) x (глубина рекурсии) места, что не всегда оптимально. Скажем, при такой структуре:
int func(int arg)
{
    char big_array[1024];
    int val;
    //compute val using big_array
    return func(val)
}


Я не уверен, что оптимизатор догадается освободить место, занятое под big_array перед рекурсивным вызовом. И даже если здесь догадается, то в менее тривиальном примере уже нет.
Но вообще, задача похожа на "угадай, какую страницу задачника экзаменатор прочел за час до собеседования".

M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить.

Я обычно всегда начинаю с тривиального варианта, явно проговаривая, что он тривиальный.
Тривиальный вариант — свести все к общему знаменателю каким-нибудь монстроидальным bigint-ом и в лоб сложить. Для 1000 чисел особой разницы не будет. Дальше уже можно рассуждать на тему оптимизации.

M>Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал.

Не барское это дело — резюме читать. На самом деле, уже на этом пункте обычно можно разворачиваться. Если собеседующий не нашел времени прочесть ваше резюме, то в найме он явно не заинтересован и собеседование проводит для других целей.
Re[3]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 23:05
Оценка:
Здравствуйте, opt1k, Вы писали:

O>Ты, мне кажется, излишне паришься. Как по мне, так ты собес прошёл неплохо, собеседующий просто хотел посмотреть как ты мыслишь. Имхо, мыслишь ты нормально. Есть, конечно, вариант, что собеседующий сам не знал ответы на свои вопросы, но я его не учитываю, предполагая что ты собеседовался в приличную компанию.


Спс, ободрил. Контора — , объявление тут нашел, в Питере в офисе в центре сидят несколько человек и всё. Говорят, работают на норвегов, с перспективой командировок и трудоустройства там.
Но, вообще, я когда шел, думал что-то посолиднее будет — пиджачек надел, цивилом прикинулся, папочку для солидности взял А там — по-простецки как-то. Вот думаю, может надо было в свитере и трениках ехать. А то может за мажора халявщика приняли
Маньяк Робокряк колесит по городу
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 23:16
Оценка:
Здравствуйте, bazis1, Вы писали:

M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить.

B>Я обычно всегда начинаю с тривиального варианта, явно проговаривая, что он тривиальный.
B>Тривиальный вариант — свести все к общему знаменателю каким-нибудь монстроидальным bigint-ом и в лоб сложить. Для 1000 чисел особой разницы не будет. Дальше уже можно рассуждать на тему оптимизации.

На те вопросы, где собесед чего-то еще ждал от меня, кроме того, что я сказал, я отвечал так: "вы похоже ждете от меня чего-то, что я считаю слишком очевидным, и в силу очевидности этих вещей для меня мне даже не приходит мысль об этом что-то говорить"


M>>Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал.

B>Не барское это дело — резюме читать. На самом деле, уже на этом пункте обычно можно разворачиваться. Если собеседующий не нашел времени прочесть ваше резюме, то в найме он явно не заинтересован и собеседование проводит для других целей.

Ну, пересекалось с резюме там только пара пунктов. Да и резюме я отсылал очень краткое. Но этот момент несколько напряг — можно было эти пункты просто по резюме обсудить, а не напрягать меня писаниной, чтобы потом все равно устно обсуждать
Маньяк Робокряк колесит по городу
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.04.17 23:19
Оценка:
Здравствуйте, Zhendos, Вы писали:

M>>Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял)


Z>Так есть, ТЗ или нет? То его нет, то оказывается что 10^26 * 3 и 10^18 * 3 это равные величины?


Да я и сам не понял


M>>Ну, и вообще, всё норм с собеседованием?


Z>Очень странное исходя из моего опыта, если не на junior позицию


Уверенный мидл, как минимум
Маньяк Робокряк колесит по городу
Re[3]: Вопросы на собеседовании (в очередной раз)
От: bazis1 Канада  
Дата: 08.04.17 04:19
Оценка: 1 (1)
Здравствуйте, Marty, Вы писали:

M>На те вопросы, где собесед чего-то еще ждал от меня, кроме того, что я сказал, я отвечал так: "вы похоже ждете от меня чего-то, что я считаю слишком очевидным, и в силу очевидности этих вещей для меня мне даже не приходит мысль об этом что-то говорить"

Вы некомандный . Так отвечать нельзя ни в коем случае, потому что этот ответ подразумевает, что Вы умнее собеседующего.
Ваша задача на корпоративном собеседовании — показать, что Вы:
а) Глупее собеседующего, смотрите на него снизу вверх и не претендуете на его место
б) Достаточно умны, чтобы выполнять работу, которую ему самому делать западло

Я в эти ворота в свое время головой побился зачетно.
Не хотите играть в этот цирк — качайте язык и ищите удалёнку на Штаты. Удаленщики обычно люди второсортные, но мозги им выносят меньше.

M>Ну, пересекалось с резюме там только пара пунктов. Да и резюме я отсылал очень краткое. Но этот момент несколько напряг — можно было эти пункты просто по резюме обсудить, а не напрягать меня писаниной, чтобы потом все равно устно обсуждать

Писанина нужна для отчетности. Вам же сороковник скоро, а Вы все как маленький
Re[4]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 08.04.17 08:24
Оценка:
Здравствуйте, bazis1, Вы писали:

M>>На те вопросы, где собесед чего-то еще ждал от меня, кроме того, что я сказал, я отвечал так: "вы похоже ждете от меня чего-то, что я считаю слишком очевидным, и в силу очевидности этих вещей для меня мне даже не приходит мысль об этом что-то говорить"

B>Вы некомандный . Так отвечать нельзя ни в коем случае, потому что этот ответ подразумевает, что Вы умнее собеседующего.

А как правильно отвечать? Чтобы и валенком прикинуться, и не совсем уж валенком?
Маньяк Робокряк колесит по городу
Re[9]: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 08.04.17 21:20
Оценка:
Здравствуйте, landerhigh, Вы писали:


L>>>"В математических вычислениях" — это и есть примеры из учебников. Конкретики хочется.

I>>Программируют не только БД, веб странички и т.п. но и математические расчёты и вычисления . Там и встречается.

L>Поконкретнее, пожалуйста.


ну куда уж конкретнее.

I>>Я уже выше привёл: если вы напишите мне функцию для расчёта числа Fibonachi, которая рекурсией считает быстрей чем обычным методом, буду вам очень признателен.


L>Э нет, это уже демагогия пошла и натягивание совы на глобус. Рекурсивность вовсе не самоцель, а всего лишь инструмент.

L>Впрочем, на плюсах пожалуйста, как просили. С точки зрения рантайма — однозначно самый быстрый способ
Какая тут демагогия? Конкретная задача, требуется найти решение. Ваш пример это совсем не то, что я просил.
Я вам и том и толкую, что рекурсия это лишь иструмент, и применять его надо, где он подходит.

I>>Ещё раз повторю свою мысль: расчёт будет выполнятся всегда быстрее, если вычисление необходимого промежуточного результата будет выполняться один раз и сохранятся для использования в других местах расчёта, чем этот промежуточный результат каждый раз в этих местах по новой вычислять.


L>Спасибо, кэп. Только при чем тут рекурсия?

При рекурсии в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.
Re[10]: Вопросы на собеседовании (в очередной раз)
От: · Великобритания  
Дата: 08.04.17 21:56
Оценка: 9 (2) +2
Здравствуйте, Iso12, Вы писали:

L>>Спасибо, кэп. Только при чем тут рекурсия?

I>При рекурсии в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.
Бред, дело не в рекурсии, а в алгоритме. Без рекурсии тоже можно тупой алгоритм написать. А вот рекурсия без "промежуточных" результатов:
int fib(int term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 if(term == 1) return val;
 return fib(term - 1, val+prev, val);
}
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[10]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 08.04.17 23:10
Оценка:
Здравствуйте, Iso12, Вы писали:

I>ну куда уж конкретнее.


Ну, конкретики не будет, значит.

L>>Э нет, это уже демагогия пошла и натягивание совы на глобус. Рекурсивность вовсе не самоцель, а всего лишь инструмент.

L>>Впрочем, на плюсах пожалуйста, как просили. С точки зрения рантайма — однозначно самый быстрый способ
I>Какая тут демагогия? Конкретная задача, требуется найти решение. Ваш пример это совсем не то, что я просил.

Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.

I>Я вам и том и толкую, что рекурсия это лишь иструмент, и применять его надо, где он подходит.


Вот только не надо с умным видом декламировать прописные истины. Это не чат детского сада. И это не имеет никакого отношения к изначальной теме.

L>>Спасибо, кэп. Только при чем тут рекурсия?

I>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.

Ошибку исправил.
www.blinnov.com
Re[11]: Вопросы на собеседовании (в очередной раз)
От: samius Япония http://sams-tricks.blogspot.com
Дата: 09.04.17 04:25
Оценка:
Здравствуйте, ·, Вы писали:

·>Без рекурсии тоже можно тупой алгоритм написать.


Мне кажется, что это сложнее, чем привести тупой рекурсивный к хвостовой оптимизации.
Можно, конечно, взять тупой рекурсивный и проэмулировать рекурсивный вызов стеком, но интересно именно "тупой алгоритм" написать с нуля. Пока не вышло.
Re[4]: Вопросы на собеседовании (в очередной раз)
От: ry Россия  
Дата: 09.04.17 05:34
Оценка:
Здравствуйте, bazis1, Вы писали:

B>Не хотите играть в этот цирк — качайте язык и ищите удалёнку на Штаты.

Не твой клиент
Автор: Marty
Дата: 08.04.17
? Ты вроде сам искал удалёнщиков для embedded, если не путаю, конечно.
Re[12]: Вопросы на собеседовании (в очередной раз)
От: · Великобритания  
Дата: 09.04.17 09:04
Оценка: +1
Здравствуйте, samius, Вы писали:

S>·>Без рекурсии тоже можно тупой алгоритм написать.

S>Мне кажется, что это сложнее, чем привести тупой рекурсивный к хвостовой оптимизации.
S>Можно, конечно, взять тупой рекурсивный и проэмулировать рекурсивный вызов стеком, но интересно именно "тупой алгоритм" написать с нуля. Пока не вышло.
Вполне возможно, что для конкретной задачи, типа Фиббоначчи оно и правда, что многие могут сходу написать только эффективный цикл, но затрудняются с рекурсией, но это не является каким-то доказательством того, что "рекурсия медленнее" и т.п.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[13]: В очередной раз мысль вслух
От: landerhigh Пират  
Дата: 09.04.17 09:08
Оценка:
Здравствуйте, ·, Вы писали:

·>Вполне возможно, что для конкретной задачи, типа Фиббоначчи оно и правда, что многие могут сходу написать только эффективный цикл,


Все же за требование "написать сходу" нужно гнать ссаными тряпками из профессии и лишать ученой степени/диплома.
Реализации алгоритмов либо берутся библиотечные, либо обязаны быть продуманными, просчтитанными и протестированными.
www.blinnov.com
Re: Вопросы на собеседовании (в очередной раз)
От: andyp  
Дата: 09.04.17 09:55
Оценка:
Здравствуйте, Marty, Вы писали:

M> Здравствуйте!


M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.


M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

M>Интересует, что в пп 1-2 я не понял?


M>Ну, и вообще, всё норм с собеседованием?


По 1) — подумалось — может от тебя нечто про мемоизацию услышать ждали? В рекурсивных реализациях алгоритмов часто приходится вычислять одно и то же много раз и с этим иногда как-то бороться надо.
Re[14]: В очередной раз мысль вслух
От: samius Япония http://sams-tricks.blogspot.com
Дата: 09.04.17 11:34
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Здравствуйте, ·, Вы писали:


L>·>Вполне возможно, что для конкретной задачи, типа Фиббоначчи оно и правда, что многие могут сходу написать только эффективный цикл,


L>Все же за требование "написать сходу" нужно гнать ссаными тряпками из профессии и лишать ученой степени/диплома.

Не было требования "написать сходу". Это я написал что у меня не получилось написать с нуля тупую неэффективную реализацию Фибоначчи, не используюя при этом рекурсию.
Re: Вопросы на собеседовании (в очередной раз)
От: turbocode  
Дата: 10.04.17 10:21
Оценка:
M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?
M>Мне: Нет, и так много времени потратили.
M>Ну, и вообще, всё норм с собеседованием?

Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.
Re[5]: Вопросы на собеседовании (в очередной раз)
От: Silver_S Ниоткуда  
Дата: 10.04.17 10:41
Оценка:
Здравствуйте, ·, Вы писали:

M>>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы

·>Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..
Лучше, наверно, это не считать, не играть в наперстки — считать что здесь эти два числа равны (или не больше и не меньше).
Отредактировано 10.04.2017 10:42 Silver_S . Предыдущая версия .
Re: Вопросы на собеседовании (в очередной раз)
От: Silver_S Ниоткуда  
Дата: 10.04.17 10:59
Оценка:
Здравствуйте, Marty, Вы писали:

M> Здравствуйте!


M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.


M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

Может он тупо чего-то примитивное в инете вычитал. Google что-то выдает про проблемы:
https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

Можно заметить, что F(3) вычисляется три раза. Если рассмотреть вычисление F(n) при больших n, то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии — повторные вычисления одних и тех же значений.

Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 10.04.17 11:05
Оценка:
Здравствуйте, turbocode, Вы писали:

M>>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?

M>>Мне: Нет, и так много времени потратили.
M>>Ну, и вообще, всё норм с собеседованием?

T>Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.


Я конечно понимаю, что ты хочешь меня унизить, но два часа интервью на "побыстрее" ну никак не натянуть
Маньяк Робокряк колесит по городу
Re[6]: Вопросы на собеседовании (в очередной раз)
От: · Великобритания  
Дата: 10.04.17 11:08
Оценка:
Здравствуйте, Silver_S, Вы писали:

M>>>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы

S_S>·>Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..
S_S> Лучше, наверно, это не считать, не играть в наперстки — считать что здесь эти два числа равны (или не больше и не меньше).
На практике я бы при таких требованиях плавучку бы и не использовал — во избежание.

Но это я так... в качестве этюда интересуюсь — возможно ли. Например, отсортировать оба массива по убыванию, а потом сделать алгоритм напоминающий sorted merge join — брать и прибавлять элементы первого или вычитать элементы второго массивов в зависимости от знака текущей суммы. Сработает?..
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[3]: Вопросы на собеседовании (в очередной раз)
От: turbocode  
Дата: 10.04.17 11:14
Оценка:
T>>Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.
M>Я конечно понимаю, что ты хочешь меня унизить, но два часа интервью на "побыстрее" ну никак не натянуть

"солдат спит служба идет" — игра на собеседовании в одни ворота это всегда провал.
Re[7]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 10.04.17 19:19
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Я прошу пример реализуемого через рекурсию алгоритма, который эффективнее реализовать без оной.


Я взял в качестве дерева просто LinkedList<int> из .Net :D
Складываем элементы списка.
Тестировал итеративный алгоритм и два варианта рекурсии. Собиралось все с таргетом x86.
Результаты у меня такие:
Started!
Iterative: 38 ms, recursiveSimple: 80 ms, recursiveAcc: 92 ms


  Код
    class Program
    {
        static void Main(string[] args)
        {
            var runner = new Thread(Run, 1000 * 1024 * 1024);
            runner.Start();
            runner.Join();
        }

        static void Run()
        {
            var T = new Stopwatch();

            var src = Generate(10);

            SumIterative(src.First);
            SumRecursiveSimple(src.First);
            SumRecursiveAcc(src.First);

            src = Generate(10000000);

            Console.WriteLine("Started!");

            int count = 100;

            var iterative = 0l;
            var recursiveSimple = 0l;
            var recursiveAcc = 0l;

            for (int i = 0; i < count; i++)
            {
                T.Restart();
                SumIterative(src.First);
                T.Stop();

                iterative += T.ElapsedMilliseconds;

                T.Restart();
                SumRecursiveSimple(src.First);
                T.Stop();

                recursiveSimple += T.ElapsedMilliseconds;

                T.Restart();
                SumRecursiveAcc(src.First);
                T.Stop();

                recursiveAcc += T.ElapsedMilliseconds;
            }

            Console.WriteLine($"Iterative: {iterative/count} ms, recursiveSimple: {recursiveSimple/count} ms, recursiveAcc: {recursiveAcc/count} ms");
        }

        static LinkedList<int> Generate(int size)
        {
            var r = new LinkedList<int>();
            var random = new Random();

            for (int i = 0; i < size; i++)
            {
                r.AddLast(random.Next());
            }

            return r;
        }

        static int SumIterative(LinkedListNode<int> e)
        {
            var r = 0;
            for (var curr = e; curr != null; curr = curr.Next)
                r += curr.Value;

            return r;
        }

        static int SumRecursiveAcc(LinkedListNode<int> e, int curr = 0)
        {
            if (e == null)
                return curr;

            return SumRecursiveAcc(e.Next, e.Value + curr);
        }

        static int SumRecursiveSimple(LinkedListNode<int> e)
        {
            if (e == null)
                return 0;

            return e.Value + SumRecursiveAcc(e.Next);
        }
    }
Re[8]: Вопросы на собеседовании (в очередной раз)
От: samius Япония http://sams-tricks.blogspot.com
Дата: 10.04.17 19:41
Оценка: +1
Здравствуйте, StatujaLeha, Вы писали:

SL>
SL>        static int SumRecursiveSimple(LinkedListNode<int> e)
SL>        {
SL>            if (e == null)
SL>                return 0;

SL>            return e.Value + SumRecursiveAcc(e.Next); /// Вызван не тот метод
SL>        }
SL>


А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.
Re[9]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 10.04.17 19:53
Оценка:
Здравствуйте, samius, Вы писали:

Пофиксил.
Результаты:
Iterative: 39 ms, recursiveSimple: 138 ms, recursiveAcc: 84 ms

  Код
    class Program
    {
        static void Main(string[] args)
        {
            var runner = new Thread(Run, 1000 * 1024 * 1024);
            runner.Start();
            runner.Join();
        }

        static void Run()
        {
            var T = new Stopwatch();

            var src = Generate(10);
            SumIterative(src.First);
            SumRecursiveSimple(src.First);
            SumRecursiveAcc(src.First);

            src = Generate(10000000);

            Console.WriteLine("Started!");

            int count = 100;

            var iterative = 0l;
            var recursiveSimple = 0l;
            var recursiveAcc = 0l;

            for (int i = 0; i < count; i++)
            {
                T.Restart();
                SumIterative(src.First);
                T.Stop();

                iterative += T.ElapsedMilliseconds;

                T.Restart();
                SumRecursiveSimple(src.First);
                T.Stop();

                recursiveSimple += T.ElapsedMilliseconds;

                T.Restart();
                SumRecursiveAcc(src.First);
                T.Stop();

                recursiveAcc += T.ElapsedMilliseconds;
            }

            Console.WriteLine($"Iterative: {iterative/count} ms, recursiveSimple: {recursiveSimple/count} ms, recursiveAcc: {recursiveAcc/count} ms");
        }

        static LinkedList<int> Generate(int size)
        {
            var r = new LinkedList<int>();
            var random = new Random();

            for (int i = 0; i < size; i++)
            {
                r.AddLast(random.Next());
            }

            return r;
        }

        static int SumIterative(LinkedListNode<int> e)
        {
            var r = 0;
            for (var curr = e; curr != null; curr = curr.Next)
                r += curr.Value;

            return r;
        }

        static int SumRecursiveAcc(LinkedListNode<int> e, int curr = 0)
        {
            if (e == null)
                return curr;

            return SumRecursiveAcc(e.Next, e.Value + curr);
        }

        static int SumRecursiveSimple(LinkedListNode<int> e)
        {
            if (e == null)
                return 0;

            return e.Value + SumRecursiveSimple(e.Next);
        }
    }


S>А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.


Да, согласен. Но есть надежда на JIT-compiler.
Ну и разница во времени работы между двумя алгоритмами есть.
Re[10]: Вопросы на собеседовании (в очередной раз)
От: samius Япония http://sams-tricks.blogspot.com
Дата: 10.04.17 20:40
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Здравствуйте, samius, Вы писали:


S>>А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.


SL>Да, согласен. Но есть надежда на JIT-compiler.

Нету, т.к. надежда JIT-compiler-а — OpCode.Tailсall. А без него он делать ничего сам не будет.

SL>Ну и разница во времени работы между двумя алгоритмами есть.


вот разница у меня

Iterative: 17 ms, recursiveSimple: 31 ms, recursiveAcc: 33 ms
FSharp: 17 ms


где
module FsModule1

    let rec sumRec (n : System.Collections.Generic.LinkedListNode<int>) sum =
        if obj.ReferenceEquals(n, null) then sum
        else sumRec n.Next (sum + n.Value)
Re[11]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 10.04.17 20:51
Оценка:
Здравствуйте, samius, Вы писали:

Ясно.
Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.
Пример же с обходом полноценного дерева лень делать.
Re[12]: Вопросы на собеседовании (в очередной раз)
От: samius Япония http://sams-tricks.blogspot.com
Дата: 10.04.17 20:59
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Здравствуйте, samius, Вы писали:


SL>Ясно.

SL>Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.
А разве есть другие?
Re[11]: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 10.04.17 21:41
Оценка:
Здравствуйте, ·, Вы писали:


·>Бред, дело не в рекурсии, а в алгоритме. Без рекурсии тоже можно тупой алгоритм написать. А вот рекурсия без "промежуточных" результатов:

·>
·>int fib(int term, int val = 1, int prev = 0)
·>{
·> if(term == 0) return prev;
·> if(term == 1) return val;
·> return fib(term - 1, val+prev, val);
·>}
·>


Да, как раз то что я просил сделать. Хорошее решение, с передачей через стек промежуточных результатов (через val).
Re[11]: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 10.04.17 22:08
Оценка:
Здравствуйте, landerhigh, Вы писали:


I>>Какая тут демагогия? Конкретная задача, требуется найти решение. Ваш пример это совсем не то, что я просил.


L>Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.

То что я просил сделать, сделали вот здесь
Автор: ·
Дата: 09.04.17
.

В вашем коде:
return fibonacci(index - 1) + fibonacci(index - 2);

Код, который привёл ".":
return fib(term - 1, val+prev, val);

разницу видно?

I>>Я вам и том и толкую, что рекурсия это лишь иструмент, и применять его надо, где он подходит.

L>Вот только не надо с умным видом декламировать прописные истины. Это не чат детского сада. И это не имеет никакого отношения к изначальной теме.
Я только повторил ваш тезис, с которым я согласился. Все претензии по декламированию только к себе.

I>>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.


L>Ошибку исправил.

После этого примера
Автор: ·
Дата: 09.04.17
, пожалуй соглашусь.
Re[10]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 10.04.17 22:10
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Ну и разница во времени работы между двумя алгоритмами есть.


Что доказывает, что при должном рвении все, что угодно можно сделать через одно место

А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.
www.blinnov.com
Re[12]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 10.04.17 22:25
Оценка:
Здравствуйте, Iso12, Вы писали:

L>>Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.

I>То что я просил сделать, сделали вот здесь
Автор: ·
Дата: 09.04.17
.


Мне было лень ровно это же писать, ибо идея лежит насколько на поверхности, что даже дуб вроде меня ее видит как само собой разумеющееся.

I>В вашем коде:

I>
I>return fibonacci(index - 1) + fibonacci(index - 2);
I>


Это не мой код, а классика шаблонного метапрограммирования. Еще раз, там присутствует мемоизация промежуточных результатов (достается "бесплатно" с точки зрения расхода времени программиста), то есть промежуточные результаты считаются ровно один раз. Небольшой такой нюанс.

I>>>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.

L>>Ошибку исправил.
I>После этого примера
Автор: ·
Дата: 09.04.17
, пожалуй соглашусь.


Числа Фибоначчи — просто такой странный пример, когда определение понятия является определениеам алгоритма, который можно один-в-один перенести в реализацию и оно даже будет работать. Но определение не обязано быть ни алгоритмом, ни оптимальным алгоритмом.
www.blinnov.com
Re[13]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 11.04.17 19:24
Оценка:
Здравствуйте, samius, Вы писали:


S>А разве есть другие?


В смысле? Возможны ли алгоритмы, где нельзя tail-call?
В моем примере SumRecursiveSimple: рекурсивный, но у него рекурсивный вызов — не последнее действие. Как тут tail-call делать?
Re[11]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 11.04.17 20:34
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Что доказывает, что при должном рвении все, что угодно можно сделать через одно место


Само собой, это ничего не доказывает.

Например, samius делал утверждение о tail-оптимизации и в подтверждение кинул код с результатами. Можно увидеть цифру и проверить ее самому.
И именно поэтому это что-то доказывает.

А фраза "все, что угодно можно сделать через одно место" — это вода

В моем примере используется стандартный контейнер из широко используемого фреймворка.
Выбранная задача проще некуда.
Реализации тоже проще некуда.

Буду рад хоть какому-то подтверждению указанных слов.
Пересмотрел код, вроде как для данной платформы улучшать там нечего

L>А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.


Так ждем

Заодно посмотрим, что имеется ввиду под "полноценным деревом" и чем оно полноценнее двусвязаного списка(который частный случай дерева).
Сначала можно рекурсивно, а потом, так и быть, итеративно.
И даже больше! Можно сначала итеративно, а потом рекурсивно! :D
Re[12]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 11.04.17 21:20
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Само собой, это ничего не доказывает.


Да нет, как раз доказывает. Что при должном рвении и черное можно белым назвать.

SL>Например, samius делал утверждение о tail-оптимизации и в подтверждение кинул код с результатами. Можно увидеть цифру и проверить ее самому.

SL>И именно поэтому это что-то доказывает.

SL>А фраза "все, что угодно можно сделать через одно место" — это вода


Нет, это констатация приведенного "примера", в котором применение рекурсии как минимум бессмысленно.

SL>В моем примере используется стандартный контейнер из широко используемого фреймворка.

SL>Выбранная задача проще некуда.

И бессмысленнее тоже некуда

SL>Буду рад хоть какому-то подтверждению указанных слов.


Каких именно?

L>>А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.

SL>Так ждем

Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках).

SL>Заодно посмотрим, что имеется ввиду под "полноценным деревом" и чем оно полноценнее двусвязаного списка(который частный случай дерева).


Да, а змея — это частный случай крокодила.
www.blinnov.com
Re[14]: Вопросы на собеседовании (в очередной раз)
От: samius Япония http://sams-tricks.blogspot.com
Дата: 12.04.17 06:33
Оценка: +1
Здравствуйте, StatujaLeha, Вы писали:

SL>Здравствуйте, samius, Вы писали:



S>>А разве есть другие?


SL>В смысле? Возможны ли алгоритмы, где нельзя tail-call?

Угу
SL>В моем примере SumRecursiveSimple: рекурсивный, но у него рекурсивный вызов — не последнее действие. Как тут tail-call делать?
SumRecursiveSimple — это не алгоритм, а частная реализация. Алгоритмом здесь является что-то вроде "значение каждого элемента списка прибавить к результирующей сумме". Таким образом, SumRecursiveSimple, SumRecursiveAcc, ... ForeachSum, AggregateSum, ParallelForSum — формы записи одного алгоритма. Способы обхода и итерирования — специфичные особенности каждой реализации. И среди всех способов записи обязательно (на сколько я понимаю) найдется рекурсивная с потенциальной возможностью tail-call оптимизации. В данном случае такой является SumRecursiveAcc.
Re[13]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 12.04.17 21:27
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Да нет, как раз доказывает. Что при должном рвении и черное можно белым назвать.


Черное всегда можно назвать белым. Тут доказательств не надо

Именно поэтому в этой ветке код и выкладывался, чтобы желающие могли у себя запустить и сравнить цифры.
А цифры они ни белые, ни черные.

L>Нет, это констатация приведенного "примера", в котором применение рекурсии как минимум бессмысленно.


Я напомню. По результатам испытаний они одинаковы, по 17 ms: http://rsdn.org/forum/job/6753349.1
Автор: samius
Дата: 10.04.17

Так что хватит уже воду бездоказательно лить. "как минимум бессмысленно"... железный аргумент.
Конкретно эти две реализации — одна не лучше и не хуже другой.

И второе.
Тут я совсем в непонятках.
Сообщение http://rsdn.org/forum/job/6750431.1
Автор: landerhigh
Дата: 07.04.17
: "Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией."
А тут уже пишется, что в моем примере рекурсия бессмысленна. Выходит, что итерация ок
Т.е. ты в блокнотике уже записал мою итеративную реализацию обхода LinkedList<int>?

L>И бессмысленнее тоже некуда


Хороший подход: нечего возразить по существу, назови задачу бессмысленной.


SL>>Буду рад хоть какому-то подтверждению указанных слов.


L>Каких именно?


1. Было написано, что в моем исходном примере разница в производительности объясняется тем, "что при должном рвении все, что угодно можно сделать через одно место".
В примере кода мало. Думаю, не составит труда сделать все через "правильное место". Верно же?
2. Было предложение "попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно."
Кода как не было, так и нет
Время идет, а мы так и не узнали, что такое "полноценное дерево" и на сколько оно полноценнее LinkedList<int>.

L>Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках).


Код кинешь?

У тебя в подписи ссылка на сайт www.blinnov.com
Статьи с тегом ".Net" там есть. Я же правильно полагаю, что можно ожидать от автора этого сайта владения навыками разработки на платформе .Net?

L>Да, а змея — это частный случай крокодила.


Да ради бога! Мне не жалко
Re[14]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират  
Дата: 12.04.17 22:03
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Я напомню. По результатам испытаний они одинаковы, по 17 ms: http://rsdn.org/forum/job/6753349.1
Автор: samius
Дата: 10.04.17

SL>Так что хватит уже воду бездоказательно лить. "как минимум бессмысленно"... железный аргумент.
SL>Конкретно эти две реализации — одна не лучше и не хуже другой.

Одна таки хуже. Почему, сам догадаешься?

SL>Сообщение http://rsdn.org/forum/job/6750431.1
Автор: landerhigh
Дата: 07.04.17
: "Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией."

SL>А тут уже пишется, что в моем примере рекурсия бессмысленна. Выходит, что итерация ок
SL>Т.е. ты в блокнотике уже записал мою итеративную реализацию обхода LinkedList<int>?

Записал, конечно. Только в другой блокнотик.

L>>И бессмысленнее тоже некуда

SL>Хороший подход: нечего возразить по существу, назови задачу бессмысленной.

По существу — рекурсивное сложение элементов списка как минимум бессмысленно. А как максимум <догадаться факультативно>.

L>>Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках).

SL>Код кинешь?

Берешь первый попавшийся стек протокола, основанного на ASN.1, смотришь. А троллям я не подаю. С аргументом "список — тоже дерево" спорить сложно.
www.blinnov.com
Re[15]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 13.04.17 18:28
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Одна таки хуже. Почему, сам догадаешься?


Пожалуй, я останусь при своем мнении: они одинаковы.

L>По существу — рекурсивное сложение элементов списка как минимум бессмысленно. А как максимум <догадаться факультативно>.


Есть задача: вернуть сумму чисел из списка.
Есть две реализации алгоритма, которые работают за одинаковое время. Размер кода сопоставим.
Не вижу ни одной причины отдавать предпочтение какому-либо варианту.

L>Берешь первый попавшийся стек протокола, основанного на ASN.1, смотришь.


Так твое предложение, возьми и реализуй Чего на других спихивать свои "гениальные задумки"?

L>А троллям я не подаю.


Подавать мне не надо. Да тебе пока и нечего

L>С аргументом "список — тоже дерево" спорить сложно.


Это не аргумент. Это факт.
А пример работы с "полноценным" деревом ты предложил реализовать, но почему-то сам не стал.
Похоже, так мы и не узнаем, что же это за "полноценное" дерево... И действительно ли оно "полноценнее" обычного двусвязного списка.

PS А за предложение огромное спасибо! Даже не знаю, чтобы я без него делал
Re: Вопросы на собеседовании (в очередной раз)
От: borya_ilin  
Дата: 14.04.17 08:31
Оценка:
числа сравнивать так:
if (fabs(a - b) <= DBL_EPSILON * fmax(fabs(a), fabs(b))) {
  // будем считать равны
}

суммировать алгоритмом Кэхэна

про рекурсию не знаю какие там проблемы кроме стека
Re[2]: Вопросы на собеседовании (в очередной раз)
От: chaotic-kotik  
Дата: 22.04.17 07:21
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно.

L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью

Он хотел услышать о многоэтажных стектрейсах в, казлаось бы, линейном коде.

L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял".

L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
L>Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.

Тут задача явно на умение считать погрешности вычислений. Это примерно как считать сложности алгоритмов, но только для погрешностей. Я думаю тут просто какая-нибудь специфическая вакансия, для которой это нужно понимать. Тут нужно сложить числа в массиве и получить 2 числа, результат и погрешность (которая зависит от данных), а потом уже сравнивать.
Re[13]: Вопросы на собеседовании (в очередной раз)
От: DreamMaker  
Дата: 24.04.17 05:29
Оценка:
Здравствуйте, samius, Вы писали:

SL>>Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.

S>А разве есть другие?


разумеется есть.
попробуйте запрограммировать, например, такую незатейливую целочисленную функцию:

A(m,n) =
n+1, если m==0
A(m-1, 1), если m>0, n==0
A(m-1, A(m,n-1)), если m>0, n>0

...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут


нормальный вопрос для собеседования — что это за функция? для джедаев: таки посчитать А(4,4)
In P=NP we trust.
Re[14]: Вопросы на собеседовании (в очередной раз)
От: samius Япония http://sams-tricks.blogspot.com
Дата: 24.04.17 07:24
Оценка:
Здравствуйте, DreamMaker, Вы писали:

DM>Здравствуйте, samius, Вы писали:


SL>>>Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.

S>>А разве есть другие?


DM>разумеется есть.

Раз есть, так где же они?

DM>попробуйте запрограммировать, например, такую незатейливую целочисленную функцию:


DM>A(m,n) =

DM> n+1, если m==0
DM> A(m-1, 1), если m>0, n==0
DM> A(m-1, A(m,n-1)), если m>0, n>0
Попробовал

let rec A m n cont =
    match m, n with
    | 0, _-> n + 1 |> cont
    | _, 0 when m > 0 -> A (m-1) 1 cont
    | _, _ when m > 0 && n > 0 ->
        A m (n-1) (fun x -> A (m-1) x cont)
    | _, _ -> failwith ""


DM>...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут

треснуть вряд ли им грозит. tail-call стек не жрет. Но времени таки жалко.
А с вас алгоритм, не сводящийся к tail-call.
Re[15]: Вопросы на собеседовании (в очередной раз)
От: DreamMaker  
Дата: 24.04.17 13:57
Оценка: -1
Здравствуйте, samius, Вы писали:

DM>>разумеется есть.

S>Раз есть, так где же они?

в учебниках по CS. классический пример я привел.

S>Попробовал


если б это было собеседование, то вы его провалили.


DM>>...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут

S>треснуть вряд ли им грозит. tail-call стек не жрет. Но времени таки жалко.

ну-ну..

приведенная ф-ция не является примитивно рекурсивной со всеми вытекающими отсюда следствиями.
ее не получится сделать хвостовой (с константной памятью, разумеется).
и А(4,4) посчитать в лоб тоже не получится. потому как битиков в этом незатейлевом числе больше чем элементарных частиц во вселенной.
In P=NP we trust.
Re[16]: Вопросы на собеседовании (в очередной раз)
От: samius Япония http://sams-tricks.blogspot.com
Дата: 24.04.17 15:02
Оценка:
Здравствуйте, DreamMaker, Вы писали:

DM>Здравствуйте, samius, Вы писали:


DM>>>разумеется есть.

S>>Раз есть, так где же они?

DM>в учебниках по CS. классический пример я привел.

А я привел классический контрпример.

S>>Попробовал


DM>если б это было собеседование, то вы его провалили.

Конечно. Ведь я сделал то, в чем собеседующий уверен что такое сделать нельзя.


DM>>>...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут

S>>треснуть вряд ли им грозит. tail-call стек не жрет. Но времени таки жалко.

DM>ну-ну..


DM>приведенная ф-ция не является примитивно рекурсивной со всеми вытекающими отсюда следствиями.

DM>ее не получится сделать хвостовой (с константной памятью, разумеется).
Разумеется, условие про константную память вы упомянули после того, как я свел функцию к tail-call.

DM>и А(4,4) посчитать в лоб тоже не получится. потому как битиков в этом незатейлевом числе больше чем элементарных частиц во вселенной.

Ну так а тут никто и не говорил что tail-call посчитает все что даже нельзя посчитать.
Re[17]: Вопросы на собеседовании (в очередной раз)
От: DreamMaker  
Дата: 26.04.17 13:39
Оценка:
Здравствуйте, samius, Вы писали:


DM>>в учебниках по CS. классический пример я привел.

S>А я привел классический контрпример.

только он неверный

читайте учебники
In P=NP we trust.
Re[18]: Вопросы на собеседовании (в очередной раз)
От: samius Япония http://sams-tricks.blogspot.com
Дата: 26.04.17 14:42
Оценка:
Здравствуйте, DreamMaker, Вы писали:

DM>Здравствуйте, samius, Вы писали:



DM>>>в учебниках по CS. классический пример я привел.

S>>А я привел классический контрпример.

DM>только он неверный

В чем неверный?

DM>читайте учебники

Тут вилка. Либо вы сами что-то не то поняли в учебнике, тогда читайте снова.
Либо учебник отвергает возможность построения SSA формы, используемой компиляторами. Тогда такой учебник вряд ли достоин внимания в этом вопросе.
В любом случае будет любопытно взглянуть. Не подскажете название?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.