Вопросы на собеседовании (в очередной раз)
От: Marty Пират  
Дата: 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 я не понял?

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

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

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

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

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

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


модуль забыл :P
Re: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират http://www.blinnov.com
Дата: 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 Пират  
Дата: 06.04.17 22:46
Оценка:
Здравствуйте, std.denis, Вы писали:

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


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





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


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


Можно поподробнее?
Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался
Вам как-бы показали сцыкливое мурло российской оппозиции — вот оно
Автор: Министр Промышленности
Дата: 17.10.19
!
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 Пират http://www.blinnov.com
Дата: 06.04.17 22:55
Оценка: +5
Здравствуйте, pilgrim_, Вы писали:

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

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

Случается, что собеседователи ожидают, что ответ будет совпадать с вычитанным в учебнике.
www.blinnov.com
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират  
Дата: 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 хранить?
Вам как-бы показали сцыкливое мурло российской оппозиции — вот оно
Автор: Министр Промышленности
Дата: 17.10.19
!
Re[3]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират http://www.blinnov.com
Дата: 06.04.17 22:59
Оценка:
Здравствуйте, ononim, Вы писали:

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


Для начала нужно все же с физическим смыслом величин определиться, чтобы не решать несуществующую задачу. А в принципе, наверное, так и поступают. Мне не приходилось это сакральное знание применять на практике.
www.blinnov.com
Re[3]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират http://www.blinnov.com
Дата: 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 Пират  
Дата: 06.04.17 23:10
Оценка:
Здравствуйте, std.denis, Вы писали:

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

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

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


Обычный модуль — это из разряда того, что просто подразумевается Я думаю, копать надо глубже
Вам как-бы показали сцыкливое мурло российской оппозиции — вот оно
Автор: Министр Промышленности
Дата: 17.10.19
!
Re[4]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират  
Дата: 06.04.17 23:15
Оценка: +1
Здравствуйте, landerhigh, Вы писали:

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


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


А-ха-ха. Кто о чем, а ты о юнит тестах. А я — о сроках. Жизнь научила, что лучше срок поставить долгий, а потом перевыполнить и сделать быстрее, чем малый, а потом оправдываться о его несоблюдении
Вам как-бы показали сцыкливое мурло российской оппозиции — вот оно
Автор: Министр Промышленности
Дата: 17.10.19
!
Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират  
Дата: 06.04.17 23:20
Оценка:
Здравствуйте, cserg, Вы писали:

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

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

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


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

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

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


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

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

Денег вроде дают. Не так что бы очень, но некоторые перспективы есть.
Вам как-бы показали сцыкливое мурло российской оппозиции — вот оно
Автор: Министр Промышленности
Дата: 17.10.19
!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.