CODEWITHSUNDEEP
algorithm
Bapta Arjun
Bapta Arjun

Reputation: 43

Algorithm for sequential reward points

I want to write an algorithm to find the sequential reward points. The inviter gets (1/2)^k points for each confirmed invitation, where k is the level of the invitation: level 0 (people directly invited) yields 1 point, level 1 (people invited by someone invited by the original customer) gives 1/2 points, level 2 invitations (people invited by someone on level 1) awards 1/4 points and so on. Only the first invitation counts: multiple invites sent to the same person don't produce any further points, even if they come from different inviters and only the first invitation counts. For instance:

Input:

A recommends B
B accepts
B recommends C
C accepts
C recommends D
B recommends D
D accepts

would calculate as: A receives 1 Point from the recommendation of B, 0.5 Point from the recommendation of C by B and another 0.25 Point by the recommendation of D by C. A gets a total score of 1.75 Points.

B receives 1 Point from the recommendation of C and 0.5 Point from the recommendation of D by C. B receives no Points from the recommendation of D because D was invited by C before. B gets a total score of 1.5 Points.

C receives 1 Point from the recommendation of D. C gets a total score of 1 Point.

Output: { “A”: 1.75, “B”: 1.5, “C”: 1 }

What should be the algorithm for that? I think Dynamic Programing has to be use here.

Upvotes: 0

Views: 661

Answers (1)

Olivier Melançon
Olivier Melançon

Reputation: 22294

This is simply an ancestors search in a tree. By keeping track of the depth, you know how many points to award.

Pseudocode

def add_points(accepter):
    depth = 0
    while accepter has an inviter:
        accepter.inviter.points += (0.5)^depth
        accepter = accepter.inviter
        depth += 1

This algorithm is O(number of parents) and since you need to traverse all parents to update, you know you can't do any better complexity-wise.

Upvotes: 2

Related Questions