Это вопрос, который мне задавали в интервью:
Реализуйте функцию, которая получает целое число n и выполняет следующие действия:
1. если n равно 3 -> вернуть 7.
2.иначе, если n равно 7 -> вернуть 3.
3. в противном случае вернуть любое число, которое вам нравится (неопределенное поведение).
Также опишите, какова длительность выполнения и сложность пространства каждого способа.
Итак, сначала я дал тривиальный способ использования оператора if-else и сказал, что это O(1)
сложность времени выполнения + пространства.Затем интервьюер сказал: «Что делать, если вы не можете использовать операторы if (в том числе переключатели и другие сходства операторов)?»
Поэтому я предложил использовать побитовые операции: return n^=4
.Сказал, что это O(1)
время выполнения + сложность пространства.Тогда интервьюер сказал: «Что делать, если вы не можете использовать побитовые операции?»
Поэтому я предложил использовать массив, подобный следующему:
int mem[8] = {-1, -1, -1, 7, -1, -1, -1, 3};
return mem[n];
Сказал, что это O(1)
время выполнения + сложность пространства, как бы это ни было неэффективно, если вместо этого у нас есть большие числа3
и 7
.
Тогда интервьюер сказал: «Что делать, если вы не можете использовать массивы?»- и тут я застрял.
Кажется, есть четвертый путь ... есть предложения?