How to solve this recursion question I saw during job interview?

user_7067164 0
Viewed 229

I was asked this question during an online assessment (I'm a student looking for an SDE internship) and couldn't solve it in time (I was only given 5 minutes...). Do you guys think 5 minutes for this question is enough btw? I'm just kinda curious how good everyone else is.

Anyways, here's the question:

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.

Example:

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

I'll put what I 'thought' I wrote during the assessment here (I'm only 70% sure). It seems to be working fine and I'm not sure why it wouldn't pass the tests. If you guys know what the problem is, or the correct solution, please let me know!

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)
recursion algorithm python
5 Answers

Here is a full solution, which will work for mixtures of positive and negative integers.

I would not expect a prospective intern to work this out in 5 minutes. And the fact that they expected you to I'd call a red flag.

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
user_5854110

There's a unique path down from the target (assuming positive integers), so go that direction to avoid a large search space.

I.e. always decrease the larger coord by the smaller, or any integer multiple of the smaller that doesn't overshoot your target.

E.g. 8,11 -> 8,3 -> 2,3 is the unique path down from the target attained by decreasing the larger coord by the largest mult of the smaller that doesn't overshoot.

We can use similar logic anytime the starting & ending coordinates are in the same quadrant.

There's no solution if the start is in quadrants I or III while the end is in II or IV. For the reverse situation, I think (but haven't proven) that there is a solution iff gcd(A,B) = gcd(C,D). I'll get back to this and edit my answer after the kiddos go to bed.

user_20410770

You have to be careful, if A==0 or B==0 you could get an infinite recursion and blow your stack. You need to detect that condition and return False.

return (B != 0 and func(A + B , B, C, D)) or (A != 0 and func(A, A + B, C, D))
Mark_Ransom_59870

I hope it helps

def recursively(A,B,C,D):

    if A < C :
        A = A + B
        return recursively(A,B,C,D)
    if B < D:
        B = A + B
        return recursively(A,B,C,D)
    if A  == C and B == D:
        return True
    if A > C and B > D:
        return False
    return False


print(recursively(2,3,8,11))
user_131631340

You can try using BFS or DFS approach. I'd go with BFS as it'll get you there(the solution state) the fastest. Also, make sure you have a threshold to stop your loop for the cases where there is no solution (can't reach C,D)

user_63477790
Related