噪声隐藏值

Question

这是一道面试题，我一点都不知道怎么解。面试结束了，但我真的很想看看他们在寻找什么。我试图混淆这一点以尊重提出要求的公司。

有一个由 N 位组成的秘密整数 S。我们的工作是非常确定地猜测这个秘密整数。

我们只能通过秘密方法 foo(G) 访问 S，该方法接受猜测 G 并将该猜测与 S 和随机生成的值 [= =17=] 其中 V 中的每个位都有 10% 的机会是 1。然后它计算 1 和 returns 的数量作为整数

foo(g):
    generate v
    return bin(g ^ v ^ s).count('1')

每次调用 foo 都会生成

V 我们只给了我们 100,000 次运行 foo 的尝试，然后我们才能通过面试，否则世界会爆炸什么的。

我们如何解决这个问题？

让我抓狂的是，即使是猜测正确答案也有 N/10 的机会从 foo 返回非零值。因此，即使是蛮力尝试似乎也不在 table.

Answer 1

假设：如果你用相同的G重复函数foo(G)足够多次，foo(G)的平均结果将足够接近期望值。

例如，假设S有N位，其中M位为1，设G = N bits of 0，那么foo(G)的期望就是E(N,M)=M*0.9 + (N-M)*0.1。既然知道了N，并且可以求出foo(G)的平均值，那么求出M的个数就很简单了，其实我们甚至不需要去求出M.

当我们有了数字E(N,M)，那么剩下的就简单了：迭代i到N，使G的第i位等于1，其余为零，然后重复foo(G) 足够多的次数。如果s的第i位等于1，那么foo(G)的期望就是E(N-1,M-1)+0.1=E(N,M)-0.8，否则如果S的第i位等于0，那么期望foo(G) 的将是 E(N-1,M)+0.9=E(N,M)+0.8.

然后你最终可以计算出S的值。在同一个 G 上重复 foo(G) 的次数越多，您获得的确定性就越高。

一些示例代码：

import numpy as np

S = 1117506159690372465501725393907 # an 100 bit number

def foo(S, N, G):
    bits = np.random.choice(2, size=N, p=[0.9,0.1])
    V = int("".join(str(b) for b in bits), 2)
    return bin(G^V^S).count('1')

if __name__ == '__main__':
    N = 100
    result = np.empty((101,1000))
    for j in range(1000):
        G = int("0" * N, 2)
        result[0,j] = foo(S, N, G)
    for i in range(100):
        for j in range(1000):
            G = int("0"*i + "1" + "0"*(N-i-1), 2)
            result[i+1, j] = foo(S, N, G)
    avg = np.mean(result, axis=1)
    avg -= avg[0]
    out = "0b"+"".join("1" if num < 0 else "0" for num in avg[1:])
    print(str(bin(S))==out) # True

Answer 2

我会这样做：

from random import random as r
from collections import defaultdict

N = 8                # Number of bits
S = 123              # Secret number

stop_iter = 100      # Number of iterations
#stop_tol -- also an option, but seems risky given noise

def foo(g):
    V = int(''.join([str(int(r() < 0.1)) for _ in range(N)]), 2)
    return bin(g ^ V ^ S).count('1')

def test_guess(g, n=10):
    total = 0
    for _ in range(n):
        total += foo(g)
    return total / n

def test_perturb(g, p, n=10):
    g ^= (1 << p)
    return test_guess(g, n)

def test_bit_positions(g):
    deltas = {}
    for i in range(N):
        deltas[i] = test_perturb(g, i)

    return deltas

def itemval(i): return i[1]


history = defaultdict(list)
guess = 0                       # Initial
for _ in range(stop_iter):
    deltas = test_bit_positions(guess)
    error = sum(deltas.values())

    history[guess].append(error)

    (index, delta) = min(deltas.items(), key=itemval)
    guess ^= (1 << index)
    print(guess, bin(guess), "after flipping bit %d" % index, error)

    # If you had to, you could evaluate history at each iteration,
    #   trying to identify a value that has set itself apart
    #   potentially halting early but slowing the program

mean_error = {k:(sum(lst) / len(lst)) for (k,lst) in history.items()}

print()
print("Results:")
mean_error = sorted(mean_error.items(), key=itemval)
for (guess, err) in mean_error[:5]:
    print(guess, err)

print()
print("Guess:", mean_error[0][0])

示例输出（N=8，S=123，stop_iter=100，n=10）：

Results:
123  12.799021276595743
127  17.55975
 59  17.564333333333334
251  17.583
121  17.58742857142857

Guess: 123 (Correct)

Calls to foo(): 8000

示例输出（N=20，S=12345，stop_iter=100，n=10）

Results:
 12345 56.19999999999998
 77881 69.69999999999999
 12601 69.85
274489 69.93333333333334
  8249 70.10000000000001

Guess: 12345 (Correct)

Calls to foo(): 20000

基本上是迭代优化，通过比较当前猜测的 N 个扰动版本，尝试使 error 项尽可能接近零。由于噪音，这将比平时更棘手。

您还可以调整一些参数，两个 test_ 函数中的 n 默认参数，以及迭代次数 stop_iter.

噪声隐藏值

Noise hidden value

python

xor