Вопрос на собеседовании
От: shrecher  
Дата: 18.08.11 17:04
Оценка:
Как такой вопрос на собеседовании, был задан на позиции C++ разработчика?

Написать код на доске для функции:


string Power( int X, short Y) // вернуть строчное представление результата X в степени Y 
{



}
Re: Вопрос на собеседовании
От: Abyx Россия  
Дата: 18.08.11 17:16
Оценка:
Здравствуйте, shrecher, Вы писали:

string Power( int X, short Y) // вернуть строчное представление результата X в степени Y 
{
   return lexical_cast<string>(pow(X, Y));
}


в чем проблема?
In Zen We Trust
Re[2]: Вопрос на собеседовании
От: ilnar Россия  
Дата: 18.08.11 17:21
Оценка:
Здравствуйте, Abyx, Вы писали:

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


A>
A>string Power( int X, short Y) // вернуть строчное представление результата X в степени Y 
A>{
A>   return lexical_cast<string>(pow(X, Y));
A>}
A>


A>в чем проблема?


при такой реализации в ограниченном множестве X,Y
Re[3]: Вопрос на собеседовании
От: Abyx Россия  
Дата: 18.08.11 17:25
Оценка:
Здравствуйте, ilnar, Вы писали:

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


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


A>>
A>>string Power( int X, short Y) // вернуть строчное представление результата X в степени Y 
A>>{
A>>   return lexical_cast<string>(pow(X, Y));
A>>}
A>>


A>>в чем проблема?


I>при такой реализации в ограниченном множестве X,Y


так оно в double конвертируется
а если надо поддержать большие числа, заменяем pow() на some_bigint_lib_pow()
In Zen We Trust
Re[2]: Вопрос на собеседовании
От: shrecher  
Дата: 18.08.11 17:26
Оценка:
Здравствуйте, Abyx, Вы писали:

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


A>
A>string Power( int X, short Y) // вернуть строчное представление результата X в степени Y 
A>{
A>   return lexical_cast<string>(pow(X, Y));
A>}
A>


A>в чем проблема?


Н-да. pow вернет double, что есть максимальное число в нем — 1.79769e+308. Очевидно, что если аргументы к примеру, X=100000, Y=32000, то результат будет много больше.
Re[3]: Вопрос на собеседовании
От: Abyx Россия  
Дата: 18.08.11 17:31
Оценка:
Здравствуйте, shrecher, Вы писали:

S>Н-да. pow вернет double, что есть максимальное число в нем — 1.79769e+308. Очевидно, что если аргументы к примеру, X=100000, Y=32000, то результат будет много больше.


ну будет +inf, ну и что?
вы умножаете int32*int32 и не думаете о том что оно может переполнится
In Zen We Trust
Re[4]: Вопрос на собеседовании
От: shrecher  
Дата: 18.08.11 17:36
Оценка:
Здравствуйте, Abyx, Вы писали:

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


S>>Н-да. pow вернет double, что есть максимальное число в нем — 1.79769e+308. Очевидно, что если аргументы к примеру, X=100000, Y=32000, то результат будет много больше.


A>ну будет +inf, ну и что?

A>вы умножаете int32*int32 и не думаете о том что оно может переполнится

авторы вопроса хотят для всех всех возможных значений int и short, т.е. два миллиарда в степени тридцать две тысячи. Длинная такая строка.
Re: Вопрос на собеседовании
От: ZOI4  
Дата: 18.08.11 17:44
Оценка:
Здравствуйте, shrecher, Вы писали:

S>Как такой вопрос на собеседовании, был задан на позиции C++ разработчика?


Зависит от того сколько времени дают на решение.
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Re[3]: Вопрос на собеседовании
От: EM Великобритания  
Дата: 18.08.11 17:46
Оценка: +3
Здравствуйте, shrecher, Вы писали:

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


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


A>>
A>>string Power( int X, short Y) // вернуть строчное представление результата X в степени Y 
A>>{
A>>   return lexical_cast<string>(pow(X, Y));
A>>}
A>>


A>>в чем проблема?


S>Н-да. pow вернет double, что есть максимальное число в нем — 1.79769e+308. Очевидно, что если аргументы к примеру, X=100000, Y=32000, то результат будет много больше.



Очевидно что во Вселенной где нам выпало счастье жить, атомов 10^80 Что как бы намекает, что 10^300 на реальной задаче не переполнится
Опыт — это такая вещь, которая появляется сразу после того, как была нужна...
Re[2]: Вопрос на собеседовании
От: shrecher  
Дата: 18.08.11 17:52
Оценка:
Здравствуйте, ZOI4, Вы писали:

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


S>>Как такой вопрос на собеседовании, был задан на позиции C++ разработчика?


ZOI>Зависит от того сколько времени дают на решение.


Минут 15-20. Можно, не все решение, но хотя бы определиться со структурами данных и написать основу алгоритма.
Re[3]: Вопрос на собеседовании
От: ZOI4  
Дата: 18.08.11 18:04
Оценка: :)
Здравствуйте, shrecher,

Если в лоб, то на пятой минуте пришла в голову идея просто перемножать Х друг на друга по очереди Y раз, а промежуточные результаты запихивать в строку%))) Но пожалуй еще подумаю%)
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Re: Вопрос на собеседовании
От: ZOI4  
Дата: 18.08.11 18:19
Оценка:
Здравствуйте, shrecher, Вы писали:

В общем, на вскидку надо определить сколько раз Х можно умножить на Х, чтобы результат помещался в double, например, если погрешности пофик, или в _int64, если точность важна. И потом считать сколько таких произведений получится при проходе X*X Y раз, плюс последнее перемножение Х-ов, которое может быть меньше. В общем:
1. Сколько раз X*X*...*X, чтоб _int64 не переполнился.
2. Считаем сколько таких произведений требуется, чтобы Х на Х умножился до около Y раз, с мешьшей стороны.
3. Домножаем оставшееся.
4. Переводим это дело в строку, вручную умножая наше произведение из п.1 вручную от младшего разряда к старшему на получившееся число оных, не забывая приплюсовать остаток из п.3.

В общем как-то так, если непонятно, то сорри, вечер после рабочего дня — моска уже нет.
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Re[2]: Вопрос на собеседовании
От: shrecher  
Дата: 18.08.11 18:29
Оценка:
Здравствуйте, ZOI4, Вы писали:

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


ZOI>В общем как-то так, если непонятно, то сорри, вечер после рабочего дня — моска уже нет.


Возможно это и так. Меня больше интересует адекватность этого вопроса. Его задали моему знакомому и мы тут спорили о смысле спрашивать такое. За много лет прогерской жизни я ни разу не писал ничего подобного. Как-то лавки стали спрашивать что-то очень мудреное, видать разворот строки уже всем надоел
Re[3]: Вопрос на собеседовании
От: vb-develop  
Дата: 18.08.11 18:42
Оценка:
Здравствуйте, shrecher, Вы писали:

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


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


ZOI>>В общем как-то так, если непонятно, то сорри, вечер после рабочего дня — моска уже нет.


S>Возможно это и так. Меня больше интересует адекватность этого вопроса. Его задали моему знакомому и мы тут спорили о смысле спрашивать такое. За много лет прогерской жизни я ни разу не писал ничего подобного. Как-то лавки стали спрашивать что-то очень мудреное, видать разворот строки уже всем надоел


Да это ж школьная задача, реализовать перемножение двух длинных чисел. В тривиальном случае хранишь по одному десятичному разряду в элементе массива, и перемножаешь как на листочке.
Re[3]: Вопрос на собеседовании
От: ZOI4  
Дата: 18.08.11 18:43
Оценка:
Здравствуйте, shrecher, Вы писали:

S>Возможно это и так. Меня больше интересует адекватность этого вопроса. Его задали моему знакомому и мы тут спорили о смысле спрашивать такое. За много лет прогерской жизни я ни разу не писал ничего подобного. Как-то лавки стали спрашивать что-то очень мудреное, видать разворот строки уже всем надоел


Если оценивать как один из вопросов на смекалку, то нормально, имхо. Хотя 15-20 минут мне кажется маловато, все-таки.

ЗЫ Зато виртуальные деструкторы до сих пор не стареют — ходил тут тоже по собеседованиям не так давно — хиты номер один — виртуальные деструкторы и организация контейнеров
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Re[2]: Вопрос на собеседовании
От: ZOI4  
Дата: 18.08.11 18:46
Оценка:
ZOI>1. Сколько раз X*X*...*X, чтоб _int64 не переполнился.
ZOI>2. Считаем сколько таких произведений требуется, чтобы Х на Х умножился до около Y раз, с мешьшей стороны.
ZOI>3. Домножаем оставшееся.
ZOI>4. Переводим это дело в строку, вручную умножая наше произведение из п.1 вручную от младшего разряда к старшему на получившееся число оных, не забывая приплюсовать остаток из п.3.

Да, тут еще похоже еще одного unsigned _int64 не хватит для подсчета произведений из пункта 1. Значит надо вводить еще одно измерение и считать, сколько сумм произведений из пункта 1, поместиться еще в один unsigned _int64

ЗЫ Хы, написал, но не отправил%) Определенно, пора спать%)
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Re[4]: Вопрос на собеседовании
От: _software_engineer_  
Дата: 18.08.11 18:50
Оценка:
Здравствуйте, ZOI4, Вы писали:

ZOI>Здравствуйте, shrecher,


ZOI>Если в лоб, то на пятой минуте пришла в голову идея просто перемножать Х друг на друга по очереди Y раз, а промежуточные результаты запихивать в строку%))) Но пожалуй еще подумаю%)


пробегать каждый бит в Y
если бит == 1, то result *= x;

вне зависимости от бита делать делать X = X * X

X * X можно считать алгоритмом карацубы (это если стоит задача совсем написать велосипед и не пользоваться библиотеками для длинной арифметики)

временную сложность сами посчитайте
Re[5]: Вопрос на собеседовании
От: ZOI4  
Дата: 18.08.11 18:57
Оценка:
Здравствуйте, _software_engineer_, Вы писали:

___>пробегать каждый бит в Y

___>если бит == 1, то result *= x;

___>вне зависимости от бита делать делать X = X * X


Хм, я может чего-то пропустил, но где у вас защита переполнения в result? Основная проблема в ней.
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Re[6]: Вопрос на собеседовании
От: _software_engineer_  
Дата: 18.08.11 19:01
Оценка:
Здравствуйте, ZOI4, Вы писали:

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


___>>пробегать каждый бит в Y

___>>если бит == 1, то result *= x;

___>>вне зависимости от бита делать делать X = X * X


ZOI>Хм, я может чего-то пропустил, но где у вас защита переполнения в result? Основная проблема в ней.


Забыл уточнить — я предлагал это для длинной арифметики
Re: Вопрос на собеседовании
От: мыщъх США http://nezumi-lab.org
Дата: 18.08.11 19:05
Оценка:
Здравствуйте, shrecher, Вы писали:

S>Как такой вопрос на собеседовании, был задан на позиции C++ разработчика?


S>Написать код на доске для функции:



>string Power( int X, short Y) // вернуть строчное представление результата X в степени Y

вызвать скрипт на руби
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.