python - 如何解决我在求职面试中看到的这个递归问题？

Question

我在一次在线评估中被问到这个问题(我是一名正在寻找 SDE 实习的学生)并且无法及时解决(我只给了 5 分钟......)。你们认为这个问题 5 分钟够吗？我只是有点好奇其他人有多好。

无论如何，这是问题:

You are given two tuples of integers (A, B) and (C, D).
There are two operations you can do:
(A + B, B)
(A, A + B)
Write a function that returns True if (A, B) can be transformed into (C, D) using the two operations, False otherwise.

例子:

Input: A = 2, B = 3, C = 8, D = 11
Output: True

我会把我在评估期间写的“想法”放在这里(我只有 70% 的把握)。它似乎工作正常，我不确定为什么它不能通过测试。如果你们知道问题是什么，或者正确的解决方案，请告诉我!

def func(A, B, C, D):
    if A == C and B == D:
        return True
    if A > C or B > D:  
        return False

    return func(A + B , B, C, D) or func(A, A + B, C, D)

Answer 1

这是一个完整的解决方案，适用于正整数和负整数的混合。

我不希望 future 的实习生能在 5 分钟内解决这个问题。他们希望你这样做的事实我会发出危险信号。

def op_test(a, b, c, d):
    if a == c and b == d:
        return True

    if max(a, b) < 0 and min(a, b) < min(c, d):
        # No way to increase min(a, b)
        return False
    elif 0 < min(a, b) and max(c, d) < max(a, b):
        # No way to decrease max(a, b)
        return False

    # The 0 checks are to avoid endless recursion.
    if 0 != a and op_test(a, a+b, c, d):
        return True

    if 0 != b and op_test(a+b, b, c, d):
        return True

    return False