我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
类似于python中的函数重载解决方案:
def f(number):
if type(number) != type([]):
return [].append(number)
else:
return -1*number[0]
备选方案:静态数据成员
其他回答
这也是一个解决方案(但我们稍微改变了一下规则):
def f(n):
if isinstance(n,int):
return str(n)
else:
return -int(n)
这个Perl解决方案适用于整数、浮点数和字符串。
sub f {
my $n = shift;
return ref($n) ? -$$n : \$n;
}
尝试一些测试数据。
print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';
输出:
-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar
我参加这个聚会迟到了,现在可能是墓地了。但我有两个贡献,灵感来自viraptor先前使用lambda的Python答案。读者可能认为该解决方案仅在非类型化语言中可行,而在类型化语言中将需要一些明确的额外标记。
但下面是Haskell中的解决方案1(我不是Haskell专家)。它有点作弊,因为从技术上讲,两个f是两个不同的实现。(一个f::Int->()->Int,另一个f::(()->Int)->Int)
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}
module Main where
class Tran σ τ | σ -> τ where
tran :: σ -> τ
instance Tran Int (() -> Int) where
tran n = \_ -> (-n)
instance Tran (() -> Int) Int where
tran g = g ()
f :: Tran σ τ => σ -> τ
f = tran
main :: IO ()
main = do
print $ f (f (42 :: Int)) -- --> -42
print $ f (f (0 :: Int)) -- --> 0
print $ f (f (-69 :: Int)) -- --> 69
接下来是Typed Racket中的解决方案2。这一个满足了最大可能域的属性,因为Racket中的Number最多包含复数:
#lang typed/racket
(: f (case->
[Number -> (-> Number)]
[(-> Number) -> Number]))
(define (f x)
(if (number? x) (λ () (- x)) (x)))
(f (f 42)) ; --> -42
(f (f 0)) ; --> 0
(f (f -69)) ; --> 69
(f (f 3/4)) ; --> -3/4
(f (f 8+7i)) ; --> -8-7i
创建许多解的一种方法是注意,如果我们将整数划分为两个集合S和R
那么我们可以如下创建f:
如果x在R中,则f(x)=g(x)
如果x在S中,则f(x)=-invg(x)
其中invg(g(x))=x,所以invg是g的逆函数。
上面提到的第一个解决方案是分区R=偶数,R=奇数,g(x)=x+1。
我们可以取任意两个无限集合T,P s.T T+U=整数集合,取s=T+(-T),R=U+(-U)。
然后-S=S和-R=R通过它们的定义,我们可以将g取为从S到R的任何1-1对应关系,这必须存在,因为这两个集合都是无限的和可数的。
因此,这将为我们提供许多解决方案,但并非所有解决方案都可以编程,因为它们不会被有限地定义。
例如:
R=可被3整除的数字,S=不可被3除的数字。
然后我们取g(6r)=3r+1,g(6r+3)=3r+2。
适用于n=[0..2^31-1]
int f(int n) {
if (n & (1 << 31)) // highest bit set?
return -(n & ~(1 << 31)); // return negative of original n
else
return n | (1 << 31); // return n with highest bit set
}