我在最后一次采访中遇到了一个问题:
Design a function有任何想法吗?f
, such that:f(f(n)) == -nWheren
is a 32 bit signed integer; you can't use complex numbers arithmetic. If you can't design such a function for the whole range of numbers, design it for the largest range possible.
没有找到相关结果
已邀请:
118 个回复
ret
赞同来自:
我会改变2个最重要的位。
正如你所看到的,它只是一个补充,省去了所携带的位。 我是怎么得到答案的?我的第一个想法只是需要对称性。 4转回到我开始的地方。起初我想,这是2位格雷码。然后我认为实际上标准二进制就足够了。xatque
赞同来自:
PHP,不使用全局变量:
使用整数,浮点数和数字字符串! 刚刚意识到这会做一些不必要的工作,但无论如何mex
赞同来自:
Objective-C的 这适用于除“-1”之外的所有数字。 如果你要从使用
int
到使用NSInt
,那么你可以将-1值设置为NULL
,然后将它们第二次转换为+1,但我觉得NSInt
欺骗了提问者的意图。F(N): 当然这可以缩短为一行,但其他人可能无法阅读...... 点击 无论如何,我将BOOLEAN逻辑存储在数字状态为奇数或偶数。
id_aut
赞同来自:
我认为通过使用图表可以最直观地解释这些问题的答案。当我们忽略零时,我们可以用4个小数组来整数:
这很容易转换为代码。请注意,偶数会改变符号,奇数会增加或减少1.在C#中,它看起来像这样: 当然你可以通过巧妙的技巧来缩短这种方法,但我认为这段代码最能解释自己。 然后关于范围。 32位整数的范围从-2 ^ 31到2 ^ 31-1。数字2 ^ 31-1,-2 ^ 31-1和-2 ^ 31落在f(x)的范围之外,因为缺少数字^ 31。eipsum
赞同来自:
JavaScript单线程:
qnobis
赞同来自:
qet
赞同来自:
我承认我会欺骗,但仍然符合要求。这是编程魔法,而不是真正的数学。它适用于整个范围,除了-2 ^ 31。
ueum
赞同来自:
实际上,这些问题更多的是关于看到面试官与规范搏斗,设计,错误处理,边界情况和解决方案的合适环境的选择等,而不是实际的解决方案。但是::) 这里的函数是围绕闭合的4周期思想编写的。如果只允许函数f仅在有符号的32位整数上着陆,那么上面的各种解决方案都将起作用,除了其他人指出的三个输入范围数。 minint将永远不会满足函数方程,因此如果是输入,我们将引发异常。 在这里,我允许我的Python函数操作并返回元组或整数。任务规范承认这一点,它只指定函数的两个应用程序应该返回一个等于原始对象的对象(如果它是int32)。 (我会询问有关规范的更多细节。) 这允许我的轨道很好和对称,并覆盖所有输入整数(minint除外)。我最初设想循环访问半整数值,但我不想纠结舍入错误。因此元组表示。这是一种在不使用复杂算术机制的情况下将复杂旋转隐藏在元组中的方法。 请注意,调用之间不需要保留任何状态,但调用者确实需要允许返回值为元组或int。
所以将f应用于37两次得到-37,反之亦然: 将f两次应用于零得到零: 我们处理问题没有解决方案的一个案例(在int32中): 如果你认为该函数通过模拟乘以i的90度旋转来打破“无复数算术”规则,我们可以通过扭曲旋转来改变它。这里的元组代表半整数,而不是复数。如果跟踪数字线上的轨道,您将获得满足给定函数关系的非交叉循环。 练习:通过修改f来实现这个f2。还有其他解决方案,例如中间着陆点是半整数以外的有理数。有一个可能证明有用的分数模块。你需要一个签名功能。 这个练习确实为我提供了动态类型语言的乐趣。我在C中看不到像这样的解决方案。psequi
赞同来自:
这是一个简短的Python答案:
一般情况 稍微调整一下可以处理我们希望k
自我调用否定输入的情况 - 例如,如果k = 3
,这将意味着g(g(g(n))) = -n
: 这通过将0留在原位并且创建长度为2 * k的循环来工作,使得在任何循环内,n和-n是距离k。具体来说,每个周期看起来像: 或者,为了便于理解,这里是k = 3
的示例周期: 这组循环最大化了将在以零为中心的任何机器类型中工作的输入范围,例如signed int32或signed int64类型。 分析兼容范围 地图x -> f(x)
实际上必须形成长度为2 * k
的循环,其中x = 0
是特殊情况1长度循环,因为-0 = 0.因此,当且仅当输入的范围为1时,k
的问题是可解的(为了补偿) 0)是2 * k的倍数,正负范围是对立的。 对于有符号整数表示,我们始终具有最小负数,在该范围内没有正对应,因此问题在整个范围内变得不可解决。例如,signed char
的范围为[-128,127],因此f(f(-128)) = 128
在给定范围内是不可能的。tquod
赞同来自:
好问题! 我花了大约35秒来思考和写作:
dodit
赞同来自:
没有人说f(x)必须是同一类型。
xsit
赞同来自:
set
赞同来自:
在PHP中
我相信你可以理解这种方法对其他语言的精神。我明确地将其转换回int,以使那些不使用弱类型语言的人更清楚。你必须为某些语言重载函数。 关于这个解决方案的巧妙之处在于无论你是以字符串还是整数开头,并且在返回f(n)时都没有明显改变任何东西。 在我看来,采访者问:“这位候选人是否知道如何标记数据以便稍后进行操作”,并且“这位候选人是否知道如何标记数据,同时最少改变数据呢?”您可以使用双打,字符串或任何其他您想要投射的数据类型来执行此操作。nodit
赞同来自:
创建许多解决方案的一种方法是注意,如果我们将整数划分为两个集合S和R s.t -S = S,-R = R,并且函数g s.t g(R)= S 然后我们可以创建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。
znemo
赞同来自:
一个C函数:
Ideone Link for Testing and Download
et_et
赞同来自:
根据微软/谷歌采访者在采访中经常提出的问题,我认为提问者意味着一种创新的,轻量级的,简单的解决方案,它将使用按位操作,而不是那些复杂的高级答案。 受到@eipipuz答案的启发,我编写了这个C++函数(但没有运行它):
它将n的最左边两位存储在x中,将x加1,然后再将其替换为n的最左边两位。 如果我们继续用另一个f(n)作为参数n运行f(n),最左边的两位将像这样旋转: 请注意,最右边的30位不会改变。 8位整数的示例: 例1:get
赞同来自:
ut_sed
赞同来自:
ket
赞同来自:
C++中的另一种作弊解决方案,运算符重载。
bipsam
赞同来自:
所述问题不要求该函数必须仅接受32位整数,只有n,如给定的,是32位整数。 红宝石:
mest
赞同来自:
使用全局...但是这样?
uaut
赞同来自:
Wolfram Language中的解决方案:
应用: 因为问题没有说明f(n)的价值,f [n]仍然没有评估。nerror
赞同来自:
这里有一个证明,为什么这样的函数不能存在,对于所有数字,如果它不使用额外的信息(除了32位的int): 我们必须有f(0)= 0.(证明:假设f(0)= x。那么f(x)= f(f(0))= - 0 = 0.现在,-x = f(f(x ))= f(0)= x,表示x = 0。) 此外,对于任何
当然另一种选择是不遵守0,并获得我们删除的2个数字作为奖励。 (但这只是一个愚蠢的。)x
和y
,假设f(x) = y
。我们想要f(y) = -x
。和f(f(y)) = -y => f(-x) = -y
。总结一下:如果是f(x) = y
,那么f(-x) = -y
和f(y) = -x
,以及f(-y) = x
。 因此,我们需要将除0之外的所有整数除以4的集合,但是我们有一个奇数个这样的整数;不仅如此,如果我们删除没有正对应的整数,我们仍然有2(mod4)数。 如果我们删除剩下的2个最大数字(通过abs值),我们可以得到函数:but
赞同来自:
类似于函数重载解决方案,在python中:
替代方案:static datamembers
hipsum
赞同来自:
这个想法已被用于其他答案中,但我将其纳入了一行Python:
eet
赞同来自:
f(x)=点(x)在2D笛卡尔坐标系中绕原点逆时针旋转90度。仅假设一个数字x的输入为(x,0),并且提供具有y = 0的输出作为单个数字x。
eut
赞同来自:
好吧,我既不是数学也不是编程问题,但这不是很容易吗?
它使用大小的正负值INT_MIN,INT_MAX进行测试,它似乎有效......如果这是一个问题,可以使线程安全,但它不是任务的一部分。 或许我错过了什么?gcum
赞同来自:
nodio
赞同来自:
C++解决方案;
ut_sit
赞同来自:
感谢C++中的重载:
lsunt
赞同来自:
我还没有看到其他答案,我认为已经彻底讨论了按位技术。 我以为我会在C++中想出一些邪恶的东西,希望这不是一个骗局:
整个ImplicitlyConvertibleToInt
类型和重载是必要的,因为temporaries不能绑定到非const引用。 当然,现在看一下它是否未定义f(n)
是否在-n
之前执行。 对这种程度的邪恶来说,或许更好的解决方案就是:et_et
赞同来自:
简单的Python解决方案可以通过以下事实实现:f(x)应该输出的内容没有限制,只有f(f(x)):
xest
赞同来自:
似乎很容易。
oiusto
赞同来自:
这将适用于非常广泛的数字:
我最初的方法是使用最后一位作为检查位来知道我们在第一次或第二次调用中的位置。基本上,我会在第一次通话后将此位置为1,以表示第一次已经通过的第二次通话。但是,这种方法被第一次通话中最后一位已经到达1的负数击败。 同样的理论适用于大多数负数的倒数第二位。但是,通常发生的是大多数时候,最后和最后一位是相同的。要么它们都是1表示负数,要么它们都是0表示正数。 所以我最后的方法是检查它们是1还是0都是0,这意味着在大多数情况下这是第一次调用。如果最后一位与倒数第二位不同,那么我假设我们处于第二次调用,并且只是重新反转最后一位。显然,这对使用这两个最后位的非常大的数字不起作用。但是,它再次适用于非常广泛的数字。tet
赞同来自:
使用问题中给出的信息,您可以
uut
赞同来自:
gsint
赞同来自:
我认为可能的最大范围是暗示模块化算术解决方案。在一些模块化基础M中,存在数字,当平方与M-1一致时(其与-1一致)。例如,如果M = 13,5 * 5 = 25,25 mod 13 = 12(= -1)
注意有3个值不适用于2 ** 31-1, - (2 ** 31-1)和 - (2 ** 31)无论如何这里有一些M = 2 ** 32-3的python代码。
bsint
赞同来自:
taut
赞同来自:
怎么样
cet
赞同来自:
LUA:
uaut
赞同来自:
C#为2 ^ 32 - 1个数字,所有int32数字除外(Int32.MinValue)
打印:yautem
赞同来自:
C#重载:
要么xnobis
赞同来自:
f#中的简单解决方案(不使用“技巧”)
gvel
赞同来自:
这个怎么样?
iid
赞同来自:
我实际上并没有尝试解决问题本身,但确实有几条评论,因为问题表明这个问题是(工作?)采访的一部分:
int.MinValue
到int.MaxValue
,以及用于在该范围内呼叫f(f(n))
每个n
并检查结果是-n
),告诉我将然后使用测试驱动发展以实现这样的功能。ased
赞同来自:
用coffeescript打高尔夫球:
matque
赞同来自:
少于50个字符(C#) h2>
或者更容易阅读: h3>
测试 h3>
它有效(假设我理解正确的问题)gipsam
赞同来自:
在C中,
这将有助于了解这是什么语言。 我错过了什么吗?许多“解决方案”似乎过于复杂,坦率地说,并非如此 工作(因为我读到了问题)。lnon
赞同来自:
C++
wanimi
赞同来自:
内容太长未翻译
ad_est
赞同来自:
:d
taut
赞同来自:
set
赞同来自:
根据您的平台,某些语言允许您在功能中保持状态。 VB.Net,例如:
IIRC,C++也允许这样做。我怀疑他们正在寻找不同的解决方案。 另一个想法是,由于他们没有定义第一次调用函数的结果,你可以使用奇数/偶数来控制是否反转符号: 在所有偶数的幅度上加1,从所有奇数的幅度中减去1。两个调用的结果具有相同的幅度,但是一个调用甚至我们交换符号。在某些情况下,这将不起作用(-1,max或min int),但它比目前为止提出的任何其他方法都要好得多。womnis
赞同来自:
这个怎么样:
et_qui
赞同来自:
这个Perl解决方案适用于整数,浮点数和字符串。
尝试一些测试数据。 输出:ynulla
赞同来自:
id_aut
赞同来自:
我可以想象使用第31位作为虚数(i)位将是一种支持总范围的一半的方法。
eet
赞同来自:
一个C++版本,可能会稍微弯曲规则,但适用于所有数字类型(浮点数,整数,双精度)甚至是重载一元减号的类类型:
jenim
赞同来自:
利用JavaScript异常。
kquis
赞同来自:
适用于n = [0 .. 2 ^ 31-1]
nomnis
赞同来自:
简单,只需使
f
返回看似等于任何整数的东西,并且可以从整数转换。het
赞同来自:
在Python中
snihil
赞同来自:
SQL Server中的解决方案
killo
赞同来自:
我有另一个解决方案,有一半的时间工作:
punde
赞同来自:
这是一个不使用任何按位运算符的C / C++解决方案,并且不需要任何数学库,尽管它有点作弊......
这适用于所有32位整数,只有0x80000000
例外(因为它的相反方法不能存储在32位整数系统中)。除了那种情况外,f(f(n)) == -n
将始终为true
。 不过,我确信有更简单,更快捷的方法来实现它。这只是我想到的第一件事。zearum
赞同来自:
x86 asm(AT& T风格):
代码检查,所有可能的32位整数通过,错误与-2147483647(下溢)。adicta
赞同来自:
怎么样:
在Python中: Python自动将整数提升为任意长度的长度。在其他语言中,最大的正整数将溢出,因此它将适用于除了那个之外的所有整数。要使其适用于实数,您需要使用
{ ceiling(n) if n>0; floor(n) if n<0 }
替换(-1) n sup>中的n。 在C#中(适用于任何double,除了溢出情况):baut
赞同来自:
我给出了正确的答案... 50%的时间,所有的时间。
pporro
赞同来自:
这适用于-1073741823到1073741822的范围:
它的工作原理是获取32位signed int的可用范围并将其除以2。函数的第一次迭代将n b>置于该范围之外。第二次迭代检查它是否在此范围之外 - 如果是,则将其放回范围内但使其为负值。 它实际上是一种保持关于值n的额外“信息”的方法。xeos
赞同来自:
或者,您可能滥用预处理器:
iaut
赞同来自:
xipsam
赞同来自:
虽然问题是n必须是32位int,但它没有说参数或返回类型必须是32位int。这应该在java中编译 - 在c中你可以摆脱!= 0
编辑: 这实际上是一个非常好的面试问题。最好的是难以或无法回答的问题,因为它迫使人们思考它,你可以观察和寻找:podio
赞同来自:
yalias
赞同来自:
本质上,函数必须将可用范围划分为大小为4的循环,其中-n位于n循环的另一端。但是,0必须是大小为1的循环的一部分,否则
0->x->0->x != -x
。因为0是单独的,所以我们的范围中必须有3个其他值(其大小是4的倍数),而不是具有4个元素的正确循环。 我选择这些额外的奇怪值为MIN_INT
,MAX_INT
和MIN_INT+1
。此外,MIN_INT+1
将正确映射到MAX_INT
,但卡在那里而不是映射回来。我认为这是最好的折衷方案,因为它具有只有极端值不能正常工作的优良特性。此外,这意味着它适用于所有BigInts。xsed
赞同来自:
不记得你的上一个状态是否足够好?
eomnis
赞同来自:
问题没有说明
如果n是32位整数,则语句f
函数的输入类型和返回值必须是什么(至少不是你提出的方式)...... ...只是当n是32位整数然后是f(f(n)) = -n
那么,怎么样的f(f(n)) == -n
将为真。 显然,这种方法可以扩展到更广泛的数字......mnatus
赞同来自:
MIN_INT上没有失败:
tut
赞同来自:
以为我会先试试这个,而不先看别人的答案:
输出:[无]nin
赞同来自:
也许我错过了什么? 这不是一件简单的事情:
编辑: 所以我很想念这个问题,哼哼,所以: 丑陋但有效。qquod
赞同来自:
Python 2.6:
我意识到这对讨论没什么好处,但我无法抗拒。ut_sit
赞同来自:
我尝试过Rodrick Chapman打高尔夫球的this answer。 没有分支:74个字符
有分支,Java风格:58个字符 有分支,C风格:52个字符在快速但有效的基准测试之后,分支版本在我的机器上的速度提高了33%。 (正数和负数的随机数据集,足够的重复并阻止编译器优化代码,并进行预热。)鉴于未分支版本中的操作数和可能的良好分支预测,这并不令人惊讶该函数被调用两次:
f(f(i))
。当我将基准测试更改为:f(i)
时,分支版本的速度仅提高了28%。我认为这证明了分支预测在第一种情况下实际上做得很好。更多证明:使用f(f(f(f(i))))
进行测试时,分支版本的速度提高了42%。kex
赞同来自:
Scala中使用隐式转换的一个奇怪的,只是稍微聪明的解决方案:
我不认为这是一个非常正确的想法。tvelit
赞同来自:
jalias
赞同来自:
有些相似但只是想我会写下我的第一个想法(在C++中)
只是使用重载使f(f(n))实际调用两个不同的函数aut_id
赞同来自:
另一种利用短路的Javascript解决方案。
overo
赞同来自:
没有人说它必须是无国籍的。
作弊,但不是很多例子。更糟糕的是要查看堆栈以查看您的调用者的地址是否为& f,但这将更具可移植性(虽然不是线程安全的...线程安全版本将使用TLS)。更邪恶的是: 当然,对于MIN_INT32的情况,这些都不能很好地工作,但是除非你被允许返回更宽的类型,否则你可以做的很少。dquia
赞同来自:
这是一个灵感来自要求或声称复杂数字不能用于解决此问题的解决方案。 乘以-1的平方根是一个想法,似乎只是失败,因为-1没有整数的平方根。但是,玩像mathematica这样的程序可以得到例如等式
这几乎与-1的平方根一样好。函数的结果需要是有符号整数。因此,我将使用修改的模运算mods(x,n),它将整数y congruent返回到最接近0的x modulo n。只有极少数编程语言有模数运算,但它很容易定义。例如。在python中它是: 使用上面的等式,现在可以解决问题 这满足了[-2
31
sup>-2, 2
31
sup>-2]
范围内所有整数的f(f(x)) = -x
。f(x)
的结果也在此范围内,但当然计算需要64位整数。wnihil
赞同来自:
使用复数,您可以有效地将否定数字的任务分为两个步骤:
tiure
赞同来自:
zin
赞同来自:
zsed
赞同来自:
zrerum
赞同来自:
也许作弊? (蟒蛇)
riure
赞同来自:
使用循环置换方法来做到这一点。 -b a b -a a b -a -b 在琐碎的情况下 f(0)返回0 对不起,我的电话粗略回答,28日后我将发布完整版(现在正在考试......) 简单地说,认为f(n)是一个循环置换,问题是如何构造它。 define fk = f(f(f(f(... f(n)))))(k fs) 情况k = 2 0.trivial情况 f(0)返回0 1.制作团体,情况k = 2,团体: {0} {1,2} {3,4} ... {n,n + 1 | (n + 1)%2 = 0} ,注意:我只使用Z +,因为施工不需要使用负数。 2.构造排列: 如果n%2 = 0,那么a = n-1 b = n 如果n%2 = 1,那么a = n b = n + 1 这将产生相同的排列,因为n和f(n)在同一组中。 注意排列为P 返回P(n) 对于k = 2t,只做上面相同的事情,只是MOD k。 对于k = 2t-1,虽然方法有效但是没有意义啊,是吗? (f(n)= -n是好的)
somnis
赞同来自:
F# H3>
其中n
就是System.Int32.MinValue < n < System.Int32.MaxValue
。trerum
赞同来自:
它是通过保存状态而作弊但它可以工作,将操作分成两部分:-n =(~n + 1)表示整数
eut
赞同来自:
这是Python中的一个。适用于n的所有负值:
eomnis
赞同来自:
另一种方法是将状态保持在一位,并在负数的情况下小心地翻转二进制表示... 限制是2 ^ 29 int ffn(int n) {
cut
赞同来自:
除int.MaxValue和int.MinValue外的工作
nerror
赞同来自:
这是rossfabricant答案的C实现。请注意,由于我始终坚持使用32位整数,因此f(f(2147483647))== 2147483647,而不是-2147483647。
如果定义问题以允许f()接受并返回int64_t,则覆盖2147483647。当然,必须改变switch语句中使用的文字。liste
赞同来自:
简单: