Crash Code Part-8 (Amazon Transaction Logs in Python)

Problem Description

Your Amazonian team is responsible for maintaining a monetary transaction service. The transactions are tracked in a log file. A log file is provided as a string array where each entry represents a transaction to service. Each transaction consists of:

• sender_user_id: Unique identifier for the user that initiated the transaction. It consists of only digits with at most 9 digits.
• recipient_user_id: Unique identifier for the user that is receiving the transaction. It consists of only digits with at most 9 digits.
• amount_of_transaction: The amount of the transaction. It consists of only digits with at most 9 digits.

The values are separated by a space. For example, sender_user_id recipient_user_id amount_of_transaction.

Users that perform an excessive amount of transactions might be abusing the service so you have been tasked to identify the users that have a number of transactions over a threshold. The list of user ids should be ordered in ascending numeric value.

Example

logs = ["88 99 200", "88 99 300", "99 32 100", "12 12 15"]

threshold = 2

The transactions count for each user, regardless of role are:

There are two users with at least threshold = 2 transactions: 99 and 88. User 99 participated in three transactions, while user 88 participated in two.

Therefore, both meet the threshold of 2.

The answer is:

["88", "99"]

Note: In the last log entry, user 12 was on both sides of the transaction. This counts as only 1 transaction for user 12.

Function Description:

Complete the function processLogs in the editor below. The function has the following parameter(s):

string logs[n] # each logs[i] denotes the ith entry in the logs
int threshold  # the minimum number of transactions that a user must have to be included in the result

Returns:

string[]  # an array of user id's as strings, sorted ascending by numeric value

Constraints

• 1 ≤ n ≤ 105
• 1 ≤ threshold ≤ n
• The sender_user_id, recipient_user_id and amount_of_transaction contain only characters in the range ascii[‘0’-‘9’].
• The sender_user_id, recipient_user_id and amount_of_transaction start with a non-zero digit.
  • 0 < length of sender_user_id, recipient_user_id, amount_of_transaction ≤ 9
• The result will contain at least one element.

Approach

The simplest way to solve this problem is to use a Python dictionary as a hash map.

The dictionary stores:

user_id → transaction_count

For every transaction:

1. Split the log into sender, recipient, and amount.
2. Increment the sender’s transaction count.
3. Increment the recipient’s transaction count only when the sender and recipient are different.
4. After processing all logs, select users whose count is at least threshold.
5. Sort the resulting user IDs numerically.

The transaction amount does not affect the solution because we only need to count transactions.

Examples

Sample Case 0

Sample Input

STDIN    Function
-----    --------
4      → logs[] size n = 4
1 2 50 → logs = ["1 2 50", "1 7 70", "1 3 20", "2 2 17"]
1 7 70
1 3 20
2 2 17
2      → threshold = 2

Sample Output

1
2

Explanation The transaction counts are:

With: threshold = 2

Only users 1 and 2 have at least threshold = 2 transactions. The return array in numerically ascending order is [“1”, “2”]. Note that in the last log entry, the user with id 2 performed both roles in the transaction. This is counted as one transaction for the user.

Sample Case 1

Sample Input

STDIN    Function
-----    --------
4      → logs[] size n = 4
9 7 50 → logs = ["9 7 50", "22 7 20", "33 7 50", "22 7 30"]
22 7 20
33 7 50
22 7 30
3      → threshold = 3

Sample Output

7

Explanation The transaction counts are:

Only user 7 meets the threshold of 3.

Solve

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def processLogs(logs, threshold):
    transaction_count = {}
    for log in logs:
        sender, recipient, _ = log.split()
        transaction_count[sender] = transaction_count.get(sender, 0) + 1
        if sender != recipient:
            transaction_count[recipient] = (
                transaction_count.get(recipient, 0) + 1
            )
    result = [
        user_id
        for user_id, count in transaction_count.items()
        if count >= threshold
    ]
    result.sort(key=int)
    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    logs_count = int(input().strip())
    logs = []
    for _ in range(logs_count):
        logs_item = input()
        logs.append(logs_item)
    threshold = int(input().strip())
    result = processLogs(logs, threshold)
    fptr.write('\n'.join(result))
    fptr.write('\n')
    fptr.close()

Complexity Analysis

Let n be the number of transaction logs and u be the number of unique users.

• Processing each log takes constant time, so counting transactions requires:O(n)
• Filtering users requires: O(u)
• Sorting the qualifying user IDs requires:O(u log u)

Therefore, the overall complexity is:

Time: O(n + u log u)
Space: O(u)

Since u ≤ 2n, this is effectively:O(n log n)

Why the Dictionary Approach Is Better

A brute-force solution can repeatedly scan the complete logs array for each transaction. With up to 10⁵ logs, that can result in roughly:O(n²)operations.

Using a dictionary lets us update each user’s transaction count in constant average time:

transaction_count[user_id] = transaction_count.get(user_id, 0) + 1

This makes the solution substantially more scalable.