噪声隐藏值

Question

这是一个面试问题，我一点也不知道该怎么解决。面试结束了，但我真的很想看看他们在找什么。我试图在某种程度上混淆这一点，以尊重公司的要求。在

有一个秘密整数S，由N位组成。我们的工作是以非常高的确定性来猜测这个秘密整数。在

我们只能通过一个秘密方法foo(G)来访问foo(G)，该方法接受一个猜测G和一个随机生成的值V，其中{}中的每一位都有10%的几率是1。然后计算1的个数并将其作为整数返回

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

每次调用V时生成V 我们只能在面试失败之前，或者在世界爆炸或其他事情之前，尝试运行foo100000次。在

我们该怎么做？在

让我抓狂的是，即使是猜测正确的答案，从foo返回非零值的几率也只有十分之一。所以即使是暴力的尝试也不可能。在

Answer 1

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

例如，假设S有N个位，其中M是1，让G = N bits of 0，那么{}的期望值将是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，否则，如果{}的第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 iu iter=100，N=10）：

^{pr2}$

示例输出（N=20，S=12345，stop iu iter=100，N=10）

^{3}$

基本上是迭代优化，通过比较当前猜测的N个扰动版本，试图使error项尽可能接近于零。因为有噪音，这会比平常更棘手。在

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