我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
事实上,这些问题更多的是关于面试官与规范、设计、错误处理、边界案例以及为解决方案选择合适的环境等进行斗争,而不是关于实际解决方案。然而::)
这里的函数是围绕封闭的4循环思想编写的。如果函数f只允许落在有符号的32位整数上,那么上面的各种解决方案都将起作用,除了其他人指出的三个输入范围数。minint永远不会满足函数方程,因此如果这是一个输入,我们将引发一个异常。
在这里,我允许Python函数操作并返回元组或整数。任务规范承认这一点,它只指定函数的两个应用程序应该返回一个与原始对象相等的对象,如果它是int32。(我会询问有关规范的更多细节)
这使得我的轨道可以很好且对称,并且可以覆盖所有输入整数(minint除外)。我最初设想的循环是访问半整数值,但我不想陷入舍入错误。因此是元组表示。这是一种将复杂旋转作为元组隐藏的方式,而不使用复杂的算术机制。
注意,在调用之间不需要保留任何状态,但调用者确实需要允许返回值为元组或int。
def f(x) :
if isinstance(x, tuple) :
# return a number.
if x[0] != 0 :
raise ValueError # make sure the tuple is well formed.
else :
return ( -x[1] )
elif isinstance(x, int ) :
if x == int(-2**31 ):
# This value won't satisfy the functional relation in
# signed 2s complement 32 bit integers.
raise ValueError
else :
# send this integer to a tuple (representing ix)
return( (0,x) )
else :
# not an int or a tuple
raise TypeError
因此,将f应用于37两次得到-37,反之亦然:
>>> x = 37
>>> x = f(x)
>>> x
(0, 37)
>>> x = f(x)
>>> x
-37
>>> x = f(x)
>>> x
(0, -37)
>>> x = f(x)
>>> x
37
将f两次应用于零得到零:
>>> x=0
>>> x = f(x)
>>> x
(0, 0)
>>> x = f(x)
>>> x
0
我们处理一个问题没有解决方案的情况(在int32中):
>>> x = int( -2**31 )
>>> x = f(x)
Traceback (most recent call last):
File "<pyshell#110>", line 1, in <module>
x = f(x)
File "<pyshell#33>", line 13, in f
raise ValueError
ValueError
如果你认为函数通过模拟乘以i的90度旋转打破了“无复杂算术”规则,我们可以通过扭曲旋转来改变这一点。这里元组表示半整数,而不是复数。如果你在数字线上追踪轨道,你会得到满足给定函数关系的非相交循环。
f2: n -> (2 abs(n) +1, 2 sign( n) ) if n is int32, and not minint.
f2: (x, y) -> sign(y) * (x-1) /2 (provided y is \pm 2 and x is not more than 2maxint+1
练习:通过修改f来实现这个f2。还有其他解决方案,例如,中间着落点是有理数而不是半整数。有一个分数模块可能很有用。你需要一个符号函数。
这个练习让我真正体会到了动态类型语言的乐趣。我在C中看不到这样的解决方案。
其他回答
你没说他们期望什么样的语言。。。这是一个静态解决方案(Haskell)。这基本上是在搞乱两个最重要的比特:
f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
| otherwise = complementBit x 30
在动态语言(Python)中要容易得多。只需检查参数是否为数字X,并返回返回-X的lambda:
def f(x):
if isinstance(x,int):
return (lambda: -x)
else:
return x()
根据微软/谷歌的面试官通常在面试中提出的问题,我认为提问者指的是一种创新、轻量级、简单的解决方案,它将使用按位操作,而不是那些复杂的高级答案。
灵感来自@eipipuz的回答,我编写了这个C++函数(但没有运行它):
int32_t f(int32_t n){
int32_t temp = n & 00111111111111111111111111111111;
x = n >> 30;
x++;
x = x << 30;
return x | temp;
}
它将n的最左边的两位存储在x中,将x加1,然后再次将其替换为n的最左侧的两位。
如果我们继续以另一个f(n)作为参数n运行f(n,则最左边的两个位将如下旋转:
00 --> 01 --> 10 --> 11 --> 00 ...
请注意,最右边的30位不变。8位整数示例:
示例1:
>f(00001111)=01001111>f(01001111)=10001111[这是原始值的负值,00001111]
示例2:
>f(11101010)=00101010>f(00101010)=01101010[这是原始值11101010的负值]
PHP,不使用全局变量:
function f($num) {
static $mem;
$answer = $num-$mem;
if ($mem == 0) {
$mem = $num*2;
} else {
$mem = 0;
}
return $answer;
}
适用于整数、浮点数和数字字符串!
只是意识到这会做一些不必要的工作,但是,不管怎样
以下情况如何:
int f (int n)
{
static bool pass = false;
pass = !pass;
return pass? n : -n;
}
使用复数,您可以有效地将否定数字的任务分为两个步骤:
将n乘以i,得到n*i,n逆时针旋转90°再乘以i,得到-n
最棒的是,您不需要任何特殊的处理代码。只要乘以i就可以了。
但不允许使用复数。因此,您必须使用部分数据范围创建自己的虚拟轴。由于需要的虚(中间)值与初始值一样多,因此只剩下一半的数据范围。
我试图在下图中显示这一点,假设有符号的8位数据。您必须将其缩放为32位整数。初始n的允许范围为-64到+63。下面是函数对正n的作用:
如果n在0..63(初始范围)内,函数调用将添加64,将n映射到范围64..127(中间范围)如果n在64..127(中间范围)内,则函数从64中减去n,将n映射到范围0..-63
对于负n,函数使用中间范围-65..-128。