我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这里有一个我从未见过的变体。因为这是ruby,所以32位整数的东西就不见了(当然可以添加检查)。
def f(n)
case n
when Integer
proc { n * -1 }
when Proc
n.call
else
raise "Invalid input #{n.class} #{n.inspect}"
end
end
(-10..10).each { |num|
puts "#{num}: #{f(f(num))}"
}
其他回答
我认为这些问题的答案最好用图表直观地解释。当我们忽略零时,我们可以将整数分成4个数的小集合:
1 → 2 3 → 4 5 → 6
↑ ↓ ↑ ↓ ↑ ↓ ...
-2 ← -1 -4 ← -3 -6 ← -5
这很容易翻译成代码。注意,偶数改变符号,奇数增加或减少1。在C#中,它看起来像这样:
public static int f(int x)
{
if(x == 0)
return 0;
if(x > 0)
return (x % 2 == 0) ? -x+1 : x+1;
// we know x is negative at this point
return (x % 2 == 0) ? -x-1 : x-1;
}
当然,您可以通过使用巧妙的技巧来缩短此方法,但我认为这段代码最好地解释了它本身。
然后是范围。32位整数的范围从-2^31到2^31-1。数字2^31-1、-2^31-1和-2^31超出了f(x)的范围,因为缺少数字2^31。
在awk中,由于几乎没有任何信息被传递,因此必须求助于允许将状态信息作为函数返回的一部分传递的方法,而不会危及传递内容的可用性:
jot - -5 5 | mawk 'function _(__,___) {
return (__~(___=" ")) \
\
? substr("",sub("^[ ]?[+- ]*",\
substr(" -",__~__,index("_"___,___)-\
(__~"[-]")),__))\
(__~"[-]"?"":___)__\
: (+__<-__?___:(___)___)__
} BEGIN { CONVFMT=OFMT="%.17g"
} {
print "orig", +(__=$(__<__))<-__?__:" "__,
"f(n)....", _(__),_(_(__)),_(_(_(__))),
_(_(_(_(__)))), _(_(_(_(_(__)))))
}' |gcat -n | lgp3 5
1 orig -5 f(n).... -5 5 -5 5 -5
2 orig -4 f(n).... -4 4 -4 4 -4
3 orig -3 f(n).... -3 3 -3 3 -3
4 orig -2 f(n).... -2 2 -2 2 -2
5 orig -1 f(n).... -1 1 -1 1 -1
6 orig 0 f(n).... 0 -0 0 -0 0
7 orig 1 f(n).... 1 -1 1 -1 1
8 orig 2 f(n).... 2 -2 2 -2 2
9 orig 3 f(n).... 3 -3 3 -3 3
10 orig 4 f(n).... 4 -4 4 -4 4
11 orig 5 f(n).... 5 -5 5 -5 5
因此,这样做的限制是,只有整数或浮点值已经是字符串格式,可以在没有风险的情况下使用,因为额外的ASCII空间\040作为状态信息
这种方法的优点是
它愿意为您提供“负零”,对于绝对值小于2^53的整数,简单地添加加号,即+f(f(_))函数调用本身将具有隐式代表您完成类型铸造,结果值将再次为数字对于大整数,只需减去()任何前导空格轻松处理大整数,而不会丢失精度从类型转换为双精度浮点
`
1 orig -99999999999999999999999999999999
f(n)....
-99999999999999999999999999999999
99999999999999999999999999999999
-99999999999999999999999999999999
99999999999999999999999999999999
-99999999999999999999999999999999
2 orig -1239999999999999999999999999999
f(n).... -1239999999999999999999999999999
1239999999999999999999999999999
-1239999999999999999999999999999
1239999999999999999999999999999
-1239999999999999999999999999999`
x86 asm(AT&T风格):
; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
testl %edi, %edi
je .zero
movl %edi, %eax
movl $1, %ecx
movl %edi, %edx
andl $1, %eax
addl %eax, %eax
subl %eax, %ecx
xorl %eax, %eax
testl %edi, %edi
setg %al
shrl $31, %edx
subl %edx, %eax
imull %ecx, %eax
subl %eax, %edi
movl %edi, %eax
imull %ecx, %eax
.zero:
xorl %eax, %eax
ret
代码已检查,所有可能的32位整数都已通过,错误为-2147483647(下溢)。
#include <cmath>
int f(int n)
{
static int count = 0;
return ::cos(M_PI * count++) * n;
}
根据微软/谷歌的面试官通常在面试中提出的问题,我认为提问者指的是一种创新、轻量级、简单的解决方案,它将使用按位操作,而不是那些复杂的高级答案。
灵感来自@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的负值]